Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Algoritmi, 9 CFU => Topic started by: Daréios89 on 03-08-2011, 17:59:22



Title: Ricorrenza con albero
Post by: Daréios89 on 03-08-2011, 17:59:22
T(n)=T(n/2)+T(n/4)+T(n/8)+n

Come costruireste l' albero? Non capisco come determinare l' altezza visto che ho tre chiamate....


Title: Re:Ricorrenza con albero
Post by: corel_86 on 03-08-2011, 21:39:28
si costruisce il seguente albero di ricorsione

(http://img4.imageshack.us/img4/4631/alberob.png)

il costo totale totale di tutti i nodi alla profondità i e'

 (\frac{7}{8})^i n

per calcolare l'altezza dell'albero prendo il cammino più lungo che è

n \rightarrow \frac{n}{2}\rightarrow \frac{n}{4} \rightarrow . . . .\rightarrow 1

poiché
(\frac{1}{2})^k n\Rightarrowk=\log_2(n)

quindi in definitiva abbiamo

\sum_{i=0}^{\log_2(n)} (\frac{7}{8})^i n

calcolandoti questa serie troverai l'andamento asintotico dell'equazione di ricorrenza che se non sbaglio dovrebbe essere

\theta(n)

spero di esserti stato di aiuto


Title: Re:Ricorrenza con albero
Post by: Daréios89 on 03-08-2011, 21:42:05
Leggerò  domani che sono più fresco  :yoh
Intanto potresti anche darmi una dritta per la ricorrenza che ho riportato in questa discussione? Grazie mille.

http://forum.sdai.unict.it/index.php?topic=13430.0

Scusa, non ti seguo su una cosa, non capisco come fai a sapere e individuare  il cammino più lungo?


Title: Re:Ricorrenza con albero
Post by: corel_86 on 03-08-2011, 21:58:47
Scusa, non ti seguo su una cosa, non capisco come fai a sapere e individuare  il cammino più lungo?

Devi prendere il cammino che parte da n e arriva a 1 che ci fa più lentamente asintoticamente....

se per esempio abbiamo i seguenti cammini

n \rightarrow\frac{n}{3}\rightarrow\frac{n}{9}\rightarrow...\rightarrow1

n \rightarrow\frac{n}{2}\rightarrow\frac{n}{4}\rightarrow...\rightarrow1

quello più "lento" è questo

n \rightarrow\frac{n}{2}\rightarrow\frac{n}{4}\rightarrow...\rightarrow1


Title: Re:Ricorrenza con albero
Post by: Daréios89 on 03-08-2011, 23:08:14
Quindi nella mia ricorrenza dove compaiono \frac{n}{2}, \frac{n}{4}, \frac{n}{8} Come farei scusa? Tu hai confrontato due casi di crescita asintotica e ci siamo ma se devo confrontare solo quei valori come faccio?, il più lento non è \frac{n}{8} ?
Cioè quì a differenza del tuo esempio dove confronto due cammini ne ho uno solo, ma come faccio a stabilire la frazione mi indica l' altezza?


Title: Re:Ricorrenza con albero
Post by: corel_86 on 03-08-2011, 23:19:30
no perchè quello che va più lentamente è il cammino n \rightarrow \frac{n}{2} \rightarrow \frac{n}{4}

quei percorsi che ho fatto io sono solo un esempio

qui sotto c'è un altro esempio che non c'entra nulla con l'esercizio
n \rightarrow\frac{n}{4}\rightarrow\frac{n}{16}\rightarrow...\rightarrow1

n \rightarrow\frac{n}{8}\rightarrow\frac{n}{64}\rightarrow...\rightarrow1

quello più "lento" è questo

n \rightarrow\frac{n}{4}\rightarrow\frac{n}{16}\rightarrow...\rightarrow1


Title: Re:Ricorrenza con albero
Post by: Daréios89 on 04-08-2011, 18:18:17
Ah, e per esempio nell' ultimo tuo esempio, se dovessi stabilire la base dell' altezza di un albero sarebbe \log_4(n) ?
Inoltre nella serie non trascuri il costo del lavoro esterno? Cioè anche sulla base di quello che c' è tra gli appunti la serie dovrebbe anche contenere il numero di nodi per cui il costo diventa poi \theta(1), quindi del tipo:

\sum_{i=0}^{\log(n)-1} {\frac{7}{8}}^in+n^{\log_2(\frac{7}{8})}\theta(1)

Se non la vedi bene:

(http://latex.codecogs.com/gif.latex?\sum_{i=0}^{\log(n)-1}{\frac{7}{8}}^in+n^{\log_2(\frac{7}{8})}\theta(1))

Sempre se l' altezza è log_2(n) e si può fare quel passaggio, è l' unica cosa che mi manca...


Title: Re:Ricorrenza con albero
Post by: corel_86 on 04-08-2011, 20:33:49
bisogna risolvere questa serie:
rispolverando i manuali di analisi ti accorgi che la serie è la serie geometrica:
\sum_{i=0}^{n} (x)^i = \frac{1-(x)^{n+1}}{1-x}

quindi tornando all'esercizio:

n\sum_{i=0}^{\log_2(n)} (\frac{7}{8})^i= \rightarrown viene portato fuori perché è una costante

=n\frac{1-(\frac{7}{8})^{\log_2(n)+1}}{1-\frac{7}{8}}

applicando le regole delle potenze e dei logaritmi dovrebbe risultarti \theta(n)