Calculabilité et complexité

Dans une première partie on parle des notions de base comme le concept d'algorithme, les ensembles dénombrables, les fonctions calculables, les ensembles (semi-)décidables et les problèmes insolubles. Dans une deuxième partie, on étudie quelques modèles de calcul comme les langages de programmation, le lambda-caclcul, les fonctions récursives, et les machines de Turing, et on introduit quelques résultats-clés de la calculabilité: le problème d'arrêt, le théorème de Rice, la relation entre interprétation et compilation et les projections de Futamura. Dans une troisième partie, on introduit la théorie de la complexité et on parle des classes de complexité P, NP, et coNP, et on parle des problèmes NP-complets et leur pertinence.