ECTS : 5
Description du contenu de l'enseignement :
Introduction à la théorie des graphes.
Étude et résolution des problèmes suivants :
Connexité dans un graphe (BFS, DFS), connexité forte, fermeture transitive.
Plus court chemin (algorithmes de Bellman, de Dijkstra, de Ford et de Floyd).
Arbre couvrant de poids minimum (algorithmes de Prim et de Kruskal)
Flot maximum (algorithme de Ford et Fulkerson).
Programmation de ces algorithmes en Python (lorsque le graphe est situé sur un serveur distant, pour résoudre graphiquement un labyrinthe...).
Potentiellement lecture d'article scientifique et recherche d'algorithme en projet.
Compétence à acquérir :
Fournir les concepts de base concernant les graphes. Souligner l’apport des graphes en informatique en tant qu’outil de modélisation. Présenter certains algorithmes fondamentaux et techniques de preuves. Programmation de ces algorithmes.
Bibliographie, lectures recommandées :
Introduction to algorithms / Cormen et al.
Algorithms / Jeff Erickson (chapitres 5 à 11)
Graphes et algorithmes / Gondran Minoux