Calculabilité et complexité en master d'informatique en 2004/2005
- Cours n° 1 : introduction des machines de Turing
- Introduction
- Limitation intrinsèque des ordinateurs
- Limitation des ordinateurs en temps et en espace
- Automates
- définition des automates finis
- notion de calcul
- automates non déterministes et déterminisation
- Machines de Turing
- définition
- description
- notion de configuration et de calcul
- un petit exemple
- Cours n° 2 : exemple et premières propriétés
- Cours n° 3 : équivalence entre les différentes variantes de machines
de Turing
- Cours n° 4 : indécidabilité
- Codage d'un problème en un langage
- Codage des machines de Turing
- Définition des langages récursivement énumérables
- Propriétés des langages récursivement énumérables
- équivalence entre un énumérateur et une machine de Turing
- l'union et l'intersection de deux langages récursivement
énumérables sont récursivement énumérables
- Langage non récursivement énumérable obtenu par argument diagonal
- Langage non récursivement énumérable obtenu par un
argument de cardinalité
- Définition des langages récursifs (décidables)
- Propriétés des langages récursifs
- le complémentaire d'un langage récursif est récursif
- l'union et l'intersection de deux langages récursifs sont
récursifs
- un langage récursif est récursivement énumérable
- si un langage et son complémentaire sont récursivement
énumérables, alors il est récursif
- Langage récursivement énumérable qui n'est pas récursif
- Cours n° 5 : réductions et
autres problèmes indécidables
- Machines universelles
- Problème de l'acceptation
- Autres exemples de problèmes indécidables
- problème de l'arrêt
- problème du vide
- Cours n° 6 : théorème de récursion
- Machine qui s'affiche elle-même
- Exemple d'un programme C qui affiche
son propre source
- D'autres programmes qui affichent
leur propre source
- Machine qui utilise sa propre description
- Application à l'indécidabilité
- Point fixe de transformation
- Cours n° 7 : partiel
- Cours n° 8 : problème de correspondance
de Post
- Problème de correspondance de Post standard
- Problème de correspondance de Post modifié
- Équivalence du problème standard et du problème modifié
- Indécidabilité des deux problèmes
- Cours n° 9 : machines RAM
- Définitions
- Exemples de programmes
- Équivalence entre machines RAM et machines de Turing
- Cours n° 10 : complexité en temps
- Changement de modèle de machines
- D'une machine à plusieurs bandes à une machine à une bande
- D'une machine non déterministe à une machine déterministe
- Classes P et NP
- Exemple de problèmes dans P et NP
- Équivalence entre vérificateurs et machines non
déterministes
- Cours n° 11 : NP-complétude
- Réductions polynomiales
- NP-complétude de SAT et 3-SAT
- Exemples de problèmes NP-complets
- Cours n° 12 : complexité en espace
- Théorème de Savitch
- Classe PSPACE
- Problème QSAT
- PSPACE-complétude
- PSPACE-complétude de QSAT
- Examen : jeudi 20 janvier