Les cours ont lieu les mardi à 13h15 à Ker Lann, et les travaux dirigés les jeudis à 9h45 à Beaulieu.
Equipe pédagogique: David Baelde, Isseïnie Calviac. et Malo Revel.
Ce cours est en majeure partie un remix de celui donné par François Schwarzentruber les années précédentes. Merci à lui!
Planning des cours
Le thème des prochaines séances est donné à titre indicatif, sujet à modifications.
- 10 septembre: couplages stables, variant, invariants
- 17 septembre: FFT
- mes notes (HTML/Markdown)
- un livre Kleinberg & Tardos, page 234
- TD3
- 24 septembre: algos gloutons, matroïdes
- on se concentre sur la correction (optimalité), pas sur la complexité
- Cormen: matroïdes (§16.4), un problème d’ordonnancement (§16.5), arbres couvrants (§23)
- plus didactique, moins formel: §7 du livre de Jeff Erickson
- TD4
- 1er octobre: flots
- définition, graphe résiduel, méthode de Ford-Fulkerson, coupes
- chapitre 7 du Kleinberg & Tardos
- TD5
- 8 octobre: réductions à max-flow et min-cut
- couplage maximal dans des graphes bipartis, anonymous multi-agent path finding
- chapitre 7 du Kleinberg & Tardos
- TD6
- 15 octobre: tables de hachage
- chapitre 11 du Cormen
- l’article sur SipHash, la fonction pseudo-aléatoire cryptographique utilisée depuis dans la plupart des langages
- TD7
- 22 octobre: révisions
- algos de Dijkstra (correction) et de Prim (complexité)
- files de priorité, tas binaire…
- vacances de la Toussaint
- 5 novembre: devoir sur table, 1h + tiers-temps (TD le jeudi)
- 12 novembre: BDD + distribution du DM
- 19 novembre: DPLL (attention échange des créneaux de cours et TD)
- 26 novembre: CDCL
- 3 décembre: P, NP, NP-complétude
- 10 décembre: théorème de Cook, hiérarchies
- 19 décembre: devoir sur table, 2h + tiers-temps
Travaux dirigés
DM
Un DM sur les pingouins (PDF) a été distribué le 12 novembre, à rendre pour le 3 décembre.
Le corrigé est désormais disponible. La plupart des questions de la dernière partie ne sont pas corrigées: les élèves curieux pourront se référer à l’article de recherche dont l’énoncé est issu PDF.
Archives
Des anciens examens sont disponibles ici. Vous pouvez les utiliser pour vous préparer: le changement de prof aura un impact modéré sur le type de questions.
Livres
- Introduction à l’algorithmique (troisième édition). Cormen, Leiserson, Rivert & Stein. Dunod, 2010.
- Introduction to Algorithms (third edition). Cormen, Leiserson, Rivert & Stein. MIT Press, 2009.
- Algorithm Design. Kleinberg & Tardos. Pearson, 2005.
- Algorithms. Erickson. 2019.