Up Next

Complexité Turing

Cours de base (30 h de cours, 30h de TD)

Cours : Natacha Portier (Natacha.Portier)

TD : Irénée Briquel, Laurent Jouhet (Irenee.Briquel, Laurent.Jouhet)

Comprendre et délimiter le champ du calcul algorithmique nécessite de définir formellement des notions de calcul et d’algorithme, ce que réalisent divers modèles de calcul.

Evaluer, en fonction de ressources ressortissant d’un modèle le coût d’un algorithme ou la décidabilité d’un problème exprime leur complexité. Une part de la théorie de la complexité est de classer les problèmes algorithmiquement résolubles en fonction de ressources d’un modèle de calcul permettant leur résolution. Le modèle ici retenu est celui des machines de Turing, modèle historique dont les complexités en temps et en espace reflètent assez bien celles d’un ordinateur classique.

L’objet du cours est essentiellement l’étude de structures et de relations concernant les classes de complexité en temps et en espace. C’est aussi de situer certaines questions ouvertes et comment elles conduisent à considérer d’autres types de complexité. La plupart des preuves sont algorithmiques et introduisent des méthodes à l’œuvre dans d’autres champs de complexités.

Bibliographie

Up Next