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)
