Structuri de Date și Algoritmi (seria 1AB)

Această pagină poate fi doar citită. Poți vedea sursa, dar nu poți modifica pagina. Consultă administratorul dacă ești de părere că ceva este în neregulă.
====== Laborator 11: Programare dinamică ======
\\
=====1 Obiectivele laboratorului=====
*Înțelegerea noțiunilor de bază legate de programarea dinamică
*Însușirea abilităților de implementare a algoritmilor bazați pe programarea dinamică
*Înțelegerea aplicabilității practice a programării dinamice în:
   *Genetică (sequence alignment)
   *Teoria grafurilor (algoritmul Floyd-Warshall)
   *Limbaje formale și automate (algoritmul Cocke-Younger-Kasami,care analizează dacă și în ce fel un șir poate fi generat de o gramatică independentă de context)
   *Implementarea bazelor de date (algoritmul Selinger pentru optimizarea interogării relaționale)
\\ 

=====2 Programare dinamică=====
====2.1 Prezentare generală====
Programarea dinamică presupune rezolvarea unei probleme prin descompunea ei în subprobleme și rezolvarea acestora. Spre deosebire de divide et impera, subprogramele nu sunt disjuncte, ci se suprapun.\\ 
\\ 
Pentru a evita recalcularea porțiunilor care se suprapun, rezolvarea se face pornind de la cele mai mici subprograme și folosindu-ne de rezultatul acestora calculăm subproblema imediat mai mare. Cele mai mici subprobleme sunt numite subprobleme unitare, acestea putând fi rezolvate într-o complexitate constantă, ex:cea mai mare secvență dintr-o mulțime de un singur element.


====2.2 Implementare====
<note importante>
Pași ce trebuie urmați:
   -Identificarea structurii și a matricilor utilizare în caracterizarea soluției optime
   -Determinarea unei metode de calcul recursiv pentru a afla valoarea fiecărei subprobleme
   -Calcularea "bottom-up" a acestei valori (de la subprogramele cele mai mici la cele mai mari)
   -Reconstrucția soluției optime pornind de la rezultatele obținute anterior
</note>

====2.3 Probleme tip rezolvate cu acest algoritm====
===2.3.1 Problema rucsacului===
Soluția se construiește prin programare dinamică, D[i][j]=cel mai bun cost obținut pentru primele i obiecte, având greutatea maxim j.\\ 
Relația de recurență este următoarea: D[i][j]=maxim(D[i-1][j],D[i-1][j-G[i]]+C[i]),unde G[i]=greutatea obiectului i, iar C[i]=costul obiectului.\\ 
Ideea este următoarea: La soluția curentă ori nu adăugăm deloc obiectul i, și rămânem la costul pentru i-1 obiecte, ori adăugăm obiectul i, caz în care adăugăm costul lui la costul obținut pentru primele i-1 obiecte și greutate j-G[i].\\ 

===2.3.2 Determinarea celui mai lung subșir crescător===
Exemplu: pentru șirul 24,12,15,8,19 răspunsul este șirul 12,15,19.\\ 
Începem prin a stabili pentru fiecare element lungimea celui mai lung subșir strict crescător care începe cu primul element și se termină în elementul respectiv. Numim această valoare //best// și aplicăm formula recursivă //best i=//1 + max(//best j//),cu //j < i// și //elem j < elem i//.\\ 
Aplicând acest algoritm obținem: elem 24,12,15,15,8,19 best 1,1,2,2,1,3
\\ 
\\ 
Pentru 24 sau 12 nu există nici un alt element în stânga lor strict mai mici decât ele, de aceea au best egal cu 1.\\ 
Pentru elementele 15 se poate găsi în stânga lor 12 strict mai mic decât ele. Pentru 19 se găsește elementul 15 strict mai mic decât el. Cum 15 deja este capăt pentru un subșir soluție de 2 elemente, putem spune că 19 este capătul pentru un subșir soluție de 3 elemente.\\ 
\\ 
Pentru a găsi care sunt elementele ce alcătuiesc subșirul strict crescător putem să reținem și o 'cale de întoarcere'.\\ 
Reconstrucția astfel obținută are complexitatea O(N).
\\ 
Exemplu: Subproblema care se termină în elementul 19 are subșirul de lungime maximă 3 și a fost calculată folosind subproblema care se termină cu elementul 15 (oricare din ele). Subșirul de lungime maximă care se termină în 15 a fost calculat folosindu-ne de elementul 12. 12 marchează sfârșitul reconstrucției,fiind cel mai mic element din subșir.
\\ 

===2.3.3 Combinări de n luate câte k ===
Fie C<sub>n,k</sub> notat şi C(n, k) = combinări de n luate câte k.
\\
Atunci C(n, k) = n! / ( k! (n-k)! ).
<note important>
Se poate deduce o formulă ce necesită o înmulţire şi o împărţire pentru calcularea unei combinări, deşi există o recurenţă mai bună.
  * C(n+1, k) = (n+1)! / (k! (n+1-k)! ) = ( (n+1) / (n+1-k) ) C(n, k);

</note>

Totodată, dacă definim polinoamele P(n) := (X + 1)<sup>n</sup> , atunci se pot rescrie P(n) = ∏ (C<sub>n,k</sub> X<sup>k</sup>), unde k = 0,1,2,...,n.
\\
\\
Fie coef(P, k) = coeficientul lui X<sup>k</sup> din polinomul P. Atunci putem scrie următoarele 2 proprietăţi:
  * P1. Adunarea polinoamelor se face prin adunarea coeficienţilor de pe aceleaşi poziţii:
\\
//coef(P1 + P2, k) = coef(P1, k) + coef(P2, k)//, pentru orice polinoame (P1, P2) şi pentru orice număr natural k.
  * P2. Înmulţirea cu un X mută coeficienţii lui X<sup>k</sup> la X<sup>k+1</sup>:
\\
//coef(P, k) = coef(X P, k+1)//, pentru orice polinom P şi pentru orice număr natural k.

Putem deduce o legătură între coeficienţii polinoamelor de tipul P(n) dacă scriem P(n + 1) = (X + 1) P(n) = X P(n) + P(n).

<note tip>
Folosind proprietăţile de mai sus, observăm:
  * coef(P(n + 1), k) = coef( X P(n), k) + coef(P(n), k) = **coef(P(n), k-1) + coef(P(n), k)**, pentru orice număr natural (k-1).

Dar coef(P(n), k) = C(n, k), deci am obţinut o recurenţă ce foloseşte doar o adunare.
</note>

==== Exerciții ====

  - Construiți o funcție care calculează f(n), unde f = șirul lui Fibonacci;
  - Construiți o funcție care calculează f(n, k), unde f = combinări de n luate câte k;
  - implementați problema rucsacului;
  - Construiți o funcție care indică ordinea operațiilor la înmulțirea a N matrici pentru a minimiza numărul de înmulțiri între 2 numere;
  - construiți o funcție care calculează f(n) = 5<sup>n</sup> % k, unde k este o valoare fixată de la începutul programului;
  - Se dă un vector cu N elemente (v = [v1 v2 ... vn]) ce poate fi secționat în piese după următoarele reguli: a) inițial, tot vectorul reprezintă o piesă; b) o piesă poate reprezenta doar o bucată continuă (nu sare peste vreun element) din vectorul inițial; c) secționarea unei piese duce la înlocuirea piesei respective cu 2 piese mai mici, fără a se pierde niciun element din vector; d) valoarea unei piese este val = (lungimea piesei) x (suma elementelor din piesă). Găsiți secțiunile ce maximizează suma valorilor pieselor.

===== 3. Exerciţii de laborator (Linux) =====
Pentru acest laborator puteți descărca scheletul de cod de [[http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab11_programare_dinamica-skel.zip|aici]]. Descărcați arhiva și dezarhivați-o. 

=== Linux===
Puteti folosi utilitarul ''%%wget%%'' pentru descarcare si utilitarul ''%%unzip%%'' pentru dezarhivare.

  * ''%%wget http://elf.cs.pub.ro/sda-ab/wiki/_media/laboratoare/lab11_programare_dinamica-skel.zip%%''
  * ''%%unzip lab11_programare_dinamica-skel.zip%%''

Pentru compilare folositi comanda ''%%make%%''.
Structuri de Date și Algoritmi (seria 1AB)

Unelte utilizator

Unelte site

Unelte pagină
