Acquis d'apprentissage

Développer la compréhension mathématique de la théorie des graphes ainsi que l'aptitude d'utiliser la théorie des graphes à des fins de modélisation.

 

Objectifs

Le cours présentera divers problèmes liés à la vie réelle - comme l'algorithme de recherche de Google, la recherche du plus court chemin pour un système GPS, l'assignation de tâches à un groupe de personnes ou de machines, la programmation d'une IA jouant aux échecs, etc. - et développera à chaque fois les concepts et théories mathématiques derrière ces problèmes ainsi que les algorithmes pour les résoudre. Les démonstrations mathématiques rigoureuses des propriétés et algorithmes seront présentées. L'efficacité et la complexité des algorithmes seront également étudiés.
 

Contenu

  • Définitions de base de la théorie des graphes, graphes eulériens, graphes hamiltoniens
  • Les différents types de graphes, arbres, graphes planaires
  • Notation matricielle des graphes, recherche de plus courts chemins, algorithme de Dijkstra
  • Coupures, coupes et connectivité, robustesse des réseaux
  • Arbres couvrants de poids minimum, complexité algorithmique
  • Arbres min-max, construction d'une intelligence artificielle en théorie des jeux, élagage d'un arbre
  • Attribution de tâches, couplages, couvertures
  • Colloriage d'arêtes, théorie de Ramsey
  • Colloriage de sommets, polynôme chromatique, théorème des 4 couleurs
  • Mesures de centralité, algorithme du Page Rank de Google
  • Modélisation d’un réseau de transport routier, paradoxe de Braess
 

Méthodes d'enseignement

Cours magistral, mélangeant slides et démonstrations au tableau, et scéances d'exercices.

 

Méthode d'évaluation

Un examen écrit unique portant à la fois sur la théorie et sur des exercices, dont le contenu est le suivant :

- Partie théorie (50%) : présentation et explication des concepts, théorèmes ou algorithmes présentés au cours, restitution de démonstrations présentées au cours. Cette partie vise à évaluer les deux compétences suivantes : compréhension des concepts du cours et rigueur mathématique. 

- Partie exercices (50%) : exercices d'application du même genre que ceux proposés en séances de travaux dirigés. Cette partie vise à évaluer la compétence d'application pratique des concepts du cours.

L'entièreté de l'examen sera à cours fermé. L'examen est strictement individuel, aucune aide extérieure ni l'utilisation de matériel électronique n'est autorisée (en particulier, gsm et calculatrices interdits).

L'évaluation de cette unité d'enseignement sera uniquement organisée lors des sessions de janvier et d'août.

 

Sources, références et supports éventuels

Syllabus disponible sur Webcampus.

 

Langue d'instruction