Memoizzazione di ricorrenze triangolari - conteggio esatto e diagonali costanti

Esercitazione sulla memoizzazione (Programmazione dinamica - Fibonacci, memoizzazione e schema del paradigmala programmazione dinamica (DP) evolve il divide and conquer: invece di risolvere di nuovo le stesse sottoistanze, le salva in una tabella. Fibonacci ricorsivo costa F_n - 1 addizioni (esponenziale), quello con tabella n - 1. Tre condizioni: sottostruttura, sottoistanze ripetute, spazio dei sottoproblemi ristretto. Bottom-up o memoizzazione (ricorsione + tabella globale). Per i problemi di ottimizzazione lo schema è: sottostruttura ottima, ricorrenza sui costi, informazione addizionale, calcolo della tabella, ricostruzione.Programmazione dinamica - Fibonacci, memoizzazione e schema del paradigma →) con una ricorrenza definita sul triangolo $1 \le i \le j \le n$, come quella della sottosequenza palindroma (Allineamento di stringhe e sottosequenza palindroma più lungadue problemi di DP su stringhe con la stessa struttura della LCS. Allineamento ottimo di due stringhe di DNA con matrice di score S e penalità di gap g: C(i,j) = max{C(i-1,j-1) + s(x_i,y_j), C(i-1,j) + g, C(i,j-1) + g}, C(i,0) = i g, C(0,j) = j g; Theta(mn) tempo, spazio Theta(min{m,n}) con un solo vettore se serve solo il costo. Sottosequenza palindroma più lunga (LPS) sullo spazio delle sottostringhe X_(i..j): p(i,j) = 2 + p(i+1,j-1) se x_i = x_j, altrimenti max{p(i+1,j), p(i,j-1)}; scansione per diagonali, n(n-1)/2 confronti.Allineamento di stringhe e sottosequenza palindroma più lunga →), ma con un prodotto invece di un massimo. Lo scopo è doppio: contare esattamente le operazioni di un codice memoizzato analizzando l'albero delle chiamate, e capire come una proprietà della ricorrenza permetta di ridurre di un ordine di grandezza il numero di sottoproblemi.

La ricorrenza

Sia $n > 0$. Per $1 \le i \le j \le n$:

$$M(i, j) = \begin{cases} 1 & i = j \\ 2 & j = i + 1 \\ M(i+1, j-1) \cdot M(i+1, j) \cdot M(i, j-1) & j > i + 1 \end{cases}$$

Si vuole $M(1, n)$ con il numero esatto $T(n)$ di moltiplicazioni tra interi. La cella $(i, j)$ dipende da tre celle di lunghezza minore (la sottostringa $X_{i..j}$ ha lunghezza $\ell = j - i + 1$; le dipendenze hanno lunghezza $\ell - 2$, $\ell - 1$, $\ell - 1$): le stesse della LPS.

Il codice memoizzato standard

Il valore $0$ è un default ammissibile, perché $M(i, j) > 0$ per ogni $i \le j$ (è un prodotto di numeri positivi, a partire da $1$ e $2$).

INIT_M(n)
  if n = 1 then return 1               { M(1,1) = 1 }
  if n = 2 then return 2               { M(1,2) = 2 }
  for i <- 1 to n-1 do
    M[i, i] <- 1
    M[i, i+1] <- 2
  M[n, n] <- 1
  for i <- 1 to n-2 do
    for j <- i+2 to n do M[i, j] <- 0   { da calcolare }
  return REC_M(1, n)

REC_M(i, j)
  if M[i, j] = 0 then
    M[i, j] <- REC_M(i+1, j-1) * REC_M(i+1, j) * REC_M(i, j-1)
  return M[i, j]

Correttezza: discende dall'inizializzazione dei casi base e dalla scelta della sentinella.

Costo. INIT_M non esegue moltiplicazioni. Nell'albero delle chiamate di REC_M(1, n):

• le coppie con $j \ge i + 2$ (cioè $1 \le i \le n - 2$ e $i + 2 \le j \le n$) sono nodi interni, ciascuno una volta sola: tutte vengono raggiunte dalla radice (si arriva a $(i, j)$ togliendo caratteri dagli estremi), e alle chiamate successive la cella è già piena. Ogni nodo interno esegue due moltiplicazioni (tre fattori);
• tutte le altre chiamate sono foglie a lavoro nullo (casi base e letture di tabella).

Quindi

$$T(n) = \sum_{i=1}^{n-2} \sum_{j=i+2}^{n} 2 = 2\sum_{i=1}^{n-2} (n - i - 1) = 2 \sum_{k=1}^{n-2} k = 2 \cdot \frac{(n-2)(n-1)}{2} = (n-1)(n-2).$$

(Nella seconda uguaglianza, per $i$ fissato il numero di valori di $j$ è $n - (i+2) + 1 = n - i - 1$; nella terza si pone $k = n - i - 1$, che va da $n - 2$ a $1$.) Per $n = 6$: $20$ moltiplicazioni, $10$ nodi interni $(1,3), (1,4), (1,5), (1,6), (2,4), (2,5), (2,6), (3,5), (3,6), (4,6)$ (controllato eseguendo il codice per $n \le 15$). È un algoritmo $\Theta(n^2)$.

Un algoritmo migliore: le diagonali sono costanti

Basta scrivere la tabella per $n = 6$ (riga $i$, colonna $j$):

Ogni diagonale ($\ell = j - i + 1$ costante) ha lo stesso valore.

Proposizione. Per ogni $1 \le \ell \le n$, tutti gli elementi $M(i, j)$ con $j - i + 1 = \ell$ valgono uno stesso numero $V(\ell)$, dove $$V(\ell) = \begin{cases} 1 & \ell = 1 \\ 2 & \ell = 2 \\ V(\ell - 1)^2 \cdot V(\ell - 2) & \ell \ge 3 \end{cases}$$

Dimostrazione per induzione su $\ell$. Base: $\ell = 1$: $M(i, i) = 1 = V(1)$ per tutti gli $i$; $\ell = 2$: $M(i, i+1) = 2 = V(2)$ per tutti gli $i$. Passo: sia $\ell \ge 3$ e valga la tesi per le diagonali di indice minore di $\ell$. Un elemento $M(i, j)$ sulla diagonale $\ell$ è il prodotto di $M(i+1, j-1)$ (diagonale $\ell - 2$, valore $V(\ell - 2)$ per l'ipotesi induttiva) e di $M(i+1, j)$ e $M(i, j-1)$ (entrambi sulla diagonale $\ell - 1$, valore $V(\ell - 1)$). Quindi vale $V(\ell - 1) \cdot V(\ell - 1) \cdot V(\ell - 2)$, indipendentemente da $i$. $\square$

(Nelle dispense, nel passo induttivo, il secondo fattore è scritto $M(i-1, j)$ al posto di $M(i+1, j)$: è un refuso.)

La risposta cercata è $M(1, n) = V(n)$: non serve più una tabella bidimensionale di $\Theta(n^2)$ elementi, ma un vettore $V[1..n]$.

INIT_V(n)
  if n = 1 then return 1
  if n = 2 then return 2
  for l <- 3 to n do V[l] <- 0
  V[1] <- 1; V[2] <- 2
  return REC_V(n)

REC_V(l)
  if V[l] = 0 then V[l] <- (REC_V(l-1))^2 * REC_V(l-2)
  return V[l]

Per $n \ge 3$ l'albero di REC_V(n) ha esattamente un nodo interno per ogni $\ell$ con $3 \le \ell \le n$ (le chiamate successive trovano il valore in tabella), ciascuno con due moltiplicazioni (il quadrato e il prodotto per $V(\ell - 2)$):

$$T(n) = 2\,(n - 2).$$

È un algoritmo lineare invece che quadratico: per $n = 6$ sono $8$ moltiplicazioni invece di $20$. I valori dell'esempio sono $V(1), \dots, V(6) = 1, 2, 4, 32, 4096, 536\,870\,912$: $V(3) = 2^2 \cdot 1 = 4$, $V(4) = 4^2 \cdot 2 = 32$, $V(5) = 32^2 \cdot 4 = 4096$, $V(6) = 4096^2 \cdot 32 = 2^{24} \cdot 2^5 = 2^{29} = 536\,870\,912$. Il controllo con Python coincide con la tabella completa fino a $n = 15$.

Osservazione sulla taglia dei numeri. Tutti i valori sono potenze di $2$: $V(\ell) = 2^{e(\ell)}$ con $e(1) = 0$, $e(2) = 1$ e $e(\ell) = 2e(\ell-1) + e(\ell-2)$, cioè $e = 0, 1, 2, 5, 12, 29, 70, \dots$ (i numeri di Pell). Crescono come $(1 + \sqrt 2)^\ell$: contare ogni moltiplicazione come costo unitario è lecito solo nel modello aritmetico, perché le cifre in gioco crescono esponenzialmente.

Lezione. Prima di impostare una tabella a due indici conviene guardare i valori per $n$ piccolo: regolarità come le diagonali costanti riducono lo spazio dei sottoproblemi da $\Theta(n^2)$ a $\Theta(n)$ e il lavoro da quadratico a lineare.

Domande d'esame

1. (Risposta numerica.) Quanto vale $M(1, 5)$? E quante moltiplicazioni esegue il codice standard per $n = 7$, e quello con le diagonali? Traccia: $M(1, 5) = V(5) = 4096$; $(n-1)(n-2) = 30$ contro $2(n-2) = 10$.
2. (Quesito aperto.) Perché per analizzare un algoritmo memoizzato si conta il numero di nodi interni dell'albero delle chiamate e non si usa la ricorrenza sul numero di operazioni? Traccia: la ricorrenza conta tutte le espansioni; nel memoizzato ogni sottoistanza non di base è espansa una volta sola e le altre chiamate sono letture di tabella a costo nullo.
3. (Dimostrazione.) Provare che le diagonali sono costanti. Traccia: induzione sull'indice di diagonale $\ell$; per $\ell \ge 3$ la cella è il prodotto di una cella sulla diagonale $\ell - 2$ e di due sulla $\ell - 1$.

Altri esercizi d'esame con memoizzazione e conteggio sull'albero delle chiamate: Esercizio - ricorrenza t(i,j) con calcolo memoizzato e conteggio esatto (compito del 26 giugno 2025, es. 2) e Esercizio - ricorrenza c(i,j) con valore di default e conteggio delle operazioni (simulazione d'esame 2023-24, problema 2).