Cours de L3 "Algorithmique 1, partie 2"
Ce cours fait suite au cours d'algorithmique 1, partie 1, donné par Thomas
Chatain.
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. (Voir aussi le memento,
qui reprend tous les définitions, algorithmes et résultats en format
condensé.) Les notes de cours 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”).
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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é.
L'examen 2023-2024 (2 heures), et son corrigé.
Les documents écrits sont autorisés, et l'utilisation du memento (format court [préféré] ou long) est recommandée.
Last modified: Tue Oct 15 16:09:02 CEST 2024