| vendredi 23 septembre 2016, 13h45-15h45 |
Machines
de Turing
Définitions machines de Turing déterministes, non-déterministes. Langages acceptés. Langages décidés. Equivalence entre machines à k-rubans et un ruban. Equivalence entre machines déterministes et non-déterministes (lemme de König). Classe R et RE. Enumérateurs.
Simulateur d'une machine de Turing déterministe
|
|
vendredi 30 septembre 2016, 13h45-15h45
|
Indécidabilité
Classes R et RE. Décidabilité et indécidabilité. Problème de l'arrêt. Machine universelle (simulation d'une machine passée en entrée).
Théorème de Rice.
Problème de correspondance de Post.
|
|
vendredi 7 octobre 2016, 13h45-15h45
|
NP-complétude
Problèmes dit de recherche. Problèmes de décision, instances, certificats. Problème d'optimisation. Classe P, NP et EXPTIME. Réduction polynomiale. NP-dur. NP-complet.
Présentation de CLIQUE, ENS INDEP et VERTEX COVER. Réduction de 3-SAT à ENS INDEP.
Catalogue de réductions
|
|
vendredi 14 octobre 2016, 13h45-15h45
|
Théorème de Cook.
Fonctions récursives
Fonctions récursives primitives. Exemples. Minimisation bornée.
Exemples de fonctions récursives
|
|
mardi 8 novembre 2016, 10h15-12h15
|
Fonctions récursives (suite)
Codage de couple d'entiers. Limites. Fonction mu-récursives.
Lien avec un langage de programmation impérative.
Lien avec les machines de Turing.
Fonctions récursives vers machines de Turing
|
| mardi 24 janvier 2016, 10h15-12h15 |
PSPACE
Théorème de Savitch.
Syntaxe et sémantique : QBF.
TQBF dans PSPACE.TQBF est PSPACE-dur
Problème de géographie généralisé
Universalité d'une expression rationnelle
|