Equipe enseignante
Pierre Charbit, François Laroussinie, Roberto Mantaci,
Valia Mitsou, Dominique Poulalhon et Arnaud Sangnier.
- Séance de questions/réponses: F. Laroussinie (mercredi 15h-16h, distanciel)
- Séance de questions/réponses: F. Laroussinie (jeudi 14h-15h, distanciel)
- TD Groupe 1: F. Laroussinie (vendredi 10h45--12h45; 2001 SG)
- TD Groupe 2: D. Poulalhon et A. Sangnier (vendredi 10h45--12h45; 2035 SG)
- TD Groupe 3: P. Charbit (mardi 10h45--12h45; 2035 SG)
- TD Groupe 4: R. Mantaci (lundi 16h15--18h15; 2027 SG)
- TD Groupe 5 (math-info): V. Mitsou (vendredi 16h--18h; 2035 SG)
Actualités
L'organisation des cours est modifiée en raison du covid. Le CM n'aura pas lieu en présentiel.
Des vidéos seront mises en ligne chaque semaine pour compléter la lecture du polycopié (remis à l'amphi de rentrée). Des séances de questions/réponses seront organisées chaque semaine en distanciel. Les TD seront faits normalement (présentiel, avec masque).
Les séances de questions/réponses commenceront jeudi 10 septembre (sur les 3 premières videos) à 14h. Le lien pour y participer sera envoyé à la mailing-list du L3.
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...
TD
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: francois.laroussinie[at]univ-paris-diderot.fr