QReferate - referate pentru educatia ta.
Cercetarile noastre - sursa ta de inspiratie! Te ajutam gratuit, documente cu imagini si grafice. Fiecare document sau comentariu il poti downloada rapid si il poti folosi pentru temele tale de acasa.



AdministratieAlimentatieArta culturaAsistenta socialaAstronomie
BiologieChimieComunicareConstructiiCosmetica
DesenDiverseDreptEconomieEngleza
FilozofieFizicaFrancezaGeografieGermana
InformaticaIstorieLatinaManagementMarketing
MatematicaMecanicaMedicinaPedagogiePsihologie
RomanaStiinte politiceTransporturiTurism
Esti aici: Qreferat » Documente informatica

Metoda Divide-and-Conquer (divide-et-impera)



Metoda Divide-and-Conquer (divide-et-impera)





Descrierea metodei


Prin aceasta metoda, o problema data P este divizata recursiv intr-un numar de subprobleme independente. Solutia unei probleme situate pe un anumit nivel al recursiei, se compune din solutiile subproblemelor sale. Divizarea unei probleme se face pina cind se obtin subprobleme de dimensiuni mici ce pot fi rezolvate prin meteode elementare.


Modelul metodei

Metoda poate fi descrisa astfel:


D_and_C (P(n));



Deoarece metoda are un caracter recursiv, aplicarea ei trebuie precedata de o generalizare de tipul problema subproblema prin care dimensiunea problemei devine o variabila libera.


Eficienta metodei

Vom presupune in continuare ca dimensiunea problemei Pi este ni si satisface ni n/b , b >1. De asemenea vom presupune ca divizarea problemei in subprobleme si asamblarea solutiilor necesita timpul O(nk). Complexiatea timp T(n) a algoritmului D_and_C este data de urmatoarea relatie de recurenta:




Teorema 1: Daca n >n0 atunci :



Demontratie:

Fara a restringe generalitatea se poate presupune n=bm n0 . De asemenea se mai poate presupune ca T(n) = c n0k daca n n0 si T(n ) = a T(n/b) + c nk  daca n>n0 . Pentru n>n0 rezulta:





Se disting cazurile:


a > bk . Seria este convergenta si deci sirul sumelor partiale este convergent. De aici rezulta T(n) = = =

a = bk . Rezulta am = bkm = cnk si de aici T(n) = =

a < bk . Avem T(n)=

QED.



Daca pentru fiecare nivel r al recursiei, subproblemele Pi(r), i=1,,q(r), ale acestui nivel satisfac conditia ca d(Pi(r)) (1/b) d(PT(Pi(r))) unde d(Pi) reprezinta dimensiunea subproblemei Pi, PT problema tata iar b este o constanta pozitiva supraunitara atunci adincimea recursiei este logaritmica.

Relativ la arborele de calcul, "divide-and-conquer" realizeaza parcurgerea acestuia in stil " top-down" si apoi "bottom-up" . Aceasta se datoreaza recursiei.

Modelul metodei pentru cazul arborelui binar de recursie:



d_and_c_binar (P(n));


Avem:



Deci pe oricare nivel al recursiei suma dimensiunilor subproblemelor corespunzatoare acestui nivel este n.

Studii de caz

Sortarea prin prin interclasare

Pentru a sorta o secventa de n elemente ale unui vector A, se imparte vectorul in 2 segmente de lungime n/2  care sint sortate 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)



Procedura MERGE interclaseaza secventele sortate A[low÷mid] si A[mid+1÷high]. Pentru aceasta este nevoie de un vector auxiliar B, de aceeasi dimensiune cu A.


MERGE(A, low, mid, high)


I else

k=k+1;

}

while (i mid)


while (j high))

}

III  B[k] = A[j]; j=j+1;;

k=k+1;;

}

for k = low, . , high

A[k] = B[k];

}


Corectitudinea :


Lema 1: Procedura MERGE_SORT sorteaza crescator elementele vectorului A.


Demonstratie: Este suficient sa demonstram corectitudinea procedurii MERGE. Presupunem prin reducere la absurd ca in urma executiei procedurii MERGE exista un indice k pentru care B[k]>B[k+1].

Aceasta ar putea rezulta din urmatorele situatii:


1. B[k] fost initializat in bucla I iar B[k+1] in bucla II

2. B[k] a fost initializat in bucla I iar B[k+1] in bucla III


Cazul 1. Aceasta inseamna ca imediat dupa initializarea elementului B[k] situatia indicilor i si j este urmatoarea : i mid si j > high. Deci A[i] >= A[high], B[k] = A[high] si B[k+1] = A[i]. Din B[k] > B[k+1] 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 urmatoarea : j high si i > mid. Deci A[mid] < A[j], B[k] = A[mid] si B[k+1] = A[j]. Din B[k] > B[k+1] rezulta ca A[mid] >A[j] > A[mid]. Absurd.


Complexitatea :


Lema 2.Timpul de executie al algoritmului MERGE_SORT este:

Demonstratie: Consideram: n = 2k;

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


T(n) = 2 T(n/2) + n = 2 T(n/4) + n/2) + n = = 22·T(n/22) + 2n= 22 (2·T(n/23) + n/22) + 2n =
= 23
T(n/23) + 3n = = 2k T(n/2k) + k n T T(n) = k n = n log2n , pentru ca n = 2k , si, deci, k=log2n


Asadar complexitatea algoritmului este O(n log n)


Sortarea rapida (C.A.R. Hoare)


Pentru a sorta o secventa de n elemente ale unui vector A, se partitioneaza vectorul in 2 segmente dupa schema urmatoare utilizind un element cu statut special numit pivot.


Urmeaza apoi sortarea recursiva a secventelor separate de pivot.   


Quik_Sort(A, low, high)


Pseudocodul pentru functia partition:


Partition(A, low, high)


interchange (A[h], A[low])

return(h);



Procedura Partition considera pivotul ca fiind: A[low]. Indicele l parcurge vectorul de la stanga la dreapta, iar indicele h parcurge vectorul de la dreapta la stanga. Ei se apropie pana se intalnesc (l=h). Deci, l lasa in urma numai elemente A[i] pivot, iar h lasa in urma numai elemente A[i] > pivot.


Ciclul I while inseamna ca inainteaza l cat timp A[l] pivot. Acest ciclu se opreste pe conditia A[l] > pivot, fixandu-se aici.

Ciclul II while insemna ca inainteaza h cat timp A[h] > pivot. Acest ciclu se opreste pe conditia A[h] pivot, fixandu-se aici.


Cele doua pozitii se schimba, astfel incat sa se permita inaintarea indicilor mai departe.

Corectitudinea:


Lema3: Procedura Quick_Sort sorteaza crescator elementele vectorului A.


Demonstratie: Inductie dupa n.

Pasul 1. Pentru un tablou unidimensional A de dimensiune 2 evident algoritmul functioneza corect.

Pasul 2. Presupenem ca procedura Quick_Sort functioenaza corect pentru tablori unidimensionale A de dimensiuni n si demostram ca functioneaza corect si pentru A de dimensiune n+1:

Prodedura Partition separa vectorul A in doua segmente S1 cu elemente pivot si S2 cu elemente > pivot.

Procedura Quick_Sort aplicata asupra vectorilor S1 si S2 functioneza conform ipotezei de inductie.

Rezulta in final A = S1 S2 . Datorita proprietatilor pivotului si a vectorilor S1 si S2 vectorul rezultat A este sortat crescator.


Complexitatea:


Lema 4 Timpul de executie al algoritmului Quick_Sort este:

Demonstratie:

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

Problema se imparte in 2 subprobleme: P(n) P(n-1) , P(0).

Numarul de comparatii pentru functia Partition este (n-1). Vectorul se parcurge in doua directii, dar o singura data.

Rezulta ca timpul de functionare al algoritmului Quick_Sort este:

Rezolvand 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.


Spatiul ocupat de algoritmul Quick-Sort


Quick_Sort(A, low, high)



Avem in acest algoritm doua apeluri recursive.


Cazul cel mai defavorabil:

Consideram consumul de memorie in stiva : M(n) = c + M (n - 1) T M(n) = O(n) T un ordin de complexitate mare.

Pentru reducerea consumului de memorie, se concepe un alt algoritm la Quick_Sort, astfel incat un apel sa fie rezolvat recursiv, iar celalalt apel iterativ.




Quick_Sort(A, low, high)


else


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


Nu se poate descarca referatul
Acest document nu se poate descarca

E posibil sa te intereseze alte documente despre:


Copyright © 2024 - Toate drepturile rezervate QReferat.com Folositi documentele afisate ca sursa de inspiratie. Va recomandam sa nu copiati textul, ci sa compuneti propriul document pe baza informatiilor de pe site.
{ Home } { Contact } { Termeni si conditii }