Calculabilité et complexité en maîtrise d'informatique en 2002/2003
- 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
- automates avec ε-transitions
- Automates à pile
- définition
- notion de calcul
- Machines de Turing
- Cours n° 2 : exemples de machines de Turing
- Machine acceptant
le langage { anbn | n ≥ 0}
- Machine acceptant
le langage { a2n | n ≥ 0}
- Machine acceptant
le langage { ww | w ∈ {0, 1}*}
- Cours n° 3 : équivalence entre les différentes variantes de machines
de Turing
- Cours n° 4 : décidabilité
- 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
- 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
- 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
- l'union et l'intersection de deux langages récursivement
énumérables sont récursivement énumérables
- Cours n° 5 : indécidabilité
- Notion d'ensemble dénombrable
- définition
- exemples : N, Z, N × N, A*, Q, N3
- preuve que [0,1] n'est pas dénombrable par argument diagonal
- Codage des machines de Turing
- Indécidabilité par argument de cardinalité
- Indécidabilité par argument diagonal
- Cours n° 6 : indécidabilité (suite)
- 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° 7 : partiel
- Cours n° 8 : 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° 9 : réduction et problèmes de Post
- Définition d'une réduction
- Problèmes de correspondance Post
- problème de correspondance de Post standard
- problème de correspondance de Post modifié
- réduction du problème de Post modifié au problème de Post
standard
- indécidabilité des problèmes de correspondance Post
- Cours n° 10 : machines RAM et RAST
- Définitions
- Exemples de programmes
- Cours n° 11 : machines RAM (suite) et complexité
- Équivalence entre machines RAM et machines de Turing
- Définitions des complexités en temps et en espace
- Cours n° 12 : 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
- Classe NP
- Équivalence entre vérificateurs et machines non
déterministes
- Problèmes NP-complets
- Réductions polynomiales
- NP-complétude de SAT et 3-SAT
- Exemples de problèmes NP-complets
- Cours n° 13 : complexité en espace
- Examen