Mitica Craus - Proiectarea Algoritmilor

7/25/2019 Mitica Craus - Proiectarea Algoritmilor

1/74

Mitic!Craus

Proiectarea Algoritmilor

Autorul cere scuze pentru eventualele gre!eli ce pot apare n text


2/74


_____________________________________________________________________________________

_______________________________________________________________________________2

CuprinsCOMPLEXITATEA ALGORITMILOR........................................................................................................................... 5

M!surarea complexit!"ii...................................................... ............................................................ ........................................... 5Clase de complexitate ......................................................... ............................................................ ........................................... 5

Teze....................................................... ............................................................ ........................................................... .............. 6Complexitatea algoritmilor secventiali.................................................... ........................................................... ........................ 7

METODE DE PROIECTARE A ALGORITMILOR ORIENTATE PE PROBLEM".....................................................##

PROBLEMA C"UT"RII..............................................................................................................................................#2C!utarea secven"ial!................................................................................................................................................................. #2C!utarea binar! ........................................................................................................................................................................ #3Arbori binari de c!utare ........................................................................................................................................................... #4Pattern Matching...................................................................................................................................................................... #5

PROBLEMA SORT"RII..............................................................................................................................................#7Bubble Sort (sortare prin interschimbare)................................................................................................................................ #7Insertion Sort (sortare prin inserare) ........................................................................................................................................ #7Shell Sort (sortare prin metoda Shell) ...................................................................................................................................... #8Radix Sort ................................................................................................................................................................................ #9Heap_Sort ....................................................... ............................................................ ....................................................... ...... 20Merge_Sort $i Quick_Sort ............................................................ ............................................................ ............................... 24

METODE GENERALE DE PROIECTARE A ALGORITMILOR .................................................................................26

METODA DIVIDE-AND-CONQUER (DIVIDE-ET-IMPERA).......................................................................................28

Descrierea metodei....................................................... ............................................................ ................................................... 28

Modelul metodei........................................................... ............................................................ ................................................... 28

Eficien"a metodei.......................................................... ............................................................ ................................................... 28

Modelul metodei pentru cazul arborelui binar de recursie: .................................................... .............................................. 30

Studii de caz ....................................................... ............................................................ ....................................................... ...... 30

Sortarea prin prin interclasare ....................................................... ............................................................ ............................... 30Sortarea rapida (C.A.R. Hoare)..................................................... ........................................................... ................................ 32

METODA GREEDY.....................................................................................................................................................36

Descrierea metodei....................................................... ............................................................ ................................................... 36

Modelul metodei........................................................... ............................................................ ................................................... 36

Eficien"a metodei.......................................................... ............................................................ ................................................... 37

Studii de caz ....................................................... ............................................................ ....................................................... ...... 37

Interclasare optimala ........................................................... ............................................................ ......................................... 37Compresiile de date. Arbori Huffman..................................................... ........................................................... ...................... 40Drum minim ntr-un graf ( surs - destinatie ) .................................................. ............................................................ ............ 42

Problema rucsacului (Knapsack)............................................................ ........................................................... ...................... 43

PROGRAMAREA DINAMIC.....................................................................................................................................46


3/74


_____________________________________________________________________________________

_______________________________________________________________________________ 3

Descrierea metodei ......................................................................................................................................................................46

Modelul metodei..........................................................................................................................................................................48

Eficien"a metodei.........................................................................................................................................................................49

Comparatie intre metoda program!rii dinamice si metoda greedy........................................................................................49

Studii de caz.................................................................................................................................................................................50

Problema rucsacului (0/#) ........................................................................................................................................................50Inmultire optim de matrici ......................................................................................................................................................52Arbori binari de cautare optimali .............................................................................................................................................53

METODA BACKTRACKING...................................................................................................................................... 57

Descrierea Metodei .....................................................................................................................................................................57

Spatiul solutiilor. Restrictii......................................................................................................................................................57Backtracking si Branch-and-Bound.........................................................................................................................................59

Modelul metodei..........................................................................................................................................................................60

Studii de caz............................................................ ............................................................ ......................................................... 6#Problema celor 8 dame.............................................................................................................................................................6 #Submul"imi de sum!dat! .........................................................................................................................................................62

METODA BRANCH AND BOUND......................................................................................................................... 65

Descrierea metodei ......................................................................................................................................................................65

Branch and Bound (BB) cu strategie cost minim (LC) ............................................................................................................69

Modelul metodei pentru strategia LC.......................................................................................................................................69

M!rginire.....................................................................................................................................................................................70

Modelul metodei pentru strategia LC cu m!rginire..................................................................................................................70Problema 0/#a rucsacului ( 0/#knapsack ) .............................................................................................................................7 #Algoritmul BB_LC pentru problema 0/#a rucsacului:.............................................................................................................73


4/74


_____________________________________________________________________________________

_______________________________________________________________________________4


5/74


_____________________________________________________________________________________

_______________________________________________________________________________ 5

Complexitatea algoritmilor

Teoria complexit!tii are ca obiect de studiu clasificarea problemelor, bazat!pe timpul de executie si spatiul de lucruutilizat de algoritmi pentru solutionarea lor. Cnd se analizeaz!algoritmi paraleli, se poate lua n considerare si num!rul de

procesoare.Desi teoria complexit!tii a fost dezvoltat!pentru probleme de decizie, aceasta nu este o restrictie sever!deoarece multe

alte probleme pot fi formulate n termeni de probleme de decizie. De exemplu o problem!de optimizare poate fi rezolvat!prin punerea ntreb!rii existentei unei solutii cu cel mult sau cel putin o valoare specificat!.

M!surarea complexit!"ii

Complexitatea timpului de executie a unui algoritm paralel care rezolv!o instant!de dimensiune na unei probleme, peo masin!paralel!cupprocesoare (p=dimensiunea masinii) se noteaz!a cu T(p,n)=Tp(n).

O problem! se numeste dependent! de dimensiunea masinii (PDD) dac! n este o functie de variabil!p. Altfel,problema se numeste independent!de dimensiunea masinii (PID).Un algoritm dependent de dimensiunea masiniieste unalgoritm ce rezolv!o problem!PDD.altfel, algoritmul se numesteindependent de dimensiunea masinii.

Factorul de nc!rcare (L) a unei probleme este raportul n/p. Viteza Sp(n)) unui algoritm paralel este raportulT"(n)/Tp(n).Eficienta (Ep(n))unui algoritm paralel se defineste ca fiind raportul dintre vitez!si num!rul procesoarelor:

Ep(n)=Sp(n)/p=T"(n)/[pTp(n)].Pentru a aprecia comportarea asimtotic!a functieiTp(n)se utilizeaz!urm!toarele notiuni:Fiind date dou!functiifsigpozitive de variabilepsi nse noteaz!: o(g)={f/()>0,[{p0,n0(p)}N] a.i.()[(p>p0)(n>n0(p))]: f(p,n)p0) )(n>n0(p))]: f(p,n)


6/74


_____________________________________________________________________________________

_______________________________________________________________________________6

O alt!clas!inclus!nPspace, neinteresant!din punct de vedere al calculului secvential, dar important!pentru calcululparalel este Polylogspace.Aici snt incluse problemele rezolvabile n spatiu polilogaritmic (spatiul de lucru este m!rginit deun polinom de variabil!"log(dimensiunea problemei)"). Multe probleme din Papartin lui Polylogspace,dar n general, secrede c!P Polylogspace.Se stie totusi c!Polylogspace####Pspace .

Remarcabile n Pspace si NP snt problemele complete.Problemele Pspace-complete snt generaliz!ri ale tuturorcelorlalte probleme din Pspace n termeni de transform!ri care necesit! timp polinomial. Mai precis: o problem! estePspace-complet!sub transform!ri de timp polinomial dac!apartine lui Pspacesi oricare alt! problem!din Pspace estereductibil!la ea prin transform!ri care necesit!timp polinomial. Urmeaz!c!dac!o problem!Pspace-complet!ar apartinelui Patunci Pspace = P.Deoarece se crede c!aceasta egalitate nu este adev!rat!, este improbabil s!existe un algoritm detimp polinomial pentru o problem!Pspace-complet!. ProblemeleNPse definesc n mod asem!n!tor, rezultnd aceleasiconcluzii.

Clasa Pare si ea problemele ei complete. Problemele P-completesnt generaliz!ri ale tuturor celorlalte probleme dinclasa P, n termenii transform!rilor care necesit! spatiu de lucru logaritmic. Formal, o problem! este P-complet! subtransform!ri spatiale logaritmice dac!apartine clasei Psi orice alt!problem!din Peste reductibil!la ea prin transform!rice utilizeaz! spatiu logaritmic. Dac! o problem! P-completa ar apartine clasei Polylogspace, atunci ar fi adev!rat!

incluziunea P Polylogspace. Cum aceast!incluziune se presupune a fi fals!, nu este de asteptat s!existe un algoritmpentru o problem!P-complet!care s!utilizeze spatiu de lucru polilogaritmic.

Teze

Relatia ntre calculul secvential si paralel este dat!de teza calculului paralel (Chandra, Kozen & Stockmeyer, "98";Goldshlager, "982): pentru orice functie T(n), (n= dimensiunea problemei), clasa problemelor solvabile de o masin !cu

paralelism nem!rginit n timp T(n)O(")(polinomial n T(n) ) este egal!cu clasa problemelor solvabile de masini secventiale

cu spatiu (T(n))O(")

.

Aceast! tez! este o teorem! pentru multe dintre modelele relativ rezonabile. Astfel, clasa problemelor solvabile nT(n)

O(")timp de o masin!PRAMeste egal!cu clasa problemelor solvabile cu T(n)O(")spatiu de lucru de o masin!Turing,dac!T(n)log n(Fortune & Wyllie, "978). In consecint!, clasa problemelor solvabile de o masin!PRAM n timp paralel

polinimial este egal!cu clasa Pspace.De asemenea, Polylogspaceeste clasa problemelor solvabile de o masin!PRAM ntimp paralel polilogaritmic.

Problemele din PPolylogspacesnt solvabile n timp paralel polilogaritmic. Ele pot fi considerate cele mai usoareprobleme din P, n sensul c! influenta dimensiunii problemei asupra timpului de rezolvare a fost redus! la minimum. Oreducere ulterioar!a a timpului de solutionare la dimensiuni sublogaritmice este, n general, imposibil !. Una din ratiunileacestei afirmatii este aceea c!o masin!PRAMnecesit!O(log n)timp pentru activarea a n procesoare.

Pe de alt!parte, este improbabil ca problemele P-completes!admit!solutii n timp polilogaritmic. Dac!o astfel deproblem!ar fi rezolvabila n timp paralel polilogaritmic ar urma c!apartine clasei Polylogspacesi astfel ar fi adev!rat!incluziunea PPolylogspace. Din acest motiv, nu este de asteptat o solutie n timp paralel polilogaritmic. Orice metod!derezolvare pentruproblemele greledin Pnecesit!probabil timp superlogaritmic si aceasta deoarece natura lor este probabilinerent secventiala. Aceasta nu nseamn!ns!c!paralelismul nu poate aduce cresteri substantiale de vitez!, algoritmilor derezolvare.

In concluzie, clasa Ppoate fi partitionat! n probleme foarte usoare (very easy)care snt rezolvabile n timp paralelpolilogaritmic si probleme mai putin usoare (not so easy),pentru care este improbabil!cresterea vitezei prin paralelism.


7/74


_____________________________________________________________________________________

_______________________________________________________________________________ 7

Complexitatea algoritmilor secventiali

La evaluarea (estimarea) algoritmilor secven"iali se pune n eviden"!necesarul de timp $i de spa"iu de memorare.Studierea complexit!"ii presupune analiza completa n cadrul algoritmului a urm!toarelor 3 aspecte:

#. configura"ia de date cea mai defavorabil!(cazurile degenerate);2. configura"ia de date cea mai favorabil!;3. comportarea medie.

Comportarea medie presupune probabilitatea de apari"ie a diferitelor configura"ii de date la intrare.Aspectul #este cel mai studiat $i este folosit, de obicei, pentru compararea algoritmilor secve"iali.

Complexitatea unui algoritm secven"ial se exprim!de regul!n limbajul ordinului O.

Definitie

Fie f : N N si g : N N dou! func"ii.

Spunem c!fO(g) #i not!m f = O(g) dac!#i numai dac!o constant!cR+ #i un num!rn0N astfel nct pentru n >>>>n0 f(n) "

f(n) < cn

k

, cun0 = ". Concluzie: f = O(nk),$i ordinulO exprim!viteza de varia"ie a func"iei, func"ie de argument.

Exemplul #: Calcularea maximului unui $ir

Max_Sir (A,n)

{max = A[#];for i = 2,,n if (A[i]) > max) max = A[i];return (max)

}

Dac!not!m cu T(n) timpul de execu"ie n pa$i al acestui algoritm atunci T(n)= $+ 2(n-$) = num!rul de atribuiri $i

compara"iiCazul cel mai defavorabil: situa"ia n care vectorul este ordonat cresc!tor (pentru c! de fiecare dat! se face $i

compara"ie $i atribuire).Putem spune ca T(n) = O(n), este o functie polinomiala de gradul I. Conteaz!doar ordinul polinomului, nu coeficientul

termenului de grad maxim, iar la num!rarea pa$ilor ne concentr!m asupra num!rului buclelor, nu asupra pa$ilor dininteriorul buclei.

Exemplul 2: Insertion Sort (algoritmul de sortare prin inserare)Algoritmul INSERTION SORT consider!c!n pasul k, elementeleA[#k-#]sunt sortate, iar elementul kva fi inserat,

astfel nct, dupa aceasta inserare, primele elemente A[ #k]s!fie sortate.Pentru a realiza inserarea elementului kn secventa A[#k-#], aceasta presupune: memorarea elementului ntr-o varibil!temporar!; deplasarea tuturor elementelor din vectorul A[#k-#] care sunt mai mari dect A[k], cu o poziie la

dreapta (aceasta presupune o parcurgere de la dreapta la stnga); plasarea lui A[k]n locul ultimului element deplasat.


8/74


_____________________________________________________________________________________

_______________________________________________________________________________8

Complexitate: O(n)

Insertion_Sort (A,n)

{for k = 2,,n

{ temp = A[k];

i=k-#; while (i >=#and A[i] > temp){ A[i+#] = A[i]; i=i-#;}

A[i+#] = temp;

}

Cazul cel mai dafavorabil: situatia n care deplasarea (la dreapta cu o pozi"ie n vederea nser!rii) se face pn! lanceputul vectorului, adic!$irul este ordonat descresc!tor.

Exprimarea timpului de lucru:

T(n) = 3(n - #)+3(#+ 2 + 3+ ... +n- #) = 3(n-#) + 3n(n - #)/2

Rezult!complexitatea: T(n) = O(n2)func"ie polinomial!de gradul II.

Observa"ie:Cnd avem mai multe bucle imbricate, nivelul buclei celei mai interioare dau gradul polinomului egal cuordinul de complexitate al algoritmului.

Bucla cea mai interioara ne da complexitatea algoritmului.

i O n

i

n

== ( )2

#

Exemplul 3: nmul"irea a dou!matrici

Prod_Mat (A,B,C,n);

{ for i = #,,n

for j = #,,n {

C[i,j] = 0;

for k = #,,n C[i,j] = C[i,j] + A[i,k] * B[k,j];}

}

Rezulta complexitatea O(n3).Exemplul 4: C!utarea binar!(Binary Search)

Fie A, de ordin n, un vector ordonat cresc!tor. Se cere s! se determine dac! o valoare b se afl!printre elementelevectorului. Limita inferioar!se nume$te low, limita superioar!se nume$te high, iar mijlocul virtual al vectorului, mid (de lamiddle).


9/74


_____________________________________________________________________________________

_______________________________________________________________________________ 9

low middle high

Binary_Search (A,n,b)

{low = #;high = n;

while(low =< high){mid = (low + high)/2; // partea ntreag! if (A[mid]=b)

return (mid); else

ifA[mid]>b high=mid-#; // restrng c!utarea la partea stng! else

low = mid+#; // restrng c!utarea la dreapta}

return(0)}Calculul complexit!"ii algoritmului const!n determinarea num!rului de ori pentru care se execut!bucla while.Se observ! c!, la fiecare trecere, dimensiunea zonei c!utate se njum!t!"este. Cazul cel mai defavorabil este ca

elementul c!utat s!nu se gaseasc!n vector.Pentru simplitate se considera n = 2kunde keste num!rul de njum!t!"iri. Rezulta k = log2 n si facnd o majorare,

T(n) log2n +#.

Deci complexitatea timp a acestui algoritm este O(log2n). Baza logaritmului se poate ignora deoarece: logax = logab logbx #i logabeste o constant!, deci r!mne O(log n),adic!o func"ie logaritmic!.

Propriet!"i ale ordinului de complexitate O:

") Fief, g : N N.

Daca f = O(g) | k f = O(g)

| f = O(k g) , k R

2) Fief, g, h : N N.

si: f = O(g) |

g = O(h) | f = O(h)

3) Fief$, f2, g$, g2: N N.

si: f"= O(g") | | f"+ f2 = O(g"+ g2)f2 = O(g2) | | f"f2 = O(g"g2)

Aceast!proprietate permite ca, atunci cnd avem dou!bucle imbricate (de complexit!"i diferite), complexitatea total!s!se ob"in!nmul"indu-se cele dou!complexit!"i. Cele dou!complexit!"i se adun!, dac!buclele sunt succesive.

Teorem!:Oricare ar fi doua constante c> 0, a> #, $i f : N N, o functie monoton!strict crescatoare, atunci (f(n))c =

O(af(n))

Demonstra"ia se bazeaz!pe limita limx

p

x

x

a

ntre ordinul func"iilor polinomiale $i cel al func"iilor exponen"iale exist!rela"ia:O(nc) O(an).Au loc urm!toarele incluziuni:

O($) O(log n) O(logkn) O(n) O(nlog n) O(n2) O(nklog n) O(nk+$) O(2n)Pentru calculul complexit!"ii se va ncerca ncadrarea n clasa cea mai mic!de complexitate din acest $ir:O($) clasa algoritmilor constan"i;


10/74


_____________________________________________________________________________________

_______________________________________________________________________________#0

O(log n) clasa algoritmilor logaritmici;O(log

kn) clasa algoritmilor polilogaritmici;

O(nlog n) O(n) clasa algoritmilor liniari;O(n2) clasa algoritmilor patratici;O(n

k+$) clasa algoritmilor polinomiali;

O(nlogkn)

O(2n) clasa algoritmilor exponentiali.

Tehnici de calcul a complexit!"ii

Se folosesc urm!toarele sume:

in n

O(n )i

n2

= =

+

#

#

2

( )

in n n

O(n )i

n

32

#

# 2 #

6= =

+ +

( ) ( )

i

n n

O(ni

n43

#

2 2#

4= =

+

( )

)

2 2#

0

#

i

nn

=

+ = - #

Sa calcul!m, de exemplu, suma: ii

i

n

= 2

#

Se noteaz!: G n i i

i

n

( )= = 2

#

G n G n G n i i i i

n i i n n

i

i

n

i

i

n

i

i

n

i

i

n

n i

i

nn i

i

nn

( ) ( ) ( )

( ) ( )

= = = =

= + = = +

= =+

= =

+

=

+

=

+

2 2 2 2 2 2

2 2 # 2 2 2 2 # 2 2

# #

#

# #

#

2

#

2

#

Prin aceea$i tehnic!se calculeaz!suma: ( )n i ii

n

= 2

#


11/74


_____________________________________________________________________________________

_______________________________________________________________________________ ##

Metode de proiectare a algoritmilor

orientate pe problem$

Probleme foarte importante cum sunt c!utarea $i sortarea, ale c!ror solu"ii algoritmice sunt omniprezente n structurilealgoritmice ale solu"iilor unor clase foarte largi de probleme, sunt studiate n mod special, n perspectiva construirii dealgoritmi optimali.


12/74


_____________________________________________________________________________________

_______________________________________________________________________________#2

Problema C$ut$rii

Problema apartenen"ei unui obiect la o mul"ime de obiecte nu n mod necesar distincte sau a incluziunii unei secven"e nalt! secven"! apare frecvent ca subproblem! n rezolvarea unei probleme prin metode algoritmice. Din acest motivalgoritmii de c!utare constituie o clas!special!, masiv studiat!$i foarte important!.

C!utarea secven"ial!

C!utarea secven"ial!porne$te de la premiza c!mul"imea de procesat este secven"ializat!ntr-un mod oarecare . Algoritmulde c!utare secven"ial! const! n parcurgerea secven"ei element cu element pn! cnd fie este gasit obiectul c!utat fiesecven"a se termin!. O secven"! poate fi implementat! prin tablouri unidimensionale (vectori) sau liste liniare simplu

nl!n"uite. Corespunz!tor celor dou!tipuri de structuri de date rezult!doi algoritmi: Algoritmul #respectiv Algoritmul 2.

Algoritmul #

FieA, de ordin n, un tablou unimesional. Se cere s!se determine dac!elementul bse afl!printre elementele tabloului.

Secv_Search_A(A,n,b) // caut!n tabloul A, de dimensiune n, obiectul b{

i=#;while(A[I]b and in)

return 0; // b nu a fost g!sit n tabloul Aelse

return i; // b a fost gasit pe pozi"ia i n tabloul A}

Algoritmul 2

FieLo list!liniara simplu nlan"uit!. Se cere s!se determine dac!obiectul bse afl!printre elementele listei.

Secv_Search_L(L,b) // caut!n lista L obiectul b{

p=L;// data(p) = informa"ia de con"inut a atomului adresat de p// leg(p)=adresa atomului ce urmeaz!n list!atomului adresat de p

while(data(p)b and pnull ) p=leg(p)if (p=null)return 0; // b nu a fost g!sit n lista L

else

return p; // b a fost gasit n lista L, ca informa"ie de con"inut a atomului aflat pe pozi"ia adresata depointerul p}

Complexitatatea

Complexitatea timp pentru cazul ce mai nefavorabil este O(n) pentru ambii algoritmi.


13/74


_____________________________________________________________________________________

_______________________________________________________________________________ #3

C!utarea binar!

C!utarea binar!folose$te ca ipotez!faptul c!mul"imea de procesat este secven"ializat!dup!o cheie de sortare calculat!nfunc"ie de compozi"ia obiectelor secven"ei sau inclus! n structura obiectelor ca o component!a acestora. Deci secven"a"int!este sortat!. Algoritmul de c!utate binar!const!n eliminarea succesiv!a unei jumat!"i din subsecven"a aflat!n cursde procesare pn!cnd fie elementul c!utat este g!sit fie subsecven"a r!mas!nu mai paote fi divizat!. Aceast!eliminare aunei por"iuni din subsecven"a n curs de procesare este permis!de ipoteza ordon!rii care faciliteaz!posibilitatea deciziei

asupra imposibilit!"ii afl!rii elementului c!utat n una din jum!t!"ile subsecven"ei. De exemplu dac!cheia elementului dinmijlocul subsecven"ei curente este #0 $i cheia c!utat!este #2 iar ordonarea este cresc!toare atunci sigur elementul c!utat(#0) nu va fi g!sit n prima jum!tate. Implementare prin liste a secevn"ei nu aduce un spor de eficien"!algoritmului datorit!caracterului prin excelen"!secven"ial al unei liste care face imposibil!accesarea direct!a elementului aflat la mijlocul listei.De aceea algoritmul de c!utare binar! folose$te implementarea secven"ei sortate sub form! de tablouri unidimesionale(vectori).Fie A, de ordin n, un vector ordonat cresc!tor. Se cere s! se determine dac! o valoare b se afl! printre elementelevectorului. Limita inferioar!se nume$te low, limita superioar!se nume$te high, iar mijlocul virtual al vectorului, mid (de lamiddle).

low middle high

Binary_Search (A,n,b)

{low = #;high = n;

while(low


14/74


_____________________________________________________________________________________

_______________________________________________________________________________#4

Arbori binari de c!utare

Mul"imea de obiecte n care se face c!utarea poate fi organizat!ca arbore binar de c!utare. Aceasta permite construirea dealgoritmi de c!utare eficien"i. Arborii binari de cutare snt acei arbori ale cror noduri snt organizate n functie de valorile

unor chei care snt calculate functie de valorile nodurillor. Pentru fiecare nod, cheia sa este mai mare dect valorile cheilortuturor nodurilor din subarborele stng si este mai mic dect toate cheile de noduri din subarborele drept. Nodurilearborelui au chei distincte. In figura urmtoare este dat un arbore binar de cutare.

12

420

2 8

7

15

Traversarea n inordine pe un arbore binar de cutare produce o secvent sortat cresctor dup valorile cheilor.Operatia de creare a unui arbore binar de cutare este O(n2) timp pentru cazul cel mai defavorabil cnd arborele seconstruieste sub forma unei liste nl!ntuite. Pentru acest caz operatiile de insertie, stergere si de c!utare a unui atom se facn O(n). Pentru cazul mediu crearea se face n O(n * log n) iar insertia, stergerea, c !utarea se face n O(log n). O clas!special! de arbori binari de c!utare anume arborii binari echilibrati pentru care insertia, stergerea si c!utarea se face nO(log n) pentru cazul cel mai defavorabil.

Se consider!functia de c!utare ntr-un arbore binar de c!utare.

search(r,x){

p=r;while( p null)

{ if ( x < data(p) ) p=lchild(p); else if ( x > data(p) ) p=rchild(p); else return(p);}

return(p); // return null}

unde: r este adresa rdcinii arborelui care are noduri de forma(data, legtur la subarborele stng, legtur la subarborele drept) x este valoarea cmpului de date a nodului cutat. data(), lchild(), rchild() sint primitivele de acces la cele trei cmpuri ale unui nod, data, legtur la subarborele

stng, legtur la subarborele drept , respectiv.

Complexitatatea

Pentru un arbore echilibrat functia lucreaz n O(logn) timp, ceea ce nseamn c arborele binar echillibrat este arborelebinar optim atunci cnd se caut un element aleatoriu ales.


15/74


_____________________________________________________________________________________

_______________________________________________________________________________ #5

Pattern Matching

Problema incluziunii unei secven"e de obiecte n alt!secven"!de acela$i ( de exemplu a unui sir de caractere ca sub $ir alaltuia de acela$i tip) este cunoscut! sub numele de pattern matching. Algoritmii de pattern matching au aplica"ii n

procesarea de imagini, recunoa$terea de caractere. Vom prezenta n cadrul acestei lucr!ri doi dintre ace$tia: algoritmul decautare naiv! si algoritmul Rabin-Karp. Primul este important pentru ntelegerea conceptului de pattern matching iar aldoilea poate fi extins la pattern-uri bidimesionale deci poate fi utilizat in domeniile anterior men"ionate.

Algoritmul de c!utare naiv!

Este un algoritm foarte simplu dar si foarte ineficient: pentru fiecare pozi "ie posibil! n $ir se testeaz!dac!pattern-ul sepotrive$te cu sub$irul care ncepe cu acea pozi"ie.

PM_Naiv(s,n,p,m) // caut!n sirul s de dimnsiune n pattern-ul p de dimesiune m{

i=0;while (i


16/74


_____________________________________________________________________________________

_______________________________________________________________________________#6

PM-RK(s,n,p,m)) // caut!n sirul s de dimnsiune n pattern-ul p de dimesiune m{

dm#=#;fori-#..m-#

{dm#=dm#d mod q

}// dm#= (puterea m-#a lui d modulo) qhp=0;fori-#..m

{hp=hpd +index(p[i])}

// hp = valoare func"iei de dispersie pentru simbolul phsm=0;fori-#..m

{hsm=hsmd +index(s[i]);}

// hsm = valoare func"iei de dispersie pentru simbolul s[#..m]i=#;while(hphsm and i


17/74


_____________________________________________________________________________________

_______________________________________________________________________________ #7

Problema Sort$rii

Sortarea ese o opera"ie foarte des ntlnit!n rezolvarea unei probleme prin metode algoritmice. Din acest motiv algoritmiide sortare constituie o clas!extrem de important!care merit!o aten"ie special!iar o analiz!a celor mai cunoscu"i algoritmide sortare este util!$i necesar!.

Bubble Sort(sortare prin interschimbare)

Bubble_sort (A,n)

// A[#..n] - seceventa de sortat{flag=#;

k=n;while (flag 0 and k >= #)

{ k=k-#; flag=0; for i=#,,k;

if ( A[i] > A[i+#] ){ interchange ( A[i], A[i+#] ); flag=#;}

}}

Complexitatea: Evident O(n2)

Insertion Sort (sortare prin inserare)

Algoritmul Insertion Sort considera ca n pasul k, elementele A[#k-#] sunt sortate, iar elementul de pe pozi"ia k va fiinserat, astfel nct, dupa aceasta inserare, primele elemente A[#k] sa fie sortate.Pentru a realiza inserarea elementului kn secventa A[#k-#], aceasta presupune: memorarea elementului intr-o variabila temporara; deplasarea tuturor elementelor din vectorul A[#k-#] care sunt mai mari dect A[k], cu o poziie la dreapta (aceasta

presupune o parcurgere de la dreapta la stnga); plasarea lui A[k] n locul ultimului element deplasat.insertion_sort(A,n)

{for k=2,,n

{ temp = A[k]; i=k-#;while (i>=#and A[i] > temp)

{ A[i+#] = A[i]; i=i-#;

}

A[i+#] = temp;}

}


18/74


_____________________________________________________________________________________

_______________________________________________________________________________#8

Complexitatea:

Cazul cel mai dafavorabil: situatia n care deplasarea (la dreapta cu o pozitie n vederea nserarii) se face pna la nceputulvectorului, adica sirul este ordonat descrescator.Exprimarea timpului de lucru:T(n) = 3(n - #)+ (#+ 2 + 3+ ... +n- #) = 3(n-#) + 3n(n - #)/2Rezulta complexitatea: T(n) = O(n2)functie polinomiala de gradul II.

Observatie: Cnd avem mai multe bucle imbricate, termenii buclei celei mai interioare dau gradul polinomului egal cugradul algoritmului.

Bucla cea mai interioara ne da complexitatea algoritmului.

i O n

i

n

== ( )

2

#

Shell Sort (sortare prin metoda Shell)

Sortarea se face asupra unor subsecvente care devin din ce in ce mai mari pina la dimensiunea n.Fiecare subsecventa ioeste determinata de un hi numit increment.Incrementii satisfac conditia : ht > ht-#> > h2 > h#

Fie hi = h. Avem urmatoarele subsecvente:

A[#], A[#+h], A[#+2h], A[#+kh];A[2], A[2+h], A[2+2h], .

A[h], A[h+h], A[#+2h],

Exemplu :

h=4 # 5 7 8 3 #2 9 4 #2|____________________________|_____________________________|

|____________________________||____________________________|

|____________________________|

h=3 # 5 7 8 3 #2 9 4 #2|_____________________|_____________________| |_____________________|_____________________| |_____________________|_____________________|

h=# # 5 7 8 3 #2 9 4 #2|_______|_______|_______|_______|_______|______|_______|_______|

Shell_sort (A,n,h,t);// A[#..n] - seceventa de sortat// H[#..t] - incrementii ht> ht-#> >h#=#


19/74


_____________________________________________________________________________________

_______________________________________________________________________________ #9

{ for s=t,t-#,,#

{ h=H[s]; for j=h+#,,n

{ x=A[j];

i=j-h; while (i>0 and x


20/74


_____________________________________________________________________________________

_______________________________________________________________________________20

Heap_Sort

Definitie:Se numeste arbore heap un arbore binar T = (V, E) cu urmatoarele proprietati:

(#) functia key : V R care asociaza fiecarui nod o cheie.(2) un nod v V cu degree(v) > 0 (nu este nod terminal), atunci: key(v) > key(left_child(v)), daca left_child(v)

key(v) > key(right_child(v)), daca right_child(v)

(Pentru fiecare nod din arbore, cheia nodului este mai mare dect cheile descendentilor).Observatie: De obicei functia cheie reprezinta selectia unui subcmp din cmpul de date memorate n nod.

Generare Heap

Generare Heap prin inserari repetate

heap_gen_#(A,V, n)

// A[#..n] - seceventa de sortat// V vectorul ce contine reprezentarea heap-ului;// N numarul de noduri din heap,{

N = # //se considera pentru nceput un heap cu un singur element,//dupa care toate celelalte elemente vor fi inserate n acest heap

V[#]=A[#];for i = 2,,n

insert(V, N, A[i]);}insert(V, N, a)

// Vvectorul ce contine reprezentarea implicita a heap-ului;// Nnumarul de noduri din heap,// ambele sunt plasate prin referinta (functia insert le poate modifica);// aatomul de inserat;// #) In reprezentarea implicita: V [N + #] = a ; N = N + #// n continuare se reorganizeaza structura arborelui astfel nct sa-si pastreze structura de heap.// 2) Se utilizeaza interschimbarile. Comparatii:// Se iau 2 indici: child = N si// parent = [N/2]// Se compar !V[child] cu V[parent]// Interschimbare daca V[child] nu este mai mic dect V[parent]// 3) naintare n sus: child = parent// parent = [child/2]// 4) Se reia pasul 2) pna cnd nu se mai face interschimbarea.

{ N = N+#;V[N] = a ;child = N ;

parent = [N/2] ;while (parent #)

{ if key(V [child]) > key(V [parent])

{ interchange (V [child],V [parent]); child = parent; parent = [child/2];}

else break; // se paraseste bucla parent = 0}

}


21/74


_____________________________________________________________________________________

_______________________________________________________________________________ 2#

Complexitatea:

Complexitatea operatiei insert:

n cazul cel mai defavorabil se parcurge o ramura care leaga un nod terminal de radacina. Rezulta, complexitatea este datade adncimea arborelui. Daca N este numarul de noduri din arbore, 2kN < 2k+#, si adncimea arborelui este k+#.

2k - # N < 2k+#- # k = log2N | |

| | | |nr. de noduri nr. de noduriale arborelui ale arboreluicomplet de complet deadncime k adncime k+#

k log2N < k + # adncimea arborelui este k+#= log2N.+#Deci complexitatea este O(log N).

Complexitatatea algoritmului heap_gen_"

Se fac n-#operatii insertn heap-uri cu dimensiunea N nRezulta complexitatea acestor operatii nu depaseste O(nlog n). Facem un studiu pentru a vedea daca nu cumva ea este maimica dect O(nlog n).

Cazul cel mai defavorabileste situatia n care la fiecare inserare se parcurge o ramura completa. De fiecare data inserareaunui element se face adaugnd un nod la ultimul nivel. Pentru nivelul 2 sunt doua noduri. La inserarea lor se va face celmult o retrogradare (comparatie).

nivelul 2 : 2 noduri #comparatienivelul 3 : 4 noduri 2 comparatiinivelul 4 : 8 noduri 3 comparatii--------------------------------------------------nivelul i : 2i-# noduri i-#comparatii

Considernd un arbore complet (nivel complet) n = 2k - #numarul total de comparatii pentru toate nodurile este T(n)de la nivelul 2 la nivelul k. Vom calcula:

T n i i

i

k

( ) ( )= = # 2 #

2

Sa aratam: T n ii

i

k

( )= =

2#

#

cu tehnica T n T n T n( ) ( ) ( )= 2 . Asadar:

T n i i i i

k k k

k k

i

i

ki i i

i

k

i

k

i

k

k k k

k i

i

k

( )

... ( ) ( ) ... ( )

( ) (

= = =

= + + + + + =

= + =

=

+

=

=

=

=

2 2 2 2 2

# 2 2 2 3 2 2 2 # 2 # 2 2 2 3 2 # 2

2 # 2 2

#

#

#

#

#

#

#

#

#

2 3 4 # # 2 3 #

2

#

# 2 2 2 2 2

# 2 # 2 # 2 2 2

0 #

0

#

)

( ) ( ) ( )

+ + =

= + = +=

k ii

k

k k kk k

Rezulta: T n k k k n k k k k( ) ( ) ( ) ( ) ( )= + = + + = +2 2 2 2 2 # 2 2 2iar: k n= +log ( )2 # ,

din n k= 2 #Rezulta: T n n n n( ) (log ( ) ) log ( )= + + +2 2# 2 #

------------------------termen dominant

Facndu-se majorari, rezulta complexitateaO(nlog n)pentru Heap_Gen_#.


22/74


_____________________________________________________________________________________

_______________________________________________________________________________22

Generare Heap prin retrogradari repetate

Construim heap-ul de jos n sus (de la dreapta spre stnga). Cele mai multe noduri sunt la baza, doar nodurile din vrfparcurg drumul cel mai lung.

noduri terminale

I

II

i

Presupunem ca elementele V[i+#,n] ndeplinesc conditia de structura a heap-ului:j >i avem: V[j] > V[2*j] , daca 2*j n

V[j] > V[2*j +#] , daca 2*j + #n

Algoritmul consta n adaugarea elementului V[i] la structura heap-ului. El va fi retrogradat la baza heap-ului (prelucrare

prin retrogradare):heap_gen_2 (A,V, n)

// A[#..n] - secventa de sortat// V vectorul ce contine reprezentarea heap-ului;{

for i = #,,nV[i]=A[i];

for i = n/2,,#retrogradare(V,n, i);

}

retrogradare(V, n, i)

{parent = i ;child = 2*i ; // fiu stnga al lui iwhile (child n)

{if ( child+#n and key(V[child+#]) > key(V[child] )

child = child + #;if key(V[parent]) < key(V[child])

{interchange(V[parent], V[child]);parent = child ;child = 2*parent ;}

else break;}

}


23/74


_____________________________________________________________________________________

_______________________________________________________________________________ 23

Complexitatea

Fie un arbore complet cu n = 2k- #. Cazul cel mai defavorabileste situatia n care la fiecare retrogradare se parcurg toatenivelele:

nivel k : nu se fac operatiinivel k-#: 2k-2noduri o operatie de comparatie

nivel k-2: 2k-3

noduri 2 operatii------------------------------------------------------------------nivel i : 2i-#noduri k-i operatii-------------------------------------------------------------------nivel 2 : 2#noduri k-2 operatiinivel # : 20noduri k-#operatii

Se aduna, si rezulta: T n k i i

i

k

( ) ( )=

=

2 #

#

#

Tehnica de calcul este aceeasi: T n T n T n( ) ( ) ( )= 2

T n k i k i k k k

k k k k k

i i k k

i

k

i

k

k k k

( ) ( ) ( ) ( ) ( ) ( ) ...

( ) ( ) ( ) ... ( ) ( )

= = + + + + +

= + = +

=

=

2 2 # 2 2 2 3 2 3 2 2 2

# 2 2 2 3 2 2 2 2 2 # 2 2 # 2

# # 2 3 3 2

#

2

#

2

0 # 2 3 2 # # 0 2

2 2 2 # 2 2 # # 3 2 #

#

0

3

#

3

# 2 2 2

i

k

i

k

k k k k k k k

=

=

=

= + = + = ( ) ( )

Rezulta: T n k k k k( ) ( )= 3 2 # 3 2 # #2

T n n n( ) log ( ) + 3 # #2

------- termen dominant

Rezulta complexitatea O(n)pentru heap_gen._2

Algoritmul Heap Sort

heap_sort (A,n)

// A[#..n] - secventa de sortat{

heap_gen(A, V, n); N = n;for i = n,n-#,, 2{N = i ;A[i] = remove(V, N) ;}

}

Aceasta procedura sorteaza un vector A cu N elemente: transforma vectorul A ntr-un heap si sorteaza prin extragerisuccesive din acel heap.

heap ipartea sortataa vectorului

minmax


24/74


_____________________________________________________________________________________

_______________________________________________________________________________24

Procedura remove

remove(V, N)

// Vvectorul ce contine reprezentarea implicita a heapu-lui;// Nnumarul de noduri din heap// ambele sunt plasate prin referinta (functia remove le poate modifica);// se scoate elementul cel mai mare care este radacina heap-ului; se initializeaza cei 2 indici;// se reorganizeaza structura arborilor: se ia ultimul nod de pe nivelul incomplet si-l aduc n nodul

// radacina, si aceasta valoare va fi retrogradata pna cnd structura heap-ului este realizata.// parent = max(parent, lchild, rchild).// Exista trei cazuri:// #. conditia este ndeplinita deodata;// 2. max este n stngaretrogradarea se face n stnga;// 3. max este n dreaptaretrogradarea se face n dreapta.{

a = V[#];V[#] = V[N];

N = N-#;parent = #;child = 2;while (child N)

{ if child+#N and key(V[child+#]) > key(V[child])

child= child+#; if key (V[parent]) < key(V[child])

{ interchange(V[parent], V[child]); parent= child;child= 2*parent;}

else break;} return(a);

}

Complexitatatea algoritmului heap_sort

Complexitatea algoritmului Heap_Sort este determinata de functiile removece nu pot fi aduse la complexitate < O(log n).Astfel: Heap_Sort = O(n) + O(nlog n) --------------- termen ce determina complexitatea

Rezulta complexitatea alg. Heap_Sort = O(nlog n)

Merge_Sort $i Quick_Sort

Merge_Sort $i Quick_Sort sunt doi dintre cei mai importan"i algoritmi de sortare. Ace$tia vor fi prezenta"i ca studii de cazla metoda de proiectare Divide_et_impera (divide_and_conquer)


25/74


_____________________________________________________________________________________

_______________________________________________________________________________ 25


26/74


_____________________________________________________________________________________

_______________________________________________________________________________26

Metode generale de proiectare a

algoritmilor

Construirea unui algoritm care rezolv!o problem!presupune ca etap!intermediar!construc"ia modelului matematiccorespunz!tor problemei. Ra"iunile definirii modelului matematic snt urm!toarele:

De multe ori problemele snt descrise informal (verbal). In acest fel, unele aspecte ale problemei pot fi omise sauformulate ambiguu. Construc"ia modelului matematic eviden"iaz!$i elimin!aceste lipsuri;

Instrumentele matematice de investigare n perspectiva identific!rii $i definirii solu"iei, snt mult mai puternice;

Definirea solu"iei n termenii modelului matematic u$ureaz!foarte mult activitatea de construire a algoritmului.

O metod!de proiectare a algoritmilor se bazeaz!pe un anumit tip de model matematic $i pune la dispozi"ie procedeeeprin care se poate construi $i implementa un model particular corespunz!tor unei probleme. Definirea unui modelmatematic cuprinde urm!toarele trei aspecte:

#. conceptual: presupune identificarea $i conceptualizarea componentelor din domeniul problemei;

2. analitic: implic!descoperirea tuturor rela"iilor ntre conceptele care conduc la identificarea $i descrierea solu"iei

3. computa#ional: se refer!la evaluarea calitativ!a algoritmului ce construie$te solu"ia.

Cele mai cunoscute metode de proiectare a algoritmilor snt urm!toarele: divide-and-conquer, greedy, programareadinamic!, backtracking, branch-and-bound.


27/74


_____________________________________________________________________________________

_______________________________________________________________________________ 27


28/74


_____________________________________________________________________________________

_______________________________________________________________________________28

Metoda Divide-and-Conquer (divide-et-

impera)

Descrierea metodei

Prin aceast!metod!, o problem! dat!P este divizat! recursiv ntr-un num!r de subprobleme independente. Solutiaunei probleme situate pe un anumit nivel al recursiei, se compune din solu"iile subproblemelor sale. Divizarea unei

probleme se face pn!cnd se ob"in subprobleme de dimensiuni mici ce pot fi rezolvate prin meteode elementare.

Modelul metodei

Metoda poate fi descris!astfel:

D_and_C (P(n));

{

if ( n". De asemenea vompresupune c!divizarea problemei n subprobleme $i asamblarea solu"iilor necesit!timpul O(nk). Complexiatea timp T(n)aalgoritmuluiD_and_Ceste dat!de urm!toarea relatie de recuren"!:


29/74


_____________________________________________________________________________________

_______________________________________________________________________________ 29

T(n)

O( ), daca n n0

a T(n

b) O(n ) , daca n n0

k=

+ >

#

Teorema #: Dac!n >n0atunci :

T n

O n daca a b

O n n daca a b

O n daca a b

b a k

k

b

k

k k

( )

( ) ,

( log ) ,

( ) ,

log

=

>

=

B[k+#].Aceasta ar putea rezulta din urmatorele situatii:

#. B[k] fost initializat in bucla I iar B[k+#] in bucla II2. B[k] a fost initializat in bucla I iar B[k+#] in bucla III

Cazul #. Aceasta inseamna ca imediat dupa initializarea elementului B[k] situatia indicilor i si j este urm!toarea : i mid si j > high. Deci A[i] >= A[high], B[k] = A[high] si B[k+#] = A[i]. Din B[k] > B[k+#] rezulta ca A[high] >A[i]>= A[high]. Absurd.

Cazul 2. Aceasta inseamna ca imediat dupa initializarea elementului B[k] situatia indicilor i si j este urm!toarea : j high si i > mid. Deci A[mid] < A[j], B[k] = A[mid] si B[k+#] = A[j]. Din B[k] > B[k+#] rezulta ca A[mid] >A[j] >A[mid]. Absurd.


32/74


_____________________________________________________________________________________

_______________________________________________________________________________32

Complexitatea :

Lema 2.Timpul de executieal algoritmului MERGE_SORT este:

T n, n

T(n/ )+n, n( )=

=

>

0 #

2 2 #Demonstratie: Consideram: n = 2k;

Evident procedura MERGE este de de complexitate O(n) .

T(n) = 2T(n/2) + n = 2(2T(n/4) + n/2) + n = ... = 22T(n/22) + 2n= 22 (2T(n/23) + n/22) + 2n == 23T(n/23) + 3n = ... = 2kT(n/2k) + kn T(n) = kn = nlog2n , pentru ca n = 2

k, si, deci, k=log2n

Asadar complexitatea algoritmului este O(nlog n).

Sortarea rapida (C.A.R. Hoare)

Pentru a sorta o secvent! de n elemente ale unui vector A, se partitioneaz! vectorul n 2 segmente dup! schemaurm!toare utiliznd un element cu statut special numitpivot.

elemente pivotA[k]=pivot elementepivot

l h

Urmeaz!apoi sortarea recursiv!a secventelor separate depivot.

Quik_Sort(A, low, high)

{

if(high >low)

{k= Partition(A, low, high) ; // procedura de

// partitionare

Quick_Sort (A, low, k-") ;

Quick_Sort(A, k+", high) ;

}

}

Pseudocodul pentru functiapartition:

Partition(A, low, high)

{

l= low; h= high;

x= A[l];while (l < h)

{

I while (A[l] x and l high) l=l+";II while (A[h] > x and h low) h=h-"-;

if (l pivot.


33/74


_____________________________________________________________________________________

_______________________________________________________________________________ 33

Ciclul Iwhilenseamna ca nainteaza l ct timp A[l] pivot. Acest ciclu se opreste pe conditia A[l] >pivot, fixndu-seaici.

Ciclul II whilensemna ca nainteaza hct timp A[h] >pivot. Acest ciclu se opreste pe conditia A[h] pivot, fixndu-se aici.

Cele doua pozitii se schimba, astfel nct sa se permita naintarea indicilor mai departe.

low h

Corectitudinea:

Lema3: Procedura Quick_Sortsorteaz!cresc!tor elementele vectorului A.

Demonstratie:Inductie dupa n.Pasul#. Pentru un tablou unidimensional A de dimensiune 2 evident algoritmul functioneza corect.Pasul2. Presupenem ca procedura Quick_Sortfunctioenaza corect pentru tablori unidimensionale A de dimensiuni n

si demostram ca functioneaza corect si pentru A de dimensiune n+#:ProdeduraPartitionsepara vectorul A in dou!segmente S#cu elemente pivot si S2cu elemente > pivot.

Procedura Quick_Sort aplicata asupra vectorilor S#si S2functioneza conform ipotezei de inductie.Rezulta in final A = S#{ pivot } S2 . Datorita propriet!tilor pivotului si a vectorilor S#si S2vectorul rezultat A

este sortat crescator.

Complexitatea:

Lema 4. Timpul de executieal algoritmului Quick_Sort este: T n n n( ) ( ) /= # 2Demonstratie:

Cercetam cazul cel mai defavorabil. Fie cazul n care vectorul este ordonat descrescator. Pivotul gasit, la primul pas,este elementul maxim din vector, rezulta ca trebuie plasat n ultima pozitie. Pivotul va fi maximul dintre elementelesecventei, deci, va fi plasat n ultima pozitie din secventa.

Problema se mparte n 2 subprobleme:P(n) P(n-$) , P(0).

Numarul de comparatii pentru functiaPartitioneste (n-$). Vectorul se parcurge n doua directii, dar o singura data.Rezulta ca timpul de functionare al algoritmului Quick_Sort este: T n n T n( ) ( ) ( )= + # #Rezolvnd aceasta ecuatie, avem:T n n T n n n T n n n n T ( ) ( ) ( ) ... ... ( )= + = + + = = + + + + +# # # 2 2 # 2 3 # #unde: T(#) este 0 (nu se partitioneaza). Rezulta:

T n i n n

i

n

( ) ( ) /= = =

# 2#

#

Aceasta suma este de complexitate O(n2). Rezulta ca este un algoritm ineficient.

Spatiul ocupat de algoritmul Quick-Sort

Quick_Sort(A, low, high){

if (low < high)

{

k = Partition(A, low, high) ;

Quick_Sort(A, low, k-") ;

Quick_Sort(A, k+", high) ;

}

}

low k highAvem n acest algoritm doua apeluri recursive.


34/74


_____________________________________________________________________________________

_______________________________________________________________________________34

Cazul cel mai defavorabil:

lowk

high

Consideram consumul de memorie n stiva : M(n) = c + M (n - #)

M(n) = O(n)

un ordin de complexitate mare.Pentru reducerea consumului de memorie, se concepe un alt algoritm la Quick_Sort, astfel nct un apel sa fie rezolvatrecursiv, iar celalalt apel iterativ.

secventa mica rezolvata recursiv

k

secventa mare rezolvata iterativ

Quick_Sort(A, low, high){

while (low < high)

{

k = Partition(A, low, high);

if( k-low > high-k)

{

Quick_Sort(A, k+#, high);

high = k-#;}

else

{

Quick_Sort(A, low, k-#);

low = k+#;}

}

Necesarul de memorie pentru aceasta este M(n) c + M(n/2), nsemnnd ca oricare ar fi secventa mai mica, ea este dect jumatatea secventei din care a fost obtinut!M(n) = O(log n)am redus ordinul de complexitate.


35/74


_____________________________________________________________________________________

_______________________________________________________________________________ 35


36/74


_____________________________________________________________________________________

_______________________________________________________________________________36

Metoda Greedy

Descrierea metodei

Metoda Greedy este o metod! general! de proiectare a algoritmilor care const! n construirea solutiei globaleoptimale printr-un sir de solutii cu caracter de optim local atunci cnd este posibil ! exprimarea optimului global ca ocombinatie de o optime locale.

Schema de proiectare:Problema se prezint!sub forma unei multimi S cu ncomponente. O parte din submultimilelui S reprezint! solutii care satisfac un anume criteriu si se numesc solutii admisibile. In spatiul solutiilor admisibile

prezint!interes o solutie care maximizeaz!/minimizeaz!o functie obiectiv. Solu"iile admisibile au proprietatea c! odat!cuo solu"ie admisibil! toate submul"imile sale snt de asemenea admisibile. Metoda Greedy sugereaz! un algoritm deconstruc"ie a solu"iei optimale pas cu pas pornind de la mul"imea vid!. La fiecare pas se selecteaz!un element nou care va finghi"it n solu"ie (greedy) n baza unei proceduri de selec"ie. De exemplu la problemele de optimizare procedura deselec"ie alege acel element care face s!creasc! cel mai mult valoarea func"iei obiectiv. Desigur nu n toate problemele,aceast!strategie conduce la solu"ia optim!, metoda Greedy nefiind o metod!universal!.

Modelul metodei

FieSo multime finit!de intr!ri $i C o colec"ie de submul"imi ale lui S. Spuneme c!C este admisibil!dac!satisfaceaxioma de admisibilitate:

X C: X (xX: X \ (x) C)

Dac!C este admisibil!atunci perechea(S,C) se num$tesistem admisibil. O submul"imeXC se nume$tebaz!dac!este maximal!(nu exist!xS \X astefel nctX {x} C.Clasa de probleme pentru care se pot defini algoritmi greedyeste definit!de urm!toarea schem!:

Se consider!date unsistem admisibil (S,C) #i o func"ie obiectiv f:CR.Se cere determinareadeterminarea unei baze B C. care satisface:

f(B) = optim { f(X) | X baz!In C }

n general prin optim se va n"elege minim sau maxim. Strategia greedy (lacom) const!n g!sirea unui criteriude selec"ie a elementelor din Scare candideaz!la formarea bazei optime, numit criteriu de selec#ie greedysaucriteriu de

selec#ie localasauoptim local.

Schema strategiei greedy este urm!toarea:

// Ini"ial

S$= S;

B = ;

repeat


37/74


_____________________________________________________________________________________

_______________________________________________________________________________ 37

// pasul de selec"ie greedyalege x din S$conform unui criteriu de optim local ;

S$= S$- {x} ;

dac!B {x} este n C atunci B = B {x};

// Condi"ia de terminare

until (nu se mai pot ad!uga elemente din S$la B)

Obs.n studiile teoretice, optimul local are o defini"ie exact!:

f(B {x}) = optim { f(B {y}) | y S"}

n practica construirii de algorimi greedy, este recomandabil s! fie lasat! liber! defini"ia optimului local. Exist!totu$i restric"ia ca defini"ia acestuia s!nu depind!de alegerile ulterioare sau de solu"iile subproblemelor. n schimb poatedepinde de selec"iile f!cute la acel moment. n acest fel se ob"ine o flexibilitate mai mare n proiectarea de algoritmi greedydar de fiecare dat!trebuie demonstrat c!selec"ia conform optimului local conduce la o baz!pentru care se ob"ine optimulglobal pentru func"ia obiectiv.

Din p!cate numai condi"iile de optim local $i admisibilitate nu asigur!existen"a unui crieriu de selec"ie local!care s!conduc!la determinarea unei baze optime. Aceasta nseamn!c!pentru anumite probleme algoritmii greedy nu construiesco solu"ie optima ci numai o baz!pentru care func"ia obiectiv poate avea valori apropiate de cea optim!. Acesta este cazulunor probleme NP-complete.

Eficien%a metodei

Se presupune c!pasul de alegere greedy selectioneaz!elementexnO(kp)timp undek = #S"iar testarea condi"ieiB {x}

Cnecesit!O(lq)timp, l = #B, k + l n . De asemenea se presupune ca opera"iileB {x} $i S - {x}necesit!O(") timp.Rezult!:

T(n)= O(np

+$q) + + O($p+ nq) = O($p ++ np+ $q + + nq)= O(np+$+ nq+$) = O(nmax(p+$, q+$))

Studii de caz

Interclasare optimala

Definirea problemei: Avem secventele X#,X2,.....Xn fiecare sortate.Sa se gaseasca o strategie de interclasare dou ctedou astfel nct numrul de operatii sa fie minim.Exemplu: Fie urmatoarele secvente X#, X2, X3unde

X# are 30 elem.X2 are 20 elem.X3 are #0 elem.

Se aplic citeva variante de organizare a interclasrii

#. Y=merge(X#,X2) 50 operatii Y-50 elem. Z=merge(Y,X3) 60 operatii

---------------


38/74


_____________________________________________________________________________________

_______________________________________________________________________________38

##0 operatii

2. Y=merge(X2,X3) 30 operatii Y-30 elem. Z=merge(Y,X#) 60 operatii

--------------- 90 operatii

Solutia: Problema se rezolv aplicind o tehnic Greedy la fiecare pas cind se interclaseaza cele mai mici 2 secvente.Problema se poate reprezenta ca un arbore binar.

Exemplu 95 y4

y2 35 60 y3

y# #5 x# 20 30 x5 30 x2

5 #0 x4 x3

X3,X4-> Y# -#5 elem.X#,Y#-> Y2 -35 elem.X2,X5-> Y3 -60 elemY3,Y2 -> Y4 -95 elem. 205 elem.

Nodul x4este la distanta 3 de nodul y4, deci valoarea din x4se va aduna de 3 ori.Daca notam di distanta de la radacina la nodul frunza xi si cu qivaloarea nodului, atunci

di = level ( qi) - #

q di ii

n

= =

#

nr. total operatii

5*3 + #0*3 + 20*2 + 30*2 + 30*2 = #5 + 30 +40 + 60 + 60 = 205

S = q di ii

n

=

#

se numeste lungimea drumurilor externe ponderate ale arborelui

O interclasare optimal corespunde construirii unui arbore binar optimal relativ la S.

Algoritm pentru construirea unui arbore binar optimal

tree ( L,n )

{// L- o list de arbori. Initial contine arbori de forma (val, 0, 0 ) - noduri terminale// foloseste: get_node() -- crearea unui nod// least(L) -- sterge din lista arborele cu valoarea din rdcin minim// insert(L,t) -- insereaz in list un arborefor i=#,,n-#

{ t = get_node() lchild(t) = least(L) rchild(t) = least(L) data(t) = data(lchild(t)) + data(rchild(t)) insert(L,t)}


39/74


_____________________________________________________________________________________

_______________________________________________________________________________ 39

return (least(L))}

Teorema #Fie algoritmul treesiLcontinnd initial narbori cu cte un singur nod de valori ( q", q2, ... qn ).Atunci tree

genereaz un arbore binar cu S = d qi ii

n

=

#

minim ( didistanta de la rdcin la nodul qi)

Demonstratie . Demonstratia se face prin inductie dup n

#. n = #evident , arbore minimal

2. P(n-#) : Pentru orice secvent initial de valori nod ( q", q2, ... qm), #mn-#treegenereaz un arbore Tamoptimal

Presupunem P(n-#) adevrat.

P(n) : Pentru orice secvent initial de valori nod ( q", q2, ... qn), treegenereaz un arbore Tan optimal

Demonstrm P(n) adevrat.

Lema #: Fie qisi qjcele mai mici dou valori ale secventei (nodurile care vor fi returnate n prima iteratie a buclei fordefunctia least ). Fie T un arbore optimal ( nu neaprat cel construit de tree). Fie P nodul interior cel mai ndeprtat derdcin si presupunem c descendentii luiP au valorile qk, ql diferite de qi, q : (qi qk) si / sau (qj ql) se pot interschimba n arbore T, obtinndu-se un arbore Tcare ramne optimal.

Demonstratie:

Fie di

distanta de la nodul de valoare qila rdcin

dj distanta de la nodul de valoare qjla rdcindk distanta de la nodul de valoare qkla rdcindl distanta de la nodul de valoare qlla rdcin

qi

qj

qk ql

S(T) = q d q d q d r r i i k k r

r i k

n

+ +=

#

,

Dupa interschimbarea valorilor qi, qkse obtine :

S(T') = q d q d q d r r k i i k r

r i k

n

+ +=#

,


40/74


_____________________________________________________________________________________

_______________________________________________________________________________40

AvemD = S(T') - S(T) = qi(dk-di) - qk(dk-di) = (dk-di) (qi-qk)= -(dk-di) (qk-qi)

Dar dk di pentru caP-ul e mai ndeprtat S(T')-S(T) 0 S(T') S(T) qk qi pentru ca qi, qjminime Tminimal

S(T) = S(T) .

Analog se procedeaz pentru perechea (qj,ql).Se obtine Tpentru careS(T)=S(T).

Revenim la demonstratia P(n) adevrat:

Din Lema anterioara rezult c Teste optimal pentru secventa de valori nod ( q", q2, ... qn) si contine nodulPcare are ndescendenti valorile qi, qjcele mai mici.

nlocuim subarborelePcu un nod care are valoarea qi+qj.Noul arboreTfiind un subarbore al arborelui Teste optimalpentru secventa de valori nord (q" ... qi-" qi+qj qi+" ... qj-" qj+" ... qn) deci S(T) = q"d"++qi-"dI-"+ (qi+qj)di+j+qi+"di+"++ qj-"dj-"+ qj+"dj+"++ qndn minim

S(T) - S(T) = (qidi+ qjdj) - (qi+qj)di+j= qi(di-di+j) + qj(dj-di+j)=qi+qj.

Rezult S(T) = S(T) + qi+qj

NodulPeste construit de treen prima iteratie, dup care n iteratia urmtoare se intr n secventa de valori nod (q" ... qi-"qi+qjqi+"... qj-"qj+"... qn)

Conform ipotezei inductive algoritmul construieste un arbore optimal Tan-"

pentru secventa de valori nord (q" ... qi-"qi+qjqi+"... qj-"qj+"... qn) deci S(Ta

n-") minima. RezultS(Ta

n-") = S(T)

Din modul de constructie a luiTan-"

si Tan avemS(Ta

n)-S(Ta

n-")=(qidi+ qjdj) - (qi+qj)di+j= qi(di-di+j) + qj(dj-di+j)=qi+qj .

Rezult in final S(Tan) = S(Ta

n-")+ qi+qr= S(T) + qi+qj= S(T) deciTa

neste optimal.

Complexitatea : Buclafor se execut de nori .

Functiile least()si insert():

L - list nlntuit: least() - O(n)

insert() - O(#) treeO(n2)L - list nlntuit ordonat: least() - O(#)

insert() - O(n)L - heap: least() - O(logn) treeO(nlogn)

insert() - O(logn)

Obs. Metoda functioneaz si pentru arbori k-ari ( fiecare nod cu kdescendenti )

Compresiile de date. Arbori Huffman

Definirea problemei: FieD = ( D", D2, ... , Dn)un grup de date, fiecare de lungime lsiM un mesaj compus din acestedate . Exemplu:Diocteti de date siMun fisier ). Se cunoaste cDi aparenMde qiori i = ", n.S se construiasc un sistemde coduri binare pentru elementele luiDa.Ms fie de lungime minim.

Solutia: Se codific fiecare datDi, i = ", n cu un numr variabil de biti pe baza unui arbore binar cu arcele etichetateastfel:


41/74


_____________________________________________________________________________________

_______________________________________________________________________________ 4#

0 - pentru arcele de forma ( p, left(p))#- pentru arcele de forma ( p, right(p))

Arborele are nnoduri terminale cte unul asociat fiecrei dateDi. Codul asociat dateiDi va fi secventa de biti de biti (0,#)care apar ca etichete pe drumul de la rdcin laDi.

Exemplu: D = ( D#, D2, ... , Dn) = ( rosu, alb, verde, crem, bleu, galben, negru, maro) r a v c b g n m

coduri(D) = ( 000, 00#, ... , ###)

0 #

0 # 0 #

0 # 0 # 0 # 0 #

r a v c b g n m

ins, de asemenea, poate fi si coduri(D) = ( 00, 0#, #00, #0#, ##00, ##0#, ####0, #####)

0 #

0 # 0 #

r a 0 # 0 #

v c 0 # 0 #

b g n m

Obs.Pentru a codifica nobiecte sunt necesare log2n biti

Decodarea: #. Codurile sunt de aceeasi lungime . Este suficient o tabel de indirectare.2. Codurile sunt de lungime variabil. Se foloseste arborele de codare . Aceasta se bazeaz pe faptul c se

obtine un sistem de coduri care sunt "prefix distinctibile", adic i, j cod(Di) nu este prefix al secventeicod(Dj).

Exemplu: M = 0#####00 00 0#0#0##0####0 ##00 00 #00 ##0###0# a m r r a a a c n b r v g g

Lungime mesaj:M = a m r r a a a c n b r v g g

n prima codare: l(M) = #4*3 = 42 bitin a doua codare: l(M) = 40 biti


42/74


_____________________________________________________________________________________

_______________________________________________________________________________42

Obs. Problema determinrii unei codri care s minimizeze lungimea lui M se reduce la determinarea unui arbore binar culungimea drumurilor externe ponderate minime

Fie M = Di#Di2... Dik compus din datele (D#, D2, ...Dn) cu frecventele de aparitii Q = (q#, q2, ...,qn) , qi= nr. deaparitii n M ale datelor Di,atunci

l(M) = q lungime cod Di i

i

n

=

( ( ))#

= q dist Di i

i

n

=

( )#

dist(Di) - distanta de la rdcin la Di

Pentru exemplul anterior:M = a m r r a a a c n b r v g g ,D = ( b, m, v, n, c, g, r, a )Q = ( #, #, #, #, #, 2, 3, 4 )

Rezult M de forma:

M = 00 0#0#####00 00 00 #00 0###0#00 ##0##0 #0##0# -- 39 biti

a m r r a a a c n b r v g g

cu desenul din figura urmtoare:

#40 #

2 60 # 0 #

4 4 3 3 a r

0 # 0 #2 2 # 2

c g0 # 0 #

# # # #

b m v n

Obs. - Metoda este eficient atunci cnd frecventa aparitiilor este cunoscut exact, si nu estimat;- Ambele procese codor, decodor trebuie s cunoasc arborele;- Pstrarea codificrii luiMmpreun cu arborele de decodificare ridic probleme de ineficienta ocuprii spatiului;- Pentru texte se foloseste un arbore cu qiestimate statistic;

- Exemplu pentru un CD-ROM cu crti nmagazinate - se poate pstra un album 38 frunze ( alfabetul latin , plussemnele de punctuatie );

Drum minim ntr-un graf ( surs - destinatie )

Definirea problemei: Se d G = ( V, E ) un graf, e: E R+functia de etichetare. Se cere un drum (s = v#v2...vk= d),

unde dist(s,d) =

= +

#

## ),(

k

iii vve minimal.


43/74


_____________________________________________________________________________________

_______________________________________________________________________________ 43

Obs.: Exist un algoritm care da toate aceste drumuri ( cu nmultire de matrici , de cost O(n3)).

Algoritmul Greedy pentru determinarea drumurilor minime de la nodul ila toate celelalte noduri :

short_path( G, C, s, n ){// G = ( V, E ) , V = {#,2,...,n}

// C - matrice de cost C[i,j] =e i j i j E

altfel

( , ), ( , )

,

+

// folosim vectorii dist[#..n] si pred[#..n]// S - multimea nodurilor atinse

S = {s}

for i=#,,n{

dist[i] = C[s,i]pred[i] = s

}for k=2,,n-#{

fie u a.. dist[u] = min{dist[w]} // * xV\S

S = S {u} for all vV\S

{

if ( dist[v] > dist[u] + C[u,v] ){dist[v] = dist[u] + C[u,v]

pred[v] = u}

}}return (dist, pred)}

Teorema 2 . Algoritmul obtine drumurile minime de la s la orice nod vV.

Complexitatea: O(n2).

Problema rucsacului (Knapsack)

Definrea problemei: Datele problemei sunt:

obiectele: i" i2 ... in

greuttile: w" w2 ... wnprofiturile: p" p2 ... pncapacitatea: M


44/74


_____________________________________________________________________________________

_______________________________________________________________________________44

Se cere o alegere X = ( x#, x2, ... , xn) , 0 xi #, astfel nct

x w Mi ii

(*) si

x pi ii

- maxim (**)

o solutie admisibil satisface (*).

o solutie optim este admisibil si satisface (**)

Obs. #. Daca w Mii

solutia optimala este xi=#, i=#,,n. Deci problema are sens pentru w Mii

> $i astfel

condi"ia de admisibilitate a unei solu"ii devine x w Mi ii

= .

Un algoritm relativ performant se obtine pornind de la sortarea obiectelor n ordinea descresctoare a valorilor pi/wi.

greedy_knapsack (P,W,M,n)// P(#..n) - profiturile// W(#..n) - greuttile// M - capacitatea rucsacului// X(#..n) vectorul solutie// obiectele snt ordonate astfel nct P(i)/W(i) P(i+#)/W(i+#){for i=#,,n X(i) = 0; i=#;C = M; // C = capacitatea rmaswhile (C > W(i) and i n)

{C=C - W(i);

X(i) = #;i=i+#;}

if (in) X(i) = C/W(i);return (X)}

Teorema 3.Solutia generat de GREEDY_KNAPSACK este optimal.Demonstratie:Fie X=(x#,x2,,xn) solutia generat de algoritm. Din modul de constructie rezult

w xii

n

i=

#

= M.

Dac X=(#,#,.,#) rezult X optimal.

Daca X(#,#,.,#) fie j indicele pentru care xi=#, #i


45/74


_____________________________________________________________________________________

_______________________________________________________________________________ 45

w y M w y w y w y w x w y w y

M w x w y w y M w y x w y

i ii

n

i ii

j

j j ii j

n

i ii

j

i j j ii j

n

i

j j j j ii j

n

i j j j ii j

n

i

= =

= + =

= +

= + = +

= = + + = + + =

+ + = + +

# #

#

# #

#

#

# #

( )

Dac yj>xj atunci M= w yii

n

i=

#

=M w y x w yj j j i ii j

n

+ += +( )

#

>M. Imposibil. Deci yj++=

=++=+=+=

=

=

+===

==

==

0

#

##

#

#

#

##

Imposibil.Crestem acum ykpn la xk si descrestem yk+#, yk+2, ., ynatt ct este necesar astfel nct w y Mi i

i

n

= =

#

(capacitatea total rmne M). Se obtine o solutie Z=(z#,z2,,zn) cu zi=xi, i=#,,k si w y z w z yi i ii k

n

k k k( ) ( ) = = +

#

Suma ponderilor descresterilor yk+#, yk+2, ., yn este egala cu ponderea cresterii lui yk).

Pentru Z avem :

p z

p y z y p z y p p y z y w p w y z w p w

p y z y w y z w p w p y p x

i ii

n

i i k k k i i i i i k k k k k i i i i ii k

n

i

n

i k

n

i

n

i i k k k i i i k k i k

n

i

n

i ii

n

i ii

=

+ + = +

+ = >

=

= +== +=

= += = =

#

####

## #

( ) ( ) ( ) / ( ) /

[( ) ( ) ] /#

n

n relatia anterioara au fost utilizate inegalittile pi/wipi+#/wi+#, i=#n-#.

Dac Z=X rezulta o inegalitate imposibil : p xi ii

> p xi ii

. Deci presupunerea initalX nu este optimaleste fals.

Dac Z X atunci repetm (***) cu Z in locul lui Y si continum procesul pna cnd obtinem Z = X adica ipotezaX nu esteoptimal fals.

Complexitatea: O(n)


46/74


47/74


_____________________________________________________________________________________

_______________________________________________________________________________ 47

Problema se noteaz!cu : knap(#,n,M). Presupunem c!exist!o secvent!X=(x", x2, ....xn) reprezentnd o alegereoptimal!.

Exist!urm!toarele dou!variante:

#. x"=0 si atunci secventa (x2, x3, ....xn) este optimal!pentru problema knap(2,n,M).

2. x"=# si atunci secventa (x2, x3, ....xn) este optimal!pentru problema knap(2,n,M-w").

Se observ c si n acest caz principiul optimalittii se respect

**

Fies0starea initial a problemei. Presupunem c snt necesare n decizii d", d2, ....dn. Prima decizie poate lua unadin valorile multimiiD={ r", r2, .rk}. Dac!decizia d"ia valoarea rifie sistarea problemei dup!aceast!decizie, si fieRisecventa optimal! corespunz!toare subproblemei corespunz!toare starii si.. Dac! este indeplinit principiul optimalit!tiisecventa optim!global!va fi cea mai bun!din secventele: r"R", r2R2,.., rkRk.

Exemple:

Drum minim

Se caut!ntr-un graf drumul minim de la nodul i la nodul j. Fie E i={ i#, i2, .is} multimea succesorilor nodului i si fiedrumurile minime corespunz!toare de la fiecare din acesti succesori la j, anume Rk= drumul minim de la ikla j, (k=#,,s).Atunci drumul minim de la nodul i la nodul j va fi cel mai mic dintre drumurile (i Rk ), k=#,,s.

Problema rucsacului 0/#

Fie problema knap(#,n,.M) si fie 0(M) valoarea profitului maxim pentru aceast!problem!. In general pentru o problem!knap(j+#,n,Y) valoarea profitului maxim se noteaz! cu j(Y). Deoarece x# ia valori din multimea de decizii D#={0,#},avem:

0(M)= max{ #(M), #(M-w#)+p#} ( * )

***

Dac!pentru o problem!dat!este valabil principiul optimalit!tii n starea initial!, atunci se poate aplica acest principiu si laurm!toarele stari intermediare

Exemple:

Drum minim

Dac! (i, i#, i2, ..im, j) este drumul minim de la nodul i la nodul j si ikeste un nod intermediar, atunci secventa ( i, i#, ,i2,ik) este drum minim de la nodul i la nodul ik iar secventa (ik,ik+#, .j) este drum minim de la nodul ikla nodul j.

Problema rucsacului 0/#

Fie (x#,x2,xn) o secvent! alegere optimal!pentru problema knap(#,n,M). Atunci pentru orice valoare j ( j=#,n) :

(x#, x2, ..xj) este solutie optimal!pentru problema knap(#,j, =

j

i

iixw#

)

(xj+#,xj+2, xn) este solutie optimal!pentru problema knap(j+#, n, M-=

j

i

iixw#

)

Relatia anterioar!( * ) se generalizeaz!laj(Y) = max { j+#(Y), j+#(Y-wj+#) + pj+#} ( ** )

relatia (**) este o recurent!care se poate calcula stiind c! n(Y)=0 pentru orice Y num!r real.


48/74


_____________________________________________________________________________________

_______________________________________________________________________________48

****

Exemplele anterioare evidentiaz!recurente de tip forward ( n fat!). Se pot defini aceste recurente si n mod backward.

Exemple

Drum minim

Dac! (i, i#, i2, ..im, j) este drumul minim de la nodul i la nodul j, fie Ej={k ; (k,j)=arc din graf}, |E|=p multimeapredecesorilor nodului j. Pentru fiecare predecesor k fie Rkdrumul minim de la nodul i la nodul k. Evident, drumul minimgeneral va fi cel mai scurt drum din drumurile de forma (Rkj) pentru k=#,,p

Probelema rucsacului (0/#)

Dac!se noteaz!cu fi(x) valoarea optim!a problemei knap(#,i,x) se obtin recurentele:fi(x)= max { fi-#(x), fi-#(x-wi) + pi} i=#,2, n (*)

Recurentele snt rezolvabile stiind c! f0(x) = 0 x 0, f0(x) = , x < 0

Modelul metodei

Problemele ale c!ror solutii se pot obtine prin programarea dinamica sunt probleme de optim. Un prototip de astfel deproblem!este urm!torul:

S!se determine determine : optimR(x$,,xm) (#)

n conditiile n care acestea satisfac restrictii de forma

g(x$,,xm) ? 0 (2)

unde ? {}.

Prin optimse ntelege de obicei min sau maxiar ecuatia (#) se mai numeste sifunctie obiectiv.Un alt prototip este furnizatde digrafurile ponderate, unde R(x",,xm) exprima suma poderilor arcelor x",,xm iar restrictiile impun ca x",,xm s! fiedrum sau circuit cu anumite propriet!ti.

Metoda program!rii dinamice propune determinarea valorii optime prin luarea unui sir de decizii


49/74


_____________________________________________________________________________________

_______________________________________________________________________________ 49

Ex: Problema rucsacului:i(Yi) = max {i+#(Yi), i+#(Yi-wi+#) + pi+#}

unde i(Yi) = valoarea de optim pentru Knap(i+#,n,Yi), Yi= M-=

i

k

kkxw#

Notatiile din (4) conduc la urm!toarele:z=i , s=si, f(i) = optim-Knap(i+#,n,Yi) = i(Yi). Rezult!: f(i)=f(i+#)+pi+#xi+#y {0,#}, T[i,y]=i+#, s=si+#, H(i,y,f(T(i,y)))=f(i+#)+ pi+#yH(i,0,f(T(i,0))) = H(i,0,f(i+#)] = f(i+#) = i+#(Yi+#) = i+#(Yi)H(i,#, f(T(i,#))) = H(i,#,f(i+#)] = f(i+#)+pi=i+#(Yi+#)+pi+#=i+#(Yi- wi+#)+pi+#

Rezult!: f(i)= max {i+#(Yi), i+#(Yi-wi+#) + pi+#}

Principiul de optim implic!proprietatea de substructur!optim!a solu"iei, care afirm!c!solu#ia optim!a problemei includesolu#iile optime ale subproblemelor sale. Aceast! proprietate este utilizat! la g!sirea solu"iilor corespunz!toare stariloroptime. n general, programele care implementeaz!modelul dat de programarea dinamic!au dou!p!rti:

#. Determinarea valorilor optime date de sirul de decizii optime, prin rezolvarea ecuatiilor (4)2. Construirea solutiilor (valorilorxi care dau optimul) corespunz!toare st!rilor optime pe baza valorilor calculate n prima

parte, utiliznd proprietatea de substructur!optim!.

Eficien%a metodei

n general, nu se recomand! scrierea unui program recursiv care s! calculeze valorile optime. In cazul programelorrecusive, dac!n procesul de descompunere problem!subproblem!, o anumit!subproblem!apare de mai multe ori, eava fi rezolvat! ori de cte ori apare. Asa se procedeaz! n cazul aplic!rii metodei Divideand-Conquer. Este mult maiconvenabil ca valorile optime corespunz!toare subproblemelor s!fie memorate ntr-un tablou $i apoi combinate pe bazaecuatiilor (4) pentru a obtine valoarea optim!a unei subprobleme. n acest fel orice subproblem!este solu"ionat!o singur!dat!, iar calcularea valorilor optime se face de la subproblemele mai mici la cele mai mari (bottom-up). Prin memorareavalorilor optime ntr-un tablou se reduce si timpul de calcul pentru optimul unei subprobleme, datorit! accesului la unelement dintr-un tablou n O(#) timp.

Complexitatea algoritmilor care implementeaz! metoda program!rii dinamice depinde direct de tipul de recursivitateimplicat de recurentele rezultate prin aplicarea principiului optimalit!tii. n cazul recursiei liniare valorile optime pot ficalculate n timp liniar. In cazul recursiei n cascad! rezult! 2n subprobleme. De obicei n aceste situatii se studiaz!

posibilitatea redefinirii starilor astfel nct sa rezulte o recursie liniar!

Comparatie intre metoda program$rii dinamice si metoda greedy

#. - Metoda greedy utilizeaz!proprietatea alegerii locale: solutia globala optim!este construita prin selectii optime locale- Metoda program!rii dinamice utilizeaz!proprietatea de substructur!optim!: solutia optim!a unei probleme include n

structura sa solu"iile optime ale subproblemelor

2. - Alegerea local! n cazul metodei greedy nu depinde de alegerile ulterioare, deci metoda greedy nu are caracterrecursiv.

- Proprietate de substructur!optim!utilizat!n programarea dinamic!are un caracter recursiv: pentru a construi solutiaoptima a problemei este necesar! cunoasterea solutiilor subproblemelor. Deci rezolvarea problemei implic!rezolvarea subproblemelor.

3. - Parcurgerea arborelui subproblemelor in cazul metodei greedy se face n manier! top-down- Parcurgerea arborelui subproblemelor in cazul metodei programarii dinamice este facut!n stil bottom-up


50/74


_____________________________________________________________________________________

_______________________________________________________________________________50

Studii de caz

Problema rucsacului (0/#)

Relatiile de recurent! backward rezultate din aplicarea principiului de optim sint urm!toarele:fi(x)= max { fi-#(x), fi-#(x-wi) + pi} i=#,2, n (*)unde fi(x) este valoarea optim!a problemei knap(#,i,x).

Recurentele snt rezolvabile stiind c! f0(x) = 0 x 0, f0(x) = , x < 0

Exemplu : n=3, (w#, w2 , w3) = (2 , 3 , 4), (p#, p2 , p3) = (#, 2 , 5), M = 6

f0(x) = 0 g#(x) = f0(x-w#)+p#= f0(x-2) + #

f#(x) = max{f0(x) , f0(x-2) + #} g2(x) = f#(x-w2) + p2= f#(x-3) + 2

f2(x) = max{f#(x) , f#(x-3) + 2} g3(x) = f2(x-w3) + p3= f2(x-4) + 5

7/25/2019 Mitica Cr

Mitica Craus - Proiectarea Algoritmilor

Documents

Transcript of Mitica Craus - Proiectarea Algoritmilor