Programarea dinamica - principii fundamentale

Lucrare de licenta despre Programarea dinamica - principii fundamentale
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).

Lucrare de licenta despre Programarea dinamica - principii fundamentale

Lucrare de licenta despre Programarea dinamica - principii fundamentale
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 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