Cours de L3 “Calculabilité, complexité”

En général, voir l’emploi du temps.

Le contenu du cours

En première partie, on parlera de machines de Turing, de décidabilité et d’indécidabilité. En seconde partie, on parlera de complexité: combien de temps, combien d’espace est-il nécessaire pour résoudre une question algorithmique (décidable) donnée?

Modalités d’examen

Les modalités d’examen sont en cours de définition. Il y aura un partiel à mi-parcours, et un examen en janvier, sur table.

En cas d’échec, une session 2 sera organisée, sous forme d’oral ou d’examen écrit.

Le programme des cours

Pour 2021, et en ce concerne la première partie (calculabilité), je reprendrai les notes de cours de Hubert Comon, qui assurait ce cours jusqu’ici.

  • Machines de Turing, fonctions calculables et semi-calculables, problèmes décidables et récursivement énumérables, variantes: le poly, les transparents.
  • Machines I/O à k bandes, équivalence des modèles, illustration du pouvoir expressif: même poly, les transparents.
  • Machines de Turing universelles, indécidabilité, problème de l’arrêt. Le second poly, les transparents.
  • Réductions, et quelques problèmes indécidables fondamentaux: théorème de Rice, systèmes semi-Thue, problème de correspondance de Post: même poly, les transparents.
  • Problèmes de pavage (optionnel): le troisième poly, les transparents d’Hubert Comon.
  • Fonctions récursives: le quatrième poly, sur les fonctions récursives primitives, le cinquième poly, sur les fonctions récursives générales, et les transparents.

Le sujet du partiel du lundi 8 novembre 2021, et le même avec une solution possible.