Cours de L3 “Algorithmique 1, partie 2”

Ce cours fait suite au cours d’algorithmique 1, partie 1, donné par Serge Haddad.

Dans cette partie, il sera question d’algorithmique des graphes, et notions connexes: graphes valués, et flots.

Il y a des notes de cours, sur lesquelles nous nous fonderons. Elles reposent sur, et complètent une partie des chapitres 4, 7 et 8 du livre Éléments d’algorithmique de Danièle Beauquier, Jean Berstel, et Philippe Chrétienne (que j’appellerai familièrement le “BBC”).

  1. Graphes, chemins, arbres non orientés, cycles, accessibilité: les transparents en version longue (avec animations), et en version courte; la vidéo de 2020. Section 4 des notes de cours.
  2. Graphes orientés, parcours, parcours en profondeur, détection de circuits: les transparents en version longue et en version courte; la vidéo de 2020, qui va jusqu’au début de la description de l’algorithme dfs_1 de calcul de rangs et de temps de fin. Section 5 des notes de cours.
  3. Tri topologique, composantes fortement connexes, les algorithmes de Sanders-Mehlhorn-Dietzfelbinger-Dementiev, de Tarjan: les transparents en version longue et en version courte; la vidéo de 2020, qui va jusqu’au début de la description de l’algorithme SMDD. En bonus, une exécution pas à pas de l’algorithme SMDD. Section 6 des notes de cours.
  4. Algorithme de Roy-Warshall, semi-anneaux, algèbres de Kleene, algorithme de Roy-Warshall généralisé, de McNaughton-Yamada, de Floyd (distances max, distances min): les transparents en version longue et en version courte; la vidéo de 2020, qui couvre surtout la fin des algorithmes de composantes fortement connexes, et Roy-Warshall uniquement dans les 20 dernières minutes. Section 7 des notes de cours.
  5. Algorithmes de plus courts chemins à point de départ fixé: Bellman-Ford, Ford[-Gallo-Pallattino], Dijkstra, cas sans circuit: les transparents en version longue et en version courte. La première vidéo de 2020, qui couvre la fin du point précédent, Bellman-Ford, et le résultat fondamental d’existence d’un arbre des plus courts chemins, nécessaire pour les algorithmes de Ford et de Dijkstra. La deuxième vidéo de 2020, où l’on termine ce qu’il y a à dire sur le sujet. Section 8 des notes de cours.
  6. Flots maximaux, coupes minimales: Ford-Fulkerson, Edmonds-Karp/Dinic: les transparents, et les mêmes en version courte. La vidéo de 2020, qui couvre Ford-Fulkerson, jusqu’au tout début d’Edmonds-Karp/Dinic (notion de distance estimée). Section 9.1–9.8 des notes de cours.
  7. Autres algorithmes de flots maximaux: à échelonnement, à préflots (Karzanov, Goldberg-Tarjan); applications: chemins disjoints, couplages, théorème de Menger; les transparents, et les mêmes en version courte; voir BBC, sections 8.3.3, 8.3.4. Section 9.9–9.11 des notes de cours.

Examen

L’examen 2021-2022 (2 heures), et son corrigé.

L’examen 2022-2023 (2 heures), et son corrigé.