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).
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