Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Algoritmi, 9 CFU => Topic started by: Alexios on 02-09-2010, 18:42:45



Title: Dubbio esame 2 settembre 2010
Post by: Alexios on 02-09-2010, 18:42:45
Salve ragazzi, sapreste dirmi come avete risolto le seguenti ricorrenze:

1) T(n)=5T(n/4) + n logn e posto k=log4 5

a. T(n)=O(n log n)
b. T(n)=O(n^k)
c. T(n)=O(n^k log n)
d. T(n)=O((n log n)^k)

2) T(n)=2T(n-1)+2(n-1)

a. T(n)=O(n^2 log n)
b. T(n)=O(n log n)
c. T(n)=O(n)
d. T(n)=O(2^n n)

3) Siano T(n)=3T(n/a)+n^a un'equazione di ricorrenza con parametro a>2. Allora,

a. T(n)=O(n^a) qualunque sia il parametro di a
b. T(n)=Ω(n^a) qualunque sia il parametro di a
c. E' possibile trovare un valore di a tale che T(n)=O(n^a log n)
d. Nessuna delle precedenti affermazioni è vera

4) T(n)=T(n/3)+T(n/6)+T(n/9)+n

a. T(n)=O(n)
b. T(n)=O(n log log n)
c. T(n)=O(n log n)
d. T(n)=O(n^2)


Grazie  :-OK


Title: Re:Dubbio esame 2 settembre 2010
Post by: Aigor on 02-09-2010, 19:00:32
1) T(n)=5T(n/4) + n logn e posto k=log4 5

Con il Master si ha il caso 1. O(n^{k})

2) T(n)=2T(n-1)+2(n-1)

Con l'albero di ricorrenza T(n)=O(2^{n}n)

3) Siano T(n)=3T(n/a)+n^a un'equazione di ricorrenza con parametro a>2.
Anche questa con il teorema Master, prova a sostituire a e otterrai che rientra nel terzo caso, quindi la (a).



Title: Re:Dubbio esame 2 settembre 2010
Post by: Gam on 02-09-2010, 19:02:22
Alexios potresti postare le soluzioni delle ricorrenze? le risposte multiple intendo


Title: Re:Dubbio esame 2 settembre 2010
Post by: Alexios on 02-09-2010, 19:17:17
Alexios potresti postare le soluzioni delle ricorrenze? le risposte multiple intendo

Ho modificato sopra


Grazie Aigor per le risposte, ma la 4 ricorrenza non me la sapresti dire?


Title: Re:Dubbio esame 2 settembre 2010
Post by: Giuseppo on 03-09-2010, 09:45:27
scusa aigor, per la prima, come fai a dire che è il primo caso del master? io non riesco a confrontare f(n) con n^k


Title: Re:Dubbio esame 2 settembre 2010
Post by: AngelEvil on 04-09-2010, 11:00:10
aigor non riesco a capire come mai la terza ricorrenza dici che sia a)......o meglio rientra nel terzo caso del T.master ma non dovrebbe essere \Theta(n^a)


Title: Re:Dubbio esame 2 settembre 2010
Post by: Aigor on 04-09-2010, 14:25:40
Alexios potresti postare le soluzioni delle ricorrenze? le risposte multiple intendo

Ho modificato sopra


Grazie Aigor per le risposte, ma la 4 ricorrenza non me la sapresti dire?

La 4 si risolve con l'albero di ricorsione. La sommatoria che ne viene fuori è una serie geometrica di ragione < 1.
Alla fine si ha che la sua complessità è O(n).

scusa aigor, per la prima, come fai a dire che è il primo caso del master? io non riesco a confrontare f(n) con n^k

In che senso non riesci a confrontare f(n) con n^{k} ?
Si nota subito che O(n^{log_{4}5 + \epsilon})= f(n).
Se non credi che n^{log_{4}5 } cresca più velocemente di  n \log n ti consiglio di provare a confrontare le due funzioni con il limite asintotico...

aigor non riesco a capire come mai la terza ricorrenza dici che sia a)......o meglio rientra nel terzo caso del T.master ma non dovrebbe essere \Theta(n^a)

Scusami, se è il terzo caso del teorema dell'esperto, ossia \Omega(n^{log_{b}a + \epsilon})= f(n) e vale la seconda ipotesi, ovvero che  af(n/b)<=c f(n) , allora sarà sicuramente vero che T(n)=\Theta(f(n)), e quindi sarà uguale a  T(n)=\Theta(n^{a}) e conoscendo le notazioni asintotiche credo che non avrai niente in contrario a dire che è anche vero che T(n)=O(n^{a})


EDIT : Gam mi ha giustamente fatto notare che ho fatto un errore di segno nel trascrivere la soluzione della prima equazione di ricorrenza . Ovviamente è  O(n^{log_{4}5 - \epsilon})= f(n)


Title: Re:Dubbio esame 2 settembre 2010
Post by: AngelEvil on 04-09-2010, 14:31:56
ok perfetto....grazie gentilissimo!


Title: Re:Dubbio esame 2 settembre 2010
Post by: n2o1988 on 16-09-2010, 13:32:51
2) T(n)=2T(n-1)+2(n-1)

Con l'albero di ricorrenza T(n)=O(2^{n}n)


Ciao, non mi è ben chiaro come si arriva a questo risultato... La sommatoria finale dei costi ad ogni livello come l'hai risolta?


Title: Re:Dubbio esame 2 settembre 2010
Post by: Aigor on 16-09-2010, 13:39:19
E' una serie telescopica, il procedimento di come si risolve è troppo lungo da scrivere qui, lo trovi su un qualsiasi libro di analisi o su wikipedia.


Title: Re:Dubbio esame 2 settembre 2010
Post by: n2o1988 on 16-09-2010, 13:53:12
E' una serie telescopica, il procedimento di come si risolve è troppo lungo da scrivere qui, lo trovi su un qualsiasi libro di analisi o su wikipedia.

Capisco... Vedrò di cercare qualcosa a riguardo. Un ultima domanda: la serie di cui parli è questa per caso: \sum_{i=1}^{n-1} 2^i(n-i) ? Perchè a me è risultata così...