Cours de complexité algorithmique & optimisation discrète correspondant à la seconde partie du cours d'A. Bondy « Optimisation discrète » au sein du mastère M2 Mathématiques et Applications de l'université Pierre et Marie Curie (Paris 6), spécialité Mathématiques de la modélisation, parcours Optimisation, Théorie de Jeux, Modélisation en Économie (OJME)

Présentation du cours

L'objet de ce cours est de donner à sens à "résoudre un problème donné dans un temps donné" et à la notion d'efficacité. Après avoir introduit les machines de Turing, nous définirons la notion de calculabilité puis de temps de calcul. Nous définirons la classe P, des problèmes qu'on peut résoudre efficacement, et la classe NP, des problèmes dont on peut vérifier une solution efficacement. Nous verrons qu'il existe des problèmes universellement plus difficiles que les autres dans NP, les problème NP-complets, problèmes qui pourraient rester à jamais inattaquables efficacement. Après avoir démontré que la résolution d'un système de variables booléennes (problème SAT) est un problème NP-complet, nous verrons comment procéder pour démontrer que la plupart des problèmes d'optimisation sont eux aussi NP-complets. À la fin du cours, nous verrons comment on peut malgré tout garantir l'obtention efficace de solutions approchées.

Bibliographie :

• S. Arora, B. Barak, Complexity theory: a modern approach. Princeton university press (à paraître, 2008)
• C. Papadimitriou, Computational complexity. Addison-Wesley (1994). ISBN: 978-0201530827.
• T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms. MIT Press, 2nde éd. (2001), ISBN: 0-262-03293-7. Traduit en français par X. Cazin et G.-L. Kocher, Dunod (2002), ISBN: 2-10-003922-9.
• V. Vazirani, Approximation Algorithms. Springer, 2nde éd. (1ère éd. 2001), ISBN: 978-3-540-65367-7. (Traduction en français par N. Schabanel)

Archives du cours en vidéo 2008

• 12/11/2008 [ 1A | 1B | 1C ] Introduction aux machines Turing
• 19/11/2008 [ 2A | 2B | 2C ] Machine de Turing universelle & la classe P
• 26/11/2008 [ 3A | 3B | 3C | 3D ] La classe NP
• 03/12/2008 [ 4A | 4B | 4C | 4D ! problème technique: aucun son ! ] EXP, formes normales CNF & DNF des fonctions booléennes, SAT, et introduction à la NP-complétude
• 10/12/2008 [ 5A | 5B | 5C | 5D ] NP-complétude
• 17/12/2008 [ 6A | 6B | 6C | 6D ] Réductions polynomiales, problèmes NP-complets, inapproximabilité, algorithmes d'approximation