Next PDF List

Notes de cours : introduction a la theorie du calcul Universite Pierre et Marie CurieIntroduction a la theorie du calcul : notes de cours(premiere partie : les machines de Turing)1 IntroductionOn possede aujourd'hui une denition precise de ce qu'on doit appeler methodes de calcul (oualgorithmes).

On sait ainsi quels sont les problemes qu'elles peuvent traiter, et on sait egalementque certains problemes ne sont pas \traitables".

On a des resultats negatifs, de la forme : \pour telprobleme non seulement aucun algorithme n'est actuellement connu, mais aucun ne le sera jamais."Ces problemes pour lesquels on demontre qu'il n'existe aucun algorithme les resolvants s'appellent desproblemes indecidables.Heureusement, de nombreux problemes que l'on aimerait reoudre par ordinateur ne sont pasindecidables.

Il existe cependant de grandes dierences parmi ces problemes qui peuvent ^etre resoluspar un algorithme.|Certains son tdits faciles : il s'agit de la plupart de sprobl emesque v ousa vezrencon tresjusqu' apresent.|d'autres probl emesson tdits diciles : on a p ources probl emesdes r esultatsn egatifs,de la forme \pour tel probleme, non seulement aucun algorithme ecace n'est actuellement connu,mais un algorithme ecace resolvant ce probleme resoudrait egalement toute une liste d'autresproblemes pour lesquels de nombreux chercheurs ont cherche en vain un algorithme ecace".1.

1) Exemples|Le probleme de la cha^ne.Donnees: un graphe non oriente, deux sommetssettdu graphe.Question: est-ce qu'il existe une cha^ne qui liesett(autrement, dit : est-ce qu'il est possible,en passant d'un sommet a un autre sommet voisin, de partir deset d'arriver at)?Ce probleme est dit facile.

On le resoud en faisant un parcours a partir du sommets: sitappartient a la m^eme composante connexe ques, alors il existe une cha^ne liantsat.

Pourmontrer qu'un probleme est facile, on donne un algorithme ecace le resolvant (ecace veutdire qui se resoud en temps polynomial en l'entree du probleme, comme on le rappellera par lasuite).|Le probleme de la cha^ne hamiltonienne.Donnees: un graphe non orienteG= (S;A), deux sommetssettdeG.Question: est-ce qu'il existe une cha^ne d'extremitessettqui passe une fois et une seule foispar chaque sommet du graphe?Ce probleme est dit dicile (NP-complet).

On peut le resoudre (par exemple par une rechercheexhaustive, ce qui represente (jSj 2)! permutations a tester), mais on ne conna^t pas d'algo-rithme ecace le resolvant (et on conjecture qu'il n'existe pas de tel algorithme).

De nombreuxproblemes rencontres dans l'industrie (en recherche operationnelle) sont diciles.

1) Notes de cours : introduction a la theorie du calcul Universite Pierre et Marie Curie|Le probleme du pavage de Wang.Un ensemble detuiles de Wangest un ensemble ni de carres aux c^otes colores.

Deux tuilespeuvent s'assembler selon deux c^otes si ces deux c^otes sont de la m^eme couleur (il est interditde faire tourner les tuiles : pour chaque tuile il est indique quel c^ote doit ^etre en haut, a droite,etc.).

Unpavageest un recouvrement du plan tel que chaque assemblage de tuile deux-a-deuxest valide (cf.

Figure 1).Donnees: un ensemble niTde tuiles de Wang, une tuile d'originet0.Question: peut-on paver le plan avec des tuiles deT(on peut disposer d'un nombre inni detuile de chaque sorte) en partant d'une tuilet02T?Figure1 { A gauche : tuiles, a droite : un pavage possible.Ce probleme est indecidable.1.

2) Probleme d'optimisation vs. probleme de decisionDans unprobleme d'optimisation, on cherche une solution qui optimise une fonction objectif souscertaines contraintes.

Dans unprobleme de decision, on cherche s'il existe une solution qui respectecertaines contraintes.

Alors que la solution d'un probleme d'optimisation peut ^etre de divers types (unnombre, un chemin dans un graphe, un arbre couvrant, etc.), la solution d'un probleme de decisionest toujours Oui ou Non.Par exemple : rechercher un plus court chemin dans un graphe entre deux sommetsaetbest unprobleme d'optimisation; savoir s'il existe un chemin de longueur au plusBentre les sommetsaetbdu m^eme graphe est un probleme de decision.Quand on s'interesse a la complexite d'un probleme d'optimisation, on cherche en fait la dicultedu probleme de decision associe : si le probleme de decision associe est \dicile", alors le probleme d'op-timisation le sera egalement.

Dans la suite de ce premier cours, on s'interessera donc a des problemesde decision.An de montrer que certains problemes peuvent ^etre facilement resolus par un ordinateur, d'autresdicilement, et d'autres pas du tout (problemes indecidables), il est necessaire de formaliser ce quepeut faire un ordinateur : c'est ce que font les machines de Turing.

2) Les machines de Turing2. 1) Alan TuringMathematicien, cryptologue et informaticien britannique.

2) Notes de cours : introduction a la theorie du calcul Universite Pierre et Marie Curie|1912 : Naissance aLondres |1936 : La mac hined eT uringAlan Turing,On computable numbers with an applicationto the Entsheidungsproblem, Proc.

London Math. Society,serie 2, vol. 42, 1937, pages 230-265.

Article fondateur de lascience informatique.|1936 : D ecodagedu co desecret allemand ENIGMA. |1950 : In telligenceArticielle, \te stde T uring"|1954 : Mort (suicide ?) 2.

2) Qu'est ce qu'une machine de Turing?Une machine de Turing peut resoudre tout probleme qu'un ordinateur peut resoudre (ici \resoudre"est synonyme de \calculer" : \ordinateur = computer").

Cependant, comme un ordinateur, une ma-chine de Turing ne peut pas tout calculer.

Une fonctionfestcalculables'il existe une methode precise(un algorithme) qui, etant donne un argumentx, permet d'obtenir l'imagef(x) en un nombre nid'etapes.

Une fonction calculable est une fonction calculable par une machine de Turing.Voir ce qui est calculable et ce qui ne l'est pas permet de voir les limites des problemes que peuventresoudre les ordinateurs.NB : il existe d'autres formalismes, comme par exemple le lambda-calcul, qui sont equivalents auxmachines de Turing.2.

3) Modele de la machine de TuringUne machine de Turing M est un mecanisme idealise destine a eectuer des calculs.

Pour eectuerses calculs la machine de Turing M utilise un ruban inni decoupe en cases, et une t^ete de lecture-ecriture qui lui permet de lire et d'ecrire sur le ruban.

Cette t^ete de lecture-ecriture (que l'on appeleraensuite t^ete de lecture) peut se deplacer sur le ruban et c'est la machine elle-m^eme qui commande lesdeplacements.Une machine de Turing est donc composee de :|Un ruban inni (qui repr esenteune m emoireinnie) |Une t ^etede lecture qui p eutlire et ecriredes sym boleset se d eplacerle long du ruban ( adroite et a gauche)|Des r eglesqui, etantdon nel' etatcouran t,in diquentla pro cedure asuivre : symbole a ecrire a la position courante (la case sur laquelle pointe la t^ete de lecture),se deplacer d'une case vers la droite ou vers la gauche,etat dans lequel on arrive abaabatete de lecturerubanFigure2 { Schema d'une machine de Turing.Initialement, le ruban contient une cha^ne de caracteres qui est l'entree du probleme, et est blanc3Notes de cours : introduction a la theorie du calcul Universite Pierre et Marie Curiepartout ailleurs.

La machine continue a lire/ecrire des informations jusqu'a ce qu'elle produise unesortie :accepterourejeter.

Si elle ne rentre pas dans un tel etat, elle peut ne jamais s'arr^eter.Une instruction elementaire de machine de Turing est par exemple : \si je suis dans l'etatE1etque je lis le symbole 0 dans la case ou se trouve la t^ete de lecture, alors ecrire 1, puis me deplacerd'une case vers la droite.

Je passe alors dans l'etatE2".La programmation des machines de Turing est fastidieuse, l'inter^et de la notion tient a la tresgrande simplicite des machines obtenues, pas a leur convivialite! Comme nous le verrons ensuite,l'importance du concept de machines de Turing tient dans le fait que le type de calculs qu'ellespermettent de faire est absolument general.

Toutes les tentatives de denition d'algorithme (souventplus compliquees et en apparence beaucoup plus riches) conduisent en fait a une denition exactementequivalente en puissance.2.

4) Probleme de decision et langageNotons qu'un probleme de decision peut ^etre exprime comme l'appartenance d'un mot a un langage(un langage est un ensemble de mots).

En eet chaque entree du probleme se represente par un mot(une suite de symboles) et l'ensemble des entrees pour lesquelles la solution au probleme est Oui estle langage associe au probleme de decision.Prenons par exemple le probleme qui prend en entree une liste de mots (composes de 0 et 1) separespar des#, et cherche a savoir si tous les mots sont dierents les uns des autres.

Le langage associe ace probleme de decision estL=f#x1#x2:::#xnjxi2 f0;1getxi6=xjpour touti6=jg.Nous verrons par la suite qu'une machine de Turing reconna^t un langage.

Ce langage est l'ensembledes entrees que la machine de Turing accepte.

Une machine de Turing resolvant un probleme de decisionPdoit donc accepter un mot si et seulement si ce mot code une entree dePpour laquelle la reponseaPest Oui.2.

5) ExempleOn veut construire une machine de Turing qui teste si le mot de depart sur le ruban est composede deux mots identiques composes de 0 et de 1, et separes par un#(i.e. le mot appartient afw#wjw2f0;1gg).Pour comprendre ce que faire la machine de Turing, imaginez que vous vous deplacez sur une routetres longue sur laquelle se trouve des millions de 0, 1 et #.

Vous devez, uniquement en vous deplacantsur la route et en remplacant des symboles par d'autres, dire si le message inscrit sur la route estconstitue de deux mots identiques separes par un#.Description (haut niveau) de la machine de Turing (appeleeM1) :M1=|\Se d eplacerde la premi erep ositiondu mot agauc hedu #a lapremiere position du mot a droite du#et verier que ces positonscontiennent le m^eme symbole.

Si ce n'est pas le cas,rejeter. Barrerles symboles des qu'ils sont veries (pour se souvenir de la positioncourante).

Recommencer avec la position suivante tant que tous lessymboles a gauche du#n'ont pas ete barres (et que l'etatrejetern'apas ete rencontre).|Quand tous les sym boles agauc hedu #ont ete barres, regarder s'ilreste des symboles a doite du#.

Si c'est le casrejeter, sinonaccepter."4Notes de cours : introduction a la theorie du calcul Universite Pierre et Marie CurieExemple :0 0 1 0 1 1 1 0 1 0 1 # 0 0 1 0 1 1 1 0 1 0 1x 0 1 0 1 1 1 0 1 0 1 # 0 0 1 0 1 1 1 0 1 0 1x 0 1 0 1 1 1 0 1 0 1 # x 0 1 0 1 1 1 0 1 0 1x x 1 0 1 1 1 0 1 0 1 # x 0 1 0 1 1 1 0 1 0 1. x x x x x x x x x x x # x x x x x x x x x x x2.

6) Denition formelle d'une machine de TuringUne machine de Turing est un 7-uplet, (Q;;), ouQ; et sont des ensembles nis et1.Qest l'ensemble des etats2. est l'alphab etd'en treequi ne con tientp asle sym boleblan c3. est l'alphab etdu ruban, a vec2 et 24.:Q!Q fG;Dgest la fonction de transition (Gsignie que la t^ete de lecture sedeplace d'une case vers la gauche,Dsignie qu'elle se deplace d'une case vers la droite)5.q0est l'etat initial6.qaccepter2Qest l'etat d'acceptation7.qrejeter2Qest l'etat de rejet, avecqrejeter6=qaccepter.Remarque : on considere que le ruban commence la ou se trouve le premier symbole de l'entree :si la machine essaie d'aller plus a gauche que cette position, alors la t^ete de lecture reste a la m^emeplace, m^eme si la fonction de transition indiqueG.2.

7) Retour a l'exemple (mot appartenant afw#wjw2 f0;1gg)|Q=fq1;:::;q8;qaccepter;qrejeterg| = f0;1;#g, et =f0;1;#;xg|On d ecritavec un diagramme d'etats (ci-dessous)|Etat initial :q1, etat d'acceptation :qaccepter, etat de rejet :qrejeter.En general, on donnera une description de plus haut niveau des machines de Turing.

Il est cependantimportant de se souvenir que toute description de plus haut niveau est seulement un raccourci de ladenition precise d'une machine de Turing.2.

8) Un deuxieme exemple : le probleme des elements distinctsEtant donnee une liste de mots (composes de 0 et 1) separes par des#, on cherche a savoir si tousles mots sont dierents les uns des autres.

Si tel est le cas, la machine doit accepter l'entree, sinon elledoit la rejeter.

Autrement dit, le langage reconnu par la machine de Turing est :E=f#x1#x2:::#xnjxi2 f0;1getxi6=xjpour touti6=jgDescription (haut niveau) de la machine de Turing (appeleeM2) :5Notes de cours : introduction a la theorie du calcul Universite Pierre et Marie Curie1!x,G0,1,x!G0,1!Gx!D0,1!D#!D#!Dx!D!D1!x,D0!x,D0!x,G0,1!Dq1q2q8q3q5q6q7qaccepterq4x!Dx!D#!DF