====== Calculabilité et Complexité (M1) ======
Cette page concerne la partie //calculabilité// du module.

La seconde partie du cours (//complexité//) est enseignée par [[https://www.irif.fr/~vmitsou/|Valia Mitsou]].

Le syllabus du module complet est disponible [[http://www.informatique.univ-paris-diderot.fr/formations/masters/ue/m1/cc7|ici]].

Notes de cours sur les {{ :users:feree:godel.pdf | théorèmes d'incomplétude de Gödel}} .

/* La date du **partiel** est actuellement fixée au **mercredi 9 novembre à 14h**. */

/* ===== 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//).
{{ :users:feree:ens:calc: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.

  * {{ :users:feree:ens:calc:td1.pdf |TD1 }}
  * {{ :users:feree:ens:calc:td2.pdf |TD2 }}
  * {{ :users:feree:ens:calc:td3.pdf |TD3 }}
  * {{ :users:feree:ens:calc:td4.pdf |TD4 }}/*
  * {{ :users:feree:ens:calc:td5.pdf |TD5 }}
*/

===== Partiel =====
TBA
/* La correction (hors questions de cours) est disponible {{ :users:feree:ens:calc:correction.pdf |ici}}. */

===== 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 [[http://www.cs.cmu.edu/~lblum/flac/schedule.html|notes de cours de Leonore Blum]] pertinentes.

Le livre de [[https://www.irif.fr/users/sperifel/livre_complexite | Sylvain Périfel]] (en français) sur la complexité couvre aussi une petite partie de ce que nous abordons en calculabilité.