Cette unité d'enseignement a pour objectif d'étudier la théorie de la calculabilité pour distinguer les problèmes qu'on peut résoudre en informatique, de ceux qu'on ne peut pas résoudre.
- Machine de Turing : déterministe (équivalence non-déterministe et multi-ruban)
- Décider et calculer : langage récursif et récursivement énumérable, fonction calculable et semi-calculable.
- Propriétés de clotûre des langages récursifs et r.e.
- Existence de fonctions non calculables par dénombrement (diagonale de Cantor)
- Problème de l'arrêt
- Réduction : many-one-réduction Turing
- Théorème de Rice
- Universalité et complétude
- Thèse de Church Turing
- λ-calcul : termes, beta-réduction, forme normale, terminaison…
- P, NP, NP-difficile : parler de certificats et montrer des exemples de problèmes NP-difficiles avec le genre de réduction que cela implique (pas un acquis attendu en fin de cours)