Cours de L3 "Calculabilité, complexité"

• Cours: Jean Goubault-Larrecq (première partie, documentée plus bas), Philippe Schnoebelen (deuxième partie), les lundis de 10h45 à 12h45;
• TD: Luc Lapointe, Guillaume Scerri, les jeudis de 14h à 16h.
• Tutorat: les jeudis de 16h15 à 16h15.

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

Il y aura un partiel à mi-parcours, qui aura lieu sous forme de devoir à la maison à préparer en une semaine (ou deux semaines, selon la longueur du devoir), à une date en novembre qui sera déterminée en classe; et un examen en janvier, sur table.

Le devoir à la maison:

• est donné le lundi 10 novembre matin ici;
• devra être retourné le lundi 24 novembre (soir) au plus tard;
• à Jean Goubault-Larrecq, par email (uniquement), sous forme d'un unique fichier pdf.
  Pour créer votre pdf, vous pouvez utiliser LaTeX, si vous connaissez (ce sera une bonne idée d'apprendre un jour de toute façon), ou écrire à la main de façon lisible et scanner le résultat. Si votre pdf est trop gros, ne le découpez pas; vous pouvez le comprimer, par exemple via le site I♡pdf. Si vous utilisez LaTeX, voici un patron; inscrivez votre nom sur la ligne "Votre nom" et vos réponses à la place des macros \votresolutionici.
• En voici un corrigé possible.

A titre d'exemple,

• le partiel de l'année 2024, et un corrigé possible.

En cas d'échec à l'examen final, une session 2 sera organisée, sous forme d'oral ou d'examen écrit.

Le programme des cours

En ce concerne la première partie (calculabilité), nous nous baserons sur les notes de cours de Hubert Comon, qui assurait ce cours jusqu'en 2020.

1. Machines de Turing, fonctions calculables et semi-calculables, problèmes décidables et récursivement énumérables, variantes: le poly, les transparents avec les animations, les transparents en version courte (sans animation).
2. Machines I/O à k bandes, équivalence des modèles, illustration du pouvoir expressif: même poly, les transparents avec les animations, les transparents en version courte.
3. Machines de Turing universelles, indécidabilité, problème de l'arrêt. Le second poly, les transparents avec animations, les transparents en version courte.
4. 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 avec animations, les transparents en version courte.
5. Problèmes de pavage (optionnel): le troisième poly, les transparents d'Hubert Comon.
6. 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; les transparents avec animations, les transparents en version courte.