D'où vient cette page ?
Cette page correspond à un cours d'algorithmique dans les graphes donné en L3 pendant l'année 2020-2021. Elle n'est plus active. Les videos sont toujours en ligne. Le document qui a servi de support de cours sera mis en ligne prochainement.
Videos
C'est ici.
ICI.
- Videos #1, #2 et #3: présentatin du cours, introduction aux graphes, rappels de complexité (mises en ligne le 8 septembre 2020).
- Videos #4 et #5: parcours en largeur (mises en ligne le 15 septembre 2020).
- Videos #6 et #7: parcours en profondeur (mises en ligne le 21 septembre 2020).
- Videos #8 et #9: applications (tri topologique et recherche des CFC) du parcours en profondeur (mises en ligne le 28 septembre 2020).
- Vidéos #10, #11, #12 et #13 sur la 2-connexité (mises en ligne jeudi 7 octobre 2020). Pour compléter, une petites notes ICI.
- Videos #14 et #15: plus courts chemins et algorithme de Belmman-Ford (mis en ligne le 13 octobre).
- Videos #16.a et #16.b sur les files de priorité et l'algorithme de Dijkstra (mises en ligne le 21 octobre).
- Video 17 sur l'algorithme de Floyd-Warshall (mises en ligne le 2 novembre).
- Video 18 sur la frontière entre problèmes difficiles et problèmes faciles (mise en ligne le 6 novembre).
- Videos 19 et 20 sur les arbres couvrants minimaux (definitions + algo. de Prim).
- Vidéo 21 sur l'algorithme de Kruskal. Vidéos 22 et 23 sur les structures Union-Find (mis enligne le 17 novembre).
- Videos 24 et 25 sur les flots et l'algorithme de Ford-Fulkerson (en ligne le 24 novembre).
- Videos 26 et 27 sur l'algorithme de Edmonds-Karp et l'algorithme "Delta" (en ligne depuis le 1er décembre).
- Video 28: Bilan et perspectives... (en ligne depuis le 8 décembre).
Programme
Au programme: l'algorithmique dans les graphe: parcours, composantes connexes, 2-connexité, plus courts chemins, arbres couvrants minimaux, flots...
Références bibliographiques
- "Eléments d'algorithmique", D. Beauquier, J. Berstel,
Ph. Chrétienne, Edition Masson. Ce livre est épuisé... mais disponible sur Internet ICI
- "Introduction à l'analyse des algorithmes", R. Sedgewick, Ph. Flajolet,
International Thomson Publishing.
- "Introduction à l'Algorithmique", T.H. Cormen, C.E. Leiserson,
R.L. Rivest, C. Stein, Dunod.
- "Computers and intractability, a guide to the theory of NP-completeness", M.R. Garey, D.S. Johnson, Freeman and Company.
Email: francoisl[at]irif.fr