Calculabilité & Complexité SOM2IF08
Désolé, cette activité n’est pas visible actuellement
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é (7h30)
- 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.
- NP-complétude problèmes NP-complets, CIRCUIT-SAT, Vertex-Cover, SubsetSum, CUBIC.