Introduction à la théorie de la complexité.

Le but de cet exposé est de définir les classes de complexité P, NP
et de comprendre ce qu'est un problème NP-complet. Dans ce but, on
sera amené à définir les modèles de calcul que sont les automates
finis et les machines de Türing (déterministes ou non). Ces modèles
permettront de formaliser les notions de temps de calcul et de
difficulté des problèmes. L'exposé sera illustré d'exemples
essentiellement issus de la théorie des graphes.