Algorithmique pour l'optimisation

Informations pratiques

• Intervenants : Théo Pierron (CM + Groupe A), Nicolas Bousquet (CM + Groupe B), Laurent Feuilloley (Groupe C), Stéphane Bonnevay (Groupe D).
• Contact : prenom.nom@univ-lyon1.fr
• MCC : Examen final (40%) + 3 tests de 20-30mn en début de chaque TD (20% chacun).

(Ébauches de) notes de cours

• CM1 Algorithmes gloutons.
• CM2 Algorithmes probabilistes.
• CM3 Programmation dynamique.
• CM4-5 Programmation linéaire.
• CM6-7 Approximation et méta-heuristiques.
• CM8 Modélisation et structure.

Sujets de TD/TP

• TD1 (english version).
• TD2 (english version).
• TD3 (english version).
• TP1 (english version).
• TP2 (english version).
• Fiche d'exercices de révision.

Annales

• Examen et un corrigé (très) sommaire.

Quelques références

• The Design of Approximation Algorithms de David P. Williamson et David B. Shmoys.
• Understanding and Using Linear Programming de Jiří Matoušek et Bernd Gärtner.
• Algorithms de Christos Papadimitriou, Sanjoy Dasgupta et Umesh Vazirani.
• Introduction à l'algorithmique de Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein.