Esercizio - algoritmo ibrido e valore ottimo della soglia (compito del 27 gennaio 2025, es. 1)

Teoria usata: 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 → (in particolare $f^\ast(n, n_0)$ e la taglia delle foglie), Master Theorem - enunciato, casi e applicazioniMaster Theorem per T(n) = aT(n/b) + w(n): si confronta w(n) con la funzione soglia n^(log_b a). Caso 1 (w minore di una potenza polinomiale): Theta(n^(log_b a)); caso 2 (w della stessa taglia): Theta(n^(log_b a) log n); caso 3 (w maggiore e regolare): Theta(w(n)). Prova completa dai livelli dell'albero, versione estesa (parti intere, n0 qualsiasi), esempi, e l'uso scorretto quando nessun caso si applica (w = n log n).Master Theorem - enunciato, casi e applicazioni →, 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 →.

L'idea dell'ibridazione: un algoritmo ricorsivo asintoticamente migliore ($64n^3$) può essere battuto, sulle istanze piccole, da uno asintoticamente peggiore ma con costanti piccole ($n^4$ batte $64n^3$ per $n < 64$). Si ferma allora la ricorsione a una taglia $n_0$ e si passa a $A^2$.

(a) Pseudocodice dell'algoritmo ibrido

Si cambia solo il caso base del codice di $A^1$: invece di fermarsi a $n = 1$ ci si ferma a $n \le n_0$ e si chiama $A^2$. La ricorrenza di $A^1$ ha $s(n) = 6$ sottoistanze di taglia $n/2$ e lavoro $w(n) = 16n^3$ (Divide più Conquer); il resto del codice resta quello di $A^1$, con le chiamate ricorsive a HYBRID.

HYBRID(i, n0)                                 {n0 potenza di due, costante}
n <- size(i)
[B]: if n <= n0 then return A2(i)             // costo n^4
[D]: <i_1, ..., i_6> <- A_D(i)                // Divide di A1: 6 sottoistanze di taglia n/2
[R]: for j <- 1 to 6 do s_j <- HYBRID(i_j, n0)    // il parametro n0 resta fisso
[C]: return A_C(s_1, ..., s_6)                // Conquer di A1

La correttezza segue da quella dei due algoritmi: sulle istanze di base si usa $A^2$ (corretto per ipotesi) e sulle altre la stessa proprietà di sottostruttura di $A^1$.

(b) $T(n) = 64\,n^3$

Si pone $n = 2^k$ e si procede per induzione su $k$.

• [B] $k = 0$: $n = 1$, $T(1) = 64 = 64\cdot 1^3$.
• [HP] $T(n/2) = 64\,(n/2)^3$ (la tesi per $n/2 = 2^{k-1}$).
• [TH] $T(n) = 6\,T(n/2) + 16n^3 = 6\cdot 64\,\frac{n^3}{8} + 16n^3 = 48n^3 + 16n^3 = 64\,n^3$. $\square$

Coerente con il Master Theorem: $a = 6$, $b = 2$, soglia $n^{\log_2 6} \approx n^{2{,}58}$, $w = 16n^3 = \Omega(n^{\log_2 6 + \varepsilon})$ con regolarità $6\cdot16(n/2)^3 = \frac34\cdot16n^3$, quindi Caso 3: $\Theta(n^3)$.

(c) La complessità $T_{n_0}(n)$ dell'algoritmo ibrido

La ricorrenza dipende da due parametri, $n$ e $n_0$ (con $n_0 \le n$ potenze di due): $$T_{n_0}(n) = \begin{cases} n^4 & n \le n_0 \\ 6\,T_{n_0}(n/2) + 16\,n^3 & n > n_0. \end{cases}$$ Formula generale con $s = 6$, $f(n) = n/2$, $w(n) = 16n^3$, taglia di base $n_0$ e costo di base $T_0 = n_0^4$ (tutte le foglie hanno taglia esattamente $n_0$). Per $f(n) = n/2$ si ha $f^\ast(n, n_0) = \log_2(n/n_0) - 1$: i livelli non di base sono $\ell = 0, \dots, m - 1$ con $m = \log_2(n/n_0)$, e le foglie, al livello $m$, sono $6^m$. Dunque $$T_{n_0}(n) = \sum_{\ell=0}^{m-1} 6^\ell\cdot 16\left(\frac{n}{2^\ell}\right)^3 + 6^{m}\, n_0^4.$$

Somma dei livelli. $6^\ell\left(\frac{n}{2^\ell}\right)^3 = n^3\left(\frac{6}{8}\right)^\ell = n^3\left(\frac34\right)^\ell$, quindi, con la somma geometrica di ragione $\frac34$, $$16\,n^3\sum_{\ell=0}^{m-1}\left(\frac34\right)^\ell = 16\,n^3\,\frac{1 - (3/4)^m}{1 - 3/4} = 64\,n^3\left(1 - \left(\tfrac34\right)^m\right).$$

Riscrittura in potenze di $n$ e $n_0$. Con $L = \log_2 3$ si ha $\log_2\frac34 = L - 2$, e $m = \log_2\frac n{n_0}$, quindi $$\left(\tfrac34\right)^m = \left(\tfrac{n}{n_0}\right)^{L - 2}, \qquad 6^m = \left(\tfrac{n}{n_0}\right)^{\log_2 6} = \left(\tfrac{n}{n_0}\right)^{1 + L}.$$ Allora:

• $64\,n^3\left(\frac{n}{n_0}\right)^{L-2} = 64\,n^{1+L}\,n_0^{2-L}$ (perché $n^3\cdot n^{L-2} = n^{1+L}$);
• $6^m\,n_0^4 = n^{1+L}\,n_0^{-1-L}\,n_0^4 = n^{1+L}\,n_0^{3-L}$.

Sommando, con $n^{1+L} = n^{\log_2 6}$: $$T_{n_0}(n) = 64\,n^3 - 64\,n^{\log_2 6}\,n_0^{2-\log_2 3} + n^{\log_2 6}\,n_0^{3-\log_2 3} = 64\,n^3 + c(n_0)\,n^{\log_2 6},$$ $$c(n_0) = -64\,n_0^{\,2-\log_2 3} + n_0^{\,3-\log_2 3}.$$

Controlli. Per $n_0 = 1$ ($A^2$ a taglia $1$ costa $1$ invece di $64$): $c(1) = -64 + 1 = -63$, quindi $T_1(n) = 64n^3 - 63\,n^{\log_2 6}$; per $n = 1$ dà $1$. La formula coincide con la ricorrenza per ogni $n = 2^k \le 2^{15}$ e ogni $n_0 = 2^j \le n$ (verificato con Python). Per $n_0 = 64$ si ha $c(64) = 64^{2-L}(-64 + 64) = 0$ e $T_{64}(n) = 64n^3$: coincide con $A^1$, perché a taglia $64$ i due algoritmi costano uguale ($64^4 = 64\cdot 64^3$).

(d) Il valore ottimo di $n_0$

Il coefficiente del termine dominante, $64\,n^3$, non dipende da $n_0$: l'ibridazione può agire solo sulla costante $c(n_0)$ del termine di ordine inferiore $n^{\log_2 6}$ (esponente $\approx 2{,}58 < 3$). Il costo è minimo dove $c(n_0)$ è minimo (più negativo). Si studia il segno della derivata: $$\frac{d\,c}{d\,n_0} = -64(2 - L)\,n_0^{1-L} + (3 - L)\,n_0^{2-L} = n_0^{\,1-L}\Bigl[-64(2-L) + (3-L)\,n_0\Bigr].$$ Poiché $n_0^{1-L} > 0$, il segno è quello della parentesi, che è negativa per $n_0$ piccolo, si annulla in $$n_0^\ast = \frac{64\,(2 - \log_2 3)}{3 - \log_2 3} \approx 18{,}77$$ e poi è positiva: $c$ decresce fino a $n_0^\ast$ e cresce dopo. Il minimo tra le potenze di due sta in una delle due più vicine a $18{,}77$, cioè $16$ o $32$. Per confrontarle si usa $16^{2-L} = 2^{4(2-L)} = \frac{2^8}{3^4} = \frac{256}{81}$ e $32^{2-L} = 2^{5(2-L)} = \frac{2^{10}}{3^5} = \frac{1024}{243}$; il secondo termine di $c$ è $n_0\cdot n_0^{2-L}$: $$c(16) = 16^{2-L}(-64 + 16) = -48\cdot\frac{256}{81} \approx -151{,}70, \qquad c(32) = 32^{2-L}(-64 + 32) = -32\cdot\frac{1024}{243} \approx -134{,}85.$$ Poiché $c(16) < c(32)$, la soglia migliore è $$\boxed{n_0 = 16, \qquad T_{16}(n) \simeq 64\,n^3 - 151{,}70\,n^{\log_2 6} \quad (n \ge 16).}$$

Errore nella soluzione del corso. La soluzione ufficiale riporta $c(32) \simeq -202{,}27$ e conclude $n_0 = 32$ con $T_{32}(n) \simeq 64n^3 - 202{,}27\,n^{\log_2 6}$. Ma il secondo termine di $c(32)$ è $32^{3-L} = 32\cdot 32^{2-L}$, non $16\cdot 32^{2-L}$: la soluzione ha riusato il fattore $16$ di $c(16)$, e così $-64\cdot\frac{1024}{243} + 16\cdot\frac{1024}{243} = -48\cdot\frac{1024}{243} \simeq -202{,}27$ invece del corretto $-32\cdot\frac{1024}{243} \simeq -134{,}85$. Con il valore giusto vince $16$. Lo conferma la ricorrenza valutata direttamente per $n = 2^{14}$:

Il guadagno è modesto: a $n = 2^{14}$ il costo scende da $64n^3 = 2{,}815\cdot10^{14}$ (puro $A^1$, o $n_0 = 64$) a $2{,}696\cdot10^{14}$, circa il $4{,}2\%$, perché agisce solo su un termine di ordine inferiore. Per $n_0 > 64$ l'ibrido è peggiore di $A^1$ ($c > 0$).

import math
from functools import lru_cache

@lru_cache(None)
def Th(n, n0):
    return n**4 if n <= n0 else 6 * Th(n // 2, n0) + 16 * n**3

L = math.log2(3)
c = lambda n0: -64 * n0**(2 - L) + n0**(3 - L)

n = 2**14
for j in range(2, 8):
    n0 = 2**j
    pred = 64 * n**3 + c(n0) * n**math.log2(6)
    assert abs(Th(n, n0) - pred) < 1e-9 * pred
print(min(range(15), key=lambda j: Th(n, 2**j)))   # 4, cioe' n0 = 16
print(round(c(16), 2), round(c(32), 2))            # -151.7 -134.85