Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Decidabilite Séance Décidabilité et Complexité Objet Sensibiliser les étudiants aux principes de la décidabilité et de la complexité des algorithmes Plan Rappel de Calculabilité - Décidabilité - Complexité algorithmique VI Rappel de calculabilité La calcu

Séance Décidabilité et Complexité Objet Sensibiliser les étudiants aux principes de la décidabilité et de la complexité des algorithmes Plan Rappel de Calculabilité - Décidabilité - Complexité algorithmique VI Rappel de calculabilité La calculabilité cherche d'une part à identi ?er la classe des fonctions qui peuvent être calculées à l'aide d'un algorithme et à appliquer ces concepts à des questions fondamentales des mathématiques Une bonne appréhension de ce qui est calculcable et de ce qui ne l'est pas permet de voir les limites des problèmes que peuvent résoudre les ordinateurs Il peut être démontré qu'il existe des fonctions f qui sont incalculables c'est à dire qu'il n'existe aucun algorithme qui étant donné x retourne toujours la valeur f x en un temps ?ni L'exemple le plus courant est celui du problème de l'arrêt il n'existe pas de programme universel qui prenne n'importe quel programme en argument et qui en temps ?ni renvoie oui ? si l'exécution du programme reçu en argument ?nit par s'arrêter et non ? s'il ne ?nit pas Plusieurs modèles de calcul sont utilisés en calculabilité machines de Turing machine à compteurs lambda-calcul automates cellulaires fonctions récursives etc Malgré la diversité de ces modèles la classe de fonctions calculables par chacun de ceux-ci est unique et cette constatation mène à la thèse Church-Turing La thèse de Church- Turing ou simplement thèse de Church des noms des mathématiciens Alonzo Church et Alan Turing est une idée qui se rattache au domaine de l'informatique Dans sa forme la plus ordinaire elle a ?rme que tout traitement réalisable mécaniquement peut être accompli par une machine de Turing Tout programme d'ordinateur peut donc être traduit en une machine de Turing DUT informatique ?? Page CD'autre part certaines machines de Turing dites universelles peuvent e ?ectuer tous les traitements possibles avec une machine de Turing quelconque La plupart des langages de programmation usuels ont plus exactement auraient sur un ordinateur disposant d'une mémoire in ?nie les possibilités de calcul d'une machine de Turing universelle de sorte que toutes les machines de Turing peuvent être simulées par un programme écrit dans l'un de ces langages La thèse de Church-Turing a ?rme donc que n'importe quel langage de programmation Turing-complet permet d'exprimer tous les algorithmes La thèse de Church-Turing est généralement considérée comme vraie Mais ce n'est pas un énoncé mathématique chercher à la démontrer n'a pas de sens Elle serait en revanche réfutée si un calcul que l'on s'accorde à considérer comme réalisable mécaniquement s'avérait hors de portée des machines de Turing La thèse peut être reformulée en disant que les machines de Turing formalisent correctement la notion de méthode e ?ective de calcul On considère généralement qu'une méthode e ?ective doit satisfaire aux obligations suivantes l'algorithme consiste en un ensemble ?ni d'instructions simples et précises qui sont décrites avec un nombre limité de symboles l'algorithme doit toujours produire le résultat en un nombre ?ni d'étapes l'algorithme peut en principe être suivi par un humain avec seulement du papier et un crayon l'exécution