Modèles de calcul :
table des matières
Chapitre 0
: Introduction, liens, notes historiques.
Chapitre 1
: Numérotations.
Annexe
.
Chapitre 2
: Paradoxes de la diagonalisation et problème de l'arrêt.
Exercices
avec solutions.
Chapitre 3
: Récursion et théorème de Rice.
Exercices
avec solutions.
Chapitre 4
: Ensembles récursivement énumérables.
Exercices
avec solutions.
Chapitre 5
: Machines de Turing.
Chapitre 6
: λ-calcul.
Exercices
avec solutions.
Chapitre 7
: Complexité descriptive (Chaitin-Kolmogorov).
Chapitre 8
: Classes de complexité
P
et
NP
.
Chapitre 9
: Problèmes
NP
-complets.
Chapitre 10
: Algorithmes probabilistes et fonctions à sens unique.
Chapitre 11
: Mémoire et classe de complexité
PSPACE
.
Vos commentaires sont les bienvenus, envoyez-les à :