podm

Parantezare optimă de matrici

== include(page="template/taskheader" task_id="podm") ==

Se dă un produs matricial $M = M{~1~}M{~2~}...M{~n~}$. Rezultatul înmulţirii matricilor poate să difere în funcţie de ordinea efectuării calculelor, ordine dată de paranteze. Dimensiunile celor $n$ matrici se dau sub forma unui şir $d$ astfel încât perechea $(d{~i-1~}, d{~i~})$ reprezintă dimensiunile matricii $M{~i~}$.

Se dă un produs matricial $M = M{~1~}M{~2~}...M{~n~}$. Cum înmulţirea matricelor este asociativă, toate parantezările conduc la acelaşi rezultat. Însă, numărul total de înmulţiri scalare al produsului matricial poate să difere substanţial în funcţie de ordinea efectuării calculelor, ordine dată de paranteze. Dimensiunile celor $n$ matrici se dau sub forma unui şir $d$ astfel încât perechea $(d{~i-1~}, d{~i~})$ reprezintă dimensiunile matricii $M{~i~}$.

h2. Cerinţă

Se cere să se determine valoarea minimă a lui $M$, valoare ce corespunde unei parantezări optime a produsului matricial.

Se cere să se minimizeze numărul total de înmulţiri scalare al produsului matricial $M$, valoare ce corespunde unei parantezări optime.

h2. Date de intrare

Fişierul de intrare $podm.in$ conţine pe prima linie un număr natural $n$, reprezentând numărul matricilor. Pe următoarea linie se găsesc $n + 1$ numere naturale, reprezentând valorile şirului $d$.

Fişierul de intrare $podm.in$ conţine pe prima linie un număr natural $n$, reprezentând numărul matricelor. Pe următoarea linie se găsesc $n + 1$ numere naturale, reprezentând valorile şirului $d$.

h2. Date de ieşire

În fişierul de ieşire $podm.out$ se va găsit un singur număr natural egal cu valoarea minimă a lui $M$.

În fişierul de ieşire $podm.out$ se va găsi un singur număr natural egal cu valoarea minimă a numărului total de înmulţiri scalare a produsului matricial $M$.

h2. Restricţii

Din fericire, principiul optimalităţii al metodei _programării dinamice_ se poate aplica la această problemă. Dacă cel mai bun mod de a înmulţi toate matricele presupune o tăietură între a $i$-a şi a $i + 1$ a matrice a produsului, atunci subprodusele $M{~1~}M{~2~}...M{~i~}$ şi $M{~i+1~}M{~i+2~}...M{~n~}$ trebuie calculate la rândul lor într-un mod optim.

Vom construi tabloul $m[1..n, 1..n]$, unde $m[i, j]$ este numărul minim de înmulţiri scalare necesare pentru a calcula partea $M{~i~}M{~i+1~}...M{~j~}$ a produsului iniţial. Soluţia problemei iniţiale va fi $m[1, n]$. Presupunem că tabloul $d[0..n]$ conţine dimensiunile matricilor, astfel încât matricea $M{~i~}$ este de dimensiuni $d[i-1] x d[i], 1 ≤ i ≤ n$. Construcţia tabloului se face diagonală cu diagonală:

Vom construi tabloul $m[1..n, 1..n]$, unde $m[i, j]$ este numărul minim de înmulţiri scalare necesare pentru a calcula partea $M{~i~}M{~i+1~}...M{~j~}$ a produsului iniţial. Soluţia problemei iniţiale va fi $m[1, n]$. Presupunem că tabloul $d[0..n]$ conţine dimensiunile matricilor, astfel încât matricea $M{~i~}$ este de dimensiuni $(d[i-1], d[i]), 1 ≤ i ≤ n$. Construcţia tabloului se face diagonală cu diagonală:

* <tex> d = 0: m[i, i] = 0, 1 \le i \le n </tex>
* <tex> d = 1: m[i, i + 1] = d[i - 1] * d[i] * d[i + 1], 1 \le i \le n - 1 </tex>
* <tex> 1 < d < n: m[i, i + d] = Min\{m[i, k] + m[k + 1, i + d] + d[i - 1] * d[k] * d[i + d] : i \le k < i + d\}, 1 \le i \le n - d </tex>

Timpul de execuţie este de ordinul $O(N^3^)$, iar sursa demonstrativă se găseşte aici(?).

Timpul de execuţie este de ordinul $O(N^3^)$, iar sursa demonstrativă se găseşte 'aici':job_detail/262669?action=view-source.
 
Pentru a studia în detaliu problema înmulţirii înlănţuite de matrici puteţi consulta capitolul 16 din '_Introducere în algoritmi_':http://zhuzeyuan.hp.infoseek.co.jp/ita/toc.htm de Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest.

h2. Aplicaţii

Parantezarea optimă de matrici este o aplicaţie clasică a metodei _programării dinamice_ ce doreşte a ilustra principiul construcţiei unui tablou diagonală cu diagonală. Pentru a vă însuşi această tehnică vă recomand să rezolvaţi următoarele probleme:

Parantezarea optimă de matrici este o aplicaţie clasică ce ilustrează cele două caracteristici care permit o rezolvare folosind _metoda programării dinamice_: substructură optimală, suprapunerea subproblemelor. Pentru a vă însuşi această tehnică vă recomand să rezolvaţi următoarele probleme:
* 'Redu':problema/redu

* 'Recycling':http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2518, _UVa_
* 'Stiva':problema/stiva, _Baraj ONI, 2008_

* 'Expresii algebrice':problema/expresii
* "Game Po":http://acm.sgu.ru/problem.php?contest=0&problem=273, _SGU_

== include(page="template/taskfooter" task_id="podm") ==

4318