Esercizio - funzione g(n) definita per ricorrenza, calcolo memoizzato e formula chiusa (compito del 19 giugno 2024, es. 2)

Teoria usata: 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 → (memoizzazione), Algoritmi ricorsiviAlgoritmi ricorsivi come induzione eseguita; albero della ricorsione e record di attivazione nello stack; esempi ReverseArray, LinearSum, Power in tempo logaritmico, Fibonacci ricorsivo (esponenziale) e con memoizzazione; analisi della complessità con l'albero della ricorsione e correttezza per induzione.Algoritmi ricorsivi → (Fibonacci ricorsivo e memoizzato in Dati e Algoritmi), Albero della ricorrenza e formula generale per le ricorrenzeL'albero della ricorrenza ha la forma dell'albero delle chiamate dell'istanza peggiore e T(n) è la somma dei lavori dei nodi. Per la famiglia T(n) = s(n)T(f(n)) + w(n) con base T0 per n <= n0, contando i nodi per livello con le iterate di f e il livello f*(n,n0) si ottiene la formula chiusa T(n) = somma_l [prodotto_j s(f^(j)(n))] w(f^(l)(n)) + [prodotto s] T0, verificata per induzione e applicata a esempi (merge sort, Hanoi, ricorrenze con radice).Albero della ricorrenza e formula generale per le ricorrenze →, Problemi computazionali - istanze, soluzioni, correttezza e complessitàUn problema computazionale è una relazione totale (non necessariamente univoca) tra istanze e soluzioni; un algoritmo è una funzione dalle istanze alle soluzioni e risolve il problema se la sua uscita è sempre in relazione con l'ingresso. Correttezza = coerenza con la specifica; complessità = costo in funzione della taglia, per default al caso peggiore, con le istruzioni a costo unitario scelte in modo significativo.Problemi computazionali - istanze, soluzioni, correttezza e complessità → (taglia di un intero), Principio di induzionePer dimostrare una proprietà per ogni n basta il passo base e il passo induttivo da n a n+1.Principio di induzione →.

La definizione chiama la funzione su $n-1$ e su $n-2$, come Fibonacci: l'algoritmo ricorsivo "alla lettera" ripete gli stessi sottoproblemi (il D&C non ha memoria, Divide and conquer - proprietà di sottostruttura e albero delle chiamateUn algoritmo divide and conquer nasce da una proprietà di sottostruttura (funzioni Divide e Conquer, base n0) con sottoistanze di taglia strettamente minore; l'albero delle chiamate ne descrive l'esecuzione, e il D&C non ha memoria (ripete le sottoistanze uguali). Esempio completo: MAX di un array, con correttezza per induzione, ricorrenza e conteggio esatto n-1 tramite il teorema sugli alberi binari pieni.Divide and conquer - proprietà di sottostruttura e albero delle chiamate →). La memoizzazione ricorda i valori già calcolati.

(a) Il calcolo memoizzato

Tabella e valore di default. Si usa un array $G[1..n]$ con $G[i] = g(i)$ una volta calcolato. Serve un valore di default che non sia mai un valore valido di $g$, per riconoscere le celle non ancora calcolate. Si prova per induzione che $g(n) \ge 3$ per ogni $n \ge 1$: base $g(1) = 3$, $g(2) = 4$; passo, per $n > 2$, $g(n) \ge \left\lfloor\frac{3 + 3}{2}\right\rfloor + 2 = 5 \ge 3$. Quindi $g$ è strettamente positiva e il valore $0$ è un default ammissibile.

INIT_G(n)
if n <= 2 then return n + 2                  // g(1) = 3, g(2) = 4
G[1] <- 3;  G[2] <- 4
for i <- 3 to n do G[i] <- 0                 // 0 = "non ancora calcolato"
return REC_G(n)

REC_G(i)
if G[i] = 0 then
    G[i] <- floor( (REC_G(i - 1) + REC_G(i - 2)) / 2 ) + 2
return G[i]

Esecuzione per $n = 5$. $G = [3, 4, 0, 0, 0]$ dopo l'inizializzazione. L'albero delle chiamate (le foglie sono chiamate che trovano $G[i] \ne 0$ e ritornano subito):

REC_G(5)
├── REC_G(4)
│   ├── REC_G(3)
│   │   ├── REC_G(2)   foglia, G[2] = 4
│   │   └── REC_G(1)   foglia, G[1] = 3
│   │   -> G[3] = floor((4+3)/2) + 2 = 5
│   └── REC_G(2)       foglia, G[2] = 4
│   -> G[4] = floor((5+4)/2) + 2 = 6
└── REC_G(3)           foglia, G[3] = 5
-> G[5] = floor((6+5)/2) + 2 = 7

Correttezza. La procedura calcola $g(i)$ con la definizione, e ogni chiamata ricorsiva avviene su un indice minore: per induzione su $i$, $\text{REC\_G}(i)$ restituisce $g(i)$ (i casi $i = 1, 2$ sono già nella tabella, per $i \ge 3$ vale la definizione applicata ai valori restituiti dalle chiamate su $i-1$ e $i-2$). L'ordine "prima $i-1$ poi $i-2$" fa sì che alla seconda chiamata la cella sia già piena.

(b) Analisi del tempo

Si conta il numero di operazioni aritmetiche tra interi. $\text{INIT\_G}$ non ne esegue. Per $\text{REC\_G}(n)$ si osserva che ogni indice $i$ con $3 \le i \le n$ viene calcolato una sola volta: la prima chiamata su $i$ riempie $G[i]$ (nodo interno), tutte le successive trovano la cella piena (foglie, lavoro nullo). L'albero ha quindi esattamente $n - 2$ nodi interni, e le chiamate in totale sono $2(n-2) + 1 = 2n - 3$ (ogni nodo interno ne fa due, più la radice). Ogni nodo interno esegue tre operazioni: una somma $g(i-1) + g(i-2)$, una divisione intera per $2$ e una somma di $2$. Quindi $$T(n) = 3\,(n - 2) \qquad (n \ge 3), \qquad T(1) = T(2) = 0.$$ (Conteggio verificato con un'implementazione strumentata per $3 \le n < 200$.)

Polinomiale nella taglia? No. La taglia dell'istanza $\langle n\rangle$ è il numero di bit della sua codifica binaria, $b = \lceil\log_2(n+1)\rceil = \Theta(\log n)$, quindi $n \approx 2^b$ e $$T(n) = 3(n-2) \approx 3\cdot 2^{b},$$ esponenziale nella taglia, anche se lineare nel valore $n$. Un algoritmo che, sullo stesso input, esegue la definizione senza memoria avrebbe $\text{chiamate}(n) = 2F(n) - 1$ (con $F$ i numeri di Fibonacci, $F(1) = F(2) = 1$: per $n = 3, \dots, 10$ le chiamate sono $3, 5, 9, 15, 25, 41, 67, 109$), cioè $\Theta(\varphi^n)$ con $\varphi \approx 1{,}618$: doppiamente esponenziale nella taglia.

(c) Una formula chiusa

Valori. $g(1) = 3$, $g(2) = 4$, $g(3) = \left\lfloor\frac{4 + 3}{2}\right\rfloor + 2 = 3 + 2 = 5$, $g(4) = \left\lfloor\frac{5 + 4}{2}\right\rfloor + 2 = 4 + 2 = 6$ (e $g(5) = 7$, $g(6) = 8$). Ogni valore supera l'indice di $2$: congettura $g(n) = n + 2$.

Dimostrazione per induzione forte su $n \ge 1$.

• [B] $n = 1$: $g(1) = 3 = 1 + 2$; $n = 2$: $g(2) = 4 = 2 + 2$ (servono due basi perché la definizione usa $g(n-1)$ e $g(n-2)$).
• [HP] $g(k) = k + 2$ per ogni $1 \le k < n$, con $n > 2$.
• [TH] Gli indici $n - 1$ e $n - 2$ sono $\ge 1$ e $< n$, quindi $$g(n) = \left\lfloor \frac{g(n-1) + g(n-2)}{2}\right\rfloor + 2 = \left\lfloor \frac{(n+1) + n}{2}\right\rfloor + 2 = \left\lfloor \frac{2n + 1}{2}\right\rfloor + 2 = \left\lfloor n + \tfrac12\right\rfloor + 2 = n + 2,$$ perché $n$ è intero e $0 \le \frac12 < 1$. $\square$

Come per Fibonacci, l'esistenza di una formula chiusa dà un algoritmo molto più veloce di quello memoizzato: $g(n) = n + 2$ si calcola con una sola operazione aritmetica, polinomiale nella taglia (quasi lineare nel numero di bit).

def g(n, memo={}):
    if n in (1, 2): return n + 2
    if n not in memo:
        memo[n] = (g(n - 1) + g(n - 2)) // 2 + 2
    return memo[n]

assert all(g(n) == n + 2 for n in range(1, 800))
print([g(n) for n in range(1, 7)])      # [3, 4, 5, 6, 7, 8]