Algoritmi/Il paradigma "divide et impera"

1. divide: un problema di dimensione $n$ viene ripartito in a sottoproblemi, ciascuno di dimensione ${\tfrac {n}{b}}$, tra loro indipendenti (↔ ricorsione su ogni sottoproblema);
2. impera: quando si arriva alla soluzione elementare, avviene la risoluzione diretta (↔ condizione di terminazione);
3. combina: le soluzioni parziali (elementari) vengono ricombinate per ottenere la soluzione del problema di partenza.

Equazioni alle ricorrenze

L'equazione alle ricorrenze permette di analizzare la complessità di ogni passo del procedimento divide et impera:

${\begin{cases}T\left(n\right)=D\left(n\right)+a\cdot T\left({n \over b}\right)+C\left(n\right),\quad n>c\\T\left(n\right)=\Theta \left(1\right),\quad n\leq c\end{cases}}$

1. divide: $D\left(n\right)$ (costo della divisione)
2. impera: $\Theta \left(1\right)$ (costo della soluzione elementare)
3. combina: $C\left(n\right)$ (costo della ricombinazione)

• $a$ = numero di sottoproblemi che risulta dalla fase di divide
• ${\tfrac {n}{b}}$ = dimensione di ciascun sottoproblema

Eseguire l'unfolding significa sviluppare alcuni passi di un'equazione alle ricorrenze per trovare una forma analitica chiusa della ricorrenza stessa sotto forma di sommatoria. Serve per analizzare la complessità di una funzione ricorsiva.

Ricerca binaria

Equazione alle ricorrenze

${\begin{cases}D\left(n\right)=\Theta \left(1\right)\\C\left(n\right)=\Theta \left(1\right)\\a=1,\,b=2\end{cases}}\rightarrow {\begin{cases}T\left(n\right)=T\left({n \over 2}\right)+1{\cancel {+1}},\quad n>1\\T\left(1\right)=1,\quad n=1\end{cases}}$

Unfolding

1. sviluppo: $T\left(n\right)=T\left({n \over 2}\right)+1=T\left({n \over 4}\right)+1+1=\cdots =T\left({n \over 2^{i}}\right)+\sum 1=\cdots$
2. condizione di terminazione: $T\left({n \over 2^{i}}\right)=T\left(1\right);\;{n \over 2^{i}}=1;\;i=\log _{2}{n}$
3. sommatoria: $T\left(n\right)=\sum _{i=0}^{\log _{2}{n}}1=1+\log _{2}{n}$
4. complessità asintotica: $T\left(n\right)=O\left(\log {n}\right)$ → algoritmo logaritmico

Ricerca del massimo di un vettore

Equazione alle ricorrenze

${\begin{cases}D\left(n\right)=\Theta \left(1\right)\\C\left(n\right)=\Theta \left(1\right)\\a=2,\,b=2\end{cases}}\rightarrow {\begin{cases}T\left(n\right)=2T\left({n \over 2}\right)+1{\cancel {+1}},\quad n>1\\T\left(1\right)=1,\quad n=1\end{cases}}$

• a = 2: il vettore viene suddiviso in due sottovettori
• b = 2: ciascun sottovettore è ampio la metà del vettore di partenza

Unfolding

• $T\left(n\right)=1+2+4+8T\left({n \over 8}\right)=1+2+4+\cdots =\sum _{i=0}^{\log _{2}{n}}2^{i}$
• progressione geometrica → $T\left(n\right)={\frac {2^{\log _{2}{n}+1}-1}{2-1}}=2^{\log _{2}{n}+1}-1=2n-1$
• $T\left(n\right)=O\left(n\right)$ → algoritmo lineare

Moltiplicazione rapida di 2 interi

$x\cdot y=x_{s}\cdot y_{s}\cdot {10}^{n}+x_{s}\cdot y_{d}\cdot {10}^{n \over 2}+x_{d}\cdot y_{s}\cdot {10}^{n \over 2}+x_{d}\cdot y_{d}$

Equazione alle ricorrenze

${\begin{cases}D\left(n\right)=\Theta \left(1\right)\\C\left(n\right)=\Theta \left(n\right)\\a=4,\,b=2\end{cases}}\rightarrow {\begin{cases}T\left(n\right)=4T\left({n \over 2}\right)+n{\cancel {+1}},\quad n>1\\T\left(1\right)=1,\quad n=1\end{cases}}$

• $C\left(n\right)=\Theta \left(n\right)$: per eseguire la somma binaria di due numeri di n cifre occorre scandire ciascuna cifra
• a = 4: i problemi ricorsivi sono le 4 operazioni di prodotto (le somme hanno complessità lineare ma non sono ricorsive)
• b = 2: x_s, x_d, y_s e y_d sono ampi la metà dei vettori di partenza

Unfolding

• $T\left(n\right)=n+4\cdot {n \over 2}+4^{2}\cdot {n \over 4}+4^{3}\cdot T\left({n \over 8}\right)=n\left(1+2+4+\cdots \right)=n\sum _{i=0}^{\log _{2}{n}}2^{i}$
• progressione geometrica → $T\left(n\right)=n\cdot \left(2^{\log _{2}{n}+1}-1\right)=2n^{2}-n$
• $T\left(n\right)=O\left(n^{2}\right)$ → algoritmo quadratico

Moltiplicazione rapida di 2 interi ottimizzata

Equazione alle ricorrenze

$a=3\rightarrow T\left(n\right)=3T\left({n \over 2}\right)+n$

Unfolding

• $T\left(n\right)=n+3\cdot {n \over 2}+3^{2}\cdot {n \over 4}+3^{3}\cdot T\left({n \over 8}\right)=n\left[1+{3 \over 2}+{\left({3 \over 2}\right)}^{2}+\cdots \right]=n\sum _{i=0}^{\log _{2}{n}}{\left({3 \over 2}\right)}^{i}$
• progressione geometrica → $T\left(n\right)=2n\left[{\left({3 \over 2}\right)}^{\log _{2}{n}+1}-1\right]=3\cdot 3^{\log _{2}{n}}-2n$
• per la proprietà dei logaritmi: $a^{log_{b}{n}}=n^{log_{b}{a}}\rightarrow T\left(n\right)=3\cdot n^{log_{2}{3}}{\cancel {-2n}}$
• $T\left(n\right)=O\left(n^{\log _{2}{3}}\right)$ → più efficiente della moltiplicazione non ottimizzata ($\log _{2}{3}<2$)

 

Le Torri di Hanoi

Ho k = 3 pioli verticali, con n = 3 dischi forati in ordine decrescente di diametro sul primo piolo. Si vuole portarli tutti e 3 sul terzo piolo. Condizioni per lo spostamento:

1. si può spostare un solo piolo per volta;
2. sopra ogni disco solo dischi più piccoli.

Il problema si suddivide in 3 sottoproblemi:

1. problema da n − 1: 000 → 011 (2 deposito) → si suddivide a sua volta in 3 sottoproblemi elementari
2. problema da 1: 011 → 211 → sottoproblema elementare
3. problema da n − 1: 211 → 222 (0 deposito) → si suddivide a sua volta in 3 sottoproblemi elementari

Equazione alle ricorrenze: $T\left(n\right)=2T\left(n-1\right)+1$

1. dividi: $D\left(n\right)=\Theta \left(1\right)$ (considero n − 1 dischi)
2. risolvi: $2T\left(n-1\right)$ (ho 2 sottoproblemi ciascuno da n − 1)
3. impera: $\Theta \left(1\right)$ (termino quando sposto un disco solo)
4. combina: $C\left(n\right)=\Theta \left(1\right)$ (nessuna combinazione)

Unfolding:

• $T\left(n\right)=1+2+4+8T\left(n-3\right)=2^{0}+2^{1}+2^{2}+\cdots$
• $n-i=1;\;i=n-1\rightarrow T\left(n\right)=\sum _{i=0}^{n-1}2^{i}$
• progressione geometrica → $T\left(n\right)=2^{n}{\cancel {-1}}$
• $T\left(n\right)=O\left(2^{n}\right)$ → algoritmo esponenziale (anche se decidibile)

Il righello

Disegnare le tacche di un righello in maniera ricorsiva, di differenti altezze, fino a quando si arriva all'altezza 0. Si disegna ricorsivamente a metà del sottointervallo la tacca, quindi si considerano i due sottointervalli sinistro e destro e si disegna la tacca di una unità di altezza inferiore.

Backtrack: Si esplora una scelta per volta, e se la scelta non va bene si ritorna indietro. (vd. filo di Arianna) Si termina quando tutte le scelte sono esaurite. Tramite il backtrack si può esplorare tutto lo spazio delle soluzioni.

Gli algoritmi ricorsivi di ordinamento

Merge sort (o ordinamento per fusione)

Passi

1. divide: si suddivide il vettore in due sottovettori
2. ricorsione:
   • si applica il merge sort sul sottovettore sinistro
   • si applica il merge sort sul sottovettore destro
   • condizione di terminazione: il sottovettore ha 1 cella
3. combina: si uniscono tutti i sottovettori ordinati, scandendo in parallelo i due sottovettori da sinistra verso destra e confrontando di volta in volta i valori scegliendo quello minore:

Analisi di complessità

Ragionamento intuitivo: ho $\log _{2}{n}$ livelli di ricorsione e devo fare ${\tfrac {n}{2}}+{\tfrac {n}{2}}=n$ unioni → $n\log _{2}{n}$ operazioni totali:

Equazione alle ricorrenze

${\begin{cases}T\left(n\right)=2T\left({n \over 2}\right)+n,\quad n>1\\T\left(1\right)=1,\quad n=1\end{cases}}$

1. dividi: $D\left(n\right)=\Theta \left(1\right)$ (calcola la metà di un vettore)
2. risolvi: $2T\left({\tfrac {n}{2}}\right)$ (risolve 2 sottoproblemi di dimensione ${\tfrac {n}{2}}$ ciascuno)
3. terminazione: $\Theta \left(1\right)$ (semplice test)
4. combina: $C\left(n\right)=\Theta \left(n\right)$

Unfolding

$T\left(n\right)=n+2\cdot {n \over 2}+2^{2}\cdot {n \over 4}+2^{3}T\left({n \over 8}\right)=\sum _{i=0}^{\log _{2}{n}}n=n\sum _{i=0}^{log_{2}{n}}1=n\left(1+\log _{2}{n}\right)=n\log _{2}{n}{\cancel {+n}}$

$T\left(n\right)=O\left(n\log {n}\right)$ → algoritmo linearitmico (ottimo)

Quicksort

Passi

È quadratico ($O\left(n^{2}\right)$) → secondo la teoria degli algoritmi non dovrebbe essere ottimo, però: sperimentalmente si dimostra che il caso peggiore ricorre molto raramente, a differenza del caso medio.

Partizione: La divisione non avviene a metà, ma secondo una certa proprietà: sceglie arbitrariamente un elemento separatore (= pivot), quindi separa gli altri valori in sottovettore sinistro e destro a seconda se sono minori o maggiori del pivot.

Individua (tramite un ciclo ascendente su i e un ciclo discendente su j) una coppia di elementi di indici i e j che siano entrambi fuori posto (ovvero l'i-esimo è maggiore del pivot, e il j-esimo è minore del pivot), quindi li scambia.

Condizione di terminazione: i == j (si ferma quando tutte le coppie sono già a posto).

Costo della partizione: $T\left(n\right)=\Theta \left(n\right)$ (cioè la scansione di tutti gli n elementi).

Al termine della ricorsione è inutile una fase di ricombinazione, perché i dati si trovano già nella posizione corretta.

Analisi di complessità

Il quicksort non segue la formula generale del divide et impera.

Caso peggiore

Il vettore si trova in ordine inverso → la partizione genera un sottovettore da n ‒ 1 elementi e l'altro da 1 elemento.

Equazione alle ricorrenze:

$T\left(n\right)=T\left(1\right)+T\left(n-1\right)+n+1=T\left(n-1\right)+n{\cancel {+2}}$

• $T\left(1\right)$ = costo per il sottovettore da 1 elemento
• $T\left(n-1\right)$ = costo per il sottovettore da n ‒ 1 elementi
• $n$ = costo della partizione
• $1$ = costo unitario della risoluzione (riguarda gli elementi al termine della ricorsione)

Unfolding:

$T\left(n\right)=n+T\left(n-1\right)=n+\left(n-1+T\left(n-2\right)\right)=\cdots ={n \over 2}\left(n+1\right)$

Caso migliore

Ogni sottovettore è esattamente la metà → ricorda il merge sort (in questo caso è linearitmico).

Caso medio

Partizione fortemente sbilanciata, senza arrivare al caso peggiore → il quicksort è linearitmico.

È meglio cercare un pivot in modo da dividere sempre in maniera conveniente il vettore → la complessità non cambia (neanche prendendo un pivot che separa sempre il vettore a metà), ma si possono ridurre le costanti.