Théorie de la complexité

Crédit : 3 ECTS
Langue du cours : anglais

Description du contenu de l'enseignement

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 », …
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, lectures recommandées

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.


Année universitaire 2019 - 2020 - Fiche modifiée le : 20-12-2018 (11H37) - Sous réserve de modification.