Algoritmi e programmazione/Il paradigma "divide et impera"

Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 6. Il paradigma "divide et impera".

[[{{#ifcategory:Traduzioni||Algoritmi e programmazione|/Il paradigma "divide et impera"}}/La ricorsione{{#ifcategory:Traduzioni|/Il paradigma "divide et impera"||/Il paradigma "divide et impera"}}|5. La ricorsione]]	[[{{#ifcategory:Traduzioni|/Il paradigma "divide et impera"|Algoritmi e programmazione|/Il paradigma "divide et impera"}}|{{#ifcategory:Traduzioni||Algoritmi e programmazione|/Il paradigma "divide et impera"}}]]	[[{{#ifcategory:Traduzioni||Algoritmi e programmazione|/Il paradigma "divide et impera"}}/Gli heap{{#ifcategory:Traduzioni|/Il paradigma "divide et impera"||/Il paradigma "divide et impera"}}|7. Gli heap]]

1. 2 divide: un problema di dimensione <math>n</math> viene ripartito in a sottoproblemi, ciascuno di dimensione <math>\tfrac{n}{b}</math>, 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

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

<math>\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}</math>

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

• <math>a</math> = numero di sottoproblemi che risulta dalla fase di divide
• <math>\tfrac{n}{b}</math> = 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

7 Equazione alle ricorrenze

<math>\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}</math>

8 Unfolding

1. sviluppo: <math>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</math>
2. condizione di terminazione: <math>T \left( {n \over 2^i} \right) = T \left( 1 \right) ; \; {n \over 2^i} = 1 ; \; i = \log_2{n}</math>
3. sommatoria: <math>T \left( n \right) = \sum_{i = 0}^{\log_2{n}} 1 = 1 + \log_2{n}</math>
4. complessità asintotica: <math>T \left( n \right) = O \left( \log{n} \right)</math> → algoritmo logaritmico

Ricerca del massimo di un vettore

9 Equazione alle ricorrenze

<math>\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) = 2 T \left( {n \over 2} \right) + 1 \cancel{+ 1} , \quad n > 1 \\ T \left( 1 \right) = 1 , \quad n = 1 \end{cases}</math>

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

10 Unfolding

• <math>T \left( n \right) = 1 + 2 + 4 + 8 T \left( {n \over 8} \right) = 1 + 2 + 4 + \cdots = \sum_{i = 0}^{\log_2{n}} 2^i</math>
• progressione geometrica → <math>T \left( n \right) = \frac{2^{\log_2{n} + 1} - 1}{2-1} = 2^{\log_2{n} + 1} - 1 = 2n - 1</math>
• <math>T \left( n \right) = O \left( n \right)</math> → algoritmo lineare

Moltiplicazione rapida di 2 interi

<math>x \cdot y = x_s \cdot y_s \cdot {10}^n + x_s \cdot y_d \cdot {10}^Template:N \over 2 + x_d \cdot y_s \cdot {10}^Template:N \over 2 + x_d \cdot y_d</math>

11 Equazione alle ricorrenze

<math>\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) = 4 T \left( {n \over 2} \right) + n \cancel{+ 1} , \quad n > 1 \\ T \left( 1 \right) = 1 , \quad n = 1 \end{cases}</math>

• <math>C \left( n \right) = \Theta \left( n \right)</math>: 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

12 Unfolding

• <math>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</math>
• progressione geometrica → <math>T \left( n \right) = n \cdot \left( 2^{\log_2{n} + 1} - 1 \right) = 2 n^2 - n</math>
• <math>T \left( n \right) = O \left( n^2 \right)</math> → algoritmo quadratico

Moltiplicazione rapida di 2 interi ottimizzata

13 Equazione alle ricorrenze

<math>a=3 \rightarrow T\left( n \right) = 3 T \left( {n \over 2} \right) +n</math>

14 Unfolding

• <math>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</math>
• progressione geometrica → <math>T \left( n \right) = 2n \left[ {\left( {3 \over 2} \right)}^{\log_2{n} + 1} - 1 \right] = 3 \cdot 3^{\log_2{n}} - 2n</math>
• per la proprietà dei logaritmi: <math>a^{log_b{n}} =n^{log_b{a}} \rightarrow T \left( n \right) = 3 \cdot n^{log_2{3}} \cancel{-2n}</math>
• <math>T \left( n \right) = O \left( n^{\log_2{3}} \right)</math> → più efficiente della moltiplicazione non ottimizzata (<math>\log_2{3} < 2</math>)

 

Le Torri di Hanoi

36 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.

41 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

42 Equazione alle ricorrenze: <math>T \left( n \right) = 2T \left( n - 1 \right) +1</math>

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

43 Unfolding:

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

Il righello

44 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.

48 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. 17 divide: si suddivide il vettore in due sottovettori
2. 18 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à

23 Ragionamento intuitivo: ho <math>\log_2{n}</math> livelli di ricorsione e devo fare <math>\tfrac{n}{2} + \tfrac{n}{2} = n</math> unioni → <math>n \log_2{n}</math> operazioni totali:

21 Equazione alle ricorrenze

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

T \left( 1 \right) = 1 , \quad n = 1 \end{cases}</math>

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

22 Unfolding

<math>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}</math>

<math>T \left( n \right) = O \left( n \log{n} \right)</math> → algoritmo linearitmico (ottimo)

Quicksort

Passi

24 È quadratico (<math>O \left( n^2 \right)</math>) → 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.

26 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: <math>T \left( n \right) = \Theta \left( n \right)</math> (cioè la scansione di tutti gli n elementi).

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

Analisi di complessità

30 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:

<math>T \left( n \right) = T \left( 1 \right) +T \left( n-1 \right) +n+1= T \left( n-1 \right) +n \cancel{+2}</math>

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

Unfolding:

<math>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)</math>

31 Caso migliore

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

32 Caso medio

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

34 È 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

Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 6. Il paradigma "divide et impera".

[[{{#ifcategory:Traduzioni||Algoritmi e programmazione|/Il paradigma "divide et impera"}}/La ricorsione{{#ifcategory:Traduzioni|/Il paradigma "divide et impera"||/Il paradigma "divide et impera"}}|5. La ricorsione]]	[[{{#ifcategory:Traduzioni|/Il paradigma "divide et impera"|Algoritmi e programmazione|/Il paradigma "divide et impera"}}|{{#ifcategory:Traduzioni||Algoritmi e programmazione|/Il paradigma "divide et impera"}}]]	[[{{#ifcategory:Traduzioni||Algoritmi e programmazione|/Il paradigma "divide et impera"}}/Gli heap{{#ifcategory:Traduzioni|/Il paradigma "divide et impera"||/Il paradigma "divide et impera"}}|7. Gli heap]]