Esercizio - ricorrenza c(i,j) con bordi dati da due array, calcolo iterativo e spazio lineare (compito del 18 giugno 2026, es. 2)

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

Testo

Sia $n > 0$. Dati due array di numeri reali $A[1..n]$ e $B[1..n]$, si consideri la seguente ricorrenza:

$$c(i, j) = \begin{cases} A[i] & (1 \le i \le n) \ \land \ (j = 1) \\ B[j] & (i = n) \ \land \ (1 < j \le n) \\ c(i, j-1) + c(i+1, j-1) - c(i+1, j) & (i < n) \ \land \ (j > 1) \end{cases}$$

• (a) [11 punti] Si fornisca lo pseudocodice di un algoritmo iterativo COMPUTE_c(A, B) che, dati in ingresso i due array $A$ e $B$ a $n$ componenti, restituisca in uscita il valore $c(1, n)$. Si provi la correttezza dell'algoritmo proposto.
• (b) [5 punti] Si determini il numero esatto $T_C(n)$ di operazioni aritmetiche tra numeri reali effettuate da COMPUTE_c(A, B).

Soluzione

Lettura della ricorrenza

I tre casi coprono tutte le coppie $(i, j)$ con $1 \le i, j \le n$ senza sovrapposizioni: la prima colonna ($j = 1$) vale $A[i]$; la ultima riga ($i = n$), per $j > 1$, vale $B[j]$ (quindi $B[1]$ non viene mai usato, perché $c(n, 1) = A[n]$); le celle interne, con $i < n$ e $j > 1$, si calcolano con una somma e una sottrazione. È la struttura tipica della programmazione dinamica (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 →): una tabella $C[1..n, 1..n]$ con i casi base sul bordo e le altre celle determinate da celle già note.

(a) Ordine di riempimento

La cella $(i, j)$ dipende da tre celle:

• $(i, j-1)$: stessa riga, colonna precedente;
• $(i+1, j-1)$: riga sotto, colonna precedente;
• $(i+1, j)$: riga sotto, stessa colonna.

Va scelto un ordine in cui queste tre siano calcolate prima di $(i, j)$. Le dipendenze vanno verso colonne di indice minore o uguale e verso righe di indice maggiore: l'ordine naturale è per colonne crescenti ($j = 2, 3, \dots, n$) e, dentro ogni colonna, per righe decrescenti ($i = n - 1, \dots, 1$). Con questo ordine, quando si arriva a $(i, j)$:

• $(i, j-1)$ e $(i+1, j-1)$ stanno nella colonna $j - 1$, già completa (o sono nella colonna $1$, che contiene i dati);
• $(i+1, j)$ è nella stessa colonna $j$, ma una riga più in basso, già calcolata o appartenente alla riga base $i + 1 = n$.

(Funziona anche la scansione per righe, dalla riga $n - 1$ alla riga $1$, ciascuna per colonne crescenti: la riga $i + 1$ è completa quando si lavora sulla riga $i$, e $(i, j-1)$ precede $(i, j)$ nella stessa riga. Non funzionano né le righe crescenti né le colonne decrescenti.)

COMPUTE_c(A, B)
  n <- A.len
  C[1, 1] <- A[1]
  for i <- 2 to n do
    C[i, 1] <- A[i]                  { prima colonna }
    C[n, i] <- B[i]                  { ultima riga, colonne 2..n }
  for j <- 2 to n do
    for i <- n-1 downto 1 do
      C[i, j] <- C[i, j-1] + C[i+1, j-1] - C[i+1, j]
  return C[1, n]

(Per $n = 1$ i cicli sono vuoti e si restituisce $C[1, 1] = A[1] = c(1, 1)$.)

Correttezza

Affermazione. Al termine di ogni scrittura di una cella $C[i, j]$, vale $C[i, j] = c(i, j)$.

Per induzione sull'ordine di scrittura delle celle.

• Base. Le celle scritte nei cicli di inizializzazione, $C[i, 1] = A[i] = c(i, 1)$ per $1 \le i \le n$ e $C[n, j] = B[j] = c(n, j)$ per $2 \le j \le n$, sono corrette per la definizione dei primi due casi.
• Passo. Sia $(i, j)$ con $i < n$, $j \ge 2$, calcolata nel ciclo doppio. Per l'ordine di scansione, nel momento in cui si esegue l'assegnamento le tre celle $(i, j-1)$, $(i+1, j-1)$ e $(i+1, j)$ sono già state scritte (vedi sopra) e quindi, per ipotesi induttiva, contengono $c(i, j-1)$, $c(i+1, j-1)$ e $c(i+1, j)$. Allora $C[i, j] = c(i, j-1) + c(i+1, j-1) - c(i+1, j) = c(i, j)$ per il terzo caso.

Poiché la cella $(1, n)$ è calcolata dal ciclo (per $n \ge 2$), l'algoritmo restituisce $c(1, n)$. $\square$

Spazio: basta un vettore

Per calcolare una cella della colonna $j$ servono solo due celle della colonna $j - 1$ e quella immediatamente sotto, nella stessa colonna. Quindi non serve la tabella quadratica. Con un solo vettore $V[1..n]$ che contiene la colonna corrente (si sovrascrive man mano la colonna $j - 1$ con la colonna $j$):

COMPUTE_c_LINEARE(A, B)
  n <- A.len
  for i <- 1 to n do V[i] <- A[i]            { V = colonna 1 }
  for j <- 2 to n do
    old <- V[n]                             { c(n, j-1) }
    V[n] <- B[j]                            { c(n, j) }
    for i <- n-1 downto 1 do
      tmp <- V[i]                           { c(i, j-1) }
      V[i] <- tmp + old - V[i+1]            { V[i+1] contiene già c(i+1, j) }
      old <- tmp                            { diventa c(i+1, j-1) per la riga i-1 }
  return V[1]

Invariante: all'inizio del passo $i$ della colonna $j$, old $= c(i+1, j-1)$ e $V[i+1] = c(i+1, j)$. Spazio $\Theta(n)$ invece di $\Theta(n^2)$. (Se si usano due vettori prev e curr bisogna che prev <- curr sia una copia o uno scambio di ruoli, non un'assegnazione che fa puntare i due nomi allo stesso array: altrimenti la colonna $j - 1$ verrebbe sovrascritta mentre serve ancora.)

Esempio ($n = 4$)

$A = (2, 5, 1, 3)$, $B = (7, 4, 6, 2)$ (il valore $B[1] = 7$ non viene usato). Tabella $c(i, j)$, con le righe $i$ dall'alto e le colonne $j$ da sinistra:

La prima colonna è $A$ e l'ultima riga è $(3, 4, 6, 2)$: $c(4, 1) = A[4] = 3$ e poi $B[2], B[3], B[4]$. Colonna $j = 2$ dal basso: $c(3, 2) = c(3, 1) + c(4, 1) - c(4, 2) = 1 + 3 - 4 = 0$; $c(2, 2) = c(2, 1) + c(3, 1) - c(3, 2) = 5 + 1 - 0 = 6$; $c(1, 2) = c(1, 1) + c(2, 1) - c(2, 2) = 2 + 5 - 6 = 1$. Colonna $j = 4$: $c(1, 4) = c(1, 3) + c(2, 3) - c(2, 4) = -1 + 8 - 4 = 3$. Il risultato è $c(1, 4) = 3$ con $18$ operazioni.

Verifica: lo pseudocodice (tabella e vettore) è stato confrontato in Python con la definizione ricorsiva su $300$ coppie casuali di array, con $n$ fino a $8$.

(b) Numero esatto di operazioni

Per ogni cella interna ($i < n$, $j \ge 2$) si fanno due operazioni aritmetiche (una somma e una sottrazione); le inizializzazioni non fanno operazioni. Le celle interne sono $n - 1$ righe per $n - 1$ colonne:

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

(Per $n = 4$: $2 \cdot 9 = 18$; per $n = 1$: $0$.) Il conto si ottiene con la regola di sostituzione dei cicli con le sommatorie (SommatorieIl simbolo di sommatoria, le sue proprietà (linearità, additività, cambio di indice) e le somme notevoli di Gauss e geometrica.Sommatorie →). La versione a vettore esegue le stesse operazioni: l'unica differenza è l'uso della memoria.