Correction de lExamen Final PDF Complexité algorithmique 2010-2011. P.

Exercices avec Solutions

Exercices Corrigés d'Algorithmique – 1ére Année MI 5. EXERCICE 1. Ecrire un algorithme qui demande 1- Calcul de la somme des N premiers nombres entiers.

Exercices Corrigés Matrices Exercice 1 – Considérons les matrices

Puis calculer A-1. Exercice 8 – Appliquer avec précision aux matrices M et N suivantes l'algorithme du cours qui détermine si une matrice est inversible et

Langage C : énoncé et corrigé des exercices IUP GéniE

Exercice 1 1 Ecrire un progra mm e dans l e q ue l vous : 1. Déc l arere z un entier i et un pointeur vers un entier p

Exercices corrigés

Les scripts du cours. Cours no 1 : « Premiers pas en Python ». 1. Affectez les variables temps et distance par les valeurs 6.892 et 19.7.

ALGORITHME SECONDE Exercice 5.1 Ecrire un algorithme qui

Exercice 5.1. Ecrire un algorithme qui demande à l'utilisateur un nombre compris entre 1 et 3 jusqu'à ce que la réponse convienne. corrigé - retour au cours.

Algorithmique — M1 - Examen du 11/1/11 -corrigé

11 janv. 2011 Examen du 11/1/11 -corrigé. Université Paris Diderot. On applique un algorithme de cours. Exercice 1 – Routage.

Correction de lExamen Final

Complexité algorithmique 2010-2011. P. Baillot. B. Grenet. Correction de l'Examen Final. Exercice 1. Pour les définitions

Algorithmique — M1 - Examen du 11 janvier 2010

11 janv. 2010 Examen du 11 janvier 2010. Corrigé. On applique un algorithme de cours. Exercice 1 – Flux maximum. Pour le réseau ci-dessus on cherche à ...

Examen du 18 janvier 2008 - corrigé - version ?2

18 janv. 2008 Exercice 1 – Arbre couvrant minimum ... un algorithme de cours. 1. Choisissez un algorithme (écrivez juste son nom s'il s'agit d'un ...

Examen dalgorithmique géométrique

Examen. M1 Info M1 Math-Info. - Examen d'algorithmique géométrique -. - Corrigé rapide -. Barême : Exercice 1 sur 8 points : 1) 0.5pts - 2) 1pt - 3) 1pt

Master IF, ENS Lyon. Complexité algorithmique,2010-2011. P. Baillot. B. Grenet

Correction de l"Examen Final

Exercice1.

Pour les définitions, voir le cours.

Les inclusions sont :

PZPPRPBPPEXP,

RPNPEXP.

(par contre on ne sait pas comparerBPPetNP)

Pour lesexercices2et3se référer au cours.

Exercice4.

On va définir des machines à partir deMdépendant d"un paramètre entierk, puis choisir une valeur dekgarantissant la propriété demandée. Pourk1 on définit ainsi la machine probabilisteMk, qui, sur l"entréex: initialise un compteur à la v aleurket une variablebà0, tant que le compteur est dif férentde 0: ef fectueune nouv elleexécution de Msur l"entréex; si cette exécution accepte, alors b:=1; décr émentele compteur ; si b=1 alors la machine accepte, sinon elle rejette. AinsiMkeffectuekexécutions indépendantes deMet accepte ssi l"une de ces exécutions accepte.

On a alors :

si x/2L, alorsPr[Mk(x) =1] =0, carPr[M(x) =1] =0. si x2L, alorsPr[Mk(x) =0] =Pr[E1^E2^ ^Ek], oùEidésigne l"événement "lai-ème exécution deMrejette", pour 1ik. Or, comme les exécutions deMsont indépendantes, on a :

Pr[E1^E2^ ^Ek] =Pki=1Pr[Ei],

etPr[Ei](1nc), pour 1ik. Donc :

Pr[Mk(x) =0](1nc)k.

On veut donc choisirkde telle sorte que :(1nc)k2nd. Il nous suffit pour cela d"avoir : log((1nc)k)log(2nd), soitk nd/log(1nc). On peut donc prendreM0=Mkavec unksatisfaisant cette condition.

Exercice5.

1.Montrons queFCappartient àNL.

On considère la machine non déterministeMsuivante : sur l"entréeG, (on notemle nombre de sommets de ce graphe orienté) 1 -pour chaque sommet v1deG, pour chaque sommetv26=v1deG, on initialise un compteur à xmy, -v:=v1, (*) on choisit non déter ministiquementun sommet wdeGtel que(v,w)est une arête, on décr émentele compteur , si w6=v2alors {si le compteur est à0on rejette, sinonv:=wet on retourne à (*)} % à ce point on a trouvé un chemin dev1àv2 on passe auv2suivant on passe auv1suivant on accepte.

On a :

Si Gest fortement connexe, alors : pour tous sommetsv16=v2deG, il existe un chemin de longeur inférieure ou égale àmdev1àv2, donc une des exécutions deMaccepte G; Si Gn"est pas fortement connexe, alors : il existe deux sommetsv16=v2deGtels qu"il n"y a pas de chemin de longueur inférieure ou égale àmdev1àv2, donc aucune exécution deMn"accepteG. Donc la machine non-déterministeMdécide bien le langageFC. De plus cette machine n"utilise que5variables (v1,v2,v,w, le compteur) contenant des mots de longueur inférieure ou égale à logm. DoncMfonctionne en espace logarith- mique par rapport à la taille de l"entréeG. DoncFCappartient àNL.

2.Montrons queFCestNL-dur.

On sait que le langagePATHestNL-complet. On va donc essayer de donner une réduc- tion logspace dePATHàFC. On considère pour cela la fonctionfsuivante sur les mots def0,1g: si xn"est pas de la formeavecGest un graphe orienté ets,tdeux sommets deG, alorsf(x) =x0constant qui n"est pas de la formepourG0un graphe orienté, si x=pourGun graphe orienté ets,tdeux sommets deG, alors : f(x) =, oùG0est le graphe obtenu à partir deGen : ajoutant pour chaque sommet v6=sune arête devàs, ajoutant pour chaque sommet v6=s,tune arête detàv.

Alors on a :

Si 2PATH:

il existe un chemingdesàtdansG, donc aussi dansG0. Considérons alorsv16=v2 deux sommets deG0. Siv16=setv26=ton a : une arête dev1às, un chemingdesà t, une arête detàv2. Donc il existe dansG0un chemin dev1àv2. Les cas oùv1=sou v

2=tsont similaires. DoncG02FC.

Si /2PATH:

supposons qu"on ait dansG0un cheming0desàt. Quitte à le raccourcir on peut supposer qu"il ne visite qu"une seule foissett, donc il n"utilise aucune des "nouvelles" arêtes deG0, donc c"est aussi un chemin deG. Ceci contredit le fait que/2 PATH. Donc il n"existe pas de chemin desàtdansG0, doncG0/2FC.

On a donc bien :f(x)2FCssix2PATH.

De plus la fonctionfpeut être calculée en espace logarithmique, car il suffit pour cela d"effectuer un parcours des sommets deG, en gardant en mémoire le sommetvcourant (de taille logm, oùmest le nombre de sommets deG). 2 DoncPATHLFC. On en déduit ainsi queFCestNL-dur, et d"après la question précé- dente il estNL-complet.

Exercice6.

1.Supposons queE6=ESPACE. AlorsE(ESPACEdonc il existe un langageLdansESPACE

qui n"est pas dansE. Soitc>0 tel queL2SPACE(2cn). Considérons le langage L pad:=fhx,12cjxji:x2Lg. AlorsLpad2PSPACE. En effet, pour décider si un mot quelconqueyappartient àLpad, on décode d"abordyenhx,12cjxji(siyn"est pas de cette forme, on rejette). On applique ensuite àxl"algorithme témoin de l"appartenance deLàSPACE(2cn)et on accepte si et seulementx2L. L"espace utilisé est alors au plus 2cjxj, qui est bien polynomial en la taille dey=hx,12cjxji. Montrons maintenant queLpad/2P, par contraposée. Supposons qu"il existe un algorithmeAdécidantLpaden tempsndpour un certaind>0. L"algorithme suivant décideLen temps exponentiel : sur l"entréex, on calculehx,12cjxji(ce qui prend essentiellement le temps d"écrire le couple, donc un temps exponentiel). Puis on applique

Aau couple obtenu, et on accepte si et seulement siAaccepte. Le temps de calcul esthx,12cjxjid=O(2cjxjd) =O(2cdjxj). Ainsi,L2Ece qui est absurde.

2.On utilise ici aussi la technique dupadding, mais de manière plus délicate. Le langage de

padding utilisé est unaire. SoitLle même langage qu"à la question précédente, etLunle langage défini par L un:=f11x:x2Lg où 1xest le mot obtenu en ajoutant un 1 devant le motx, et est vu comme un entier bi- naire. Le langageLunest dansPSPACE: sur l"entréeyconstituée uniquement de 1 (sinon on rejette), on calculextel quey=11x(ce qui se fait aisément en espace polynomial), puis on utilise l"algorithme qui témoigne de l"appartenance deLàESPACE. L"espace uti- lisé est exponentiel enjxj, donc polynomial enj11xj=1x. Il est également dansP/poly

grâce à l"indication. Pour la même raison qu"à la question précédente,Lunne peut pas

être dansP.

3.(a) On veut montrer queLp

TU, c"est-à-dire que le langageLpeut être décidé en temps polynomial par une machine de Turing avec oracleU. Pour toutn, notonsa(n)la taille du conseilan(a(n)est par définition un polynôme enn). Pour déciderLen temps polynomial grâce à l"oracleU, on utilise l"algorithme suivant : sur une entréexde longueurn, on teste pour toutia(n)lequel de 1hn,i,0iou 1hn,i,1iappartient àU. Une fois cette boucle effectuée pour toutia(n)(donc un nombre polynomial de fois), on connaît le conseilan. On peut alors exécuter la machineMen se servant du conseil a n, et elle permet de décider en temps polynomial sixappartient àL. (b)SoitMla machine qui décideLen temps polynomial avec conseil(an)n, etNla machine qui décideLen espace polynomial. Notons toujoursa(n)la longueur du conseilan. On énumère dans l"ordre lexicographique tous les motsbde longueur a(n). Pour chacun de ces mots, on énumère tous les motsxde longueurn. On lance en parallèle les machinesMavec le conseilbetNsur l"entréex. Si les deux sont d"accord, on passe au motxsuivant. Sinon, on arrête l"énumération desx, et on passe 3 au motbsuivant. Si pour un motb, les deux machines s"accordent sur tous les mots de longueurn, on posebn=b. Pour les deux énumérations imbriquées, on n"a à chaque fois besoin de retenir que les motsbetxcourants. De plus, exécuterMse faisant en temps poynomial, cela prend un espace au plus polynomial. Enfin, exécuterNprend par définition un espace au plus polynomial. Ainsi, l"algorithme proposé utilise un espace au plus polynomial en n. (c)On peut montrer qu"une variante du langageUde la question3(a)vérifie les condi- tions requises. On considère U

0=f1hn,i,bn,ii:bn,iest lei-ème bit debng,

où(bn)nest la famille définie à la question3(b). On peut déciderLen temps polyno- mial avec oracleU0(Lp TU0) avec le même algorithme qu"à la question3(a)puisque qu"en temps qu"oracle pourL,U0se comporte par définition de la même façon queU. De plus,U0est bien décidable en espace polynomial : sur une entrée 1t, on décompose tenhn,i,bi(oùbest un unique bit). On calcule ensuitebnen espace polynomial enn (et donc enj1tj), puis on teste si lei-ème bit debnestb. (d)En utilisant la clôture dePpar réduction Cook-Turing1, on peut conclure : siU0 appartenait àP, alors ce serait le cas deL, ce qui n"est pas. (e)Les questions précédentes prouvent que siP6=PSPACE\P/poly, alors il existe un langage unaireU0dansPSPACEnP. Considérons le langage U bin:=fx: 11x2U0g. Ce langage appartient àESPACE: il suffit sur l"entréexde calculer 11xpuis de tester l"appartenance de 1

1xàU0. De même, il n"appartient pas àEcarU0/2P. DoncE6=

ESPACE.

4.Par le théorème de Sipser et Gács, on sait queBPPSP2\PP2. Donc par définition

BPPPH. Mais commePHPSPACE,BPPPSPACE.

5.Le théorème d"Adelman nous apprend queBPPP/poly. Ainsi, avec la question

précédente,BPPPSPACE\P/poly. CommePBPP, alorsP6=BPPimplique

P6=PSPACE\P/poly. D"oùE6=ESPACEgrâce à la question3.1. Également appeléeréduction par oracle.

4quotesdbs_dbs46.pdfusesText_46

[PDF] Correction de lExamen Final Complexité algorithmique 2010-2011. P.