Complexité et calculabilité

Description du cours

Ce cours s’articule autour de deux thèmes : la notion de calcul et les questions de complexité. Dans la partie Calcul, les sujets abordés sont :

• La formalisation de la notion intuitive de calcul à l’aide d’un modèle de calcul élémentaire : les machines de Turing.
• La thèse de Turing-Church : tous les modèles de calculs raisonnables (machines de Turing, automates cellulaires, λ-calcul, programmes en C, Python ...) sont équivalents.
• La machine de Turing universelle : une machine capable de simuler le comportement de n’importe quelle autre machine de Turing, autrement dit, une machine programmable comme un ordinateur.
• L’existence de problèmes indécidables, problèmes qui ne peuvent être résolus par aucun algorithme. Entre autres : le problème de l’arrêt et le problème de correspondance de Post. Dans la partie Complexité, les sujets abordés sont :
• La classification des problèmes en fonction des ressources temps ou espace nécessaires pour les résoudre, en particulier les classes de complexité P, PSPACE, EXP
• Les machines de Turing non déterministes qui peuvent avoir plusieurs transitions possibles à chaque étape du calcul. En particulier, on donnera une autre caractérisation de la classe NP vue au premier semestre.
• La classe PSPACE des problèmes solvables en espace polynomial. Cette classe, intermédaire entre NP et EXP, permet typiquement de modéliser les problèmes de stratégie des jeux à deux joueurs, de planification de tâches ...
• Le théorème de Savitch : en espace polynomial, les machines déterministes ont les mêmes capacités que les non déterministes.
• L’existence de problèmes PSPACE-complets qui capturent toute la difficulté des problèmes PSPACE, dont le problème emblématique Q-CLAUSE-SAT.
• Un aperçu des machines de Turing probabilistes qui introduisent de l’aléatoire dans les calculs.