Divide et Impera

Un approccio per ideare algoritmi ricorsivi si basa sul paradigma di Divide et Impera. Il metodo divide et impera applica tre passi ad ogni livello di ricorsione:

• Divide: questo passo divide il problema in un certo numero di sottoproblemi, che sono istanze più piccole dello stesso problema.
• Impera: i sottoproblemi vengono risolti in modo ricorsivo. Ovviamente, quando i sottoproblemi hanno una dimensione sufficientemente piccola, essi vengono risolti direttamente.
• Combina: le soluzioni dei sottoproblemi vengono combinate per generare la soluzione del problema originale.

Quando i sottoproblemi sono abbastanza grandi da essere risolti ricorsivamente, si ha il cosiddetto caso ricorsivo. Mentre sei sottoproblemi hanno una dimensione sufficientemente piccola da non richiedere ricorsione, si dice che la ricorsione ha toccato il fondo e che si è raggiunto il caso base. A volte, oltre ai sottoproblemi che sono istanze più piccole dello stesso problema, dobbiamo anche risolvere dei sottoproblemi che non sono affatto uguali al problema originale. Noi consideriamo la soluzione di questi sottoproblemi come parte del passo combina.

Ricorrenze

Le ricorrenze vanno mano nella mano con il paradigma di divide et impera, in quanto ci offrono un modo naturale per caratterizzare i tempi di esecuzione degli algoritmi divide et impera. Una ricorrenza è un’equazione o disequazione che descrive una funzione in termini del suo valore con input più piccoli. Un esempio di ricorrenza è la ricorrenza che caratterizza il tempo di esecuzione di merge-sort:

$T(n)=\{\begin{array}{cc}\mathrm{\Theta }(1)& \text{se }n=1\\ 2T(n/2)+\mathrm{\Theta }(n)& \text{se }n>1\end{array}$

la cui soluzione è $T(n)=\mathrm{\Theta }(n\cdot lo{g}_2(n))$

Risolvere le ricorrenze

Le ricorrenze possono avere varie forme: non sempre un algoritmo divide il problema originale in due sottoproblemi, può capitare una ripartizione 1/3 e 2/3, e non tutti gli algoritmi che adottano questo approccio dividono il problema in sottoproblemi di dimensione costante. Dato questa grande varietà di casistiche sono stati elaborati tre metodi per risolvere le ricorrenze:

• Metodo di sostituzione: si ipotizza un limite e poi si usa l’induzione matematica per dimostrare che l’ipotesi è corretta
• Metodo dell’albero di ricorsione: converte la ricorrenza in un albero i cui nodi rappresentano i costi ai vari livelli della ricorsione; per risolvere la ricorrenza si adottano tecniche che limitano le sommatorie.
• Metodo dell’esperto: fornisce i limiti per ricorrenze della forma $T(n)=aT(n/b)+f(n)$ dove $a\ge 1,b>1\text{ e }f(n)$ è una funzione data. Una ricorrenza di questa forma caratterizza un algoritmo "divide et impera" che crea $a$ sottoproblemi, ciascuno dei quali ha una dimensione pari a $1/b$ quella del problema originale ed in cui i passi divide e combina insieme richiedono un tempo $f(n)$.

Metodo di sostituzione

Il metodo di sostituzione per risolvere le ricorrenze richiede due passi:

1. Ipotizzare la forma della soluzione
2. Usare l'induzione matematica per trovare le costanti e dimostrare che la soluzione funziona.

Questo metodo è potente, ma il problema è che può essere solamente applicato nei casi in cui sia facile immaginare la forma della soluzione. Il metodo di sostituzione può essere usato per determinare il limite inferiore o superiore di una ricorrenza. Ad esempio, si consideri la seguente ricorrenza:

$T(n)=\{\begin{array}{cc}\mathrm{\Theta }(1)& \text{se }n=1\\ 3T(n/3)+n^3& \text{se }n>1\end{array}$

Supponiamo che la soluzione sia $T(n)=O(n^3)$. Il nostro metodo consiste nel dimostrare che esistono delle costanti positive $c\text{ ed }{n}_0$ tali che $T(n)\le c{n}^3$ per ogni $n\ge n_0$. Procediamo per induzione su $n$.

• Caso base: $n=1$. Se scegliamo $c\ge 1\text{ allora }T(1)=1\le c=c{1}^3$.
• Passo induttivo: $n\ge 1$.

$\begin{array}{cc}T(n)& =n^3+3T(n/3)\\ \\ & \le n^3+3c(n/3{)}^3\text{ per ip. induttiva }T(n/3)\le c(n/3{)}^3\\ \\ & =n^3+\frac{1}{9}c{n}^3\\ \\ & =(1+\frac{1}{9}c)n^3\\ \\ & \le c{n}^3\end{array}$

L'ultima disuguaglianza è vera solo se la costante $c$ è scelta in maniera tale che $1+\frac{1}{9}c\le c$, ossia se $c-\frac{1}{9}c\ge 1$, il che implica $\frac{8}{9}c\ge 1\text{ e quindi }c\ge \frac{9}{8}$. Ricapitolando se scegliamo $c\ge \frac{9}{8}\text{ e }{n}_0=1$, allora $T(n)\le c{n}^3\text{ per ogni }n\ge n_0$.

Metodo dell'albero di ricorsione

Il metodo dell'albero di ricorsione permette di visualizzare lo sviluppo della ricorsione e dei costi. Ogni nodo rappresenta il costo di una particolare sotto problema appartenente all'insieme delle chiamate ricorsive della funzione. Il valore della ricorrenza viene calcolato sommando prima i costi dei nodi su ciascun livello, e poi determinando il costo totale di tutti i livelli dell'albero di ricorsione. Un albero di ricorsione è un ottimo metodo per ottenere una buona ipotesi, che poi viene verificata col metodo di sostituzione. Si può però usare anche l'albero di ricorsione come prova diretta di una soluzione della ricorrenza. Per esempio vediamo come un albero di ricorsione possa fornire una buona ipotesi per la ricorrenza:

Albero di ricorsione per T(n)=2T(n/2)+cn^2

$T(n)=\{\begin{array}{cc}\mathrm{\Theta }(1)& \text{se }n=1\\ 2T(n/2)+\mathrm{\Theta }(n^2)& \text{se }n>1\end{array}$

Creiamo un albero di ricorsione per la ricorrenza $T(n)=2T(n/2)+c{n}^2$, ricordando che il coefficiente $c>0$ è costante. Osserviamo che:

• ogni livello $i$ ha $2^i$ nodi ognuno dei quali ha un costo pari ha ${\left(\frac{n}{2^i}\right)}^2$. Il costo di ciascun livello è:

$c_i=2^i\cdot {\left(\frac{n}{2^i}\right)}^2=\frac{n^2}{2^i}$.

• l'ultimo livello corrisponde ad una chiamata di $T\left(\frac{n}{2^h}\right)$ con $\frac{n}{2^h}=1$ e quindi $h=lo{g}_2(n)$.
• $T(n)$ è pari alla somma della somma dei costi associati a ciascun nodo dell'albero di ricorsione. Quindi:

$\begin{array}{cc}T(n)& =\sum _{i=0}^{lo{g}_2(n)}\frac{n^2}{2^i}=n^2\sum _{i=0}^{lo{g}_2(n)}\frac{1}{2^i}=n^2\frac{1-{\left(\frac{1}{2}\right)}^{lo{g}_2(n)+1}}{1-\frac{1}{2}}\\ \\ & =n^2\frac{1-\frac{1}{2}\cdot {\frac{1}{2}}^{lo{g}_2(n)}}{\frac{1}{2}}=\frac{n^2}{2}\cdot (1-\frac{1}{2}\cdot {\left(\frac{1}{2}\right)}^{lo{g}_{2}n})\\ \\ & =\frac{n^2}{2}(1-\frac{1}{2\cdot 2^{lo{g}_{2}n}})=\frac{n^2}{2}(1-\frac{1}{2\cdot n^{lo{g}_2(2)}})=\frac{n^2}{2}(1-\frac{1}{2n})\\ \\ & =\frac{n^2}{2}\left(\frac{2n-1}{2n}\right)=\frac{n^2}{2}-\frac{n}{4}=\mathrm{\Theta }(n^2)\end{array}$

Metodo dell'esperto

il metodo dell'esperto rappresenta un "ricettario" per risolvere le ricorrenze della forma $T(n)=aT(n/b)+f(n)\text{ dove }a\ge 1\text{ e }b>1$ sono costanti e $f(n)$ è una funzione asintoticamente positiva. La ricorrenza $T(n)=aT(n/b)+f(n)$ descrive il tempo di esecuzione di un algoritmo che divide un problema di dimensione $n\text{ in }a$ sottoproblemi, ciascuno di dimensione $n/b$. Mentre la funzione $f(n)$ comprende il costo per dividere il problema e combinare i risultati dei sottoproblemi.

Teorema

Date le costanti $a\ge 1\text{ e }b>1$ e la funzione $f(n)$, sia $T(n)$ una funzione definita sugli interi non negativi dalla ricorrenza $T(n)=aT(n/b)+f(n)$ dove $n/b$ rappresenta $\lfloor (n/b)\rfloor \text{ (floor di }n/b\text{) o }\lceil (n/b)\rceil \text{ (ceil di }n/b\text{)}$.Allora $T(n)$ può essere asintoticamente limitata nei seguenti modi:

1. Se $f(n)=O(n^{lo{g}_b(a-ϵ)})\text{ per qualche costante }ϵ>0,\text{ allora }T(n)=\mathrm{\Theta }(n^{lo{g}_b(a)})$.
2. Se $f(n)=\mathrm{\Theta }(n^{lo{g}_b(a)}),\text{ allora }T(n)=\mathrm{\Theta }(n^{lo{g}_b(a)}\cdot lo{g}_2(n))$.
3. Se $f(n)=\mathrm{\Omega }(n^{lo{g}_b(a+ϵ)})\text{ per qualche costante }ϵ>0\text{ e se }af(n/b)\le cf(n)\text{ per qualche costante }c<1\text{ e per ogni }n\text{ sufficientemente grande},\text{ allora }T(n)=\mathrm{\Theta }(f(n))$.

Intuitivamente, il teorema afferma che, data una relazione di ricorrenza della forma $T(n)=aT(n/b)+f(n)\text{ dove }a\ge 1\text{ e }b>1$, la soluzione si può ottenere confrontando la funzione $f(n)$ con la funzione $n^{lo{g}_b(a)}$. Se la funzione $f$ è asintoticamente più piccola di $n^{lo{g}_b(a)}$ per un fattore $n^{ϵ}$, per qualche costante $ϵ>0$, allora $T(n)=\mathrm{\Theta }(n^{lo{g}_b(a)})$; se le due funzioni asintoticamente hanno la stessa grandezza allora $T(n)=\mathrm{\Theta }(n^{lo{g}_b(a)}\cdot lo{g}_{2}n)$; infine, se $f(n)$ è polinomialmente più grande di $n^{lo{g}_b(a)}$ e soddisfa la condizione di regolarità $af(n/b)\le cf(n)$, allora la soluzione è $T(n)=\mathrm{\Theta }(f(n))$.

Applicazione del teorema dell'esperto

Per utilizzare il metodo dell'esperto, determiniamo semplicemente quale caso (se esiste) del teorema dell'esperto possiamo applicare e scriviamo la soluzione. Per esempio consideriamo le tre seguenti ricorrenze:

• $T(n)=4T(n/2)+n$
• $T(n)=4T(n/2)+n^2$
• $T(n)=4T(n/2)+n^3$

In tutti e tre i casi abbiamo che $a=4\text{ e }b=2$. Cambia invece il "rapporto" tra $f(n)\text{ e }{n}^{lo{g}_b(a)}=n^2$. Ognuna delle tre ricorrenze corrisponde ad un diverso caso del teorema dell'esperto.

• $f(n)=n\text{ e }f(n)=O(n)=\mathrm{\Theta }(n^{lo{g}_b(a-ϵ)})\text{ con }ϵ=1>0$ (in altri termini $n^{lo{g}_b(a)}$ è un limite superiore per $f(n)$). Primo caso del teorema dell'esperto: $T(n)=\mathrm{\Theta }(n^{lo{g}_b(a)})=\mathrm{\Theta }(n^2)$.
• $f(n)=n^2\text{ ed }f(n)=O(n^2)=\mathrm{\Theta }(n^{lo{g}_b(a)})$ (ossia $n^{lo{g}_b(a)}$ è un limite stretto per $f(n)$). Secondo caso del teorema dell'esperto: $T(n)=\mathrm{\Theta }(n^{lo{g}_b(a)}\cdot lo{g}_2(n))=\mathrm{\Theta }(n^2\cdot lo{g}_2(n))$.
• $f(n)=n^3\text{ ed }f(n)=\mathrm{\Omega }(n^3)=\mathrm{\Omega }(n^{lo{g}_b(a+ϵ)})\text{ con }ϵ=1>0$ (ossia, $n^{lo{g}_b(a)}$ è un limite inferiore per $f(n)$). Terzo caso del teorema dell'esperto: $T(n)=\mathrm{\Theta }(f(n))=\mathrm{\Theta }(n^3)$.

Consideriamo, però anche un caso dove il metodo dell'esperto non si può applicare. Consideriamo la seguente ricorrenza:

$T(n)=2T(n/2)+n\cdot lo{g}_2(n)$

dove $a=2\text{ , }b=2\text{ , }f(n)=n\cdot lo{g}_2(n)\text{ e }{n}^{lo{g}_b(a)}=n$. Potremmo erroneamente ritenere che si possa applicare il caso 3, in quanto $f(n)=n\cdot lo{g}_2(n)$ è asintoticamente più grande di $n^{lo{g}_b(a)}=n$; il problema è che non è polinomialmente più grande. Il rapporto $f(n)/n^{lo{g}_b(a)}=(n\cdot lo{g}_2(n))/n=lo{g}_2(n)$ è asintoticamente minore di $n^{ϵ}$ per qualsiasi costante positiva $ϵ$. Quindi, la ricorrenza ricade nell'intervallo fra i casi 2 e 3.