Calculabilité complexité : ressources pédago.
Slides supports de cours
- [Cours 1 pdf] Introduction, M.T.
- [Cours 2 pdf] Simplification
des M.T., décidabilité, réductions
[Cours 2' pdf] Rice, arrêt uniforme
- [Cours
3 pdf] Classes P et NP (S. Brandel)
- [Cours
4 pdf] NP-complétude (S. Brandel)
- [Cours 5 pdf] Fonctions
récursives, un peu de récriture
- [Cours 5' pdf] Encore un
peu de récriture
[Cours 6 pdf] λ-calcul pur
- [Cours 7 et 8 pdf]
λ-calculs pur et typés
Quelques exercices
- [html] (TD1 Machines de
Turing)
- [html] (TD2 Machines de Turing,
décision)
- [html] (TD3 et 4 Classes P, NP,
complétude)
- [html] (TD5 fonctions récursives)
- [pdf] (Un peu de λ-calcul)
Annales