Calculabilité & Complexité
Aperçu des sections
-
-
Calculabilité (7h30)
- Introduction et Machines de Turing Définitions MT, configuration, acceptation, rejet, fonction calculable, langage récursivement énumérable, langage récursif
- Thèse de Church-Turing et codage Thèse de Church-Turing, codage raisonnable récursif et bijectif.
- Machines de Turing universelle et dénombrement machine de Turing universelle, ensembles dénombrables et indénombrables, diagonalisation.
- Indécidabilité Indécidabilité du problème de l'arrêt, notion de problème, langage associé, notion de réduction, théorème de Rice.
- Indécidabilité (suite) indécidabilité de MPCP et de PCP.
Complexité (6h30)
- Complexité en temps déterministe définitions MT à k rubans, temps et espace de calcul, thèse de Church-Turing étendue, DTIME(f(n)), accélération linéaire.
- Classes de complexité en temps déterministe hiérarchie en temps déterministe, les classes P et EXP.
- Non déterminisme définition MT non déterministe, NTIME(f(n)), les classes NP, coNP et NEXP, certificat, hiérarchie en temps non-déterministe, padding, réduction many-one en temps polynomial, problème NP-difficile, NP-complet.
- NP-complétude SAT, 3SAT, théorème de Cook-Levin, problèmes NP-complets, CIRCUIT-SAT, Vertex-Cover, SubsetSum.
-
-
☆☆☆ La machine de Turing ci-dessus, partant de la configuration toute blanche, s'arrête au bout d'un temps fini. Saurez-vous mesurer le nombre de pas de calcul nécessaires à son arrêt ?
