Algorithmique (AL5)

De nombreux problèmes pratiques peuvent être modélisés à l'aide de graphes, et leur résolution nécessite des algorithmes de graphes. Ce cours explore les algorithmes pour les problèmes les plus classiques, tels que les parcours de graphes, le plus court chemin, les arbres couvrants de poids minimum, et le flot maximum.

1. Introduction
   • Graphes : définitions de base
   • Représentation matricielle et par listes
   • Lemme de la poignée de main
   • Connexité
   • Arbres
   • Rappels sur la complexité algorithmique, notation grand O, Ω et Θ
2. Parcours de graphes
   • Parcours en largeur (BFS)
   • Parcours en profondeur (DFS)
   • Graphes orientés acycliques (DAG)
   • Tri topologique
   • Composantes fortement connexes
3. Plus court chemin
   • Algorithme de Dijkstra
   • Algorithme de Bellman–Ford
   • Algorithme de Floyd–Warshall
   • Algorithme de Johnson
4. Arbres couvrants de poids minimum
   • Algorithme de Kruskal
   • Implementation de l'algorithme de Kruskal avec la structure de données union-find
   • Algorithme de Prim
   • Implementation de l'algorithme de Prim avec les files de priorité
5. Flot max, coupe min
   • Algorithme de Ford–Fulkerson
   • Algorithme de Edmonds–Karp
   • Couplages dans les graphes bipartis : théorèmes de König et de Hall
6. Algorithme d'approximation
   • Algorithme d'approximation pour vertex cover
   • Graphes eulériens, algorithme de Hierholzer
   • Problème du voyageur de commerce (TSP) : algorithme de Christofides

1. - Coloration
   • Algorithme glouton de coloration
   • Graphes d'intervalles