Metoda divide et impera

Laborator
7.5/10 (2 voturi)
Conține 1 fișier: docx
Pagini : 13 în total
Cuvinte : 1646
Mărime: 68.15KB (arhivat)
Cost: Gratis
Profesor îndrumător / Prezentat Profesorului: Catruc Mariana

Cuprins

Introducere

1.Scopul lucrarii

2.Sarcina lucrarii

3.Listingul programului

4.Reprezentarea rezultatelor

Concluzie

Extras din document

Introducere

Divide et impera se bazează pe principiul descompunerii problemei în două sau mai multe subprobleme (mai ușoare), care se rezolvă, iar soluția pentru problema inițială se obține combinând soluțiile subproblemelor. De multe ori, subproblemele sunt de același tip și pentru fiecare din ele se poate aplica aceeași tactică a descompunerii în (alte) subprobleme, până când (în urma descompunerilor repetate) se ajunge la probleme care admit rezolvare imediată.

Nu toate problemele pot fi rezolvate prin utilizarea acestei tehnici. Se poate afirma că numărul celor rezolvabile prin "divide et impera" este relativ mic, tocmai datorită cerinței ca problema să admită o descompunere repetată.

Divide et impera este o tehnică ce admite o implementare recursivă. Principiul general prin care se elaborează algoritmi recursivi este: "ce se întâmplă la un nivel, se întâmplă la orice nivel" (având grijă să asigurăm condițiile de terminare). Așadar, un algoritm prin divide et impera se elaborează astfel: la un anumit nivel avem două posibilități:

1. s-a ajuns la o problemă care admite o rezolvare imediată (condiția de terminare), caz în care se rezolvă și se revine din apel;

2. nu s-a ajuns în situația de la punctul 1, caz în care problema curentă este descompusă în (două sau mai multe) subprobleme, pentru fiecare din ele urmează un apel recursiv al funcției, după care combinarea rezultatelor are loc fie pentru fiecare subproblemă, fie la final, înaintea revenirii din apel.

Dupa cum sugereaza si numele 'desparte si stapaneste 'etapele rezolvarii unei probleme (numita problema initiala) in DIVIDE ET IMPERA sunt :

- descompunerea problemei initiale in subprobleme independente similare problemei de baza ,de dimensiuni mai mici;

- descompunerea treptata a subproblemelor in alte subprobleme din ce in ce mai simple ,pana cand se pot rezolva imediata prin algoritmul simplificat;

- rezolvarea subproblemelor simple;

- combinarea solutiilor gasite pentru construirea solutiilor subproblemelor de dimensiuni din ce in ce mai mari;

- combinarea ultimelor solutii determina obtinerea solutiei problemei initiale.

Scopul lucrarii

- Studierea metodei divide et impera.

- Analiza și implementarea algoritmilor bazați pe metoda divide et impera.

Sarcina lucrarii

1. Studiați noțiunile teoretice despre metoda divide et impera.

2. Implementați algoritmii Mergesort și Quicksort.

3. Efectuați analiza empirică a algoritmilor Mergesort și Quicksort.

4. Faceți o concluzie asupra lucrării efectuate.

Algoritmul formal al metodei divide et impera:

function divimp(x)

{returnează o soluție pentru cazul x}

1: if x este suficient de mic

2: then return adhoc(x)

3: {descompune x în subcazurile x1, x2, , xk}

4: for i 1 to k do yi divimp(xi)

5: {recompune y1, y2, , yk în scopul obținerii soluției y pentru x}

6: return y

unde adhoc este subalgoritmul de bază folosit pentru rezolvarea micilor subcazuri ale problemei în cauză.

Mergesort (sortarea prin interclasare)

Fie T[1 .. n] un tablou pe care dorim sa-l sortam crescător. Prin tehnica divide et impera putem proceda astfel: separăm tabloul T în două părți de mărimi cât mai apropiate, sortăm aceste părți prin apeluri recursive, apoi interclasăm soluțiile pentru fiecare parte, fiind atenți să păstrăm ordonarea crescătoare a elementelor. Obținem următorul algoritm pentru rezolvarea unei subprobleme:

procedure mergesort (T, p, r) 1: if p < r

2: then q (p+r/2)

3: mergesort(T,p,q)

4: mergesort(T,q+1,r)

5: merge(T,p,q,r)

Preview document

Metoda divide et impera - Pagina 1
Metoda divide et impera - Pagina 2
Metoda divide et impera - Pagina 3
Metoda divide et impera - Pagina 4
Metoda divide et impera - Pagina 5
Metoda divide et impera - Pagina 6
Metoda divide et impera - Pagina 7
Metoda divide et impera - Pagina 8
Metoda divide et impera - Pagina 9
Metoda divide et impera - Pagina 10
Metoda divide et impera - Pagina 11
Metoda divide et impera - Pagina 12
Metoda divide et impera - Pagina 13

Conținut arhivă zip

  • Metoda divide et impera.docx

Alții au mai descărcat și

Sortarea

Metodele de sortare se clasifică în metode directe şi metode avansate. Metodele directe se bazează, pe algoritmi de dificultate redusă, uşor de...

Metoda Backtracking

Metoda Backtracking - metoda „revenirii”, definită şi elaborată de AI (Artificial Intelligence); este o metodă folosită în cazul problemelor în...

Hackeri

Hackerii sunt pasionati ai informaticii, care, de obicei au ca scop „spargerea” anumitor coduri, baze de date, pagini web etc. Ei sunt considerati...

Programarea Calculatorului

Scopul lucrării: Evidenţierea nivelului de cunoştinţe a fiecărui student la informatică, în mod deosebit algoritmizarea, pentru elaborarea unui...

Limbajul Client JavaScript

Exemplu 1: crearea unui tablou <html> <body> <script type="text/javascript"> var mycars = new Array() mycars[0] = "Saab" mycars[1] = "Volvo"...

Laboratoare C

Fie a, b doua numere intregi, date de la tastatura. Sa se realizeze, in C/C++, programe care afiseaza: a) suma lor b) diferenta lor c) produsul...

Comenzi de Baza - Linux

Laboratorul nr.1 - Comenzi de baza Linux Distribuţii Linux. Sistemul de fişiere Linux, tipuri de fişiere Unix, inode. Caracteristicile de bază ale...

Introducere în Limbajul Java

Programare Orientată pe Obiecte 1.Introducere în limbajul Java Java ca limbaj şi mediu de programare a fost lansat de firma Sun Microsystems. Cea...

Ai nevoie de altceva?