FANDOM


  1. 2 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 ricorrenzeModifica

5 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 binariaModifica

7 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}
8 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}[1]
  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 vettoreModifica

9 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) = 2 T \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
10 Unfolding

Moltiplicazione rapida di 2 interiModifica

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
11 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) = 4 T \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: xs, xd, ys e yd sono ampi la metà dei vettori di partenza
12 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) = 2 n^2 - n
  • T \left( n \right) = O \left( n^2 \right) → algoritmo quadratico

Moltiplicazione rapida di 2 interi ottimizzataModifica

13 Equazione alle ricorrenze
a=3 \rightarrow T\left( n \right) = 3 T \left( {n \over 2} \right) +n
14 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 HanoiModifica

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: 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: 2 T \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)

43 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 righelloModifica

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 ordinamentoModifica

Merge sort (o ordinamento per fusione)Modifica

PassiModifica

  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
  • 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:
Ricombinazione merge sort

Analisi di complessitàModifica

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

Merge sort intuitivo
21 Equazione alle ricorrenze
\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}
  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)
22 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)

QuicksortModifica

PassiModifica

24 È 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.

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: T \left( n \right) = \Theta \left( n \right) (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àModifica

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:

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

NoteModifica

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

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

Inoltre su FANDOM

Wiki casuale