Ce cours s’intéresse à deux notions essentielles en informatique:

• la calculabilité qui est la capacité à résoudre un problème étant données des régles de calcul
• la complexité qui mesure les ressources (temps et mémoire) nécessaires pour résoudre un problème

Supports de cours

1. Machines de Turing
2. Machines de Turing universelles, thèse de Church-Turing
3. Indécidabilité
4. Réduction, théorème de Rice
5. Complexité: P, NP, EXPTIME
6. Réduction polynomiale, NP-complétude
7. Complexité en espace: PSPACE
8. Introduction au calcul quantique

Supports de TD

• Feuilles d’exercices

Ressources supplémentaires

Les fichiers ci-dessous peuvent être utilisés dans le simulateur en ligne https://turingmachinesimulator.com.

• Machine de Turing pour (01)* (cours #1). Cette machine de Turing décide si le mot d’entrée est dans le langage (01)*.
• Machine de Turing pour PAL (cours #1). La machine de Turing décrite dans ce fichier décide si le mot d’entrée est un mot palindrome sur {0,1}. Le mot d’entrée doit débuter par le symbole spécial $ qui n’est pas considéré comme faisant partie du mot.