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) : Debrabant Patrice

Titre : Mathématice. N° 80. La machine de Turing (2/2). Les complexités de la complexité.

Editeur : Sésamath Erôme, 2022

Type : article de périodique ou revue Langue : Français Support : internet

Public visé : enseignant, formateur Niveau Niveau scolaire visé par l'article : licence, master

Classification : A39Revues, article de revue, article sur un site internet
Formation à l'enseignement, initiale et continue.
 P29Informatique théorique (structuration des données, codage des données, théorie du codage et de l'information, analyse des algorithmes et problèmes de complexité, modes de calcul et complexité calculatoire, langages formels)
Formation à l'enseignement, initiale et continue.
 

Résumé :

Suite au premier article Ressource en ligne sur la Machine de Turing, l'auteur réfléchit, dans celui-ci, à la notion de complexité algorithmique. Celle-ci mesure la quantité de ressources (temps ou espace mémoire) consommée pour résoudre un problème. Là où la calculabilité détermine si on peut le faire en théorie, la complexité en précise le coût, autrement dit si on peut le faire en pratique. Ce déplacement de problématique conduit à des questions fondamentales dont la plupart sont ouvertes. On pourrait penser a priori que cela dépend du dispositif (de la machine) utilisé. C'est bien entendu exact d'un certain point de vue. Mais on va voir que l'on peut définir une notion de complexité (asymptotique) qui ne dépend pas de la machine utilisée. La plupart des questions qui se posent alors pour cette complexité (comme le fameux problème "P est-il égal à NP ?") ne sont pas résolues. Et elles sont fondamentales.
L'auteur s'intéresse, tout d'abord, à la complexité en temps. Le coût en temps d'une machine de Turing déterministe appliquée à une entrée donnée w est égal au nombre de changements d'états que fait la machine pour arriver à un état final. Il se limite à des entrées w pour lesquelles ce nombre de changements d'états est fini. L'auteur juge, que dans ce contexte, il est judicieux de « se limiter » à un type particulier de machines de Turing. Ces machines de Turing ont deux états finaux : un état d'acceptation et un état de refus.

Notes :
Il est possible de lire et répondre à cet article : http://revue.sesamath.net/spip.php?article1508
MathémaTICE est une revue collaborative libre portant sur l'utilisation des TICE en classe de Mathématiques.
Une liste de thèmes est proposée en page d'accueil. A chaque requête thématique, MathémaTICE propose un dossier virtuel d'articles et de brèves correspondant à ce thème.

Cet article est en libre accès sur le site MathémaTICE

Mots clés :


© ADIREM-APMEP -2003- ISSN 1292-8054 Mise à jour 11/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