Théorie de la complexité

Objectifs : Le but de ce cours est d’enseigner les fondamentaux de la théorie de la complexité algorithmique tels la difficulté intrinsèque d’un problème informatique, les outils de son analyse, les notions de « problèmes plus difficiles que d’autres », …

Contenu :

• Analyse de la difficulté intrinsèque (complexité) d’un problème

• Préservation de l’appartenance à une classe de complexité (réductions), problèmes difficiles (complets) pour une classe

• Rôle des paramètres pour évaluer la complexité d’un problème

• Classes de complexité (mesurée en considérant la taille de l’instance comme paramètre) : P, NP, co-NP, préservation de l’appartenance à P par réductions de Karp et de Turing et NP-complétude

• Classes de complexité (mesurée en considérant la valeur de la solution comme paramètre), XP, FPT, hiérarchies W[], réductions FPT

Bibliographie

• R. G. Downey, M. R. Fellows, Parameterized Complexity, Springer-Verlag, 1999.

• M.R Garey, D. S. Johnson, Computers and intractability. A guide to the theory of NP-completeness, W. H. Freeman, 1979.

• C. H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.

• V. Th. Paschos, Complexité et Approximation Polynomiale, Hermès, 2004.