[PDF] Programmation dynamique - LRI Question 2 2 Donner l’

View - Download Programmation dynamique - LRI

Previous PDF

Next PDF

Complexite et Graphe 2014-2015

ENSTA Programmation dynamiqueExercice 1Triangle de Pascal

On veut calculer les coecients binomiauxCkn=n

k n!k!(nk)!. Rappellons les proprietes suivantes : |n k =n1 k1 +n1 k pour 0< k < n, n n = 1 etn 0 = 1. Question 1.1Donner un algorithme recursif du calcul den k . Evaluer sa complexite.Correction Fonctionbc(n;k)1.Si k= 0 ouk=nalors retourner 1;2.sinon retourner bc(n1;k1) +bc(n1;k):2

Question 1.2Ecrire l'algorithme qui retournen

k en utilisant la technique de la pro- grammation dynamique. Evaluer sa complexite.Correction

Principe de l'algorithme

1.

On rempli les kpremieres cases de chaque ligne de haut en bas.2.On s'arr ^ete ala ligne n3.T emps: T(n;k) =O(nk).1

Voici la procedure pour calculer

n

kSoitbc[n][n] le tableau qui stoque les coecients.1.p ouriallant de 1 anfairebc[i][0] = 1;2.p ouriallant de 1 anfairebc[i][i] = 1;3.p ouriallant de 1 anfaire(a)p ourjallant de 1 ajfairebc[i][j] =bc[i1][j1] +bc[i1][j];4.Retourner bc[n][k]2

Exercice 2Probleme du stockage

ConsideronsnprogrammesP1;P2;:::;Pnqui peuvent ^etre stocker sur un disque dur de capaciteDgigabytes. Chaque programme Pia besoinsigigabytes pour ^etre stocke et a une valeurvi T ousles programmes ne p euventpas ^ etresto ckessur le disque : nX i=1s i> D: Les programmes stockes dans le disque dur doivent maximiser la valeur totale, sans depasser la capacite du disque dur. L'objectif est de concevoir un algorithme qui permet de calculer un tel ensemble. Nous allons construire un tableauTdans lequel les lignes seront indexees par les programmes et les colonnes par les valeurs. L'elementT[i;j] representera la valeur maximale pour un disque dur de capaciteja l'aide desipremiers programmes. Question 2.1Donner la formule de recurrence.Correction

Soit OPT une solution optimale avec un disque dur de capaciteDet un ensemblePdenelements. NotonsT[i;j] la valeur maximale pour un disque dur de capaciteja l'aidedesipremiers objets.1.Si le nieme element appartient a la solution optimale, cela signie, que la solutionoptimale privee dunieme element est aussi une solution optimale avec un disque durde capaciteDsnet un ensemblePprive dunieme element.T[n;D] =vn+T[n1;Dsn]2.Si le nieme element n'appartient pas a la solution optimale, cela signie, que lasolution optimale OPT est aussi une solution optimale avec un disque dur de capacite

Det un ensemblePprive dunieme element.T[n;D] =T[n1;D]Donc par recurence on peut en deduire pour touti2 f1;:::;ngSij < vi, alorsT[i;j] =T[i1;j] sinonT[i;j] =max(T[i1;j];T[i1;jsi] +vi)On supposera que8j2 f1;:::;Dg, on aT[0;j] = 02

2 Question 2.2Donner l'algorithme utilisant la programmation dynamique.Correction Entree : un ensemble d'objectsP=f1;:::;ng. L'objetia une valeurviet un poidss i.Sortie : un entier 1.

In tialisert ousles elementsdu tableau Ta zero.2.P ourtout iallant de 1 an(a)P ourtout jallant de 1 aD2 (a).1 Sij < vi, alorsT[i;j] =T[i1;j]sinonT[i;j] =max(T[i1;j];T[i1;jsi] +vi)3.Retourner T[n;D]2

Question 2.3Donner la complexite de cet algorithme.Correction

La complexite de cet algorithme estO(nD) car1.l'initialisation du tableau se fait en O(nD) operations;2.L'instruction 2 ( a).1co ^uteO(1) operations. Et elle est executeenDfois.2

Remarque :Le probleme de stockage peut se formuler sous forme du probleme duSaca Dosqui est un probleme classique en informatique. Il modelise une situation analogue au remplissage d'un sac. Une personne veut remplir un sac a dos ne pouvant pas supporter plus d'un certain poidsD2N, et elle dispose denobjets (On note l'ensemble des objects par P=f1;:::;ng). Chaque objetia une valeurvi2Nnf0get un poidssi2Nnf0g. Le probleme est de trouver un ensemble d'objets tels que tous les ob jetsde cet ensem blepuissen t^ etremis dans le sac. la somme des v aleursde ces ob jetssoit maximale. Exercice 3ProblemeLe chemin le plus long dans un graphe SoitG= (V;E) un graphe oriente avecV=fv1;:::;vng. On dit queGest ordonne si il verie les deux proprietes suivantes : 1. Chaque arc de ce graphe est de la forme ( i!j) sii < j 2. T ousles som metssauf le sommet vnont au moins un arc sortant. Ici, par souci de simplication, nous supposerons qu'il existe un chemin allant deviversvn pour touti= 1;:::;n. L'objectif est de trouver le chemin le plus long entre les sommetsv1etvn. Question 3.1Montrer que l'algorithme glouton suivant ne resoud pas correctement le probleme. 3

1.u v1;

2.L 0;

3.

T antqu'il existe un arc sortan tdu sommet u

(a) c hoisirl'arc ( u!vj) tel quejest le plus petit possible (b)u vj; (c)L L+ 1; 4.

retourner LCorrection12435Le chemin retourne par l'algorithme estf1;2;5g. Le chemin le plus long estf1;3;4;5g2Question 3.2Donner la formule de recurrence qui permet de calculer la longueur du chemin

le plus long commencant parv1nissant parv`.Correction

Notonslong(v`) la longueur du plus long chemin dev1versv`.|Si il n'existe pas de c heminde v1versv`, alors par convention on supposera quelong(v`) =1.|Suppp osonsqu'il existe un c heminde v1versv`.Notonslong(v`) la longueur du pluslong chemin dev1versv`.|Si il n'existe pas d ec heminde v1versv`, alors par convention on supposera quelong(v`) =1.|Suppp osonsqu'il existe un c heminde v1versv`.SoitL=fv1;:::;v`gle chemin le plus long dev1versv`. Par denition dugraphe oriente ordonne, les sommets deLsont dansfvi: 1i`gNotonsvjle sommet deLvoisin dev`etL0le sous-chemin dev1versvj.Nous pouvons montrer queL0est le plus long chemin allant dev1nissant parv

jet que les sommets deL0sont dansfvi: 1ijglong(v`) =1 +maxflong(vi) :i2(v`)gsi `6= 1

0si `= 12

Question 3.3Donner un algorithme qui retourne la longueur du chemin le plus long com- mencant parv1nissant parvn.Correction

Soitlong:V!Nun tableau d'entiers tel quelong(vi) designe la longueur du plusgrand chemin dev1avi.Entree: un graphe oriente et ordonneGSortie: un entier4

1.long(v1) 0;// O(1) operations2.p ourtout iallant de 2 anfairelong(vi) 1;// O(n) operations3.p ourtout iallant de 1 anfaire// la boucle est executeeO(n)fois(a)p ourtout vj2+(vi) faire// la boucle est executeeO(n)foisi.si ( long(vi) + 1> long(vj) ) alorslong(vj) long(vi) + 1;4.retourner long(vn);Complexite :O(n2) operations.2

Question 3.4Modier l'algorithme precedent an qu'il retourne le chemin.Correction

SoitTun tableau ou chaque elementT[vI] correspond un chemin dev1avicorrespon-dant au chemin de plus grande la longueur.

Entree: un graphe oriente et ordonneGSortie: un chemin1.long(v1) 0;T[v1] fv1g;// O(1) operations2.p ourtout iallant de 2 anfaire// la boucle est executeeO(n)fois(a)long(vi) 1;// O(1) operations(b)T[vi] ;;// O(1) operations3.p ourtout iallant de 1 anfaire// la boucle est executeeO(n)fois(a)p ourtout vj2+(vi) faire// la boucle est executeeO(n)foisi.si ( long(vi) + 1> long(vj) ) alorslong(vj) long(vi) + 1;// O(1) operationsT[vj] T[vi][ fvjg;// O(n) operations au pire4.retourner T[vn];Complexite :O(n3) operations.2

Nous allons considerer les graphes orientes et ordonnes possedant une fonction de poidsw sur les arcsw:E!N+. L'objectif est de trouver le poids du chemin de poids maximal commencant parv1nissant parvn(si il n'en existe pas, la valeur retournee doit ^etre egale a1). Formellement, on veut trouverpmax=maxfP e2Pw(e) :Pest un chemin dev1avng Question 3.5Donner la formule de recurrence permettant de calculer le chemin de poids maximum commencant parv1nissant parvn.Correction

Notonspoids(v`) la longueur du plus long chemin dev1versv`.Si il n'existe pas de chemin dev1versv`, alors par convention on supposera quepoids(v`) =1.Suppposons qu'il existe un chemin dev1versv`. SoitL=fv1;:::;v`gle chemin depoids maximum dev1versv`. Par denition, par la denition du graphe oriente ordonne,5

les sommets deLsont dansfvi: 1i`gpoids(v`) =maxfpoids(vi) +w(vi;v`) :vi2(v`)gsi `6= 1

0si `= 12

Question 3.6En deduire l'algorithme.Correction

Soitlong:V!Nun tableau d'entiers tel quelong(vi) designe la longueur du plusgrand chemin dev1avi.Entree: un graphe oriente et ordonneGSortie: un entier1.long(v1) 0;// O(1) operations2.p ourtout iallant de 2 anfairelong(vi) 1;// O(n) operations3.p ourtout iallant de 1 anfaire// la boucle est executeeO(n)fois(a)p ourtout vj2+(vi) faire// la boucle est executeeO(n)foisi.si ( poids(vi)+w(vi;vj)> poids(vj) ) alorspoids(vj) poids(vi)+w(vi;vj);4.retourner poids(vn);Complexite :O(n2) operations.2

Maintenant, l'objectif est de trouver le poids du chemin de poids maximal commencant parv1 compose dekarcs. Nous utiliserons un tableauTdont la valeur de l'elementT[i;`] correspond au poids du chemin de poids maximal commencant parv1nissant parviet compose de` arcs. Question 3.7Donner la formule de recurrence qui permet de calculer le chemin de poids maximal de`arcs commencant parv1nissant parvi. En deduire l'algorithme.

Exercice 4Planning

Considerons un chef de projet qui doit gerer une equipe en lui aectant un projet qui dure une semaine. Le chef de projet doit choisir si il prend un projet stressantounon- stressant pour la semaine. 1. Si le c hefde pr ojetc hoisitle pro jetqui n'est pas stressantdurant la semainei, alors l'entreprise recoit un revenu`i. 2.

Si le c hefde pro jetc hoisitle pro jetqu iest

stressantdurant la semainei, alors l'entreprise recoit un revenuhiet l'equipe ne travaille pas durant la semainei1 Exemple : Si chef de projet choisit de se reposer a la semaine 1, puis de prendre le projet stressanta la semaine 2, puis de prendre les projetsnon-stressanta la semaine 3 et

4. Le revenu total est de 70 et il correspond au maximun.

semaine 1 semaine 2 semaine 3 semaine 4`10 1 10 10 h5 50 5 1 Question 4.1Montrer que l'algorithme suivant ne resoud pas correctement le probleme. 6

1.p ourc haqueit erationi= 1;:::;n

(a) si hi+1> `i+`i+1alors i.

Choisir

Ne pas travailler a la semaine i

ii.

Choisir

le projetstressanta la semaine i+1 iii.

Con tinuer al'it erationi+ 2

(b) sinon i.

Choisir

le projetnon-stressanta la semaine i ii.

Con tinuer al'it erationi+ 1

Question 4.2Donner un algorithme qui retourne le revenu maximal que peut obtenir le chef de projet.

Exercice 5Multiplications cha^nees de matrices.

On veut calculer le produit de matricesM=M1M2Mn. Multiplier une matricepq, par une matriceqren utilisant la methode standard necessitepqrproduit scalaire. Question 5.1Considerons 4 matricesA: 205,B: 5100,C: 1008,D: 530. On veut calculer le produitABCD. En fonction des parenthetisations, le nombre de produits varie. Determiner le nombre de produits pour calculerABCD, si on utilise les parenthetisations suivantes : ((AB)C)Dou (A(BC))DCorrection 1.

le pro duitde matrices utilisan tcet ordre (( AB)C)Dnecessite 30800 produits sca-laires, c'est-a-dire,

|AB: 205100 = 10000|(( AB)C) : 201008 = 16000|(( AB)C)D: 20830 = 48002.le pro duitde matrices utilisan tcet ord re( A(BC))Dnecessite 9600 produits scalaires,c'est-a-dire,

|BC: 51008 = 4000|(( A(BC)) : 2058 = 800|(( AB)C)D: 20830 = 48002 L'objectif est de concevoir un algorithme de meilleure parenthetisation qui permet de mini- miser le nombre de produits scalaires. Nous noterons que la matriceMiest de dimensiondi1di. Denissons le nombre minimal de produits scalaires necessaires pour evaluer le produit des matricesMiMi+1:::Mj1Mjparc(i;j). Question 5.2Ecrire une formule de recurrence pour calculerc(i;j).Correction

Supposons que la meilleure facon de parentheserMi:::Mjsoit (Mi::Mk)(Mk+1:::Mj).La matriceMi:::Mkest une matricedi1dketMk+1:::Mjest une matricedkdj. Le7

produit de ces deux matrices necessitedi1dkdjproduits scalaires. Au total, le nombre totalde produits scalaires pour calculerMiMi+1:::Mj1Mjestc(i;k) +c(k+ 1;j) +di1dkdj.On obtient

c(i;j) =minik0 sii=j:2 Question 5.3Ecrire un algorithme utilisant la programmation dynamiqueCorrection

Donnee :une suite de matricesM1:::Mnavec la matriceMide dimentiondi1di.1.initialiser tous les elementsde la matrice a1+2.p ouria 1 allantnfairec(i;i) = 0;3.p our`a 1 allantnfaire(a)p ouria 1 allantn`fairei.p ourka 1 allant`fairec(i;i+`) = min(c(i;i+`);c(i;i+k)+c(i+k+1;i+`)+di1di+kdi+`);2

8quotesdbs_dbs6.pdfusesText_11

[PDF] exercices corrigés programmation linéaire méthode du simplexe

[PDF] exercices corrigés programmation matlab pdf

[PDF] exercices corrigés proportionnalité 4ème pdf

[PDF] exercices corrigés propriétés colligatives

[PDF] exercices corrigés propriétés mécaniques des matériaux pdf

[PDF] exercices corrigés rapidité de modulation

[PDF] exercices corrigés rapprochement bancaire pdf

[PDF] exercices corrigés résistance des matériaux

[PDF] exercices corrigés sage comptabilité

[PDF] exercices corrigés sage saari comptabilité 100

[PDF] exercices corrigés saponification

[PDF] exercices corrigés sciences industrielles mpsi pdf

[PDF] exercices corrigés sciences industrielles pcsi pdf

[PDF] exercices corrigés servlets java

[PDF] exercices corrigés soncas