COMPLEXITÉ ET CALCULABILITÉ

Ce cours étudie les frontières fondamentales entre le possible (calculabilité) et le faisable (complexité) dans le traitement d’information par ordinateur.

En première partie, ce cours présente une introduction à la théorie de la calculabilité et de la décidabilité en utilisant les machines de Turing comme modèle universel des ordinateurs.

La deuxième partie du cours est dédiée à l'étude de la complexité d'un algorithme, laquelle mesure l'efficacité de celui-ci. Au-delà des algorithmes, la théorie de la complexité permet aussi d'étudier la difficulté intrinsèque des problèmes rencontrés en particulier en optimisation combinatoire, par l’élaboration d'une hiérarchie de difficultés de résolution y compris les problèmes NP-complets.

Les sujets suivants seront abordés :

1. Calculabilité effective.
2. Hypothèse de Church et machines universelles.
3. Langages récursifs et récursivement énumérables.
4. Machines de Turing déterministes et non-déterministes.
5. Classes P, NP, co-NP et PSPACE.
6. Transformations polynomiales.
7. Problèmes NP-complets et NP-difficiles.

Documentation : Liste d’ouvrages de référence et notes de cours. Préparation pour : Algorithmique.