Comprendre la difficulté des problèmes d’optimisation et
maitrise de réduction ou transformation entre problèmes.
Plan du cours
1- Introduction à la théorie de complexité.
2- Rappel Modèles du calcul et complexité d’algorithmes.
3- Formulation de problèmes d'optimisation en problèmes de décision.
4- Notion d’algorithme non déterministe et les classes P, NP.
5- Réduction polynomiale (Karp) : NP-difficile, NP-complétude et PSPACE.
6- Algorithmique avec oracle NP (Cook-Turing réduction).
7- Résolution des problèmes d'optimisation faiblement NP-complets.
