Calculabilité et complexité
Calculabilité et complexité
Département
Informatique théorique
Chapitres
| Chap. 1 : |  Introduction (17) |
|---|---|
| Chap. 2 : | Rappel sur la notion de langage (17) |
| Chap. 3 : | Machine de Turing (17) |
| Chap. 4 : | Méthodologies de mise en œuvre (17) |
Annexes
| Annexe : | Bibliographie et liens (17) |
|---|
Exercices
| Exercice : | Machine de Turing (17) |
|---|
Interwikis
Présentation []
La leçon présente
- les extensions des machines de Turing, notamment aux machines de Turing non déterministes ;
- la récursivité (au sens de Turing) et mu-récursivité (au sens de Church) ;
- la Thèse de Church-Turing ;
- la machine de Turing universelle et la non-calculabilité ;
- des exemples de problèmes indécidables, classes de complexité : P, NP et EXP, NP-complétude.
Objectifs []
- assimiler les notions de décidabilité d'un problème et de classes de complexité.
Niveau et prérequis conseillés
Leçon de niveau 17. Les prérequis pour cette leçon n'ont pas encore été précisés. Pour le faire, cliquez ici.
Référents []
Ces personnes sont prêtes à vous aider concernant cette leçon :