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]

Printemps 2025

Enseignant : Arnaud Casteigts
Assistants : Alexandre-Quentin Berger et Matteo De Francesco
Monitrice : Naziha Beghdadi et Elie Bussod

Préambule : [slides]
Cours 1 : Survol du module : [slides]

Calculabilité :

Cours 2 : Problèmes, Machine, Simulation : [notes] - [Alonzo Church]
Cours 3 : Propriétés de clôture et réductions : [notes]
Cours 4 : Théorème de Rice, Diagonalisation, Non-reconnaissabilité : [notes]

Complexité :

Cours 5 : Notations asymptotiques & classes de complexité : [notes]
Cours 6 : Relation entre classes : [notes] - [Hartmanis, Stearns, Williams]
Cours 7 : Non-déterminisme : [notes]
Cours 8 : Classe NP : [notes]
Cours 9 : Réductions polynomiales : [notes]
Cours 10 : NP-complétude : [notes]
Cours 11 : Theorème de Cook-Levin : [notes]