Complexité avancée

Ects : 5
Volume horaire : 18

Description du contenu de l'enseignement :
Objectif: Introduction à la théorie de la complexité algorithmique et présentation des classes de complexité les plus importantes.
  - Rappels des notions autour des machines de Turing - Définition formelle de la notion de problème - Définition de la notion de complexité d'un problème - Classes de complexité - Classes P - NP - Co-NP - Définition de la notion de réduction polynomiale (réruction de Turing et de Karp) - Etude des propriétés des réductions - NP-complétude - Preuves de NP-completude pour des problèmes combinatoires paradigmatiques - Introduction des modèles alternatifs de complexité