Contenu
- Théorie de la calculabilité : problèmes et algorithmes, fonctions calculables et non calculables, réduction, classes de problèmes indécidables (théorème de Rice) , théorème du point fixe, thèse de Church-Turing,
- Principaux modèles de calculabilité : machine de Turing, automates,
- Logique des propositions
- Théorie de la complexité : classes de complexité, NP-complétude, théorème de Cook, résolution de problèmes NP-complets.
- Enseignant: Edurne Aguirre
- Enseignant: Yves Deville
- Enseignant: Simon François
- Enseignant: Mathieu Jacob
- Enseignant: Giovanni Karra
- Enseignant: Pierre Leboutte