Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Massimo Benerecetti » 3.Analisi di algoritmi ricorsivi


Divide et Impera

Il problema viene suddiviso in sottoproblemi analoghi, che vengono risolti separatamente.
Le soluzioni dei sottoproblemi vengono infine fuse insieme per ottenere la soluzione dei problemi più complessi.
Consiste di 3 passi:

  1. Divide il problema in vari sottoproblemi, tutti simili (tra loro e) al problema originario ma più semplici.
  2. Impera (conquista) i sottoproblemi risolvendoli ricorsivamente. Quando un sottoproblema diviene banale, risolverlo direttamente.
  3. Fondi le soluzioni dei sottoproblemi per ottenere la soluzione del (sotto)problema che li ha originati.

MergeSort: Intuizione

  • Input: una sequenza di numeri.
  • Output: una permutazione (riordinamento) tale che tra ogni coppia di elementi adiacenti nella sequenza valga “qualche” relazione di ordinamento (ad es. ≤).

Merge Sort (divide et impera)

  1. Divide: scompone la sequenza di n elementi in due sottosequenze di \frac{n}{2} elementi ciascuna.
  2. Impera: risolve i sottoproblemi, ordinando ricorsivamente le sottosequenze separatamente (tramite MergeSort stesso). Quando una sottosequenza è unitaria o vuota, il sottoproblema è banale.
  3. Fondi: compone insieme le soluzioni dei due sottoproblemi, per ottenere la sequenza ordinata del problema.

MergeSort: Intuizione (segue)

Algoritmo:

  1. A[1..n]: sequenza dei numeri in input
  2. p,r: indici degli estremi della sottosequenza da ordinare

MergeSort(array A, int p,r)
1 if p < r then

2 q = \left\lfloor\frac{(p+r)}{2}\right\rfloor\ \ \xrightarrow{\hspace{2cm}} [Divide]
3 MergeSort(A,p,q) \ \xrightarrow{\hspace{2cm}}[Impera]
4 MergeSort(A,q+1,r) \ \xrightarrow{\hspace{1.8cm}}[Impera]
5 Merge(A,p,q,r) \ \xrightarrow{\hspace{2.2cm}}[Fondi]

L’algoritmo Merge

La funzione Merge(A,p,q,r) fonde le sue sottosequenze ordinate (una tra p e q e l’altra tra q+1 e r) in un’unica sequenza ordinata tra p e r. Al fine di mantenere il suo tempo di esecuzione lineare (T_{merge}(n)=\Theta(n)), utilizza un array di appoggio B (locale) per effettuare gli spostamenti necessari.

L’algoritmo Merge (segue)


Merge: analisi

L’algoritmo di Merge ha tempo di esecuzione lineare sulla lunghezza n delle sequenza da p a r:

  • il ciclo for alle linee 1 e 2 copia la sequenza in A dentro B, viene eseguit un numero di volte lineare sulla dimensione n sequenza in input tra p e r;
  • il primo ciclo while (linee 6-12) viene eseguito un numero di volte necessariamente non superiore alla lunghezza di una delle due sottosequenze (che sono di linghezza inferiore a n);
  • l’ultimo ciclo while (linee 13-16) viene eseguito un numero di volte non superiore alla sottosequenza tra p e q, quindi ancora una volta non superiore a n;
  • poiché, le operazioni contenute nei tre cicli impiegano ciascuna un numero costante di operazioni elementari, segue che complessivamente l’algoritmo impiegherà tempo lineare sulla dimensione n della sequenza tra p e r.

MergeSort: analisi

L’analisi del tempo di esecuzione di un algoritmo ricorsivo si riduce spesso alla soluzione di una equazione di ricorrenza, che definisce implicitamente (ricorsivamente) la funzione di tempo
La forma di una equazione di ricorrenza è immediatamente riconducibile alla struttura dell’algoritmo cui è associata
Ad esempio, detto n il numero di elementi tra p e r, MergeSort viene chiamato ricorsivamente su due sottosequenza di dimensione \frac{n}{2}
Se T(n) denota il tempo quando l’input ha dimensione n, T(\frac{n}{2}) denota il tempo quando l’input ha dimensione \frac{n}{2}

MergeSort(array A, int p,r)

1 if p < r then \xrightarrow{\hspace{2cm}}\Theta(1)

2 q = \left\lfloor\frac{(p+r)}{2}\right\rfloor\ \ \xrightarrow{\hspace{2cm}}\Theta(1)

3 MergeSort(A,p,q)\ \xrightarrow{\hspace{2cm}}T(\frac{n}{2})

4 MergeSort(A,q+1,r) \ \xrightarrow{\hspace{1.8cm}} T(\frac{n}{2})
5 Merge(A,p,q,r) \ \xrightarrow{\hspace{2.2cm}}\Theta(n)

MergeSort: equazione di ricorrenza

Sommando i termini associati alle linee dell’algoritmo, otterremo dunque l’equazione di ricorrenza che definisce il tempo di esecuzione di MergeSort:

\large T(n) = \left\{\begin{array}{ll} \Theta(1) & \mbox{se } n\leq 1\\[5pt] 2\cdot T\left(\dfrac{n}{2}\right) + \Theta(n) & \mbox{se }n\geq 2 \end{array}

  • dove il termine \Theta(1) rappresenta il numero (costante) di operazioni eseguite dall’algoritmo nel caso base (cioè se n\leq 1) dovute alla sola linea 1;
  • il termine \Theta(n) rappresenta il numero (lineare) di operazioni eseguite dall’algoritmo di Merge per una sequenza di dimensione n, più il tempo costante per le operazioni delle linee 1 e 2;
  • mentre i due termini T\left(\dfrac{n}{2}\right) rappresentano la somma dei tempi necessari a completare ciascuna delle due chiamate ricorsive effettuate dall’algorimo.

MergeSort: equazione di ricorrenza (segue)

La soluzione di un’equazione di ricorrenza può essere calcolata in modo molto semplice con l’ausilio di una rappresentazione grafica.
L’idea di base è quella di rappresentare le chiamate ricorsive come nodi dell’albero delle chiamate ricorsive, tra loro collegati in modo che una chiamata che genera una o più chiamate ricorsive risulti essere, nell’albero, padre dei nodi associati a tali chiamate.
È poi necessario associare ad ogni nodo il numero di operazioni elementari eseguite localmente alla chiamata ricorosiva associata (cioè le operazioni che non coinvolgono altre chiamate ricorsive)
Infine, è necessario sommare tra di loro i contributi associati a tutti i nodi dell’albero, ottenendo in tal modo una sommatoria di termini, come nel caso di algoritmi iterativi, la cui forma chiusa rappresenta la funzione del tempo di esecuzione.
Di seguito vediamo i passi relativi alla seguente equazione di ricorrenza:

\large T(n) = \left\{\begin{array}{ll} \Theta(1) & \mbox{se } n\leq 1\\[5pt] 2\cdot T\left(\dfrac{n}{2}\right) + n & \mbox{se }n\geq 2 \end{array}

Soluzione di equazioni di ricorrenza

La soluzione di un’equazione di ricorrenza può essere calcolata in modo molto semplice con l’ausilio di una rappresentazione grafica.
L’idea di base è quella di rappresentare le chiamate ricorsive come nodi di un albero, tra loro collegati in modo che una chiamata che genera una o più chiamate ricorsive risulti essere, nell’albero, padre dei nodi associati a tali chiamate.
È poi necessario associare ad ogni nodo il numero di operazioni elementari eseguite localmente alla chiamata ricorosiva associata (cioè le operazioni che non coinvolgono chiamate ricorsive)
Infine è necessario sommare tra di loro i contributi associati a tutti i nodi dell’albero, ottenendo in tal modo una sommatoria di termini, come nel caso di algoritmi iterativi, la cui forma chiusa rappresenta la funzione del tempo di esecuzione.

La figura a destra rappresenta il nodo radice associato alla prima chiamata con input n, con il contributo locale associato e i due nodi relativi alle chiamate ricorsive su input \frac{n}{2}.

Albero di ricorrenza parziale, primo livello, associato all’equazione di ricorrenza.

Albero di ricorrenza parziale, primo livello, associato all'equazione di ricorrenza.


Soluzione di equazioni di ricorrenza (segue)

La figura a destra rappresenta il nodo radice associato alla prima chiamata con input n, con il contributo locale associato, i due nodi realtivi alle chiamate ricorsive su input \frac{n}{2} con i contributi associati.
Ciascuno dei due figli della radice avrà poi due nodi figli, associati alle due chiamate ricorsive, ciascuna su input di dimensione la metà di quello ricevuto in ingresso dal padre, cioè \frac{n}{4}.
Si noti che l’espressione associata ai nodi rappresenta il numero di operazioni elementari eseguite localmente dalla chiamata. Qundi, poiché l’equazione di ricorrenza associa n operazioni quando l’input ha dimensione n, essa associerè \frac{n}{2} operazioni quando l’input ha dimensione \frac{n}{2}.

Albero di ricorrenza parziale, primi due livelli, associato all’equazione di ricorrenza.

Albero di ricorrenza parziale, primi due livelli, associato all'equazione di ricorrenza.


Soluzione di equazioni di ricorrenza (segue)

Una volta individuato l’albero di ricorrenza e i contributi dei nodi, il tempo di esecuzione può essere calcolato sommando tutti questi conrtibuti.
- nel caso in esame, l’albero è un albero binario pieno, cioè un albero in cui tutte le foglie sono alla stessa profondità e i nodi interni hanno grado 2.
Molto spesso risulta più semplice sommarli livello per livello e individuare, ove possibile, il termine generale del livello:
- nel caso in esame, i contributi dei nodi di ciascun livello sommano sempre a n.
Calcoliamo l’altezza dell’albero, cioè il numero di livelli (o chiamate ricorsive annidate) necessario affinché l’input divenga uguale a quello del caso base dell’equazione:

  • nel caso in esame, la dimensione dell’input per un nodo del generico livello i è \frac{n}{2^i}
  • la soluzione dell’equazione \frac{n}{2^i} = 1 (dove 1 è la dimensione dell’input per il caso base dell’equazione nell’esempio) ci dà l’altezza dell’albero, in questo caso i = log_2\,n

Infine, sommiamo il contributo dei livelli su tutti i livelli individuati, in altre parole: T(n) = \sum_{i=0}^{log_2\,n}n.
La slide successiva illustra il procedimento qui descritto.

Soluzione di equazioni di ricorrenza (segue)

Albero per l’equazione di ricorrenza dell’esempio, a sinistra è riportata l’altezza dell’albero, a destra i contributi dei livelli e il contributo generale n del livello i, in basso la sommatoria complessiva e la sua soluzione.

Albero per l'equazione di ricorrenza dell'esempio, a sinistra è riportata l'altezza dell'albero, a destra i contributi dei livelli e il contributo generale n del livello i, in basso la sommatoria complessiva e la sua soluzione.


Esempio 1

A titolo di esempio, consideriamo la seguente equazione di ricorrenza:

\begin{array}{l}T(n) = \left\{\begin{array}{ll}\Theta(1) & \mbox{se } n \leq 1\\4\,T\left(\frac{n}{2}\right) + n & \mbox{se } n \geq 2\end{array}\right.\end{array}</p>
<p>

Il termine 4\cdot T\left(\dfrac{n}{2}\right) corrisponde a quattro chiamate ricorsive, ciascuna eseguita su metà dell’input della chiamata padre.
Anche in questo caso, l’albero di ricorrenza risulterà pieno, ma di grado 4
Ogni nodo avrà contributo pari alla dimensione dell’input
Il livello i-esimo avrà contributo pari a n\cdot 2^i
L’altezza dell’albero è, ancora una volta, pari a log_2 n
La slide successiva riporta la soluzione dell’equazione di ricorrenza.

Esempio 1 (segue)

Albero per l’equazione di ricorrenza dell’esempio, a sinistra è riportata l’altezza dell’albero, a destra i contributi dei livelli e il contributo generale n del livello i, in basso la sommatoria complessiva e la sua soluzione.

Albero per l'equazione di ricorrenza dell'esempio, a sinistra è riportata l'altezza dell'albero, a destra i contributi dei livelli e il contributo generale n del livello i, in basso la sommatoria complessiva e la sua soluzione.


Esempio 2

A titolo di esempio, consideriamo la seguente equazione di ricorrenza:

\large T(n) = \left\{\begin{array}{ll} \Theta(1) & \mbox{se } n\leq 2\\[5pt] 4\cdot T\left(\dfrac{2}{3}\,n\right)  + n^2 & \mbox{se }n\geq 3 \end{array}

Il termine 4\cdot T\left(\dfrac{2n}{3}\right) corrisponde a quattro chiamate ricorsive, ciascuna eseguita su due terzi dell’input della chiamata padre.
Anche in questo caso, l’albero di ricorrenza risulterà pieno e di grado 4
Ogni nodo avrà contributo pari al quadrato della dimensione dell’input
Il livello i-esimo avrà contributo pari a n^2 \cdot  \left(\frac{16}{9}\right)^i
L’altezza dell’albero si ottiene come soluzione di \left(\frac{2}{3}\right)^i n=2 ed è pari a log_{\frac{3}{2}}\left(\frac{n}{2}\right)  = log_{\frac{3}{2}} n - log_{\frac{3}{2}} 2
La slide successiva riporta la soluzione dell’equazione di ricorrenza.

Esempio 2

Albero per l’equazione di ricorrenza dell’esempio, a sinistra è riportata l’altezza dell’albero, a destra i contributi dei livelli e il contributo generale n del livello i, in basso la sommatoria complessiva e la sua soluzione.

Albero per l'equazione di ricorrenza dell'esempio, a sinistra è riportata l'altezza dell'albero, a destra i contributi dei livelli e il contributo generale n del livello i, in basso la sommatoria complessiva e la sua soluzione.


Esempio 2

L’altezza dell’albero si ottiene come soluzione di \left(\frac{2}{3}\right)^i n=2 ed è pari a log_{\frac{3}{2}}\left(\frac{n}{2}\right)  = log_{\frac{3}{2}} n - log_{\frac{3}{2}} 2
Di seguito sono riportati i calcoli della relativa sommatoria:
\begin{array}{lcl} T(n) &=& \sum_{i=0}^{log_{\frac{3}{2}}\left(\frac{n}{2}\right)\left(\frac{16}{9}\right)^in^2 =n^2\cdot \frac{\left(\frac{16}{9}\right)^{log_{\frac{3}{2}}\left(\frac{n}{2}\right)+1} - 1}{\frac{16}{9}-1} =n^2\cdot \frac{\left(\frac{16}{9}\right) \left(\frac{16}{9}\right)^{log_{\frac{3}{2}}\left(\frac{n}{2}\right)} - 1}{\frac{7}{9}}=\\ &=& n^2\cdot \left(\frac{16}{7}\right) \cdot \left(\frac{n}{2}\right)^{log_{\frac{3}{2}}\left(\frac{16}{9}\right)} -\frac{16}{9}\cdot n^2 = \frac{16}{7}\cdot n^2\cdot \frac{n^{log_{\frac{3}{2}}\left(\frac{16}{9}\right)}}{2^{log_{\frac{3}{2}}\left(\frac{16}{9}\right)}} -\frac{16}{9}\cdot n^2 = \\&=& \frac{16}{7}\cdot \frac{n^{2+2(log_{\frac{3}{2}}\,2-1)}}{2^{log_{\frac{3}{2}}\left(\frac{16}{9}\right)}}-\frac{16}{9}\cdot n^2 = \frac{16}{7}\cdot \frac{n^{2log_{\frac{3}{2}} 2 }}{2^{log_{\frac{3}{2}}\left(\frac{16}{9}\right)}}-\frac{16}{9}\cdot n^2 = \Theta(n^{log_{\frac{3}{2}}\,4})\end{array}

Esempio 3

A titolo di esempio, consideriamo la seguente equazione di ricorrenza:

\large T(n) = \left\{\begin{array}{ll} \Theta(1) & \mbox{se } n\leq 1\\[5pt] T\left(\dfrac{n}{3}\right) + T\left(\dfrac{n}{2}\right) + n\right & \mbox{se }n\geq 2 \end{array}

Il termine 4\cdot T\left(\dfrac{2n}{3}\right) corrisponde a quattro chiamate ricorsive, ciascuna eseguita su due terzi dell’input della chiamata padre.
In questo caso, l’albero di ricorrenza risulterà un albero binario non pieno.
Ogni nodo avrà contributo pari alla dimensione dell’input
Il livello i-esimo avrà contributo pari a n\cdot \left(\frac{5}{6}\right)^i
Poichè l’albero non è pieno, non è facile calcolare con precisione la somma dei contributi dei nodi
Per effettuare l’analisi, procederemo per apprissimazioni, calcolando un’approssimazione per difetto e una per eccesso della somma dei contributi.

Albero di ricorrenza non pieno (area in verde).

Albero di ricorrenza non pieno (area in verde).


Esempio 3 (segue)

Per l’approssimazione per difetto calcoleremo la somma dei contributi dei nodi del più grande albero pieno contenuto nell’albero di ricorrenza dell’equazione:

  • questo è l’albero che si ottiene considerando solo i nodi che hanno profondità minore o uguale alla lunghezza del percorso che dalla radice raggiunge la foglia a profondità minore
  • la lunghezza di tale percorso, corrispondente all’altezza dell’albero pieno che approssima per difetto, si ottine come soluzione dell’equazione

n\cdot \left(\frac{1}{3}\right)^i = 1

la cui soluzione è i = log_{3}n
Calcoliamo quindi la funzione:

T_{min}(n) = \sum_{k=0}^{log_{3}n}\left(\frac{5}{6}\right)^k\cdot n

che rappresenta un limite inferiore asintotico per T(n).

Albero di ricorrenza non pieno (area in verde) e sue approssimazioni piene per difetto (in giallo).

Albero di ricorrenza non pieno (area in verde) e sue approssimazioni piene per difetto (in giallo).


Esempio 3 (segue)

Per l’approssimazione per eccesso calcoleremo la somma dei contributi dei nodi del più piccolo albero pieno che contiene l’albero di ricorrenza dell’equazione:

  • questo è l’albero che si ottiene considerando pieni tutti i livelli dell’albero sino a quello corrispondente alla foglia a profondità maggiore (l’altezza dell’albero).
  • la lunghezza di tale percorso, corrispondente anche all’altezza dell’albero pieno che approssima per eccesso, si ottine come soluzione dell’equazione

n\cdot \left(\frac{1}{2}\right)^i = 1

la cui soluzione è i = log_{2}n
Calcoliamo quindi la funzione:

T_{max}(n) = \sum_{k=0}^{log_{2}n}\left(\frac{5}{6}\right)^k\cdot n

che rappresenta un limite superiore asintotico per T(n).

Albero di ricorrenza non pieno a sua approssimazione per eccesso (in blue).

Albero di ricorrenza non pieno a sua approssimazione per eccesso (in blue).


Esempio 3 (segue)

Albero per l’equazione di ricorrenza non pieno dell’esempio. Le due approssimazioni, per difetto e per eccesso, in questo caso coincidono asintoticamente, perciò possiamo concludere T(n)=θ(n)

Albero per l'equazione di ricorrenza non pieno dell'esempio. Le due approssimazioni, per difetto e per eccesso, in questo caso coincidono asintoticamente, perciò possiamo concludere T(n)=θ(n)


Conclusione

È possibile analizzare il tempo di esecuzione di un algoritmo ricorsivo, risolvendo un’equazione di ricorrenza.
L’equazione di ricorrenza definisce la regola di generazione dell’albero delle chiamate ricorsive dell’algoritmo.
Per risolvere l’equazione di ricorrenza, è sufficiente sommare i contributi locali, in termini di operazioni elementari, di ciascuna chiamata ricorsiva.
Un modo semplice è quello di calcolare il termine generale corrispondente alla somma dei contributi dei nodi che risiedono nello stesso livello i-esimo.
Se l’albero generato dalla ricorrenza è pieno, allora, nota l’altezza dell’albero, è sufficiente calcolare la somma, su tutti i livelli, dei termine generale.
In caso l’albero non sia pieno, si possono individuare un limite inferiore asintotico e un limite superiore asintotico, tramite il calcolo di un’approssimazione per difetto e una per eccesso, rispettivamente.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion