Algorithmique pour l'optimisation

Informations pratiques

• Intervenants : Théo Pierron (CM + Groupe A), Joachim Cendrier (Groupe B), Laurent Feuilloley (Groupe C), Nicolas Bousquet (CM + Groupe D).
• Contact : prenom.nom@univ-lyon1.fr (Groupes ACD), joachim.cendrier@ens-lyon.fr (Groupe B).
• MCC : Partiel (40%) + Examen final (40%) + 2 tests de 20mn en TD (10% chacun). Absence (justifiée ou non) à >50% des épreuves => UE non validée.

(Ébauches de) notes de cours

• CM1 Modélisation
• CM2 Algorithmes gloutons
• CM3 Programmation dynamique
• CM4 Programmation linéaire
• CM5 Modélisation en SAT
• CM6 Classes structurées
• CM7 FPT

Sujets de TD/TP

• TD1.
• TD2.
• TD3.
• TD4.
• TD5.
• TD6.
• 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.