Cours fondamental : Calculabilité et incomplétude.

Systèmes de déduction, fonctions récursives, fonctions calculables par machine. Théorèmes d'indécidabilité. Théorèmes d'incomplétude de Gödel. Classes de complexité (P, NP), problèmes NP-complets.

Année 2005-2006

Références.

En dehors de la première référence, ces livres couvrent largement plus sur le sujet que ce qui est abordé en cours.
(dernière modification le mardi 13/11/2012, 10:12:42 CET)