Cuprins

Aceasta lucrare poate fi descarcata doar daca ai statut PREMIUM si are scop consultativ. Pentru a descarca aceasta lucrare trebuie sa fii utilizator inregistrat.

Extras din document

Cuprins
COMPLEXITATEA ALGORITMILOR 5
Masurarea complexitatii 5
Clase de complexitate 5
Teze 6
Complexitatea algoritmilor secventiali 7
METODE DE PROIECTARE A ALGORITMILOR ORIENTATE PE PROBLEMA 11
PROBLEMA CAUTARII 12
Cautarea secventiala 12
Cautarea binara 13
Arbori binari de cautare 14
Pattern Matching 15
PROBLEMA SORTARII 17
Bubble Sort (sortare prin interschimbare) 17
Insertion Sort (sortare prin inserare) 17
Shell Sort (sortare prin metoda Shell) 18
Radix Sort 19
Heap_Sort 20
Merge_Sort si Quick_Sort 24
METODE GENERALE DE PROIECTARE A ALGORITMILOR 26
METODA DIVIDE-AND-CONQUER (DIVIDE-ET-IMPERA) 28
Descrierea metodei 28
Modelul metodei 28
Eficienta metodei 28
Modelul metodei pentru cazul arborelui binar de recursie: 30
Studii de caz 30
Sortarea prin prin interclasare 30
Sortarea rapida (C.A.R. Hoare) 32
METODA GREEDY 36
Descrierea metodei 36
Modelul metodei 36
Eficienta metodei 37
Studii de caz 37
Interclasare optimala 37
Compresiile de date. Arbori Huffman 41
Drum minim intr-un graf ( sursi - destinatie ) 43
Problema rucsacului (Knapsack) 44
PROGRAMAREA DINAMICi. 46
Descrierea metodei 46
Modelul metodei 48
Eficienta metodei 49
Comparatie intre metoda programarii dinamice si metoda greedy 49
Studii de caz 50
Problema rucsacului (0/1) 50
Inmultire optimi de matrici 52
Arbori binari de cautare optimali 53
METODA BACKTRACKING 57
Descrierea Metodei 57
Spatiul solutiilor. Restrictii. 57
Backtracking si Branch-and-Bound 59
Modelul metodei 60
Studii de caz 61
Problema celor 8 dame 61
Submultimi de suma data 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
Marginire 70
Modelul metodei pentru strategia LC cu marginire 70
Problema 0/1 a rucsacului ( 0/1 knapsack ) 71
Algoritmul BB_LC pentru problema 0/1 a rucsacului: 73

Alte date

?Proiectarea Algoritmilor

_____________________________________________________________________________________?Complexitatea algoritmilor

Teoria complexitatii are ca obiect de studiu clasificarea problemelor, bazata pe timpul de executie si spatiul de lucru utilizat de algoritmi pentru solutionarea lor. Cind se analizeaza algoritmi paraleli, se poate lua in considerare si numarul de procesoare.

Desi teoria complexitatii a fost dezvoltata pentru probleme de decizie, aceasta nu este o restrictie severa deoarece multe alte probleme pot fi formulate in termeni de probleme de decizie. De exemplu o problema de optimizare poate fi rezolvata prin punerea intrebarii existentei unei solutii cu cel mult sau cel putin o valoare specificata.

Masurarea complexitatii

Complexitatea timpului de executie a unui algoritm paralel care rezolva o instanta de dimensiune n a unei probleme, pe o masina paralela cu p procesoare (p=dimensiunea masinii) se noteaza a cu T(p,n)=Tp(n).

O problema se numeste dependenta de dimensiunea masinii (PDD) daca n este o functie de variabila p. Altfel, problema se numeste independenta de dimensiunea masinii (PID). Un algoritm dependent de dimensiunea masinii este un algoritm ce rezolva o problema PDD. altfel, algoritmul se numeste independent de dimensiunea masinii.

Factorul de incarcare (L) a unei probleme este raportul n/p. Viteza Sp(n)) unui algoritm paralel este raportul T1(n)/Tp(n). Eficienta (Ep(n)) unui algoritm paralel se defineste ca fiind raportul dintre viteza si numarul procesoarelor:

E p(n)=Sp(n)/p=T1(n)/[p•Tp(n)].

Pentru a aprecia comportarea asimtotica a functiei Tp(n) se utilizeaza urmatoarele notiuni:

Fiind date doua functii f si g pozitive de variabile p si n se noteaza :

o(g)={f/(?)e>0,?[{p0,n0(p)}? N] a.i.(?)[(p>p0)? (n>n0(p))]: f(p,n)Rezulta ca f este in o(g) daca limn??(f/g)=0.

O(g)={f/? [{p0,n0(p)} ? N ? c?R+] a.i.( ?)[(p>p0) )? (n>n0(p))]: f(p,n)Deci f este in O(g) daca functia f/g este marginita.

?(g)={f/? [{p0,n0(p)} ? N ? {c1,c2} ? R+] a.i.( ?)[(p>p0) )? (n>n0(p))]: 0Aceasta inseamna ca f??(g) daca f/g este o functie strict pozitiva si marginita.

?(g)={f/? [{p0,n0(p)} ? N ? c?R+] a.i.( ?)[(p>p0) )? (n>n0(p))]: 0Rezulta ca f??(g) daca f/g este marginita inferior de o valoare strict pozitiva.

Clase de complexitate

Din punctul de vedere al calculului secvential, 3 clase sint relevante: P, NP, Pspace

Clasa P contine problemele solvabile in timp polinomial ceea ce inseamna ca pentru aceste probleme exista algoritmi deterministi secventiali cu timpul de executie marginit de un polinom de variabila "dimensiunea problemei ". Problemele din P sint numite, in mod curent, bine solutionabile sau usoare.

NP este clasa problemelor pentru care exista un algoritm sevential nedeterminist cu timp de executie polinomial (echivalent : nu exista un algoritm secvential determinist cu timp de executie polinomial.)

Pspace contine problemele care sint solvabile utilizind un spatiu polinomial, adica spatiul de lucru este marginit de un polinom de variabila " dimensiunea problemei ".

Evident, P ?NP ? Pspace . Se presupune ca ambele incluziuni sint proprii (stricte).

O alta clasa inclusa in Pspace, neinteresanta din punct de vedere al calculului secvential, dar importanta pentru calculul paralel este Polylogspace. Aici sint incluse problemele rezolvabile in spatiu polilogaritmic (spatiul de lucru este marginit de un polinom de variabila "log(dimensiunea problemei)"). Multe probleme din P apartin lui Polylogspace, dar in general, se crede ca P ?Polylogspace. Se stie totusi ca Polylogspace# Pspace .

Remarcabile in Pspace si NP sint problemele complete.Problemele Pspace-complete sint generalizari ale tuturor celorlalte probleme din Pspace in termeni de transformari care necesita timp polinomial. Mai precis: o problema este Pspace-completa sub transformari de timp polinomial daca apartine lui Pspace si oricare alta problema din Pspace este reductibila la ea prin transformari care necesita timp polinomial. Urmeaza ca daca o problema Pspace-completa ar apartine lui P atunci Pspace = P. Deoarece se crede ca aceasta egalitate nu este adevarata, este improbabil sa existe un algoritm de timp polinomial pentru o problema Pspace-completa. Problemele NP se definesc in mod asemanator, rezultind aceleasi concluzii.

Clasa P are si ea problemele ei complete. Problemele P-complete sint generalizari ale tuturor celorlalte probleme din clasa P, in termenii transformarilor care necesita spatiu de lucru logaritmic. Formal, o problema este P-completa sub transformari spatiale logaritmice daca apartine clasei P si orice alta problema din P este reductibila la ea prin transformari ce utilizeaza spatiu logaritmic. Daca o problema P-completa ar apartine clasei Polylogspace, atunci ar fi adevarata incluziunea P ? Polylogspace. Cum aceasta incluziune se presupune a fi falsa, nu este de asteptat sa existe un algoritm pentru o problema P-completa care sa utilizeze spatiu de lucru polilogaritmic.

Teze

Relatia intre calculul secvential si paralel este data de teza calculului paralel (Chandra, Kozen & Stockmeyer, 1981; Goldshlager, 1982): pentru orice functie T(n), (n= dimensiunea problemei), clasa problemelor solvabile de o masina cu paralelism nemarginit in timp T(n)O(1) (polinomial in T(n) ) este egala cu clasa problemelor solvabile de masini secventiale cu spatiu (T(n))O(1) .

Aceasta teza este o teorema pentru multe dintre modelele relativ rezonabile. Astfel, clasa problemelor solvabile in T(n)O(1) timp de o masina PRAM este egala cu clasa problemelor solvabile cu T(n)O(1) spatiu de lucru de o masina Turing, daca T(n)?log n (Fortune & Wyllie, 1978). In consecinta, clasa problemelor solvabile de o masina PRAM in timp paralel polinimial este egala cu clasa Pspace. De asemenea, Polylogspace este clasa problemelor solvabile de o masina PRAM in timp paralel polilogaritmic.

Problemele din P?Polylogspace sint solvabile in timp paralel polilogaritmic. Ele pot fi considerate cele mai usoare probleme din P, in sensul ca influenta dimensiunii problemei asupra timpului de rezolvare a fost redusa la minimum. O reducere ulterioara a a timpului de solutionare la dimensiuni sublogaritmice este, in general, imposibila. Una din ratiunile acestei afirmatii este aceea ca o masina PRAM necesita O(log n) timp pentru activarea a n procesoare.