Esercizio - ricorrenza c(i,j) con valore di default e conteggio delle operazioni (simulazione d'esame 2023-24, problema 2)

Fonte: simulazione d'esame 2023-24 di Algoritmi per l'Ingegneria, Ing. Informatica UniPD, seconda parte, problema 2 (14 punti).

Testo

Per $n \ge 0$, si consideri la seguente definizione per ricorrenza della quantità intera $c(i, j)$, con $0 \le i, j \le n$:

$$c(i, j) = \begin{cases} 3 \cdot (i + j) & (i = 0) \lor (j = 0) \\ 3 \cdot \big(c(i-1, j-1) + c(i-1, j) - c(i, j-1)\big) & \text{altrimenti} \end{cases}$$

• Punto 1 [9 punti] Si fornisca lo pseudocodice di un algoritmo memoizzato per il calcolo di $c(n, n)$. Si presti attenzione alla scelta del valore di default da utilizzare nell'inizializzazione.
• Punto 2 [5 punti] Si determini, analizzando l'albero delle chiamate, il numero esatto di operazioni aritmetiche complessive effettuate dalle due routine (escluse quelle per il calcolo degli indici) che costituiscono il codice memoizzato.

Soluzione

Punto 1: il valore di default

Lo schema è quello della 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 →): INIT_C inizializza la tabella con i casi base e un valore di default, REC_C calcola solo le celle non ancora calcolate. La difficoltà è la sentinella: deve essere un valore che $c(i, j)$ non può mai assumere. Qui $c(i, j)$ può essere zero, positivo o negativo: per esempio $c(1, 1) = 3(0 + 3 - 3) = 0$ e $c(1, 3) = -36$. Quindi non vanno bene né $0$ né "un numero negativo": il caso $c(1,1) = 0$ sarebbe scambiato per una cella da calcolare e verrebbe ricalcolato a ogni chiamata, rovinando il conteggio.

Osservazione chiave: per ogni $i, j$ il valore $c(i, j)$ è un multiplo di $3$: nei casi base è $3 \cdot (i + j)$; nel caso ricorsivo è $3$ per un intero. Quindi basta scegliere come default un intero che non è multiplo di $3$, per esempio $1$.

INIT_C(n)
  if n = 0 then return 0                    { c(0,0) = 0 }
  C[0, 0] <- 0
  for i <- 1 to n do
    v <- 3 * i                              { c(i,0) = c(0,i) = 3i }
    C[i, 0] <- v
    C[0, i] <- v
  for i <- 1 to n do
    for j <- 1 to n do C[i, j] <- 1         { 1 = non ancora calcolato }
  return REC_C(n, n)

REC_C(i, j)
  if C[i, j] = 1 then
    C[i, j] <- 3 * (REC_C(i-1, j-1) + REC_C(i-1, j) - REC_C(i, j-1))
  return C[i, j]

La correttezza segue dalla ricorrenza, dalla corretta inizializzazione dei casi base (riga $0$ e colonna $0$, che hanno i valori $3i$ e $3j$) e dalla scelta del default: una cella contiene $1$ se e solo se non è ancora stata calcolata, perché nessun valore vero è $1$. Ogni chiamata con $i, j \ge 1$ ha come figli $(i-1, j-1)$, $(i-1, j)$ e $(i, j-1)$, che hanno almeno un indice minore: la ricorsione termina sui casi base (riga o colonna $0$), già pieni.

Punto 2: albero delle chiamate e operazioni

• INIT_C: per ogni $i = 1, \dots, n$ si fa una moltiplicazione ($v = 3i$), usata per scrivere sia $C[i, 0]$ sia $C[0, i]$: in tutto $n$ operazioni. Per $n = 0$ nessuna.
• REC_C(n, n): nell'albero delle chiamate, ogni coppia $(i, j)$ con $1 \le i, j \le n$ compare come nodo interno una volta sola: da $(n, n)$ si raggiunge ogni coppia con indici $\ge 1$ scendendo di un passo alla volta, e dopo il primo calcolo la cella contiene un multiplo di $3$ diverso dal default, quindi tutte le altre chiamate restituiscono subito il valore (foglie a costo nullo). Le chiamate sui casi base ($i = 0$ o $j = 0$) sono anch'esse foglie a costo nullo. Ogni nodo interno esegue tre operazioni aritmetiche: una somma, una sottrazione e una moltiplicazione per $3$.

I nodi interni sono $n^2$. Il numero totale di operazioni è

$$T(n) = \underbrace{3n^2}_{\texttt{REC\_C}} + \underbrace{n}_{\texttt{INIT\_C}}.$$

Controllo: per $n = 0$ si ha $0$; per $n = 1$: $\texttt{INIT\_C}$ calcola $v = 3$ ($1$ operazione) e $\texttt{REC\_C}(1,1) = 3(c(0,0) + c(0,1) - c(1,0)) = 3(0 + 3 - 3) = 0$ ($3$ operazioni): totale $4 = 3 \cdot 1 + 1$.

Esempio ($n = 3$)

Riga e colonna $0$: $c(i, 0) = c(0, i) = 3i$, cioè $0, 3, 6, 9$. Poi, per $i, j \ge 1$:

• $c(1,1) = 3(c(0,0) + c(0,1) - c(1,0)) = 3(0 + 3 - 3) = 0$;
• $c(1,2) = 3(c(0,1) + c(0,2) - c(1,1)) = 3(3 + 6 - 0) = 27$;
• $c(1,3) = 3(c(0,2) + c(0,3) - c(1,2)) = 3(6 + 9 - 27) = -36$;
• $c(2,1) = 3(c(1,0) + c(1,1) - c(2,0)) = 3(3 + 0 - 6) = -9$;
• $c(2,2) = 3(c(1,1) + c(1,2) - c(2,1)) = 3(0 + 27 + 9) = 108$;
• $c(2,3) = 3(c(1,2) + c(1,3) - c(2,2)) = 3(27 - 36 - 108) = -351$;
• $c(3,1) = 3(c(2,0) + c(2,1) - c(3,0)) = 3(6 - 9 - 9) = -36$;
• $c(3,2) = 3(c(2,1) + c(2,2) - c(3,1)) = 3(-9 + 108 + 36) = 405$;
• $c(3,3) = 3(c(2,2) + c(2,3) - c(3,2)) = 3(108 - 351 - 405) = -1944$.

Quindi $c(3, 3) = -1944$, calcolato con $3 \cdot 9 + 3 = 30$ operazioni. Controllato con Python (codice con contatori contro la definizione ricorsiva, per $n \le 11$). Senza memoizzazione la stessa ricorrenza a tre rami, $T(n, n) = T(n-1, n-1) + T(n-1, n) + T(n, n-1) + 3$, produrrebbe un numero esponenziale di chiamate.