Introduction à la calculabilité et la complexité

Un modèle de calcul simple: les automates

Les machines de Turing. nodéterminisme, universalité

Décidabilité et calculabilité, réductions entre problèmes

Complexité en temps, P et NP

Complexité en espace

Théorèmes d'hiérarchie