Cette page contient les ressources pédagogiques du cours de Complexité et Calculabilité des années précédentes. Pour l’année actuelle, ça se passe sur cette page.

Printemps 2024

Enseignant : Arnaud Casteigts
Assistants : Alexandre-Quentin Berger et Matteo De Francesco
Monitrice : Léa Heiniger

Préambule : [slides]
Cours 1 : Survol du module : [slides] (pb d’enregistrements, pas de vidéo :-/)
Cours 2 : Rappels de langages formels : [notes de cours]
Cours 3 : Décidable, reconnaissable, simulation : [notes de cours]
Cours 4 : Diagonalisation et indécidabilité : [notes de cours]
Cours 5 : Théorème de Rice (et degrés de Turing) : [notes de cours]
Cours 6 : Introduction à la complexité algorithmique (A. Berger) : [notes de cours]
Cours 7 : Classes de complexité basiques : [notes de cours]
Cours 8 : Relations connues; non-déterminisme; théorème de Savitch : [notes de cours]
Cours 9 : Classe NP : [notes de cours]
Cours 10 : NP-complétude : [notes de cours]
Cours 11 : Exemples de réductions : [notes de cours]
Cours 12 : Théorème de Cook-Levin : [notes de cours]