Pages: [1] 2   Go Down
Print
Author Topic: Aiuto equazione di ricorrenza  (Read 2323 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Mimmo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 433


We don't need no thought control...


« on: 22-08-2011, 18:05:00 »

Salve a tutti,
avrei un problema con un esercizio che non sto proprio riuscendo a fare (nel senso che non capisco da dove iniziare ad attaccarlo  testate )
Ecco il testo:

Data l'equazione di ricorrenza T(n)=bT(n/2)+T(n/b)+n, con parametro intero b > 1, sia S(b) la soluzione dell'equazione, fissato b. Quali delle seguenti affermazioni è vera?

a. S(b)=O(S(b+1)) per ogni b
b. S(b)=\Omega(S(b+1)) per ogni b
c. S(b)=\Theta(S(b+1)) per ogni b
d. nessuna delle precedenti

Grazie mille 
Logged

A strange game. The only winning move is not to play. How about a nice game of chess? [Joshua]
corel_86
Forumista
***
Offline Offline

Gender: Male
Posts: 570



« Reply #1 on: 23-08-2011, 18:04:20 »

secondo me bisognerebbe fare l'albero di ricorrenza e poi alla fine trovata la soluzione S(b) possiamo trarre le conclusioni......

Per prima cosa bisogna trovare S(b)
Logged

Se trovo qualcosa che non va lo faccio presente subito

Saluti ciaociao ciao

A.C.
callo
Forumista
***
Offline Offline

Gender: Male
Posts: 564


"Quanto manca alla vetta?";"Tu sali e non pensare"


« Reply #2 on: 23-08-2011, 18:12:32 »

Ecco questo è il secondo esercizio che avrei dovuto portare al prof........tu per esempio come faresti quest'albero??
Logged

"A cavallina....a cavallina.....a chi era bedda quannu  curreva" [Cit.  Dal Tenerissimo via plebiscito]
corel_86
Forumista
***
Offline Offline

Gender: Male
Posts: 570



« Reply #3 on: 23-08-2011, 20:01:15 »

beh inizierei cosi però non sono sicuro.....dato che quella ricorrenza è valida per b>1, si impone b=2 e si calcola la soluzione; tale soluzione sarà S(b).
Poi impongo b=3 e tale soluzione è S(b+1), infine confronto le due soluzioni.


Dato che tale soluzione deve essere valida per ogni b basta provarlo per b=2 e b=3 e il gioco è fatto.....almeno credo
Logged

Se trovo qualcosa che non va lo faccio presente subito

Saluti ciaociao ciao

A.C.
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #4 on: 23-08-2011, 22:24:10 »

Così dando un' occhiata veloce sulla base di quanto detto da corel, mi viene da pensare che la risposta corretta sia la a).
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
corel_86
Forumista
***
Offline Offline

Gender: Male
Posts: 570



« Reply #5 on: 25-08-2011, 00:10:29 »

beh come fai a dirlo devi calcolare le ricorrenze con b=2 e poi b=3
Logged

Se trovo qualcosa che non va lo faccio presente subito

Saluti ciaociao ciao

A.C.
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #6 on: 25-08-2011, 20:30:19 »

Si lo avevo fatto velocemente.


 T(n)=bT(n/2)+T(n/b)+n



Per b=2 io ottengo:

T(n)=3T(n/2)+n

T(n)=3T(n/2)+n

Dovrebbe essere il primo caso del teorema master e trovo come soluzione T(n)=\theta(n^{\log(3)})

Per b=3 ottengo:

T(n)=4T(n/2)+n

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

Considero la prima ricorrenza perché rappresenta il percorso più lungo fino alle foglie, sempre primo caso e come soluzione ottengo T(n)=\theta(n^2)

In questo caso dovrebbe essere la risposta a), se non ho fatto errori. 

Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #7 on: 26-08-2011, 02:29:59 »

Io le ho svolte con l'albero e per

  • n=2 => T(n)=\Theta(n^{\log 3})
  • n=3 =>T(n)=\Theta(n^{\log\frac{22}{6}})

da cui la risposta corretta dovrebbe essere la a)
Logged
Mimmo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 433


We don't need no thought control...


« Reply #8 on: 26-08-2011, 11:13:38 »

Grazie mille per l'aiuto, ora ho capito come andava svolto. Avrei una domanda:

Perché per b=3 non si ottiene
T(n)=3T(n/2)+T(n/3)+n ?
 
Logged

A strange game. The only winning move is not to play. How about a nice game of chess? [Joshua]
corel_86
Forumista
***
Offline Offline

Gender: Male
Posts: 570



« Reply #9 on: 26-08-2011, 14:45:48 »

Si lo avevo fatto velocemente.


 T(n)=bT(n/2)+T(n/b)+n



Per b=2 io ottengo:

T(n)=3T(n/2)+n

T(n)=3T(n/2)+n

Dovrebbe essere il primo caso del teorema master e trovo come soluzione T(n)=\theta(n^{\log(3)})

Per b=3 ottengo:

T(n)=4T(n/2)+n

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

Considero la prima ricorrenza perché rappresenta il percorso più lungo fino alle foglie, sempre primo caso e come soluzione ottengo T(n)=\theta(n^2)

In questo caso dovrebbe essere la risposta a), se non ho fatto errori. 


Allora l'equazione di ricorrenza:

T(n)=bT(n/2)+T(n/b)+n

Per b=2 diviene

T(n)=3T(n/2)+n

è giusto e la puoi risolvere con il Teorema Master

ma attenzione per b=3 viene

T(n)=3T(n/2)+T(n/3)+n

da risolvere solo con l'Albero di ricorsione
Logged

Se trovo qualcosa che non va lo faccio presente subito

Saluti ciaociao ciao

A.C.
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #10 on: 26-08-2011, 21:54:09 »

Quote
ma attenzione per b=3 viene
.
.
.


Si appunto, e quindi posso scriverla in due ricorrenze:

T(n)=4T(n/2)+n
T(n)=4T(n/3)+n

Utilizzo la prima per trovare una limitazione superiore. Primo caso del teorema master e quindi soluzione \theta(n^2) da cui si evince che la risposta è la a), a mio parere.
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
corel_86
Forumista
***
Offline Offline

Gender: Male
Posts: 570



« Reply #11 on: 26-08-2011, 23:10:07 »

Quote
ma attenzione per b=3 viene
.
.
.


Si appunto, e quindi posso scriverla in due ricorrenze:

T(n)=4T(n/2)+n
T(n)=4T(n/3)+n

Utilizzo la prima per trovare una limitazione superiore. Primo caso del teorema master e quindi soluzione \theta(n^2) da cui si evince che la risposta è la a), a mio parere.

Non ho capito come mai puoi dividere quella ricorrenza in quel modo......che passaggi hai svolto? non mi è chiaro per niente come hai fatto
Logged

Se trovo qualcosa che non va lo faccio presente subito

Saluti ciaociao ciao

A.C.
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #12 on: 26-08-2011, 23:19:12 »

So, perchè mi è stato detto, che quando si ha una ricorrenza come:

T(n)=T(n/2)+T(n/4)+T(n/8)+n

Si hanno in questo caso 3 ricorrenze diverse, allora si può cercare una limitazione superiore scrivendo le 3 ricorrenze come:

T(n)=3T(n/2)+n

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

T(n)=3T(n/8)+n

Metto il 3 come coefficiente perchè sono in totale 3 ricorrenze in quella di partenza.

Considero la prima perchè rappresenta il percorso più lungo, e quindi più lento dalla radice alle foglie

T(n)=3T(n/2)+n

La risolvi con il teorema master, se non sbaglio primo caso e quindi T(n)=O(n^{\log_2{3}})
Ovviamente da provare per induzione.
Forse ho sbagliato qualcosa visto che è mezzanotte, ricontrollerò, credo sia corretto.
Lo stesso principio lo applichi alla nostra ricorrenza, è quello che ho fatto nel mio secondo post se non erro.
P.S ne ho pubblicata un' altra di ricorrenza, potresti dare un' occhiata a quella?
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
corel_86
Forumista
***
Offline Offline

Gender: Male
Posts: 570



« Reply #13 on: 26-08-2011, 23:29:56 »

confronta la soluzione applicando il metodo dell'albero di ricorsione e se ti combacia allora sei apposto....ma se vuoi un consiglio ti conviene studiarti bene l'albero di ricorsione......... ok ok ok
Logged

Se trovo qualcosa che non va lo faccio presente subito

Saluti ciaociao ciao

A.C.
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #14 on: 26-08-2011, 23:31:17 »

confronta la soluzione applicando il metodo dell'albero di ricorsione e se ti combacia allora sei apposto....ma se vuoi un consiglio ti conviene studiarti bene l'albero di ricorsione......... ok ok ok

Hai fatto qualche prova e non ti risulta? L' albero di ricorsione funziona diversamente si, questa cosa si può fare a quanto mi è stato detto.
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Pages: [1] 2   Go Up
Print
Jump to: