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.

Le cours sera basé sur le livre Éléments d’algorithmique de Danièle Beauquier, Jean Berstel, et Philippe Chrétienne (que j’appellerai familièrement le “BBC”), chapitres 4, 7, et 8.

J’utiliserai des transparents détaillés, dont voici les quelques premières séries; je les mettrai à jour au fur et à mesure.

  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; depuis 2021, je ne fais plus les différentes caractérisations des arbres dans le cas non orienté (transparents 16 à 88).
  2. Graphes orientés, parcours, parcours en profondeur, détection de circuits: les transparents en version longue et en version courte, et les notes de cours (qui remplacent la partie correspondante du BBC, pas assez formelle à mon goût); ce qui est important ici, ce sera de bien comprendre la structure mathématique des parcours en profondeur. 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.
  3. Tri topologique, composantes fortement connexes, les algorithmes de Sanders-Mehlhorn-Dietzfelbinger-Dementiev, de Tarjan: les transparents en version longue et en version courte; même notes de cours que la dernière fois. 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.
  4. Algorithme de Roy-Warshall, semi-anneaux, algèbres de Kleene, algorithme de Roy-Warshall généralisé, de McNaughton-Yamada, de Floyd (plus courts chemins): les transparents en version longue et en version courte; voir BBC, sections 4.2.1, 4.2.2, 4.2.3. 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.
  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; voir BBC, section 7.2. 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.
  6. Flots maximaux, coupes minimales: Ford-Fulkerson, Edmonds-Karp/Dinic: les transparents, et les mêmes en version courte; voir BBC, sections 8.1, 8.2, 8.3.7. La vidéo de 2020, qui couvre Ford-Fulkerson, jusqu’au tout début d’Edmonds-Karp/Dinic (notion de distance estimée).
  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.

Examen

L’examen 2020-2021, qui était à rendre à goubault@lsv.fr le lundi 18 janvier 2021 ou avant, en pdf (venant d’un document LaTeX, ou écrit proprement à la main puis scanné). Son corrigé.

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