1. Nombres de Fibonacci
L'algorisme trivial per al càlcul dels nombres de Fibonacci repeteix molts càlculs. Podem evitar-ho desant tots els valors que calculem en una matriu i cercant-los allà quan ens calguin abans de calcular-los un altre cop (memoization). Si només ens cal obtenir un sol nombre de Fibonacci, podem construir una versió iterativa de l'algorisme que eviti els càlculs sense utilitzar espai de memòria addicional.
2. Producte encadenat de matrius
[FIXME: imatge multiplicació de matrius]. Hem vist que per multiplicar dues matrius podem utilitzar l'algorisme escolar o l'algorisme d'Strassen. Amb el primer d'ells, cal calcular \(\theta(pqr)\) productes escalars.
Si volem dur a terme una seqüència de multiplicacions, el nombre de productes escalars a fer canvia significativament segons com posem els parèntesis (el qual no té cap efecte sobre el resultat). Per exemple, amb tres matrius \(A_1 = 10×100\), \(A_2 = 100×5\) i \(A_3 = 5×50\), l'operació \((A_1 \cdot A_2) A_3\) resulta en \(10 \cdot 100 \cdot 50 + 10 \cdot 5 \cdot 50 = 7500\) productes escalars. En canvi, l'operació \(A_1 \cdot (A_2 \cdot A_3)\), amb les mateixes matrius, resultaria en \(100 \cdot 5 \cdot 50 + 10 \cdot 100 \cdot 50 = 75000\) productes escalars.
Heus aquí el problema la multiplicació encadenada de matrius: on «posar» els parèntesis per poder dur a terme les multiplicacions amb el mínim nombre de productes escalars?
Per força bruta, amb \(n\) matrius, les possibles formes de posar els parèntesis són igual al nombre d'arbres binaris amb \(n\) fulles, el qual correspon a \(C_n = \frac{1}{n + 1}{2n \choose n} \approx \frac{4^n}{3^{n/2}}\) (\(\small C\) és el nombre de Catalan). Podem definir la següent funció per trobar el nombre mínim de productes escalars per multiplicar les matrius \(A_i\), …, \(A_j\):
\(m(i, j) = \begin{cases}0 & i = j \\ min\left\{m(i, k) + m(k+1, j) + p_{i-1} \cdot p_k \cdot p_j\right\} & i < j\end{cases}\)Aquesta operació duplica càlculs → memorització! En resulta el següent codi C++ que triga temps \(\theta(n^3)\):
vector<vector<int>> mem(n+1, vector<int>(n+1, -1)); vector<vector<int>> tall(n+1, vector<int>(n+1, -1)); int m(int i, int j) { if (mem[i][j] != -1) return mem[i][j]; if (i == j) return 0; int s = MAX_INT; // infinit for (int k = i; k <= j; ++k) { int x = m(i, k) + m(k+1, j) + p[i-1] + p[k] + p[j]; if (x < s) { s = x; tall[i][j] = k; // resposta al problema de com multiplicar-les } } return m[i][j] = s; }
També podem construir-ne una versió iterativa:
for (int i = 1; i <= n; ++i) mem[i][i] = 0; for (int i = n; i >= 1; --i) { for (int j = i+1; j <= n; ++j) { int s = MAX_INT; // infinit for (int k = i; k <= j; ++k) { int x = mem[i][k] + mem[k+1][j] + p[i-1] + p[k] + p[j]; if (x <= s) s = x; } mem[i][j] = s; } }
3. Problema de la subseqüència comuna més llarga
Tenim dues cadenes X="abcbdab" i Y="bdcaba" i volem trobar la subseqüència comuna (per exemple, "bca") més llarga (en aquest cas, la més llarga és "bdab"). Definim \(m=|X|\), \(n=|Y|\), \(X'_i\)=\(X_1\)…\(X_i\).
- Si X i Y acaben igual: l'últim caràcter d'X (o Y) ha de ser l'últim caràcter d'LCS(X, Y).
LCS(X, Y) = \(LCS(X'_{m-1}, Y'_{n-1}) \cdot X_m\). - Si X i Y no acaben igual, pensem què passa amb LCS(X, Y).
\(LCS(X, Y) = \begin{cases}LCS(X_{n-1}, Y) \\ LCS(X, Y_{n-1})\end{cases}\) Quina de les dues? La més llarga.
Definim la funció \(l(i, j)\) = llargada de l'LCS(\(X'_i\), \(Y'_i\)).
\(l(i, j) = \begin{cases}0 & i = 0 \text{ o } j=0 \\ l(i-1, j-1)+1 & x_i = y_j \\ max\{l(i-1, j), l(i, j-1)\} & sin\acute{o}\end{cases}\)You are reading: Apunts d'Estructures de Dades i Algorismes
- Apunts d'Estructures de Dades i Algorismes: Càlcul de costs
- Apunts d'Estructures de Dades i Algorismes: Dividir i Vèncer
- Apunts d'Estructures de Dades i Algorismes: Diccionaris
- Apunts d’Estructures de Dades i Algorismes: Grafs
- Apunts d'Estructures de Dades i Algorismes: Cerca exhaustiva
- Apunts d'Estructures de Dades i Algorismes: Les classes de problemes P i NP
- Apunts d'Estructures de Dades i Algorismes: Programació dinàmica
