Accueil Publimath  Aide à la recherche   Recherche Avancée   Imprimer la fiche   Aidez-nous à améliorer cette fiche  Vidéo d'aide
Certification IDDN Valid HTML 4.01 Transitional
Auteur(s) : Hudry Olivier

Titre : De la méthode. Machines de Turing et complexité algorithmique. p. 179-212.

Editeur : Presses universitaires de Franche-Comté (PuFC) Besançon, 2011 2e éd.
Format : 16 cm x 22 cm, p. 179-212 ISBN : 2-84867-324-9 EAN : 9782848673240

Type : ouvrage (au sens classique de l'édition) Langue : Français Support : papier

Public visé : chercheur, enseignant, formateur

Classification : E29Métamathématique. Aspects philosophiques et éthiques des mathématiques. Épistémologie des mathématiques
Formation à l'enseignement, initiale et continue.
 

Résumé :

L'objectif de cet article consiste à esquisser le rôle des machines de Turing en théorie de la complexité (des algorithmes et des problèmes), dans le domaine de l'optimisation combinatoire. Après avoir rapidement rappelé le contexte historique dans lequel sont nées et ont évolué les machines de Turing, l'auteur détaille le fonctionnement de celles-ci en distinguant entre machines de Turing déterministes et machines de Turing non déterministes. Il montre ensuite comment les utiliser pour définir la complexité (en temps de calcul) des algorithmes. Enfin, il décrit grâce à elles plusieurs classes fondamentales en théorie de la complexité : la classe P, la classe NP, la classe des problèmes NP-complets et la classe co-NP.

Notes :
Chapitre de l'ouvrage De la méthode.

Mots clés :


© ADIREM-APMEP -2003- ISSN 1292-8054 Mise à jour 08/05/2022
Accueil Publimath  Aide à la recherche   Recherche Avancée   Imprimer la fiche   Aidez-nous à améliorer cette fiche  Vidéo d'aide
Certification IDDN Valid HTML 4.01 Transitional