Reasoning about a highly connected world: graph theory, game theory and networks

linfo1115  2020-2021  Louvain-la-Neuve

Reasoning about a highly connected world: graph theory, game theory and networks
En raison de la crise du COVID-19, les informations ci-dessous sont susceptibles d’être modifiées, notamment celles qui concernent le mode d’enseignement (en présentiel, en distanciel ou sous un format comodal ou hybride).
5 crédits
30.0 h + 30.0 h
Q2
Enseignants
Langue
d'enseignement
Anglais
Préalables
Ce cours suppose acquises les compétences en mathématiques discrètes visées par le cours LINFO1114

Le(s) prérequis de cette Unité d’enseignement (UE) sont précisés à la fin de cette fiche, en regard des programmes/formations qui proposent cette UE.
Thèmes abordés
  • Graphes (concepts de base, chemins et connectivité)
  • Applications des graphes, par exemple, pour modéliser les réseaux sociaux (liens, homophilie, fermeture)
  • Structures discrètes sur l'internet: graphes et propriétés des graphes, composants géants, liens forts et faibles, fermeture triadique, équilibre structurel, théorème d'équilibre, structure du Web, PageRank, lois de puissance, la longue traîne
  • Introduction à la théorie des jeux
Acquis
d'apprentissage

A la fin de cette unité d’enseignement, l’étudiant est capable de :

1
Eu égard au référentiel AA du programme « Bachelier en sciences informatiques », ce cours contribue au développement, à l'acquisition et à l'évaluation des acquis d'apprentissage suivants :
  • S1.I1, S1.G1
  • S2.2
Les étudiants ayant suivi avec fruit ce cours seront capables de
  • identifier et définir de manière précise les concepts de base des graphes et des arbres en fournissant des exemples contextualisés qui les mettent en lumière.
  • expliciter diverses méthodes de parcours de graphes
  • modéliser divers problèmes du monde réel rencontrés en informatique en utilisant les formes appropriées de graphes et d'arbres, par exemple les réseaux sociaux et le Web
  • expliciter les principaux concepts de la théorie des jeux (le type de jeu, le type de stratégie des agents) à l'aide d'exemples appropriés
  • définir et interpréter avec rigueur et précision les concepts
  • éviter les mauvaises interprétations et détecter des erreurs de raisonnement
 

La contribution de cette UE au développement et à la maîtrise des compétences et acquis du (des) programme(s) est accessible à la fin de cette fiche, dans la partie « Programmes/formations proposant cette unité d’enseignement (UE) ».
Contenu
  • Graphes (concepts de base, chemins et connectivité).
  • Applications des graphes, par exemple, pour modéliser les réseaux sociaux (liens, homophilie, fermeture).
  • Structures discrètes sur l'internet: graphes et propriétés des graphes, composants géants, liens forts et faibles, fermeture triadique, équilibre structurel, théorème d'équilibre, structure du Web, PageRank, lois de puissance, la longue traîne.
  • Introduction à la théorie des jeux et application aux graphes d'Internet.
Méthodes d'enseignement

En raison de la crise du COVID-19, les informations de cette rubrique sont particulièrement susceptibles d’être modifiées.

  • Cours magistral chaque semaine (en présentiel ou distanciel, selon les règles en vigueur).
  • Séances de travaux pratiques en salle informatique chaque semaine, pour résoudre des problèmes simplifiés en utilisant les concepts vu au cours.
  • Un grand projet de conception et d'implémentation pour appliquer ces concepts dans le cadre d'une application plus complexe.
Modes d'évaluation
des acquis des étudiants

En raison de la crise du COVID-19, les informations de cette rubrique sont particulièrement susceptibles d’être modifiées.

  • Test dispensatoire 25% (vers la 7e semaine)
  • Projet 25%
  • Examen final (50%) (ou 75% si on refait la partie du test)
Le projet est obligatoire et se fait pendant le quadrimestre.  Il ne peut être fait qu'une fois et il compte pour toute l'année académique.  Le test dispensatoire (qui est optionnel) et l'examen final seront faits en présentiel ou distanciel, selon les règles en vigueur.  Le titulaire se réserve le droit d'interroger un étudiant oralement lors de l'examen final dans certains cas.
Autres infos
En égard au référentiel AA du programme « Bachelier en sciences informatiques », ce cours contribue au développement, à l'acquisition et à l'évaluation des acquis d'apprentissage suivants :
  • S1.I1, S1.G1
  • S2.2
Les étudiants ayant suivi avec fruit ce cours seront capables de
  • identifier et définir de manière précise les concepts de base des graphes et des arbres en fournissant des exemples contextualisés qui les mettent en lumière,
  • expliciter diverses méthodes de parcours de graphes,
  • modéliser divers problèmes du monde réel rencontrés en informatique en utilisant les formes appropriées de graphes et d'arbres, par exemple les réseaux sociaux et le Web,
  • expliciter les principaux concepts de la théorie des jeux (le type de jeu, le type de stratégie des agents) à l'aide d'exemples appropriés,
  • appliquer ces concepts aux structures de l'Internet,
  • définir et interpréter avec rigueur et précision les concepts,
  • éviter les mauvaises interprétations et détecter des erreurs de raisonnement.
Ressources
en ligne
Moodle LINFO1115.
Bibliographie
David Easley and Jon Kleinberg, Networks, Crowds and Markets: Reasoning About a Highly Connected World, Cambridge University Press, 2010.
Faculté ou entité
en charge


Programmes / formations proposant cette unité d'enseignement (UE)

Intitulé du programme
Sigle
Crédits
Prérequis
Acquis
d'apprentissage
Master [120] en sciences informatiques

Bachelier en sciences informatiques

Master [60] en sciences informatiques