[PDF] Examen Final Corrigé rédigé par Paul Brunet et Laure Gonnord 1

View - Download Examen Final Corrigé rédigé par Paul Brunet et Laure Gonnord 1

Previous PDF

Next PDF

Master Info - 2015-2016

MIF15 Complexite et Calculabilite

Examen Final

Corrige redige par Paul Brunet et Laure Gonnord

Duree 1H30

Notes de cours et de TD autorisees. Livres et appareils electroniques interdits.

Le bareme est donne a titreindicatif.

1 Machines de Turing

Question 1(4 points)

Construisez une machine de Turing deterministe acceptant le langageLdes palindromes surfa;bg, deni parL=fw2 fa;bgjw=wR, ouwRest le mot miroir dew).

Vous ecrirez une machine de Turing :

A un seul ruban inni a droite, le marqueur delimitant le mot d'entree etant #, la t^ete de lecture initialement positionnee sur le premier blanc a gauche dew. Qui decideL (avec donc un etat d'acceptation et un etat de refus). Votre machine de Turing viendra avec desEXPLICATIONSet unEXEMPLE. Soi- gnez le dessin et la redaction!Solution: 01423

2'3'OUINON#=#=!a=#=!b=#=!#=#=!#=#= #=#= b=#= a=#= #=#= #=#= a=#= b=#= #=#= a=a=!

b=b=!a=a=! b=b=!a=a= b=b= MIF15 Complexite et Calculabilite, Master Info - 2015-2016 1/7

2 Fonctions primitives recursives

Denition.Une fonctionf:Nn!N(avecn0) estrecursive primitivesi elle est : Une des fonctions ren voyant0 : zeron: (x1:::xn)7!0. La fonction constantezero0: ()7!0 sera par abus de notation souvent notee 0. |succ:x7!x+ 1 la fonction successeur (alorsn= 1); |idin: (x1;:::;xn)7!xiles fonctions de projection, pour 1in; et stable par les operations de base : |Compn(g;h1;:::;hm) : (x1;:::;xn)7!g(h1(x1;:::;xn);:::;hm(x1;:::;xn)) la composi- tion. Notons quendesigne ici l'arite de la fonction obtenue (le nombre d'arguments, qui peut ^etre 0), etmdesigne l'arite de la fonctiong. Le casm= 0 permet de construire des fonctions avecgd'arite 0. |Rec(g;h) la fonction denie par recurrence (a droite) comme f(x1;:::;xn1;0) =g(x1;:::;xn1);

f(x1;:::;xn1;m+ 1) =h(x1;:::;xn1;m;f(x1;:::;xn1;m));MIF15 Complexite et Calculabilite, Master Info - 2015-2016 2/7

Question 2(3 points)

La fonctionSommeDiviseursest denie de la facon suivante : sin2N, alorsSommeDiviseurs(n) renvoie la somme des diviseurs entiers positifs den(nnon compris).

Par exempleSommeDiviseurs(6) = 1 + 2 + 3 = 6.

Montrez queSommeDiviseursest primitive recursive.

On pourra denir une fonction auxiliaire avec un argument de plus. On pourra egalement utiliser la fonctionmodulo(n;m)7!n[m](ounmodm) supposee primitive recursive, et une denition par casite(x;y;b) =if(b >0)thenxelseysupposee aussi primitive recursive.Solution: On peut denirsommebis(n;i) qui fait la somme des diviseurs denjusqu'ai. On a assez facilement : |sommebis(n;0) = 0 |sommebis(n;i+ 1) =sommebis(n;i) +( i+ 1 simodulo(n;i+ 1)>0

0sinon

Il resterait a recoller les morceaux.

Question 3(3 points)

Soitgune fonction recursive primitive.

Soitfla fonction denie parf(0;x) =g(x) etf(n+ 1;x) =f(n;f(n;x)).

Montrez que f est recursive primitive.

On commencera par prouver proprement quef: (n;x)7!g2n(x), et on pourra utiliser sans preuve le fait que la fonction2puis:n7!2n, est recursive primitive.Solution: La premiere chose a faire est de prouver une specication alternative def:

8n2N;f(n;x) =g2n(x):

Ce resultat se prouve aisement par recurrence :

|f(0;x) =g(x) =g20(x); |f(n+ 1;x) =f(n;f(n;x)) en appliquant deux fois l'hypothese de recurrence, on obtientf(n+ 1;x) =g2n(g2n(x)) =g2n+1(x). On va donc commencer par denir par recurrence une fonctionhtelle queh(x;n) =gn(x). |h(x;0) =x=id11(x); |h(x;n+ 1) =g(h(x;n)) =Comp3(g;id33)(x;n;h(x;n)).

Donc on peut denirhpar :

h :=Rec(id11;Comp3(g;id33)): Avechet2puison peut nalement ecriref(n;x) =h(x;2puis(n)), soit : f

:=Comp2(Rec(id11;Comp3(g;id33));id22;Comp2(2puis;id12))MIF15 Complexite et Calculabilite, Master Info - 2015-2016 3/7

3 Indecidabilite

Question 4(2 points)

Montrez, par reduction a partir du probleme de l'arr^et, que le probleme suivant est indecidable : entree :une machine de TuringMqui s'arr^ete sur toutes les donnees. question :L(M) est-il inni?Solution: Soit< M;w >une instance du probleme de l'arr^et. On construitM0comme suit : |M0prend en entree un compteur c. Si Ms'arr^ete en moins decetapes,M0accepte, sinon elle rejette. M

0acceptecssi M s'arr^ete en moins decetapes surw.L(M0) =fc2Ntels quec

longueur du calcul de M surwgest donc inni ssiMs'arr^ete surw.

4 Probleme : NP-completude

Le problemeCliqueconsiste a etablir si un grapheGdonne contient une clique de cardinal egal a un entier donnek. Un grapheGest deni par la donnee de son ensemble de sommetsV et de l'ensemble de ses ar^etesEVV. Le cardinal d'un graphe est son nombre de sommets. Un ensembleCVde sommets deGest unecliquesi tous ces sommets sont relies entre eux dansG, c'est a dire :

8u;v2C;u6=v)(u;v)2E:

Question 5(1 point)

Donnez un exemple de graphe contenant une clique de cardinal quatre.Solution: On poseG= (V;E) avecV=f0;1;2;3getE=VV. Il est trivial de verier queV lui-m^eme est une clique de cardinal quatre dansG.01 23
MIF15 Complexite et Calculabilite, Master Info - 2015-2016 4/7 Le problemeCliques'enonce de la maniere suivante :

Clique :

entree :un grapheG= (V;E) et un entierk question :existe-t-il une cliqueCdansGde cardinal egal ak? Nous allons monter que ce probleme est NP-complet, en le reduisant depuisSat. Pour cela nous allons suivre une preuve proposee par Richard Karp en 1972. SoitFune formule en forme normale conjonctive. On denit le grapheGF= (VF;EF) comme suit : les sommets de ce graphe son tles paires ( `;c), oucest une clause deFet`est un litteral (c'est a dire une variable ou sa negation) qui appara^t dansc; les somme ts( `;c) et (`0;c0) sont relies dans le graphe si et seulement sic6=c0et`n'est pas la negation de`0. Par exemple siF=c1^c2^c3avecc1= (x_y),c2= (:x_ :y) etc3= (:x_y),GFest le graphe suivant :x;c 1y;c

1:x;c2:y;c2:x;c3y;c

3Question 6(3 points)

Montrez que siFest constituee denclauses, alorsFest satisable si et seulement si G Fcontient une clique de cardinaln.On prouvera soigneusement les deux implications en construisant une clique dans un sens, et une interpretation des formules dans un autre.Solution: SiFest satisable, soitIun modele deF. Pour chaque clauseckdeF, il y a au moins un litteral`(ck) danscktel que [`(ck)]I= 1. Considerons un tel ensembleCI=f(`(ck);ck)g. Fanclauses, donc le cardinal deCIvautn. De plus, si (`;c) et (`0;c0) sont deux elements dierents deCI, alorsc6=c0et comme [`]I= [`0]I= 1,`et`0ne sont pas la negation l'un de l'autre. Donc ((`;c);(`0;c0))2EF.CIest donc une clique de cardinalndansGF. Supposons au contraire qu'on a une cliqueCVFde cardinaln. On peut denir une interpretationICde la maniere suivante : I

C(p) =8

:1 si (p;c)2C;pour une certaine clausec

0 si (:p;c)2C;pour une certaine clausec

0 sinon

CommeCest une clique, pour tous (`;c) et (`0;c0) dierents dansCces deux sommets sont relies dansGF, ce qui implique en particulier quecetc0sont des clauses dierentes. Comme de plus le cardinal deCest egal au nombre de clauses deF, on en deduit que pour chaque clausecdeFil y a un litteral`tel que (`;c)2C. Par denition deIC, on a [`]IC= 1. Par consequent commeICvalide au moins un litteral dans chaque clause deF, [F]IC= 1, ce qui signie queFest satisable. Question 7(2 points)MIF15 Complexite et Calculabilite, Master Info - 2015-2016 5/7 On denit la taillejFjd'une formuleFpar le nombre de litteraux qui la constituent (dans l'exemple ci-dessus,jFj= 6), et la taillejGjd'un graphe comme la somme de son cardinal (nombre de sommets) et de son nombre d'ar^etes.

BornezjGFjpar un polyn^ome enjFj

(c'est-a-dire trouvez un polyn^omeptel quejGFj6p(jFj)).Solution: D'apres la denition deGF, on voit que chaque litteral deFdonne lieu a au plus un sommet dansVF. On en deduit que le cardinal deVFest inferieur ajFj. De plus, le nombre d'ar^etes etant borne par le carre du nombre de sommets, on a : jGFj=jVFj+jEFj6jVFj+jVFj26jFj+jFj2:

Question 8(2 points)

En utilisant les resultats precedents, prouvez queCliqueest NP-complet.Solution: On commence par montrer queCliqueest NP-dur. Pour cela on donne une reduction polynomiale depuisSat. Soitla fonction qui a une formuleFen forme normale conjonc- tive associe (GF;n), avecnle nombre de clauses deF. D'apres la question 7, on sait que G Fest de taille polynomiale par rapport a la taille deF, et il est evident a partir de la denition deGFque la construction de ce graphe est lineaire en sa taille. Le calcul den ne pose pas plus de probleme. Doncest une fonction P. D'apres la question 6, on sait que :

F2Sat,(F) = (GF;n)2Clique:

Par consequent,est bien une reduction polynomiale deSataClique, et commeSat est NP-complet,Cliqueest NP-dur. Il faut encore montrer queCliqueappartient bien a la classe NP. Considerons l'algorithme non deterministe suivant : input: Un grapheG= (V;E) et un entiern output: Un booleen, indiquant siGpossede une clique de taillen. N 0; C ;; pourv2Vfairechoix entre

C C[ fvg;

N N+ 1;

oune rien faire; nchoix npour nsi npour retourner(vrai); sinonretourner(faux); nsiMIF15 Complexite et Calculabilite, Master Info - 2015-2016 6/7 Cet algorithme calcule de maniere non-deterministe (\devine") une clique , puis verie que c'est bien une clique de taillen. Il s'execute en temps polynomial par rapport ajGj.

Par consequent on a etabli queCliqueest bien dans la classe NP.MIF15 Complexite et Calculabilite, Master Info - 2015-2016 7/7

quotesdbs_dbs45.pdfusesText_45

[PDF] fonction calculable

[PDF] langage récursif

[PDF] épaisseur atmosphère saturne

[PDF] fonction primitive récursive exercice corrigé

[PDF] théorème de godel démonstration

[PDF] codage de godel

[PDF] théorème de gödel pdf

[PDF] arithmétique de robinson

[PDF] nombre de godel

[PDF] godel dieu

[PDF] théorème d'incomplétude pour les nuls

[PDF] incomplétude définition

[PDF] introduction ? la calculabilité pdf

[PDF] indemnité prof principal 2017

[PDF] isoe prof principal