# Algoritmi/Il paradigma "divide et impera"

Algoritmi
Copertina Tutti i moduli · Sviluppo
    CopertinaAlgoritmi/Copertina
* Gli algoritmiAlgoritmi/Gli algoritmi
* L'analisi di complessità degli algoritmiAlgoritmi/L'analisi di complessità degli algoritmi
* Gli algoritmi di ordinamentoAlgoritmi/Gli algoritmi di ordinamento
* Grafi e alberiAlgoritmi/Grafi e alberi
* La ricorsioneAlgoritmi/La ricorsione
* Il paradigma "divide et impera"Algoritmi/Il paradigma "divide et impera"
* Gli heapAlgoritmi/Gli heap
* Le tabelle di simboliAlgoritmi/Le tabelle di simboli
* Alberi binari di ricerca (BST)Algoritmi/Alberi binari di ricerca (BST)
* Tipologie di problemiAlgoritmi/Tipologie di problemi
* Le tabelle di hashAlgoritmi/Le tabelle di hash
* L'ADT grafo non orientatoAlgoritmi/L'ADT grafo non orientato
* Gli algoritmi di visita dei grafiAlgoritmi/Gli algoritmi di visita dei grafi
* Le applicazioni degli algoritmi di visita dei grafiAlgoritmi/Le applicazioni degli algoritmi di visita dei grafi
* Gli alberi ricoprenti minimiAlgoritmi/Gli alberi ricoprenti minimi
* I cammini minimiAlgoritmi/I cammini minimi
Modifica il sommario
* divide: un problema di dimensione $n$ viene ripartito in a sottoproblemi, ciascuno di dimensione ${\tfrac {n}{b}}$, tra loro indipendenti (↔ ricorsione su ogni sottoproblema);
* impera: quando si arriva alla soluzione elementare, avviene la risoluzione diretta (↔ condizione di terminazione);
* 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}}$
* divide: $D\left(n\right)$ (costo della divisione)
* impera: $\Theta \left(1\right)$ (costo della soluzione elementare)
* 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

* 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$
* condizione di terminazione: $T\left({n \over 2^{i}}\right)=T\left(1\right);\;{n \over 2^{i}}=1;\;i=\log _{2}{n}$
* sommatoria: $T\left(n\right)=\sum _{i=0}^{\log _{2}{n}}1=1+\log _{2}{n}$
* 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:
* si può spostare un solo piolo per volta;
* sopra ogni disco solo dischi più piccoli.
Il problema si suddivide in 3 sottoproblemi:
* problema da n − 1: 000 → 011 (2 deposito) → si suddivide a sua volta in 3 sottoproblemi elementari
* problema da 1: 011 → 211 → sottoproblema elementare
* 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$
* dividi: $D\left(n\right)=\Theta \left(1\right)$ (considero n − 1 dischi)
* risolvi: $2T\left(n-1\right)$ (ho 2 sottoproblemi ciascuno da n − 1)
* impera: $\Theta \left(1\right)$ (termino quando sposto un disco solo)
* 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

* divide: si suddivide il vettore in due sottovettori
* 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
* 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}}$
* dividi: $D\left(n\right)=\Theta \left(1\right)$ (calcola la metà di un vettore)
* risolvi: $2T\left({\tfrac {n}{2}}\right)$ (risolve 2 sottoproblemi di dimensione ${\tfrac {n}{2}}$ ciascuno)
* terminazione: $\Theta \left(1\right)$ (semplice test)
* 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.

## Note

* ↑ Per semplicità si suppone n una potenza esatta di 2.