ECTS : 4
Lecturer in charge : Florian SIKORA (https://www.lamsade.dauphine.fr/~sikora/)
Language of instruction : French
Teaching hours : 36
Course content:
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.
Skills to be acquired:
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.
Mandatory prerequisites
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...
Bibliography, recommended reading:
Introduction to algorithms / Cormen et al. Algorithms / Jeff Erickson (chapitres 5 à 11) Graphes et algorithmes / Gondran Minoux