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
Introducere...3
Capitolul I
PREZENTARE GENERALA
1.1. Substructura optimala............4
1.2. Subprobleme superpozabile....4
1.3. inmultirea optimala a matricelor..............4
1.4. Subsir crescator maximal.......7
1.5. Suma in triunghi...8
1.6. Subsir comun maximal..........9
Capitolul II
ALGORITMI DE PROGRAMARE DINAMICA TREI PRINCIPII FUNDAMENTALE ALE PROGRAMARII DINAMICE
2.1. Determinarea celor mai scurte drumuri intr-un graf.....11
2.2. Arbori binari optimi de cautare..............13
2.3. Arborii binari de cautare tip data............14
2.4. Arborele optim...14
2.5. Cautarea in arbore..............15
2.6. Modificarea arborelui...........15
2.7. Programarea dinamica comparata cu tehnica greedy....16
Capitolul III
ALGORITMI DIVIDE ET IMPERA; TEHNICA DIVIDE ET IMPERA
3.1. Cautarea binara..20
3.2. Mergesort (sortarea prin interclasare)......21
3.3. Mergesort in clasele tablou si lista..............23
3.4. Tablouri sortabile si liste sortabile..........27
3.5. Quicksort (sortarea rapida)....29
3.6. Selectia unui element dintr-un tablou......32
3.7. O problema de criptologie....36
3.8. inmultirea matricelor..........40
3.9. inmultirea numerelor intregi mari...........42
Capitolul IV
PROGRAMARE DINAMICA
4.1. Introducere.......52
4.2. Probleme de alocare unidimensionala.......52
4.3. Un model matematic...........52
4.4. Posibilitati de rezolvare. Dificultati.........53
4.5. Rezolvarea problemelor.......54
4.6. O problema de incarcare a unui vapor de alocare unidimensionale (P) prin (PD).........55
Aplicatie .......59
Bibliografie....65

Alte date

?

Introducere

Programarea dinamica este o metoda de elaborare a algoritmilor care se aplica in general problemelor pentru care se cere determinarea unui optim in urma adoptarii unor decizii.

Nu exista un criteriu pe baza caruia sa identificam cu siguranta o problema pentru rezolvarea careia trebuie sa utilizam metoda programarii dinamice, dar putem formula doua proprietati care sugereaza o solutie prin programare dinamica.

În aceasta lucrare incerc sa prezint cateva din metodele generale de elaborare a algoritmilor.

Primul capitol al acestei lucrari este redata o prezentare generala despre structura optimala si subproblemee superpozabile cat si despre alte operatii optimale.

În al doilea capitol sunt prezentati algoritmi de programare dinamica si trei principii fundamentale ale programarii dinamice.

Capitolul trei prezinta cateva metode de sortare, algoritmii divide et impera si tehnica divide et impera.

Programarea dinamica si cateva probleme de alocare unidimensionala, sunt prezentate in ultimul capitol al acestei lucrari.

Capitolul I

PREZENTARE GENERAL?

1.1. Substructura optimala

Problema data poate fi descompusa in subprobleme si solutia optima a problemei depinde de solutiile optime ale subproblemelor sale.

Acest criteriu nu indica neaparat o solutie prin programare dinamica, ar putea fi si un indiciu ca se poate aplica metoda Greedy sau metoda "Divide et Impera".

1.2. Subprobleme superpozabile

Subproblemele problemei date nu sunt independente, ci se suprapun.

Datorita faptului ca subproblemele problemei date se suprapun, deducem ca o abordare prin metoda "Divide et Impera" ar fi dezastruoasa din punctul de vedere al timpului de executie (datorita faptului ca problemele se suprapun se ajunge la rezolvarea repetata a aceleiasi subprobleme). Prin urmare, vom rezolva subproblemele o singura, data, retinand rezultatele intr-o structura de date suplimentara (de obicei un tablou).

Rezolvarea unei probleme prin programare dinamica presupune urmatorii pasi:

- Se identifica subproblemele problemei date.

- Se alege o structura de date suplimentara, capabila sa retina solutiile subproblemelor.

- Se caracterizeaza substructura optimala a problemei printr-o relatie de recurenta.

Pentru a determina solutia optima, se rezolva relatia de recurenta in mod bottom-up (se rezolva subproblemele in ordinea crescatoare a dimensiunii lor).

În cele ce urmeaza vom exemplifica pas cu pas modul de rezolvare a problemelor prin metoda programarii dinamice.

1.3. Înmultirea optimala a matricelor

Fie n matrice A1, A2, ..., An, de dimensiuni d0xd1, d1xd2, ..., dn-1xdn. Produsul A1xA2x...xAn se poate calcula in diverse moduri, aplicand asociativitatea operatiei de inmultire a matricelor. Numim inmultire elementara inmultirea a doua elemente. În functie de modul de parantezare difera numarul de inmultiri elementare necesare pentru calculul produsului A1xA2x...xAn. Determinati o parantezare optimala a produsului A1xA2x...xAn (costul parantezarii, adica numarul total de inmultiri elementare sa fie minim).

Exemplu:

Pentru n=3 matrice cu dimensiunile (10,1000), (1000,10) si (10,100), produsul A1xA2xA3 se poate calcula in doua moduri:

(A1xA2)xA3 necesitand 1000000+10000=1010000 inmultiri elementare