Esercizio - domande di prima parte su programmazione dinamica (simulazioni d'esame)

Fonte: prima parte delle simulazioni d'esame di Algoritmi per l'Ingegneria, Ing. Informatica UniPD (2023-24 e 2025-26). Le due simulazioni hanno la stessa prima parte: dieci domande a risposta unica o a scelta multipla, in cui non si riporta il procedimento ma solo la risposta. Due riguardano la programmazione dinamica, una sulla LCS e una sulla Matrix Chain Multiplication. Qui sono svolte per esteso, con il metodo veloce da usare nel compito e la verifica con l'algoritmo. Le altre otto domande sono raccolte con gli argomenti di cui trattano.

Domanda 1: LCS dei prefissi

Testo. Siano $X = \langle a, f, r, a \rangle$ e $Y = \langle a, f, a \rangle$. Per $0 \le i \le 4$ e $0 \le j \le 3$, si denoti con $l(i, j)$ la lunghezza di una LCS dei prefissi $X_i$ e $Y_j$. Determinare $l(2, 2) + l(4, 3)$.

Risposta: $5$.

Metodo veloce

Si traducono $l(2, 2)$ e $l(4, 3)$ nelle coppie di prefissi e si ragiona direttamente (Longest Common Subsequence - ricorrenza, tabella e ricostruzionela LCS di X (m caratteri) e Y (n caratteri) è la sottosequenza comune più lunga. Sottoistanze = coppie di prefissi (Theta(mn)). Ricorrenza: l(i,j) = 0 se i = 0 o j = 0; 1 + l(i-1,j-1) se x_i = y_j; max{l(i-1,j), l(i,j-1)} altrimenti. Bottom-up con tabelle l e b (freccia): mn confronti; ricostruzione in O(m+n). Il D&C sulla stessa ricorrenza costa C(m+n,m) - 1 nodi interni nel caso peggiore (esponenziale). Memoizzazione: stessa complessità nel caso peggiore, ma molto meno lavoro su stringhe simili. Spazio ridotto a Theta(min{m,n}) se serve solo la lunghezza.Longest Common Subsequence - ricorrenza, tabella e ricostruzione →):

• $X_2 = \langle a, f \rangle$ e $Y_2 = \langle a, f \rangle$ sono uguali, quindi $l(2, 2) = |\text{LCS}(\langle a, f \rangle, \langle a, f \rangle)| = 2$;
• $X_4 = \langle a, f, r, a \rangle$ e $Y_3 = \langle a, f, a \rangle$: $Y_3$ è una sottosequenza di $X_4$ (si cancella la $r$), quindi la LCS è $Y_3$ stessa e $l(4, 3) = 3$ (non può superare $|Y_3| = 3$).

Somma: $l(2, 2) + l(4, 3) = 2 + 3 = 5$.

Regola utile: se una delle due stringhe è sottosequenza dell'altra, la LCS è la più corta e la sua lunghezza è $\min\{i, j\}$.

Con l'algoritmo

Si riempie la tabella con la ricorrenza $l(i, j) = 1 + l(i-1, j-1)$ se $x_i = y_j$, altrimenti $\max\{l(i-1, j), l(i, j-1)\}$, con riga $0$ e colonna $0$ a zero.

Le celle in grassetto sono $l(2, 2) = 2$ e $l(4, 3) = 3$: $2 + 3 = 5$. Per esempio $l(2, 2)$: $x_2 = f = y_2$, quindi $1 + l(1, 1) = 1 + 1 = 2$. E $l(4, 3)$: $x_4 = a = y_3$, quindi $1 + l(3, 2) = 1 + 2 = 3$. La ricostruzione dà $\langle a, f, a \rangle$. Tabella controllata con Python.

Domanda 2: costo della parentesizzazione ottima

Testo. Sia $p = (1, 9, 10, 4)$ il vettore delle dimensioni di una catena di $3$ matrici rettangolari. Si calcoli il numero di moltiplicazioni tra scalari nella parentesizzazione ottima.

Risposta: $130$.

Metodo veloce

Le matrici sono $A_1 \in 1 \times 9$, $A_2 \in 9 \times 10$, $A_3 \in 10 \times 4$ ($A_i$ ha dimensioni $p_{i-1} \times p_i$). Con tre matrici ci sono solo due parentesizzazioni: basta confrontarle, ricordando che un prodotto $(a \times b)(b \times c)$ costa $a \cdot b \cdot c$ (Matrix Chain Multiplication - parentesizzazione ottimadato il vettore p delle dimensioni di una catena di n matrici compatibili (A_i è p_(i-1) x p_i), si cerca la parentesizzazione che minimizza il numero di prodotti tra scalari. Le parentesizzazioni sono numeri di Catalan (esponenziali). Sottostruttura: i due sottoalberi dell'ultimo prodotto sono ottimi (cut-and-paste). Ricorrenza c(i,j) = min su k di c(i,k) + c(k+1,j) + p_(i-1) p_k p_j, c(i,i) = 0. D&C: 3^(n-1) - 1 operazioni. Bottom-up per diagonali crescenti con tabelle m e s: (n^3 - n)/3 prodotti, Theta(n^3). La memoizzazione ha lo stesso costo e non risparmia mai.Matrix Chain Multiplication - parentesizzazione ottima →).

• $((A_1 A_2) A_3)$: $A_1 A_2$ costa $1 \cdot 9 \cdot 10 = 90$ e dà una matrice $1 \times 10$; poi $(A_1 A_2) A_3$ costa $1 \cdot 10 \cdot 4 = 40$. Totale $90 + 40 = 130$.
• $(A_1 (A_2 A_3))$: $A_2 A_3$ costa $9 \cdot 10 \cdot 4 = 360$ e dà una matrice $9 \times 4$; poi $A_1 (A_2 A_3)$ costa $1 \cdot 9 \cdot 4 = 36$. Totale $360 + 36 = 396$.

Il minimo è $130$, con $((A_1 A_2) A_3)$.

Con l'algoritmo

$m[i, i] = 0$; per le sottocatene di lunghezza $2$: $m[1, 2] = p_0 p_1 p_2 = 1 \cdot 9 \cdot 10 = 90$ e $m[2, 3] = p_1 p_2 p_3 = 9 \cdot 10 \cdot 4 = 360$. Per $m[1, 3]$ si provano i due $k$:

• $k = 1$: $m[1,1] + m[2,3] + p_0 p_1 p_3 = 0 + 360 + 1 \cdot 9 \cdot 4 = 396$;
• $k = 2$: $m[1,2] + m[3,3] + p_0 p_2 p_3 = 90 + 0 + 1 \cdot 10 \cdot 4 = 130$.

Quindi $m[1, 3] = 130$ con $s[1, 3] = 2$, cioè $((A_1 A_2) A_3)$.

Varianti per esercitarsi

Stesso formato della prima parte (solo risposta). Le risposte sono state ottenute con l'algoritmo in Python e controllate a mano.

1. $X = \langle m, a, r, e \rangle$ e $Y = \langle a, m, o, r, e \rangle$. Determinare $l(2, 2) + l(4, 5)$. Risposta: $4$. $l(2,2) = |\text{LCS}(\langle m, a \rangle, \langle a, m \rangle)| = 1$ (una sola delle due lettere si può tenere, nell'ordine), $l(4,5)$: $X$ è lunga $4$ e $\langle m, r, e \rangle$ (o $\langle a, r, e \rangle$) è sottosequenza comune di lunghezza $3$, e non esiste di lunghezza $4$ perché $X$ intera non è sottosequenza di $Y$ ($m$ viene dopo $a$ in $Y$): $l(4,5) = 3$. Somma $1 + 3 = 4$.
2. $X = \langle p, a, s, t, a \rangle$ e $Y = \langle t, a, s, t, o \rangle$. Determinare $l(3, 3) + l(5, 5)$. Risposta: $5$. $l(3,3) = |\text{LCS}(\langle p,a,s \rangle, \langle t,a,s \rangle)| = |\langle a, s \rangle| = 2$; $l(5,5) = |\langle a, s, t \rangle| = 3$.
3. $p = (2, 5, 3, 4)$, catena di $3$ matrici. Costo della parentesizzazione ottima? Risposta: $54$. $((A_1 A_2) A_3)$: $2 \cdot 5 \cdot 3 + 2 \cdot 3 \cdot 4 = 30 + 24 = 54$; $(A_1 (A_2 A_3))$: $5 \cdot 3 \cdot 4 + 2 \cdot 5 \cdot 4 = 60 + 40 = 100$.
4. $p = (5, 2, 6, 3, 4)$, catena di $4$ matrici. Costo ottimo e parentesizzazione? Risposta: $100$, con $(A_1 ((A_2 A_3) A_4))$: $A_2 A_3$ costa $2 \cdot 6 \cdot 3 = 36$; $(A_2 A_3) A_4$ costa $2 \cdot 3 \cdot 4 = 24$; $A_1 \times (\dots)$ costa $5 \cdot 2 \cdot 4 = 40$; totale $36 + 24 + 40 = 100$. La tabella $m$ ha $m[1,2] = 60$, $m[2,3] = 36$, $m[3,4] = 72$, $m[1,3] = 66$, $m[2,4] = 60$, $m[1,4] = 100$.
5. Quante parentesizzazioni distinte ha una catena di $6$ matrici? Quanti prodotti tra scalari esegue MCM (con costo due per ogni $k$, vedi la nota) su $6$ matrici? Risposta: $42$ (numero di Catalan); $\frac{n^3 - n}{3} = \frac{216 - 6}{3} = 70$.