Divide and conquer - proprietà di sottostruttura e albero delle chiamate

Il primo paradigma di progetto: scomporre un'istanza grande in sottoistanze più piccole dello stesso problema, risolverle, e ricombinare le soluzioni. Gli algoritmi ricorsivi di 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 → ne sono realizzazioni. Il problema è $\Pi \subseteq I \times S$ (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à →); $A^\star$ indica le sequenze finite (anche vuote) di elementi di $A$.

Proprietà di sottostruttura

Definizione (proprietà di sottostruttura). Per $\Pi \subseteq I \times S$ è una terna $(n_0, D, C)$:

• una soglia $n_0 \in \mathbb{N}$ e la descrizione esplicita delle soluzioni delle istanze di base, cioè con $\lvert i\rvert \le n_0$;
• una funzione di Divide $D : I \to I^\star$, che a un'istanza $i$ con $\lvert i\rvert > n_0$ associa una sequenza di sottoistanze $\langle i_1, \dots, i_k\rangle$;
• una funzione di Conquer $C : S^\star \to S$, che da una sequenza di soluzioni ne costruisce una.

Devono valere, per ogni istanza non di base $i$ con $D(i) = \langle i_1, \dots, i_k\rangle$:

1. $\lvert i_j\rvert < \lvert i\rvert$ per $1 \le j \le k$ (le sottoistanze sono strettamente più piccole);
2. se $s_1, \dots, s_k \in S$ sono tali che $i_1 \,\Pi\, s_1, \dots, i_k \,\Pi\, s_k$, allora $i \,\Pi\, C(\langle s_1, \dots, s_k\rangle)$.

La condizione 1 garantisce la terminazione (le taglie sono interi non negativi e decrescono), la condizione 2 garantisce che la ricombinazione dia una soluzione. Dalla proprietà si ottiene l'algoritmo se si hanno: un metodo diretto per le istanze di base, un algoritmo $A_D$ che realizza $D$ e un algoritmo $A_C$ che realizza $C$. Il metacodice è:

D&C(i)                          {i in I}
[B]: if |i| <= n0 then *risolvi direttamente*; return
[D]: <i_1, ..., i_k> <- A_D(i)                 // fase di divide
[R]: for j <- 1 to k do s_j <- D&C(i_j)        // fase di recurse
[C]: return A_C(s_1, ..., s_k)                 // fase di conquer

Nella fase [R] le soluzioni delle sottoistanze si ottengono "gratis" con le chiamate ricorsive. Le frasi tra asterischi *...* indicano attività che non si codificano in pseudocodice: vanno usate il meno possibile e mai dove la specifica in pseudocodice è possibile; // introduce un commento.

La correttezza della proprietà implica quella dell'algoritmo: la dimostrazione ricalca la proprietà.

Albero delle chiamate

L'esecuzione su un'istanza $i$ si schematizza con l'albero delle chiamate: la radice è l'istanza principale, i figli di un nodo sono le sottoistanze generate dalla sua fase [D], le foglie sono istanze di base (taglia $\le n_0$). In principio ogni nodo può avere un numero diverso di figli; per tutti gli algoritmi del corso l'arietà è la stessa per tutti i nodi interni.

• Divide espande l'albero dalla radice alle foglie (top-down); Conquer lo contrae dalle foglie alla radice (bottom-up), fino alla soluzione dell'istanza principale.
• Quando il sottoalbero di una sottoistanza viene contratto e la sua soluzione calcolata, tutta l'informazione dei suoi nodi viene distrutta: il D&C non ha memoria del processo di risoluzione. Se la stessa sottoistanza compare in punti diversi dell'albero, il suo sottoalbero viene espanso e contratto più volte, con conseguenze sul tempo che possono essere disastrose: è la debolezza che la programmazione dinamica corregge (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 →).
• Per la stessa ragione l'ordine in cui l'albero viene espanso è irrilevante. In pratica la ricorsione usa lo stack di sistema e l'albero viene generato e contratto gradualmente, con una visita anticipata (in preordine) che contiene l'uso di memoria.

Un esempio paradigmatico: il massimo di un array

Problema. Dato $A[1..n]$ con $n \ge 1$ interi, trovare il massimo.

Sottostruttura. Per $n > 1$ si partiziona l'array in due sottoarray non vuoti (il più bilanciati possibile) e il massimo è il massimo tra i due massimi. Per $n = 1$ il massimo è l'elemento stesso, quindi $n_0 = 1$. La generica sottoistanza è il massimo del sottovettore $A[i..j]$, con $1 \le i \le j \le n$: i parametri dell'algoritmo devono poter indicare la sottoistanza, e si chiama la procedura come $\text{MAX}(A, 1, \lvert A\rvert)$. La taglia di $A[i..j]$ è $n = j - i + 1$.

MAX(A, i, j)
[B]: if i = j then return A[i]
[D]: k <- floor((i + j)/2)
[R]: m1 <- MAX(A, i, k)
     m2 <- MAX(A, k + 1, j)
[C]: if m1 >= m2 then return m1 else return m2

def MAX(A, i, j):
    if i == j:
        return A[i]
    k = (i + j) // 2
    m1 = MAX(A, i, k)
    m2 = MAX(A, k + 1, j)
    return m1 if m1 >= m2 else m2

Correttezza

Il metodo è l'induzione sulla taglia $n = \lvert i\rvert$, con tre parti: base [B] (correttezza delle istanze di taglia $\le n_0$), ipotesi [HP] (le soluzioni delle sottoistanze di taglia minore di $n$ sono corrette), tesi [TH] (Divide produce sottoistanze strettamente più piccole e Conquer dà una soluzione dell'istanza).

[B] Se $n = 1$, allora $j - i + 1 = 1$, cioè $j = i$: MAX restituisce $A[i]$, l'unico elemento di $A[i..i]$, che ne è anche il massimo.

[HP] MAX è corretta per tutte le taglie $\ell < n$, con $n > 1$.

[TH], correttezza del Divide. Le due sottoistanze sono $A[i..k]$ e $A[k+1..j]$, con $k = \lfloor (i+j)/2 \rfloor$: $$\lvert i_1\rvert = k - i + 1 = \left\lfloor \tfrac{i+j}{2} \right\rfloor - i + 1, \qquad \lvert i_2\rvert = j - (k+1) + 1 = j - \left\lfloor \tfrac{i+j}{2} \right\rfloor.$$ Poiché $n > 1$ si ha $i < j$, e di conseguenza $i - 1 < \lfloor (i+j)/2 \rfloor < j$. Il lato destro dà $\lvert i_1\rvert = k - i + 1 < j - i + 1 = n$; il lato sinistro, $k > i - 1$, dà $\lvert i_2\rvert = j - k < j - i + 1 = n$, e anche $\lvert i_1\rvert \ge 1$ e $\lvert i_2\rvert \ge 1$ (le sottoistanze sono non vuote). Quindi le due sottoistanze hanno taglia strettamente minore di $n$, e per [HP] $m_1$ e $m_2$ sono corretti.

[TH], correttezza del Conquer. Siano $\mathcal{A} = \{A[\ell] : i \le \ell \le j\}$, $\mathcal{A}_1 = \{A[\ell] : i \le \ell \le k\}$, $\mathcal{A}_2 = \{A[\ell] : k+1 \le \ell \le j\}$. Per [HP] $m_1 = \max \mathcal{A}_1$ e $m_2 = \max \mathcal{A}_2$. Poiché $\mathcal{A} = \mathcal{A}_1 \cup \mathcal{A}_2$ e il massimo di un'unione finita è il massimo dei massimi, MAX restituisce $\max\{m_1, m_2\} = \max \mathcal{A}$. $\square$

La dimostrazione dell'algoritmo ricalca quella della proprietà; nel corso si prova di norma solo la proprietà e la correttezza dell'algoritmo ne è conseguenza immediata.

Complessità: la ricorrenza

Modello di costo: costa $1$ solo il confronto tra elementi di $A$; confronti tra indici, assegnamenti e il resto costano $0$. Il caso base costa $0$ (c'è solo un confronto tra indici). Per $n > 1$ si sommano i costi di Divide ($0$: nessun confronto tra elementi), Recurse (due chiamate, che introducono i termini impliciti) e Conquer ($1$: il confronto $m_1 \ge m_2$). Le due sottoistanze hanno taglie $k - i + 1 = \lceil n/2 \rceil$ e $j - k = \lfloor n/2 \rfloor$, quindi, per ogni $n \ge 1$, $$T(n) = \begin{cases} 0 & n = 1 \\ T\left(\lfloor n/2 \rfloor\right) + T\left(\lceil n/2 \rceil\right) + 1 & n > 1. \end{cases}$$

Una ricorrenza definisce $T(n)$ in funzione di valori di $T$ su argomenti minori; di solito è data a tratti, con i casi di base espliciti. Poiché il dominio di $T$ è $\mathbb{N}$, l'argomento deve essere sempre intero: non si può scrivere $2T(n/2) + 1$ senza ipotesi. Per $n$ potenza di $2$ i valori $n/2, n/4, \dots$ restano interi a ogni livello; non basta che $n$ sia pari (per $n = 6$ si arriva a $T(3)$, dispari, a cui la definizione semplificata non si applica). Con questa restrizione si risolve facilmente e si ricava l'ordine di grandezza; poi altre tecniche generalizzano.

Srotolamento (unfolding), $n = 2^k$. Si applica ripetutamente la definizione implicita fino ai casi di base: $$\begin{aligned} T(n) &= 2T(n/2) + 1 \\ &= 2^2 T(n/2^2) + 2 + 1 \\ &= 2^2\bigl(2T(n/2^3) + 1\bigr) + 2 + 1 = 2^3 T(n/2^3) + 2^2 + 2 + 1 \\ &\ \ \vdots \\ &= 2^i\, T(n/2^i) + \sum_{j=0}^{i-1} 2^j. \end{aligned}$$ Il processo si ferma quando $n/2^i$ è il caso base, $n/2^i = 1 \iff i = \log_2 n$ (vedi Esponenziale e logaritmoLa funzione esponenziale a^x (base positiva diversa da 1) e la sua inversa, il logaritmo in base a, con grafici e proprietà.Esponenziale e logaritmo →). Sostituendo, con $2^{\log_2 n} = n$ e $T(1) = 0$: $$T(n) = n\,T(1) + \sum_{j=0}^{\log_2 n - 1} 2^j = 0 + \bigl(2^{\log_2 n} - 1\bigr) = n - 1,$$ dove si è usata la somma geometrica troncata $\sum_{j=0}^{m-1} a^j = \frac{a^m - 1}{a - 1}$ per $a \ne 0, 1$ (qui $a = 2$; vedi SommatorieIl simbolo di sommatoria, le sue proprietà (linearità, additività, cambio di indice) e le somme notevoli di Gauss e geometrica.Sommatorie →).

Verifica della formula chiusa per induzione. Ottenuta una formula chiusa, una verifica per induzione protegge dagli errori di calcolo. Si prova $T(n) = n - 1$ per $n = 2^k$:

• [B] $n = 1$: $T(1) = 0 = n - 1$.
• [HP] $T(m) = m - 1$ per le potenze di $2$ minori di $n$, con $n > 1$.
• [TH] $T(n) = 2T(n/2) + 1$ e $n/2$ è una potenza di $2$ minore di $n$, quindi $T(n) = 2(n/2 - 1) + 1 = n - 1$.

Il vero parametro dell'induzione è $k = \log_2 n$, che varia sui naturali consecutivi e genera tutte le potenze di $2$. Che il risultato valga per ogni $n$, non solo per le potenze di due, si dimostra con l'induzione parametrica (Induzione parametrica - limitazioni esatte delle ricorrenzeL'induzione parametrica prova una limitazione T(n) <= cn+d (o >=) con costanti c e d incognite: si simula la verifica per induzione, si raccolgono i vincoli su c e d dalla base e dal passo HP => TH, e se l'intersezione non è vuota si sceglie la coppia migliore. Per MAX dà esattamente T(n) = n-1; può fallire anche con guess veri (si aggiunge un parametro o un termine di ordine inferiore).Induzione parametrica - limitazioni esatte delle ricorrenze →) oppure con l'albero (sotto).

Albero della ricorrenza di MAX

Per l'istanza $A = [1, 7, 1, 7]$ (taglia $4$) l'albero delle chiamate è:

                 [1 7 1 7]
                /         \
          [1 7]             [1 7]
          /   \             /   \
        [1]   [7]         [1]   [7]

Le frecce di generazione vanno verso il basso (Divide), quelle di risoluzione verso l'alto (Conquer). Si noti che questa chiamata risolve ripetutamente sottoistanze identiche ($[1\ 7]$ compare due volte) e replica tutto il lavoro: è la mancanza di memoria. Associando a ogni nodo il costo del suo Divide più Conquer (il lavoro, o work), si ottiene l'albero della ricorrenza: stessa forma, ma con la taglia nel nodo e il lavoro accanto.

               (4) 1
              /      \
        (2) 1          (2) 1
        /    \         /    \
    (1) 0  (1) 0   (1) 0  (1) 0

La somma di tutti i lavori è $3 = n - 1$, quindi $T(4) = 3$.

Per $n$ qualsiasi l'albero non è completo: per $n = 3$ la radice ha come figlio sinistro la foglia $A[1..1]$ e come destro il nodo interno $A[2..3]$, che genera le due foglie $A[2..2]$ e $A[3..3]$. Valgono però due fatti, per ogni $n$:

1. ogni nodo interno ha sempre due figli (due chiamate ricorsive su istanze non di base) e lavoro $1$;
2. ci sono esattamente $n$ foglie, perché ogni chiamata partiziona l'insieme del suo sottovettore in due sottoinsiemi disgiunti e si arriva alle $n$ istanze $A[1..1], \dots, A[n..n]$, tutte con lavoro $0$.

Un albero binario si dice pieno se ogni nodo interno ha esattamente $2$ figli (non confondere con completo, in cui tutte le foglie sono allo stesso livello).

Teorema. Un albero binario pieno con $n$ foglie ha sempre $n - 1$ nodi interni.

Dimostrazione per induzione su $n$.

• [B] Un albero pieno con una sola foglia non ha nodi interni ($n - 1 = 0$).
• [HP] La proprietà vale per gli alberi pieni con $k$ foglie, $1 \le k < n$, con $n > 1$.
• [TH] Sia $T$ un albero pieno con $n > 1$ foglie, quindi con almeno un nodo interno. Si prenda un nodo interno $v$ di livello massimo. I suoi figli stanno a un livello maggiore e non possono essere interni (altrimenti $v$ non avrebbe livello massimo tra gli interni): sono quindi due foglie. Sia $T'$ l'albero ottenuto togliendo i due figli di $v$. In $T'$ scompaiono due foglie e compare una nuova foglia ($v$), per cui $T'$ ha $n - 2 + 1 = n - 1$ foglie ed è ancora pieno; ha un nodo interno in meno di $T$. Per [HP] $T'$ ha $n - 2$ nodi interni, quindi $T$ ne ha $n - 2 + 1 = n - 1$. $\square$

Poiché in MAX i soli contributi non nulli vengono dai nodi interni, ciascuno di lavoro $1$, si conclude $T(n) = n - 1$ per ogni $n \ge 1$, in accordo con l'induzione parametrica. Un conteggio con Python conferma il risultato:

from functools import lru_cache

@lru_cache(None)
def T(n):                      # ricorrenza con parti intere
    return 0 if n == 1 else T(n // 2) + T(-(-n // 2)) + 1

assert all(T(n) == n - 1 for n in range(1, 2000))

Lavoro che dipende dall'istanza. Non sempre istanze della stessa taglia hanno lo stesso costo. Con MERGESORT, se il modello conta solo i confronti tra chiavi, durante la fusione appena uno dei due sottovettori è esaurito il resto dell'altro si copia senza altri confronti: il lavoro del Conquer in un nodo varia con l'istanza, pur restando limitato da (somma delle lunghezze) $- 1$. Per questo la ricorrenza di MERGESORT, nel caso peggiore, è $T(n) = 2T(n/2) + n - 1$ (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 →).

Domande d'esame

1. Si determini $T(12)$ per $T(1) = 12$, $T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil)$ per $n > 1$. Risposta: la ricorrenza ha lo stesso albero di MAX ($n$ foglie, nodi interni a lavoro nullo), con lavoro $12$ a ogni foglia: $T(n) = 12n$, $T(12) = 144$. Vedi Esercizio - domande di prima parte su problemi computazionali, ricorrenze e conteggi (simulazioni d'esame).
2. Quali condizioni deve soddisfare una proprietà di sottostruttura e perché? Risposta: sottoistanze di taglia strettamente minore (terminazione) e $i \,\Pi\, C(\langle s_1..s_k\rangle)$ per $i_j \,\Pi\, s_j$ (correttezza del Conquer); più la soluzione esplicita per $\lvert i\rvert \le n_0$.
3. Dimostrare che un albero binario pieno con $n$ foglie ha $n - 1$ nodi interni. Traccia: induzione su $n$ rimuovendo i due figli-foglia di un nodo interno di livello massimo.