| Prof | Site | Cours | TP | TD | ECTS | |
|---|---|---|---|---|---|---|
| M. Pascal Schreck | 24h | 3 | ||||
| Contenu | ||||||
| Extensions des machines de Turing, machines de Turing non déterministes. | ||||||
| Récursivité (au sens de Turing) et mu-récursivité (au sens de Church). | ||||||
| Thèse de Church-Turing. Machine de Turing universelle et non-calculabilité. | ||||||
| Exemples de problèmes indécidables, classes de complexité : P, NP et EXP, NP-complétude. | ||||||
| Pre-requis | ||||||
| Théorie des langages | ||||||
| Références | ||||||
| Lewis & Papadimitriou, “Elements of the theory of computation.” | ||||||
N.B. Ces notes sont relativement incomplètes pour le moment, en attendant de faire des diagrammes.
| 15/09 | Machines de Turing | Introduction Définition et exemples de Machines de Turing Définitions de configuration, calcul, pas de calcul, etc. Exemple et exercices. |
| 22/09 | Composition de Machines de Turing | Calculer avec des MT |
| 29/09 | Fonctions rècursives (Turing calculables) | reconnaissance de langages (avec MT) semi-décisions Extensions : MT multi-ruban |
| 6/10 | MT Multi-rubans | Exercices, et théorème d'équivalence Autres extensions |
| 13/10 | 1.5 Machines de Turing non-déterministes 1.6 Grammaires générales exercice | et théorème d'équivalence |
| 20/10 | Fonctions numériques | |
| 27/10 | c_et_c_8 | mu-récursivité (calculable sens de Church)⇔ récursivité (sens de Turing) |
| 10/11 | II. Indécidabilité | II. Indécidabilité 1. Thèse de Church-Turing 2. Machines de Turing Universelles 3. “The Halting Problem” |
| 17/11 | II.4 Problèmes Indécidables | II.4 Problèmes indécidables |
| 24/11 | II.5 Problèmes indécidables pour les grammaires | II.5 Problèmes indécidables pour les grammaires |
| 1/12 | c_et_c_c | Interrogation écrite |
| 15/12 | III. Complexité | |
| 15/12 | Définitions |