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 : Partiel (40%) + Examen final (40%) + 2 tests de 20mn en TD le 09/11 et 14/12 (10% chacun). Absence (justifiée ou non) à >50% des épreuves => UE non validée.

(Ébauches de) notes de cours

• CM1-2 Modélisation
• CM3 Algorithmes gloutons.
• CM4 Programmation dynamique.
• CM7 Heuristiques.

Sujets de TD/TP

• TD1.
• TD2.
• TP1 (corrigé).
• TP2.
• TD3.
• TD4.
• TP3.
• Fiche d'exercices de révision.

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.