L'objet de cet enseignement est de présenter les notions fondamentales de calculabilité/décidabilité, de complexité et de théorie de l'information. La théorie de la calculabilité a pour objet d'étudier de manière théorique ce qui est calculable dans toute l'acceptation du terme. C'est une théorie à cheval entre l'informatique et les mathématiques. Les formalisations de la notion d'algorithme, et plus généralement de démonstration, dont on montre sous certaines hypothèses qu'elles sont toutes équivalentes, ont permis de répondre à une question récurrente depuis l'origine des sciences: "Que peut-on calculer ?".
    On montre qu'il n'existe pas d'algorithme ou de démonstration à certains problèmes (en fait la majorité des problèmes). La raison fondamentale tient en substance à l'existence de l'ensemble des nombres réels. Le modèle de machine utilisé est la machine de Turing
    Une fois le deuil fait sur la possiblité de tout démontrer ou calculer, on s'intéresse alors aux contingences matérielles (la calculabilité se moque de savoir s'il faut 10101010001 siècles pour calculer ou démontrer effectivement quelque chose) c'est-à-dire à la quantité de temps ou d'espace nécessaires à calculer ce qui peut l'être. L'objet de cette théorie est de proposer une classification des problèmes, autrement dit de les regrouper en classe de difficulté équivalente. On obtient alors (principalement) les classes P, NP et NP-complet.
    Le cours est décomposé en quatre parties : la première concerne les bases mathématiques indispensables à la suite (logique, axiomatique de Zermello-Fraenkel-Skolem, ensembles N, Q, R, cardinalité), la seconde la calculabilité/décidabilité, la troisième la théorie de l'information et la dernière la complexité des algorithmes.

    Le polycopié de cours est en gestation. Au regard du temps que j'ai déjà accordé pour rédiger les deux premières parties sur les trois que compte ce cours, j'estime qu'il ne sera pas disponible avant  2003. Tous les documents ci-dessous sont au format .dvi.gz
    Il est vraisemblable que certains sujets et/ou corrections contiennent des erreurs de natures diverses et variées qui auront échappé à ma sagacité, je vous serais reconnaissant de me les signaler.