~~NOTOC~~
====== Calculabilité et complexité ======

===== Description =====

La théorie de la calculabilité décrit d'un point de vue théorique ce qui peut, et surtout ce qui ne peut pas être calculé, notamment en utilisant des modèles simples, mais complets, de nos ordinateurs. Dans cette partie du cours, on va étudier des problèmes bien définis pour lesquels il n'y a aucun algorithme qui peut les résoudre.

De manière analogue, la théorie de la complexité adresse la question de l'efficacité d'un algorithme en fonction des ressources utilisées (temps et espace). On classifie ainsi les problèmes décidables (ceux qu'on peut résoudre à l'aide d'un ordinateur) dans des classes de complexité selon leur difficulté intrinsèque.

Dans ce module, nous nous attacherons tout particulièrement à démontrer les résultats classiques de ces deux théories.
===== Syllabus =====
==== Sujets centraux ====

=== Calculabilité ===
  - machines de Turing
  - décidabilité
    * semi-décidabilité
    * problème de l'arrêt
  - machines universelles
  - réductions (many-one, Turing)
  - théorème de Rice
  - Théorèmes de récursion
    * théorème de point fixe
    * quines

=== Complexité ===

  - complexité en temps déterministe
    * P
    * EXP
    * théorème de hiérarchie
  - complexité en temps non-déterministe
    * NP
    * NEXP
  - réductions polynomiales, théorie de la NP-complétude, théorème de Cook-Levin
  - P vs NP
    * problème du prix du millénaire
    * problèmes NP-intermédiaires, le théorème de Ladner
  - la classe complémentaire (coNP)
  - complexité en espace déterministe
    * PSPACE
    * L
    * réductions en temps polynomial, théorie de la PSPACE-complétude
  - complexité en espace non-déterministe
    * NPSPACE
    * NL
    * réductions en espace logarithmique, la théorie de la NL-complétude
    * théorème de Savitch

==== Sujets potentiellement traités ====

  - problème de correspondance de Post
  - hiérarchie arithmétique
  - théorème de Gödel
  - complexité à grain fin, ETH
  - problèmes faiblement NP-difficiles
  - hiérarchie polynomiale
  - Théorème d'Immerman-Szelepcsényi
  - problèmes P-complets

===== Pré-requis =====

Un cours en **algorithmique de graphes** est pré-requis. Une connaissance de théorie de **automates et des langages réguliers** et de **calcul propositionnel** est préférable.