Théorie de la complexité

Ects : 3

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