Equipe enseignante
Pierre Charbit, Roberto Mantaci,
Anne Micheli, Valia Mitsou, Fabien de Montgolfier.
- Cours: François Laroussinie (vendredi 10h45--12h45, amphi 1A, HaF)
- TD Groupe 1: (lundi 8h30--10h30; 2027 SG)
- TD Groupe 2: (mercredi 10h45--12h45; 2027 SG)
- TD Groupe 3: (jeudi 8h30--10h30; 2027 SG)
- TD Groupe 4: (vendredi 8h30--10h30; 2027 SG)
- TD Groupe 5 (math-info): (jeudi 15h30--17h30; 2027 SG)
Actualités
La session 2 aura lieu vendredi 19 juin. Pour passer l'épreuve, contactez François Laroussinie (francoisl@irif.fr) au plus vite.
Programme
Au programme: l'algorithmique dans les graphe: parcours, composantes connexes, 2-connexité, 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 14-19.
- Cours 3: parcours en profondeur (poly, pages 20-26)
- Cours 4: application au tri topologique et à la recherche des CFC (poly, pages 28-31)
- Cours 4-5: 2-connexité (hors poly). Une petite note sur le sujet
ICI.
- Cours 6-7: algorithmes pour les PCC: Bellman-Ford, Dijkstra, Floyd-Warshall, A*.
- Une note sur les tas et les files de priorité.
L'algo A* est ICI.
- Cours 8: Les arbres couvrants minimaux (algo de Prim et Kriskal).
- Cours 9-10: Algorithmes sur les flots. Les slides pour l'algorithme par échelonnement: ICI.
- Cours 11: Un bilan, des perspectives, un aperçu des algorithmes probabilistes.
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