Calculabilité et Complexité (M1) La seconde partie du cours (complexité) est enseignée par Sylvain Périfel La date du partiel est actuellement fixée au jeudi 22 octobre à 16h. Notes de cours Ces notes de cours sont très informelles mais permettent de décrire l'ensemble des notions couvertes par ce module. Elles sont mises à jour au fur et à mesure (dernière mise-à-jour : 2020/10/15). cm.pdf Sujets de TD 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. TD1 TD2 TD3 TD4 TD5 Partiel Correction. Références 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.