Calculabilité et Complexité (M1)

Cette page concerne la partie calculabilité du module.

La seconde partie du cours (complexité) est enseignée par Valia Mitsou.

Le syllabus du module complet est disponible ici.

Notes de cours sur les théorèmes d'incomplétude de Gödel .

Les sujets et TD sont au moins aussi importants que les notes de cours. Ils contiennent notamment des théorèmes dont l'énoncé et la (/une) preuve doivent être connus.

TBA

Le livre de Sipser : Introduction to the Theory of Computation (édition 2006) couvre l'ensemble du module. Certains pourront aussi trouver les notes de cours de Leonore Blum pertinentes.

Le livre de Sylvain Périfel (en français) sur la complexité couvre aussi une petite partie de ce que nous abordons en calculabilité.