Esercizio - ricorrenza t(i,j) con calcolo memoizzato e conteggio esatto (compito del 26 giugno 2025, es. 2)

Fonte: compito di Algoritmi per l'Ingegneria, Ing. Informatica UniPD, 26 giugno 2025, seconda parte, esercizio 2 (16 punti).

Testo

Dato un vettore $x$ di $n \ge 1$ interi positivi, si consideri la seguente ricorrenza, definita per $1 \le i, j \le n$ :

$t(i, j) = \begin{cases} x_j & i = 1 \\ x_{n+1-i} & j = n \\ \max\{\, t(i-1, j+1),\ \ t(i-1, j) + t(i, j+1) \,\} & (1 < i \le n) \ \land \ (1 \le j < n) \end{cases}$

(a) [10 punti] Si fornisca lo pseudocodice della coppia di procedure INIT_T(x) e REC_T(x, i, j) che, dato in ingresso il vettore $x$ , eseguano il calcolo memoizzato di $t(n, 1)$ .
(b) [6 punti] Si determini il numero esatto $T(n)$ di confronti e somme tra interi effettuato dall'algoritmo memoizzato.

Soluzione

Lettura della ricorrenza

Si pensi a una tabella $n \times n$ con $i$ per riga e $j$ per colonna.

Prima riga ( $i = 1$ ): $t(1, j) = x_j$ .
Ultima colonna ( $j = n$ ): $t(i, n) = x_{n+1-i}$ , cioè scende dal basso verso l'alto leggendo $x$ da sinistra a destra: $t(n, n) = x_1$ , $t(n-1, n) = x_2$ , ..., $t(1, n) = x_n$ . Nell'angolo $(1, n)$ i due casi base danno lo stesso valore $x_n$ , quindi la definizione è coerente.
Celle interne ( $2 \le i \le n$ e $1 \le j \le n - 1$ ): dipendono da tre vicine, quella in alto a destra $(i-1, j+1)$ , quella sopra $(i-1, j)$ e quella a destra $(i, j+1)$ . Il valore richiesto è l'angolo in basso a sinistra, $t(n, 1)$ .

Nelle chiamate ricorsive $i$ diminuisce o $j$ aumenta (o entrambi): la quantità $i + (n - j)$ scende di almeno $1$ a ogni livello e i casi base (prima riga, ultima colonna) sono raggiunti, quindi la ricorsione termina.

(a) Valore di default

Tutti i valori della tabella sono strettamente positivi: i casi base sono componenti di $x$ (positive), e un valore interno è il massimo tra un numero positivo e una somma di numeri positivi (induzione sull'ordine di valutazione). Quindi $0$ è un valore di default ammissibile per le celle ancora da calcolare, perché la ricorrenza non lo può mai produrre.

INIT_T(x)
  n <- x.length
  if n = 1 then return x_1                        { caso base: t(1,1) = x_1 }
  for i <- 1 to n do
    T[1, i] <- x_i                                { prima riga }
    T[n+1-i, n] <- x_i                            { ultima colonna: T[i', n] = x_{n+1-i'} }
  for i <- 2 to n do
    for j <- 1 to n-1 do T[i, j] <- 0             { da calcolare }
  return REC_T(x, n, 1)

REC_T(x, i, j)
  if T[i, j] = 0 then
    a <- REC_T(x, i-1, j)
    b <- REC_T(x, i, j+1)
    c <- REC_T(x, i-1, j+1)
    if c >= a + b then T[i, j] <- c
    else T[i, j] <- a + b
  return T[i, j]

La procedura INIT_T risolve direttamente il caso $n = 1$ , riempie la prima riga e l'ultima colonna con i casi base, mette $0$ in tutte le altre celle e chiama REC_T sull'istanza principale. La procedura REC_T calcola solo le celle non di base, e memorizza ciascun valore appena calcolato in $T[i, j]$ per non ricalcolarlo. Ogni cella è letta (cioè restituita dalla chiamata) soltanto dopo che la chiamata che la calcola è terminata, quindi contiene sempre il valore definitivo. La correttezza discende dalla ricorrenza, dai casi base e dal valore di default.

Esempio ( $n = 4$ , $x = (2, 1, 3, 2)$ )

Le celle di base: riga $1$ uguale a $x$ , colonna $4$ uguale a $(2, 3, 1, 2)$ dall'alto ( $t(1,4) = x_4$ , $t(2,4) = x_3$ , $t(3,4) = x_2$ , $t(4,4) = x_1$ ). Le altre si calcolano con la ricorrenza, ad esempio:

$t(2, 3) = \max\{t(1, 4),\ t(1, 3) + t(2, 4)\} = \max\{2,\ 3 + 3\} = 6$ ;
$t(2, 2) = \max\{t(1, 3),\ t(1, 2) + t(2, 3)\} = \max\{3,\ 1 + 6\} = 7$ ;
$t(2, 1) = \max\{t(1, 2),\ t(1, 1) + t(2, 2)\} = \max\{1,\ 2 + 7\} = 9$ .

Tabella completa $t(i, j)$ :

$i \backslash j$	1	2	3	4
1	2	1	3	2
2	9	7	6	3
3	23	14	7	1
4	46	23	9	2

Il risultato è $t(4, 1) = 46$ . L'ordine in cui le $9 = (n-1)^2$ celle interne vengono completate da REC_T(x, 4, 1) è $(2,3), (2,2), (2,1), (3,3), (3,2), (3,1), (4,3), (4,2), (4,1)$ : le righe vengono completate una per volta, ciascuna da destra a sinistra. In tutto le chiamate sono $28 = 1 + 3 \cdot 9$ (ogni nodo interno ne fa tre). Il codice è stato controllato in Python contro la ricorrenza diretta su $300$ vettori casuali, con $n \le 9$ .

(b) Numero esatto di operazioni

INIT_T non esegue operazioni aritmetiche né confronti tra interi (solo assegnamenti). Si analizza l'albero delle chiamate di REC_T(x, n, 1), non la ricorrenza (Programmazione dinamica - Fibonacci, memoizzazione e schema del paradigma):

Tutte le celle non di base $(i, j)$ con $2 \le i \le n$ e $1 \le j \le n - 1$ vengono raggiunte dalla radice: per arrivare a $(i', j')$ si fanno $n - i'$ passi verso l'alto e $j' - 1$ verso destra, e tutte le celle intermedie hanno $i \ge i' \ge 2$ e $j \le j' \le n - 1$ , quindi sono celle non di base e vengono espanse.
Ognuna compare una sola volta come nodo interno: dopo il primo calcolo la tabella contiene un valore positivo, e tutte le altre chiamate sulla stessa cella restituiscono subito il valore (foglie a lavoro nullo).
Il lavoro di un nodo interno è $2$ : una somma ( $a + b$ ) e un confronto ( $c \ge a + b$ ).

Le celle non di base sono $(n - 1)$ righe per $(n - 1)$ colonne, quindi

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

Per $n = 4$ : $18$ operazioni (nove somme e nove confronti); per $n = 1$ : $0$ . Controllato eseguendo il codice con i contatori per $n \le 9$ .

Osservazione: simmetria rispetto all'antidiagonale

La tabella è simmetrica rispetto all'antidiagonale: $t(i, j) = t(n+1-j,\, n+1-i)$ (nell'esempio $t(2, 1) = t(4, 3) = 9$ , $t(3, 1) = t(4, 2) = 23$ , $t(2, 2) = t(3, 3) = 7$ ). Prova. Si pone $u(i, j) = t(n+1-j, n+1-i)$ e si mostra che $u$ soddisfa la stessa ricorrenza di $t$ con gli stessi casi base:

$u(1, j) = t(n+1-j, n) = x_{n+1-(n+1-j)} = x_j$ ;
$u(i, n) = t(1, n+1-i) = x_{n+1-i}$ ;
per $1 < i \le n$ e $1 \le j < n$ si applica la ricorrenza di $t$ in $(n+1-j,\, n+1-i)$ (che è una cella non di base, perché $1 < n+1-j \le n$ e $1 \le n+1-i < n$ ): $u(i, j) = \max\{t(n-j, n+2-i),\ t(n-j, n+1-i) + t(n+1-j, n+2-i)\}$ , cioè $\max\{u(i-1, j+1),\ u(i, j+1) + u(i-1, j)\}$ , la ricorrenza di $t$ .

Per induzione sull'ordine di valutazione, $u = t$ . Sfruttandola, ogni volta che si calcola una cella fuori dall'antidiagonale si può scrivere anche la sua simmetrica, dimezzando la costante del termine $n^2$ (miglioramento non richiesto).

Versione ripasso

Testo. $x$ vettore di $n \ge 1$ interi positivi; $t(i,j) = x_j$ se $i = 1$ ; $x_{n+1-i}$ se $j = n$ ; $\max\{t(i-1,j+1),\ t(i-1,j) + t(i,j+1)\}$ se $1 < i \le n$ e $1 \le j < n$ . (a) [10 punti] INIT_T(x) e REC_T(x,i,j) per il calcolo memoizzato di $t(n,1)$ . (b) [6 punti] Numero esatto $T(n)$ di confronti e somme.

Struttura: prima riga $= x$ ; ultima colonna dall'alto $x_n, x_{n-1}, \dots, x_1$ (cioè $T[i,n] = x_{n+1-i}$ ); celle interne dipendono da $(i-1,j+1)$ , $(i-1,j)$ , $(i,j+1)$ . Si vuole l'angolo in basso a sinistra $(n,1)$ . Terminazione: $i + (n - j)$ scende a ogni chiamata.
Default $0$ : tutti i valori sono positivi (casi base positivi, massimo di positivi e somme di positivi).

INIT_T(x)
  n <- x.length; if n = 1 then return x_1
  for i <- 1 to n do T[1,i] <- x_i; T[n+1-i,n] <- x_i
  for i <- 2 to n do for j <- 1 to n-1 do T[i,j] <- 0
  return REC_T(x, n, 1)
REC_T(x, i, j)
  if T[i,j] = 0 then
    a <- REC_T(x,i-1,j); b <- REC_T(x,i,j+1); c <- REC_T(x,i-1,j+1)
    if c >= a + b then T[i,j] <- c else T[i,j] <- a + b
  return T[i,j]

Esempio $x = (2,1,3,2)$ : $t(2,3) = \max\{2,\ 3 + 3\} = 6$ , $t(2,2) = \max\{3,\ 1 + 6\} = 7$ , $t(2,1) = \max\{1,\ 2 + 7\} = 9$ ; $t(4,1) = 46$ . Tabella (righe $i = 1..4$ ): $(2,1,3,2)$ , $(9,7,6,3)$ , $(23,14,7,1)$ , $(46,23,9,2)$ . Ordine di completamento delle celle interne: $(2,3), (2,2), (2,1), (3,3), (3,2), (3,1), (4,3), (4,2), (4,1)$ ; $28 = 1 + 3 \cdot 9$ chiamate.
Costo (albero delle chiamate, non la ricorrenza): INIT_T non fa operazioni; ogni cella con $2 \le i \le n$ , $1 \le j \le n - 1$ è raggiunta da $(n,1)$ (si va su e a destra tra celle non di base) ed è nodo interno una volta, con lavoro $2$ (una somma e un confronto):

$T(n) = \sum_{i=2}^{n}\sum_{j=1}^{n-1} 2 = 2(n-1)^2 \quad (18 \text{ per } n = 4,\ 0 \text{ per } n = 1).$

Simmetria: $t(i,j) = t(n+1-j, n+1-i)$ . Prova: $u(i,j) = t(n+1-j, n+1-i)$ ha gli stessi casi base e soddisfa la stessa ricorrenza, quindi $u = t$ per induzione. Si potrebbe calcolare metà tabella.
Errori tipici: default $0$ senza giustificare la positività; leggere l'ultima colonna come $x_i$ invece di $x_{n+1-i}$ ; dimenticare che ogni nodo interno ha una somma e un confronto; contare $n^2$ nodi interni (le celle di base non lavorano); analizzare con una ricorrenza invece dell'albero.

Teoria collegata

Programmazione dinamica - Fibonacci, memoizzazione e schema del paradigma