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