Curriculum LDD Informatique-Mathématiques

Cours : Calculabilité et complexité

Objectifs : Le but de ce cours est de comprendre les limites de ce qui est calculable d'une part, et de ce qui est calculable efficacement d'autre part. Il sera donc question, dans une première partie (calculabilité) des modèles de calculs, au premier rang desquels les machines de Turing, mais aussi les fonctions récursives. On y verra que certains langages, au premier rang desquels le problème de l'arrêt, sont indécidables. Dans la deuxième partie (complexité), il sera question de savoir ce qu'on peut calculer ou non sous des contraintes de temps, ou d'espace. La NP-complétude, et la complétude pour d'autres classes de complexité, sera étudiée. La notion de réduction sera importante dans les deux parties.

Plan détaillé :

  1. Machines de Turing, et variantes: à une bande, à plusieurs bandes, à plusieurs bandes de travail et entrée/sortie.
  2. Équivalence des modèles de machines de Turing.
  3. Machine universelle, réductions.
  4. Exemples de problèmes indécidables: problème de l'arrêt, problème de correspondance de Post, réécriture de mots, dixième problème de Hilbert, problèmes de pavage.
  5. Récursion primitive, fonctions récursives partielles, fonction d'Ackermann-Péter, hiérarchie de Grzegorczyk.
  6. Équivalence des modèles des fonctions récursives partielles et des fonctions calculables par machines de Turing. Théorème de forme normale de Kleene.
  7. Complexité en temps et en espace.
  8. Réductions logspace entre problèmes et logspace-équivalence; la composition de deux fonctions logspace est logspace.
  9. Problèmes C-complets pour une classe C.
  10. NP-complétude; problèmes NP-complets: SAT, SUBSET-SUM, HAMILTONIAN-CIRCUIT, HAMILTONIAN-CYCLE, CHEMIN-PONDÉRÉ.
  11. Théorème de Savitch.
  12. Classe PSPACE; problèmes PSPACE-complets: QBF, universalité d'expressions régulières.
  13. Classe PTIME; problèmes PTIME-complets: HORNSAT, 3HORNSAT, BinOp, CIRCUIT-VALUE.
  14. Classe NL; NL=co-NL; problèmes NL-complets: accessibilité dans les graphes, 2SAT.

Références :