Algoritmi de programare dinamica. Trei principii fundamentale ale programarii dinamice

Introducere………………………………………………………3

Capitolul I PREZENTARE GENERALĂ
1.1. Substructura optimală………………………………………………...4
1.2. Subprobleme superpozabile………………………………………….4
1.3. Înmulţirea optimală a matricelor……………………………………..4
1.4. Subşir crescător maximal…………………………………………….7
1.5. Suma în triunghi……………………………………………………...8
1.6. Subşir comun maximal……………………………………………….9

Capitolul II ALGORITMI DE PROGRAMARE DINAMICĂ TREI PRINCIPII FUNDAMENTALE ALE PROGRAMĂRII DINAMICE
2.1. Determinarea celor mai scurte drumuri într-un graf……………..…11
2.2. Arbori binari optimi de căutare……………………………………..13
2.3. Arborii binari de căutare tip dată…………………………………...14
2.4. Arborele optim…………………………………………………...…14
2.5. Căutarea în arbore……………………………………………..……15
2.6. Modificarea arborelui………………………………………...……..15
2.7. Programarea dinamică comparată cu tehnica greedy……….………16

Capitolul III ALGORITMI DIVIDE ET IMPERA; TEHNICA DIVIDE ET IMPERA
3.1. Căutarea binară……………………………………………..………20
3.2. Mergesort (sortarea prin interclasare)………………………………21
3.3. Mergesort în clasele tablou şi lista………………………..23
3.4. Tablouri sortabile şi liste sortabile………………………………….27
3.5. Quicksort (sortarea rapidă)……………………………………….…29
3.6. Selecţia unui element dintr-un tablou………………………………32
3.7. O problema de criptologie……………………………………….…36
3.8. Înmulţirea matricelor………………………………………….……40
3.9. Înmulţirea numerelor întregi mari…………………………….…….42

Capitolul IV PROGRAMARE DINAMICĂ
4.1. Introducere…………………………………………………….……52
4.2. Probleme de alocare unidimensională………………………...…….52
4.3. Un model matematic……………………………………….……….52
4.4. Posibilităţi de rezolvare. Dificultăţi………………………………...53
4.5. Rezolvarea problemelor…………………………………………….54
4.6. O problemă de încărcare a unui vapor de alocare unidimensionale (P) prin (PD)………………………………………………………..….55
Aplicaţie ……………………………………………………………………….59
Bibliografie…………………………………………………………………….65