Algorithmes et applications dans les graphes
Enseignant responsable :
Volume horaire : 42Description 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.
Pré-requis obligatoires :
Bases de l'algorithmique et de maths discrètes : notion de complexité, structures de données (tables de hachage, tas binaire...), preuves par recurrence et contradiction...
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