Mickael Ferreira
01 57 27 68 96
Sophie Germain - Bur. 3004
En télétravail les mardis et vendredis
(permanences Zoom : 10h30-12h00 ; 14h00-15h30)
(code: 141280)
Sylvia Crochet
01 57 27 68 98
Sophie Germain - Bur. 3002
En télétravail les mardis et vendredis. Ne travaille pas les mercredis
(permanences Zoom : 10h00-11h30 ; 14h30-16h00)
(code: 242581)
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.
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.
