Ce cours s'appuie sur les problèmes de graphes pour présenter la Théorie de la Complexité. La complexité algorithmique étudie la difficulté intrinsèque des problèmes, en particulier vis-à-vis du temps nécessaire à leur résolution.

Nous faisons une introduction à l'étude des classes de complexité, en s'appuyant sur divers problèmes d'optimisation combinatoire, principalement de graphes.
 
A la fin du cours les élèves sauront évaluer la difficulté d'un problème de recherche opérationnelle et déterminer le type de résolution approprié: une méthode exacte pour un problème "facile" et, en général, une méthode approchée pour un problème "difficile".

Nous ferons une étude détaillée des classes P et NP.
Les problèmes calculables en temps polynomial déterministe forment la classe P. La classe NP contient la classe P et est constituée de problèmes dont la solution est vérifiable en temps polynomial, mais la trouver peut demander un temps exponentiel. Ces deux classes contiennent des milliers de problèmes de la théorie des graphes, de logique, des automates et d'autres domaines.