DIR Return Create A Forum - Home
---------------------------------------------------------
Forum Practic
HTML https://practic.createaforum.com
---------------------------------------------------------
*****************************************************
DIR Return to: Informatica
*****************************************************
#Post#: 129--------------------------------------------------
Algoritmul recursiv si relatii de recurenta
DIR By: iulianstoian
Date: January 13, 2015, 7:03 pm
---------------------------------------------------------
Exemplu:Problema turnurilor din Hanoi c1j19ji
Se dau n discuri: a1, a2, ... , an de dimensiuni diferite, cu d1
< d2 < ... < dn , di - fiind diametrul discului. Discurile
respective sunt stivuite pe o tija:
Se cere sa se deplaseze aceasta stiva pe o alta tija, folosind
ca manevra o tija auxiliara, respectƒndu-se conditia << Un disc
nu poate fi plasat decƒt peste un disc mai mare >>.
Problema P(n) a deplasarii a n discuri, se rezolva prin
deplasari succesive ale discurilor de pe o tija pe alta.
Deplasarea de pe o tija pe alta este echivalenta cu deplasarea a
n-1 discuri de pe tija intiala
(ti) pe tija de manevra, apoi plasarea celui mai lung disc pe
tija finala, pentru ca la sfƒrsit sa se aduca de pe tija de
manevra (tm), pe tija finala
(tf), cele n-1 discuri deplasate.
Primele miscari s-ar figura astfel:
Procedura Hanoi:
Hanoi(n, ti, tf, tm)
A if(n=1) then muta (ti, tf) //deplaseaza discul superior // de
pe ti pe tf else | Hanoi(n-1, ti, tm, tf)
| muta(ti, tf)
|_ Hanoi(n-1, tm, tf, ti)
S
Pentru o problema P(1) , timpul T(1) = 1 , pentru o mutare.
Pentru P(n) , timpul:
(1)
Dorim sa aflam ordinul de complexitate a lui T(n).
Asociem relatiei (1) ecuatia caracteristica:
Facƒnd identificarea:
Ordinul este O(2n), adica o complexitate exponentiala.
Relatii de recurenta. Clasele relatiilor de recurenta
1.f(n) = aùf(n - 1) + b x0 = aùx0 + b
Prin scaderea celor doua relatii, rezulta un algoritm
exponential cu baza a: f(n) - x0 = a (f(n-1) - x0)
2.f(n)=aùf(n-1)+bùf(n-2) f(n) = tü => tü = aùt(la n-1) + bùt(la
n-2)
Facƒnd n = 2, tý = aùt + b , cu urmatoarele cazuri: a) t1 , t2
apartin R => solutia ecuatiei este de forma:
f(n)=alfaùt1ü+betaùt2ü iar alfa si beta se calculeaza din
conditiile initiale: cu x1 si x2 constante.
Astfel, este rezolvata ecuatia recursiva. b) t1 = t2 = t Solutia
este de forma: c) t1, t2 C Solutia este de forma:
In care si C, = (conjugat) solutia trigonometrica:
3.Clasa de relatii de recurenta pentru algoritmi de tip "divide
et impera"
Exemplu: Algoritmul Merge Sort (sortare prin interclasare)
Pentru a sorta o secventa de n elemente ale unui vector A, se
Œmparte vectorul
Œn 2 segmente de lungime n/2 pe care le sorteaza separat
recursiv, dupa care urmeaza interclasarea.
Pseudocod:
Procedura MERGE_SORT primeste ca argumente A - vectorul de
sortat, si doi indici care delimiteaza o portiune din acest
vector. Apelul initial va fi
MERGE_SORT(A, 1, n).
MERGE_SORT(A, low, high)
A if(low high) return else | |½ low + high ½|
| mid=| ---------------- | //partea Œntreaga
| |_ 2 _|
| MERGE_SORT(A, low, mid) //sortare separata
| MERGE_SORT(A, mid+1, high) //sortare separata
|_MERGE(A, low, mid, high) //interclasare
S
Procedura MERGE interclaseaza secventele sortate Aalowömidi si
Aamid+1öhighi.
Pentru aceasta este nevoie de un vector auxiliar B, de aceeasi
dimensiune cu A.
MERGE(A, low, mid, high)
A i=low; j=mid+1; k=low;
while i mid and j high do
|½ if Aaii <A aji then Baki=Aaii; i=i+1
| else Baki = Aaji; j=j+1
|_ k = k+1
while i mid do
|½ Baki = Aaii; i=i+1
|_ k = k+1
whilej high do
|½ Baki = Aaji; j=j+1
|_ k = k+1 for k=low to high do
Aaki = Baki;
S
Aratam complexitatea procedurii MERGE_SORT: O(nlog n)
Aceasta functie cere pentru o secventa cn operatii.
Timpul de executie al algoritmului este:
Consideram: n = 2k;
T(n) = 2T(n/2) + n = 2(2T(n/4) + n/2) + n = ... = 22úT(n/22) +
2n=
22 (2úT(n/23) + n/22) + 2n =
= 23T(n/23) + 3n = ... = 2kT(n/2k) + kn T(n) = kn = nlog2n ,
pentru ca n = 2k , si, deci, k = log2n.
Asadar complexitatea algoritmului este O(nlog n).
Pentru a rezolva problema de dimensiune n, se rezolva pentru a
probleme de dimensiune n/b, iar combinarea rezultatelor celor a
prbleme, duce la lg(n) operatii.
Se demonstreaza, analog, si relatia de recurenta:
Solutia acestei ecuatii de recurenta este:
Utilizƒnd aceste retete putem calcula complexitatile pentru:
algoritmul Merge_Sort: a = 2 , b = 2 , k = 1 , bk = a
complexitatea O(nklog n) algoritmul Binary_Search: a = 1 , b = 2
, k = 0 complexitatea
O(n0log n) = O(log n), (situatia ak= b).
4.Relatii de recurenta cu istorie completa
Exemplu:
Exemplu: Algoritmul Quick_Sort
Quik_Sort(A, low, high)
A if(high low) then
|½ k= Partition(A, low, high) // procedura de |
// partitionare |
| Quick_Sort (A, low, k-1)
|_ Quick_Sort(A, k+1, high)
S
Pseudocodul pentru functia partition:
Partition(A, low, high)
A l= low; h= high; x= Aali;
while (l <h) do
I |½ while (Aali x) and (l _high)
| do l= l+1
II | while (Aali >x) and (h low)
| do h= h-1
|_ if (l <h) then interchange (Aali, Aahi) interchange (Aahi,
Aalowi) return(h);
S
Algoritmul considera pivotul ca fiind: Aalowi. Indicele l
parcurge vectorul de la stƒnga la dreapta, iar indicele h
parcurge vectorul de la dreapta la stƒnga. Ei se apropie pƒna se
Œntƒlnesc (l = h). Deci, l lasa Œn urma numai elemente Aaii
pivot, iar h lasa Œn urma numai elemente Aaii pivot.
Ciclul I while Œnseamna ca Œnainteaza l cƒt timp Aali pivot.
Acest ciclu se opreste pe conditia
Aahi pivot, fixƒndu-se aici.
Ciclul II while Œnsemna ca Œnainteaza h cƒt timp Aahi pivot.
Acest ciclu se opreste pe conditia
Aahi pivot, fixƒndu-se aici.
Cele doua pozitii se schimba, astfel Œncƒt sa se permita
Œnaintarea indicilor mai departe.
Pentru aflarea complexitatii, 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 elementele secventei, deci, va fi
plasat Œn ultima pozitie din secventa.
Problema se Œmparte Œn 2 subprobleme: P(n) P(n-1) , P(0).
Numarul de comparatii pentru functia Partition este (n-1).
Vectorul se parcurge
Œn doua directii, dar o singura data.
Rezulta ca timpul de functionare al algoritmului Quick_Sort
este:
Rezolvƒnd aceasta ecuatie, avem:
unde: T(1) este 0 (nu se partitioneaza). Rezulta:
Aceasta suma este de complexitate O(n2). Rezulta ca este un
algoritm ineficient
Studiul complexitatii algoritmului Quick_Sort Œn caz mediu
Pentru complexitatea medie trebuie considerata probabilitatea
tuturor aparitiilor datelor de intrare. Consideram ca orice
configuratie de date la intrare este egal probabila.
Probabilitatea ca pivotul sa fie plasat Œn pozitia k este egala
pentru . Asadar, pivotul va fi plasat Œn pozitia k prin
partitionare, cu o probabilitate egala cu 1/n, pentru .
Suma tuturor probabilitatilor este 1. Evenimentul este plasarea
pivotului Œn pozitia k. Consideram Ti(n) timpul de executie al
algoritmului Quick_Sort atunci cƒnd pivotul este plasat Œn
pozitia i:
Rezulta:
Timpul mediu va fi o medie aritmetica:
Dezvoltƒnd,
(Facƒnd schimbarea de variabila j = n - i + 1)
Rezulta relatia de recurenta cu istorie completa:
Aceasta se rezolva astfel: Œnmultind relatia cu n rezulta:
Scriem acum relatia Œnlocuind pe n cu n+1:
Si scazƒndu-le acum membru cu membru rezulta: care se Œnmulteste
cu: ,
Notam:
Facƒnd o majorare:
(un element nu se ordoneaza).
Rezulta: si este aria zonei de sub graficul functiei .
unde O(nln n) este complexitatea acestei functii.
Analiza spatiului de memorie consumat Œntr-un algoritm
Algoritmi recursivi
Algoritmii recursivi consuma memorie suplimentara pentru
simularea recursivitatii.
Fie urmatoarea procedura recursiva:
parcurgere(l) // l - lista Œnlantuita (pointer la primul
element)
A if(l 0)
|½ parcurgere(link(l))
|_ prelucrare(data(l)) // exemplu: afisare
S
Functia afiseaza o lista invers, de la coada la cap.
Apelul functiei se face astfel: se creeaza Œn stiva programului
o "Œnregistrare de activare" Œn care sunt memorate:
- parametrii de apel;
- adresa instructiunii de retur (cu care va continua programul
dupa terminarea executiei functiei); se rezerva spatiu pentru
variabile locale. se executa instructiunile functiei care
folosesc pentru parametri si variabile locale din "Œnregistrarea
de activare"; se scoate din stiva "Œnregistrarea de activare"
(decrementarea vƒrfului stivei), stiva fiind ordonata; se
continua cu instructiunea data de adresa de retur memorata Œn
"Œnregistrarea de activare".
Asadar, variabilele globale (statice) sunt memorate Œntr-o zona
de memorie fixa, mai exact Œn segmentele de date. Variabilele
automate (locale) se memoreaza Œn stiva, iar variabilele
dinamice Œn "heap"-uri (cu malloc Œn C, si cu new Œn C++).
Consumul de memorie al algoritmului recursiv este proportional
cu numarul de apeluri recursive ce se fac. Variabilele recursive
consuma mai multa memorie decƒt cele iterative. La prelucrarea
unei liste, daca primul element nu este vid, se prelucreaza
acesta, urmƒnd apoi ca restul listei sa fie considerata ca o
noua lista mai mica, etc.
De exemplu, algoritmul Quick_Sort:
Quick_Sort(A, low, high)
A if(low < high)
|½ k = Partition(A, low, high)
| Quick_Sort(A, low, k-1)
|_Quick_Sort(A, k+1, high)
S
Avem Œn acest algoritm doua apeluri recursive.
Cazul cel mai defavorabil:
Consideram consumul de memorie Œn stiva : M(n) = c + M (n - 1)
M(n) = O(n) un ordin de complexitate mare.
Pentru reducerea consumului de memorie, se concepe un alt
algoritm la
Quick_Sort, astfel Œncƒt un apel sa fie rezolvat recursiv, iar
celalalt apel iterativ.
Quick_Sort(A, low, high)
A
while (low < high)
|½ k = Partition(A, low, high)
| if( k-low > high-k)
| |½ Quick_Sort(A, k+1, high)
| |_high = k-1
| else
| |½ Quick_Sort(A, low, k-1)
| _|_low = k-1
S
Necesarul de memorie pentru aceasta este M(n) c + M(n/2),
Œnsemnƒnd ca oricare ar fi secventa mai mica, ea este decƒt
jumatatea M(n) = O(log n) am redus ordinul de complexitate.
Liste generalizate
Definitie:
Data o multime de elemente (atomi), se numeste lista
generalizata o secventa finita (1, 2, ... , n), Œn care i sunt
atomi.
Exemplu: A = (a, b, c)
B = (x, A, (a, c), ( ))
| | | \ atom lista lista lista vida
Observatie: Listele generalizate pot sa aiba elemente comune. Se
permite definirea de liste recursive.
Reprezentarea listelor generalizate
Presupunem o lista de forma: (tag, data, link) Œn care tag este
o eticheta
A0,1S.
Daca tag = 0 nodul va corespunde unui element atomic cƒmpul data
va contine atomul respectiv.
Daca tag = 1 nodul va corespunde unei subliste cƒmpul data va
semnifica legatura la primul element al sublistei; link este
legatura pentru urmatorul nod din lista.
Fie urmatoarele primitive de selectie pentru un nod de adresa p:
p adresa unui nod; link(p) cƒmpul "link" din nodul indicat de p;
Notam: tag(p) cƒmpul "tag" din nodul indicat de p data(p) cƒmpul
"data" din nodul indicat de p
Fie urmatoarele liste:
D = ( )
A = (a, (b, c))
B = (A, A, ( ))
C = (a, C) cu urmatoarele reprezentari:
D : o lista vida Œnseamna un pointer nul
Ne propunem sa dam nume unei subliste, deci daca tag = 1, adica
tag(p) = 1 data(p) va fi adresa unei structuri ce contine:
Asadar, obtinem urmatoarea reprezentare:
Operatii la liste generalizate: functia insert, este
asemanatoare cu cea de la liste Œnlantuite. Elementul ce se
insereaza poate fi un atom sau o sublista; functia del ( )
trebuie sa tina seama de existenta unor liste comune. Deci, este
necesara pastrarea Œn elementul ce contine numele listei A si a
unui indicator care sa contorizeze numarul de referinte ale lui.
Exemplu:
Numai daca acest indicator este 0, se face stergerea efectiva a
listei.
Traversarea listelor generalizate
Traversarea listelor generalizate presupune prelucrarea
elementelor listei, si a elementelor sublistelor componente.
Exemplu: O functie de copiere si o functie de test de egalitate
a doua liste generalizate, realizate recursiv si iterativ.
Functia returneaza o copie a listei. Copie mai Œntƒi primul
element, si apoi recursiv restul listei:
Varianta recursiva:
Copy (l) // l - lista Œnlantuita
A if (l = 0) then return (0) else |½ p = get_sp()
| data(p) = data(l)
| link(p) = Copy(link(l))
|_ return(p)
S
Copy (l) // l - lista generalizata
A if (l = 0) then return (0) else |½ p = get_sp()
| if (tag(l) = 0) then data(p) = data(l)
| else data(p) = Copy(data(l))
| link(p) = Copy(link(l))
|_ return(p)
S
Functia pentru testarea egalitatii este:
isEqual (l1,l2) // procedura tratata iterativ
A p1 = l1; p2 = l2
while(p1 0 and p2 0)
|½ if (data(p1) data(p2)) then return (FALSE)
| p1 = link(p1)
|_ p2 = link(p2) return(p1 = p2)
S isEqual (l1,l2) // procedura tratata recursiv
A p1 = l1; p2 = l2
while(p1 0 and p2 0)
|½ if (tag(p1) tag(p2)) then return (FALSE)
| if (tag(p1) = 0 and data(p1) data(p2)) then return (FALSE)
| if (tag(p1) = 1 and not isEqual(data(p1),data(p2)) then return
(FALSE)
| p1 = link(p1)
|_ p2 = link(p2) return (p1 == p2)
S
*****************************************************
Page 1 of 1