Pages: [1]   Go Down
Print
Author Topic: Dubbio esame 2 settembre 2010  (Read 1878 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Alexios
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 128



« 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
« Last Edit: 02-09-2010, 19:09:12 by Alexios » Logged
Aigor
Forumista Esperto
****
Offline Offline

Gender: Male
Posts: 1.184


"Il destino non è una catena, ma un volo."[A.B.]


« Reply #1 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).

Logged

"Era d'altronde uno di quegli uomini che amano assistere alla propria vita, ritenendo impropria qualsiasi ambizione a viverla.
Si sarà notato che essi osservano il loro destino nel modo in cui, i più, sono soliti osservare una giornata di pioggia." - Seta,Baricco
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« Reply #2 on: 02-09-2010, 19:02:22 »

Alexios potresti postare le soluzioni delle ricorrenze? le risposte multiple intendo
Logged
Alexios
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 128



« Reply #3 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?
Logged
Giuseppo
Apprendista Forumista
**
Offline Offline

Posts: 198



« Reply #4 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
Logged

I have nothing to declare except my genius.
AngelEvil
Forumista
***
Offline Offline

Posts: 616



« Reply #5 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)
« Last Edit: 04-09-2010, 11:03:55 by AngelEvil » Logged

Aigor
Forumista Esperto
****
Offline Offline

Gender: Male
Posts: 1.184


"Il destino non è una catena, ma un volo."[A.B.]


« Reply #6 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)
« Last Edit: 16-09-2010, 16:32:14 by Aigor » Logged

"Era d'altronde uno di quegli uomini che amano assistere alla propria vita, ritenendo impropria qualsiasi ambizione a viverla.
Si sarà notato che essi osservano il loro destino nel modo in cui, i più, sono soliti osservare una giornata di pioggia." - Seta,Baricco
AngelEvil
Forumista
***
Offline Offline

Posts: 616



« Reply #7 on: 04-09-2010, 14:31:56 »

ok perfetto....grazie gentilissimo!
Logged

n2o1988
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 206



« Reply #8 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?
Logged
Aigor
Forumista Esperto
****
Offline Offline

Gender: Male
Posts: 1.184


"Il destino non è una catena, ma un volo."[A.B.]


« Reply #9 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.
Logged

"Era d'altronde uno di quegli uomini che amano assistere alla propria vita, ritenendo impropria qualsiasi ambizione a viverla.
Si sarà notato che essi osservano il loro destino nel modo in cui, i più, sono soliti osservare una giornata di pioggia." - Seta,Baricco
n2o1988
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 206



« Reply #10 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ì...
Logged
Pages: [1]   Go Up
Print
Jump to: