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.

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

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.

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.