Remerciez-le!

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

DUT informatique – 0607 Page 1 Séance 6 : Décidabilité et Complexité Objet : Se

DUT informatique – 0607 Page 1 Séance 6 : 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.1 Rappel de calculabilité La calculabilité cherche d'une part à identifier 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 fini. 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 fini, renvoie « oui » si l'exécution du programme reçu en argument finit par s'arrêter et « non » s'il ne finit 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 affirme 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 – 0607 Page 2 D'autre part, certaines machines de Turing, dites universelles, peuvent effectuer 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 infinie) 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 affirme 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 effective de calcul. On considère généralement qu'une méthode effective doit satisfaire aux obligations suivantes : l'algorithme consiste en un ensemble fini 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 fini d'étapes ; l'algorithme peut en principe être suivi par un humain avec seulement du papier et un crayon ; l'exécution de l'algorithme ne requiert pas d'intelligence de l'humain sauf celle qui est nécessaire pour comprendre et exécuter les instructions. Un exemple d'une telle méthode est l'algorithme d'Euclide pour déterminer le plus grand commun diviseur d'entiers naturels. Il s'agit là d'une définition intuitive assez claire, mais pas d'une définition formelle, faute d'avoir précisé ce qu'on entend par « instruction simple et précise » ou par « l'intelligence requise pour exécuter les instructions ». On peut en revanche définir formellement les algorithmes comme les procédés qui peuvent être accomplis par une machine de Turing universelle. À ce stade, la thèse de Church-Turing affirme que les deux définitions, intuitive et formelle, concordent. VI.2- Décidabilité Intuitivement, P est décidable s’il existe un algorithme qui pour chaque x dit “OUI” ou “NON” à la question : “Est-ce que P(x) est vrai ?”. Ce problème avait été posé la première fois par David Hilbert, au Congrès International des Mathématiciens qui avait eu lieu à Paris en 1900. Hilbert, comme beaucoup de mathématiciens de l'époque, était assez obsédé par de nombreux problèmes de mathématiques qui ne trouvaient pas de solution. Ainsi celui des équations diophantiennes. On appelle équation diophantienne une équation du genre P(x, y, z, ...) = 0, où P est un polynôme à coefficients entiers. Résoudre une telle équation, c'est chercher les solutions sous forme d'entiers. DUT informatique – 0607 Page 3 Par exemple : x2 + y2 – 1 = 0 est une équation diophantienne qui admet pour solutions: x = 1, y = 0 et x = 0, y = 1. L'équation x2 – 991y2 – 1 = 0 est également diophantienne mais a des solutions beaucoup plus difficiles à trouver (cf J. P. Delahaye, in "Logique, informatique et paradoxes" ed. Belin), la plus petite est : x = 379 516 400 906 811 930 638 014 896 080 et y = 12 055 735 790 331 359 447 442 538 767 Hilbert posait la question : "existe-t-il un procédé mécanique permettant de dire, après un nombre fini d'étapes, si une équation diophantienne donnée possède des solutions entières?". On doit noter que, parmi ces équations, figurent certaines, qui sont associées à un problème historiquement bien connu: le problème de Fermat. Fermat pensait en effet avoir démontré que toute équation de la forme : xp + yp = zp est sans solution pour p > 2. (Pour p = 2, bien sûr... elle en a au moins une, cf: x = 3, y = 4, z = 5). De fait, on ne disposait pas, jusqu'à une date récente (Andrew Whiles, 1993) d'une telle démonstration. Au-delà de ce type de problème, Hilbert posait la question générale de savoir si l'on pouvait trouver un procédé mécanisable capable de résoudre toutes les questions mathématiques récalcitrantes. C'est à partir de cette dernière question que Turing s'est mis au travail. Elle est plus générale que la première question: en effet, on pourrait imaginer qu'il n'y ait pas de procédure uniforme pour résoudre tous les problèmes mathématiques mais qu'il y en ait une pour résoudre la problème particulier des équations diophantiennes. En fait, ni l'une ni l'autre n'existe. En logique mathématique, le terme décidabilité recouvre deux concepts liés : la décidabilité logique et la décidabilité algorithmique. L'indécidabilité est la négation de la décidabilité. Dans les deux cas il s'agit de formaliser l'idée qu'on ne peut pas toujours conclure lorsque l'on se pose une question, même si celle-ci est sous forme logique. VI.2.1- Décidabilité, indécidabilité d'un énoncé dans un système logique Définition VI.2.1.1- décidabilité Une proposition (on dit aussi énoncé) est dite décidable dans une théorie axiomatique, si on peut la démontrer ou démontrer sa négation dans le cadre de cette théorie. Un énoncé mathématique est donc indécidable dans une théorie s'il est impossible de le déduire, ou de déduire sa négation, à partir des axiomes. Remarque : Pour distinguer cette notion d'indécidabilité de la notion d'indécidabilité algorithmique (voir ci-dessous), on dit aussi que l'énoncé est indépendant du système d'axiomes. En termes plus concrets, cela veut dire qu'on demande au système de fournir une conclusion sans lui avoir fourni suffisamment d'hypothèses. Ainsi, l'âge du capitaine d'un bateau est indécidable en fonction du tonnage et de la vitesse du navire. DUT informatique – 0607 Page 4 Proposition VI.2.1.1- En logique classique, d'après le théorème de complétude, une proposition est indécidable dans une théorie s'il existe des modèles de la théorie où la proposition est fausse et des modèles où elle est vraie. On utilise souvent des modèles, pour montrer qu'un énoncé est indépendant d'un système d'axiomes (dans ce cadre on préfère employer indépendant qu'indécidable). La propriété utilisée dans ce cas n'est pas le théorème de complétude mais sa réciproque, très immédiate, appelée parfois fidélité. Probablement est-ce là d'ailleurs la première apparition de la notion de modèle, avec la construction au XIXème siècle de modèles des géométries non classiques, ne vérifiant pas l'axiome des parallèles. Exemple : Si l'on admet le fait assez intuitif que la géométrie euclidienne est cohérente — la négation de l'axiome des parallèles ne se déduit pas des autres axiomes — l'axiome des parallèles est bien alors indépendant des autres axiomes de la géométrie, ou encore indécidable dans le système formé des axiomes restant. Définition VI.2.1.2- complétude Une théorie mathématique pour laquelle tout énoncé est décidable est dite complète, sinon elle est dite incomplète. Beaucoup de théories mathématiques sont naturellement incomplètes, parce qu'il y a évidemment des énoncés qui ne sont pas déterminés par les axiomes (théorie des groupes, des anneaux, ...) . Certaines théories, comme la théorie des corps algébriquement clos, celle des corps réels clos, ou encore l'arithmétique de Presburger sont complètes. Le premier théorème d'incomplétude peut être énoncé de la façon encore un peu approximative suivante : Premier Théorème d’incomplétude de Gödel : Dans n'importe quelle théorie récursivement axiomatisable, cohérente et capable de « formaliser l'arithmétique », on peut construire un énoncé arithmétique qui ne peut être ni prouvé ni réfuté dans cette théorie. De uploads/Philosophie/ decidabilite.pdf