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

Pages du cours

sur moodle (supports, informations, modalités d’examens, etc.)
sur unige (informations administratives)

Notes de cours

Préambule : [slides]
Cours 1 : Survol du module : [slides]
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]

Pour aller plus loin

Une partie du cours s’inspire de “Introduction to the Theory of Computation (Michael Sipser)”. D’autres parties sont composées à partir de ressources variées, dont certains articles Wikipédia.

Vous pouvez aussi consulter les notes de cours des années précédentes sur cette page. Mais attention: le contenu a changé.

Enfin, le livre “Quantum Computing Since Democritus (Scott Aaronson)” est une mine d’information qui recroise une bonne partie du cours (et explore beaucoup d’autres sujets). Sa lecture est exigeante, mais elle vaut la peine !