Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  


AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


Metoda divide et impera

c

+ Font mai mare | - Font mai mic





DOCUMENTE SIMILARE

Trimite pe Messenger
STRUCTURI DE DATE
Pointeri si adrese
Caractere speciale si de punctuatie
ARBORI
SUBPROGRAME C / C++
Constanta zero
Instructiunea For
Gestiunea ecranului in mod text
Operatori relationali
Bazele

TERMENI importanti pentru acest document

Metoda divide et impera

Prezentarea metodei




Metoda divide et impera (in traducere ”imparte si stapaneste”) consta in impartirea repetata a unei probleme de dimensiune mai mare, in doua sau mai multe subprobleme de acelasi tip, urmata de combinarea rezultatelor subproblemelor, pentru a obtine rezultatul problemei initiale.

Pentru precizari, sa presupunem ca se da un tablou A = (a1,…,an) si ca trebuie efectuata o prelucrare oarecare asupra elementelor sale. Mai mult, presupunem ca pentru orice p, q naturali cu 1 p < q n, exista m natural cu p m q–1 astfel incat prelucrarea secventei se poate face prelucrand subsecventele , si apoi combinand rezultatele pentru a obtine rezultatul intregii secvente .

Varianta recursiva a metodei divide et impera este urmatoarea:

PROCEDURA DIVIMP(p, q, r);

BEGIN

IF q – p l

THEN PRELUC(p, q, r)

ELSE BEGIN

DIVIDE (p, q, m);

DIVIMP(p, m, r1);

DIVIMP(m+1, q, r2);

COMBIN(r1, r2, r);

END;

ENDIF;

END;

Avem urmatoarele semnificatii:

p q m s-au definit mai sus;

r reprezinta rezultatul secventei ;

l reprezinta lungimea maxima a secventei , pentru care prelucrarea se poate face direct;

PRELUC reprezinta numele procedurii care realizeaza prelucrarea secventei , furnizand rezultatul r;

DIVIDE reprezinta numele procedurii care realizeaza impartirea secventei in subsecventele si , furnizand valoarea m;

COMBIN reprezinta numele procedurii care realizeaza combinarea rezultatelor r1 si r2 ale prelucrarii subsecventelor , , furnizand rezultatul r al prelucrarii secventei .

Procedura se apeleaza prin DIVIMP(1, n, r).

Metoda divide et impera se poate reprezenta sub forma unui arbore binar plin, in care fiecarei secvente , i se asociaza un nod etichetat cu (p, q) in modul urmator:

nodul radacina este etichetat (1, n);

succesorii nodului (p, q) sunt etichetati (p, m) si (m+1, q);

nodurile terminale sunt etichetate (p, q) cu q – p l.

Cazul general se refera la situatia in care o problema de dimensiune n, notata P(n), este impartita in s subprobleme de dimensiune n / n0, notate P1(n/n0), … , Ps(n/n0).


Daca se noteza cu T(n) timpul cerut de prelucrarea unei probleme de dimensiune n, atunci avem

unde t0 este o constanta strict pozitiva si t(n) este timpul necesar combinarii rezultatelor subproblemelor P1(n/n0),…, Ps(n/n0).

Studiem urmatoarele cazuri:

Cazul 1 s = 2, n0 = 2.


In acest caz avem

Teorema 4.3

Daca t(n) = cn cu constanta c > 0, atunci T(n) = O(n log2n).

Demonstratie

Daca n = 2k > l, atunci se arata prin inductie dupa i ca

T(n) = T(2k) = 2i T(2k - i) + c 2k i , 1 i < k

Pentru i = 1 se obtine

T(n) = T(2k) = 2 T(2k – 1) + c 2k

care este adevarata.

Se presupune ca este adevarata relatia

T(n) = T(2k) = 2i T(2k – i) + c 2k i

si sa demonstram ca

T(n) = T(2k) = 2i+1 T(2k – i – 1) + c 2k (i+1)

Avem

2i+1 T(2k–i–1) + c 2k (i+1) = 2 2i T(2k–1–i) + 2 c 2k – 1 i + c 2k =

(2i T(2k–1–i) + c 2k -1 i) + c 2k = 2 T(2k-1) + c 2k = T(2k) = T(n).

Consideram ko I N, astfel incat . Evident ca avem k0 < k si luam i = k – k0. De asemenea, se tine cont ca , k – k0 < k, . Rezulta:

Deci T(n) = O(n log2n)

Daca 2k < n < 2k+1, atunci n se majoreaza la 2k+1

Cazul 2 s > 2, n0 = 2

Exista probleme care se incadreaza in acest caz. De exemplu, inmultirea a doua numere a si b fiecare cu n cifre binare. Daca n este par, atunci a si b se pot scrie sub forma a = a1 2n/2 + a2 si b = b1 2n/2 + b2 cu a1, a2, b1, b2, numere cu n / 2 biti. Avem a b = a1b12n + (a1b2 + a2b1) 2n/2 + a2b2 = c12n + (c3c4 – c1 – c2) 2n/2 + c2, unde c1 = a1b1, c2 = a2b2, c3 = a1+ a2, c4 = b1+ b2. Deci, pentru a b sunt necesare trei inmultiri (c1 = a1b1, c2 = a2b2, c3c4) de doua numere de cậte n/2 biti. In acest exemplu avem s = 3, n0 = 2.



In acest caz T(n) este :

Teorema 4.4

Daca t(n) = c n, cu constanta c > 0, atunci

Demonstratie

Daca n = 2k > l, atunci se arata prin inductie dupa i ca :

T(n) = T(2k) = si T(2k-i) + c 2k ( (s/2 )i-1 +…+ s/2 + 1), 1 ≤ i < k

Pentru i = 1 se obtine :

T(n) = T(2k) = s T(2k-1) + c2k

care este adevarata.

Presupunem adevarata relatia :

T(n) = T(2k) = si T(2k-i) + c 2k ((s/2 )i-1 + … + s/2 + 1)

si sa demonstram ca :

T(n) = T(2k) = si+1 T(2k-i-1) + c 2k ((s/2 )i +…+ s/2 + 1)

Avem

si+1 T(2k-i-1) + c 2k ((s/2)i +…+ s/2 +1) =

s si T(2k-1-i) + s c 2k-1 ((s/2)i-1 +…+ s/2 +1) + c 2k =

s(si T(2k-1-i) + c 2k-1((s/2)i-1 +…+ s/2 +1)) +c 2k =

s T(2k-1) + c 2k = T(2k) = T(n)

Consideram k0 I N astfel incật . Evident ca avem k0 < k si luam i = k–k0. De asemenea, se tine cont ca , k – k0 < k, . Rezulta:

Daca 2k < n < 2k +1 atunci n se majoreaza la 2k+1.

Cazul 3 s > 2, n0 > 2

In acest caz avem :

Teorema 4.5

Daca t(n) = c n cu constanta c > 0, atunci

Demonstratie

Cazurile s = n0 si s > n0 se trateaza la fel ca in teorema 4.5, respectiv teorema 4.6. Pentru cazul s < n0 se considera n = n0k > l si se arata prin inductie dupa i ca in teorema 4.6, ca

T(n) = T(n0k) = si T(n0k-i) + c n0k ((s / n0)i-1 + … + s/n0 +1), 1 ≤ i < k

Cosideram k0 IN astfel incật . Rezulta:

Daca n0k < n < n0k+1 atunci n se majoreaza la n0k+1.

Probleme rezolvate

Problema DI1

Sa se determine cel mai mic element dintr-un sir de numere reale A = (a1,…,am).

Aplicam metoda divide et impera. In acest caz, m = (p+q)/2 si consideram problema rezolvabila direct, daca numarul de elemente din secventa este cel mult 2, deci q – p 1. Pentru n=16, arborele binar plin atasat este prezentat in figura 4.6.

Figura 4.5

Programul in pseudocod este urmatorul:

FUNCTION MIN (A, p, q);

BEGIN

IF q – p l THEN

IF A(p) < A(q)

THEN MIN := A(p)

ELSE MIN := A(q)

ENDIF;

ELSE BEGIN

m := (p + q) / 2

r1 := MIN(A, p, m);

r2 := MIN(A, m+1, q);

IF r1 < r2

THEN MIN := r1

ELSE MIN := r2

ENDIF;

END;

ENDIF;

END;

PROGRAMUL MINDIVIMP;

BEGIN

ARRAY A(n);

READ(n, A);

WRITE(‘MINIM=’, MIN(A, 1, n));

END.

Codul sursa al programului este:

#include<stdio.h>

int min(int x, int y)

int minim(int a[20], int p, int q)

void main()

printf('Minimul din sir este: %dn',minim(a, 1, n));






Politica de confidentialitate



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 772
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2021 . All rights reserved

Distribuie URL

Adauga cod HTML in site