Equipe enseignante
- Cours: François Laroussinie (vendredi 8h30-10h30, amphi 1A, HaF)
- TD Groupe 1: Anne Micheli (vendredi 10h30--12h30; 2035 SG)
- TD Groupe 2: Valia Mitsou (mercredi 13h30--15h30; 2035 SG)
- TD Groupe 3: Roberto Mantaci (lundi 13h30--15h30; 2036 SG)
- TD Groupe 4: Pierre Charbit (mardi 10h30--12h30; 2035 SG)
- TD Groupe 5 (math-info): Fabien de Montgolfier (jeudi 13h30--15h30; 2035 SG)
Actualités
L'examen d'AL5 se déroulera le LUNDI 7 JANVIER de 8h30 à 11h30. Il se déroulera dans 3 salles différentes ! Attention à ne pas se tromper de salle !
- Les étudiants du groupe 1 doivent aller dans la salle 264E (HaF).
- Les étudiants des groupes 2, 3 et 4 doivent aller dans l'amphi 13E (HaF).
- Les étudiants de la double Licence math-info doivent aller dans l'amphi 1 du bâtiment Olympe de Gouges.
Aucun document ne sera autorisé.
Vous trouverez
ICI un sujet de l'an dernier.
Et
ICI le sujet d'examen de session 1.
Les notes du partiel sont ici
ICI .
Les notes du DM pour le groupe 1 sont
ICI.
Programme
Au programme: l'algorithmique dans les graphe: parcours, composantes connexes, plus courts chemins, arbres couvrants minimaux, flots...
- Introduction, notion de complexité des algorithmes
Transparents du premier cours
- Cours 2: parcours en largeur. Pour compléter, lire le poly pages 12-17.
- Pour s'entraîner aux preuves... avec les échecs.
- Cours 3: parcours en profondeur. Pour compléter, lire le poly pages 17-24.
- Cours 4: Application du parcours en profondeur (tri topologique, composantes fortement connexes). Pour compléter, lire le poly pages 25-27.
Algorithme pour les CFC (version pseudocode).
- Cours 5: Plus courts chemins. Algorithme de Bellman-Ford.
- Une note sur les tas et les files de priorité.
- Cours 6: Plus courts chemins (algorithmes de Dijkstra et Floyd-Warshall; A*).
L'algo A* est ICI.
- Cours 7: Algorithme pour la 2-connexité. Une note sur l'algo présenté en cours.
- Cours 8: Arbres couvrants minimaux.
Une note sur les structures Union-Find pour l'algorithme de Kruskal : ICI. .
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