Ce cours propose une introduction à la théorie de la complexité des problèmes d'optimisation combinatoire (théorie de la NP-complétude).
L'objectif est de donner un sens et des éléments de réponse à la question suivante : dans quelle mesure peut-on dire qu'un problème est intrinsèquement difficile à résoudre d'un point de vue algorithmique ?
Les concepts abordés sont les suivants : machines de Turing (déterministes ou non déterministes), problèmes de décision, liens entre problèmes d'optimisation et problèmes de décision, classes P et NP, transformations polynomiales, transformations de Turing, problèmes polynomiaux, NP-complets, NP-difficiles, hiérarchie polynomiale.
L'objectif est de donner un sens et des éléments de réponse à la question suivante : dans quelle mesure peut-on dire qu'un problème est intrinsèquement difficile à résoudre d'un point de vue algorithmique ?
Les concepts abordés sont les suivants : machines de Turing (déterministes ou non déterministes), problèmes de décision, liens entre problèmes d'optimisation et problèmes de décision, classes P et NP, transformations polynomiales, transformations de Turing, problèmes polynomiaux, NP-complets, NP-difficiles, hiérarchie polynomiale.
- Enseignant responsable de l'UE: Olivier Hudry