Calculabilité et complexité

Calculabilité et complexité
Chapitres
Chap. 1 :Symbole icône indiquant que la page est à l'état d'ébauche Introduction (17)
Chap. 2 :Symbole icône indiquant que la page est à l'état d'ébauche Rappel sur la notion de langage (17)
Chap. 3 :Symbole icône indiquant que la page est à l'état d'ébauche Machine de Turing (17)
Chap. 4 :Symbole icône indiquant que la page est à l'état d'ébauche Méthodologies de mise en œuvre (17)
Annexes
Annexe :Symbole icône indiquant que la page est à l'état d'ébauche Bibliographie et liens (17)
Exercices
Exercice :Symbole icône indiquant que la page est à l'état d'ébauche Machine de Turing (17)
Interwikis

Sur les autres projets Wikimedia :

Présentation [Modifier]

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 [Modifier]

  • 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 [Modifier]

Ces personnes sont prêtes à vous aider concernant cette leçon :