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.