Algorithmique pour l'optimisation

Informations pratiques

• Intervenants : Théo Pierron (CM + Groupe A), Aline Parreau (Groupe B), Laurent Feuilloley (Groupe C), Stéphane Bonnevay (Groupe D), Joachim Cendrier (Groupe E).
• Contact : prenom.nom@univ-lyon1.fr (Groupes ABCD), joachim.cendrier@ens-lyon.fr (Groupe E)
• 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
• CM3 Algorithmes gloutons
• CM4 Programmation dynamique.
• CM5 Programmation linéaire.
• CM6 Modélisation en SAT.

Sujets de TD/TP

• TD1.
• TD2.
• TP1.
• TP2.
• TD3.
• TP3.

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.