Pages: [1]   Go Down
Print
Author Topic: Problema Ricorrenza con Metodo Principale  (Read 1596 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
callo
Forumista
***
Offline Offline

Gender: Male
Posts: 564


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


« on: 22-08-2011, 00:16:11 »

Ragazzi ho da poco cominciato a svolgere un po' di esercizi sulle ricorrenze ma purtroppo sono fermo ad un esercizio nel quale non riesco proprio a comprendere la risposta!!L'esercizio è il seguente:
Data l'equazione di ricorrenza T(n)=5T(n/5)+nlogn la sua soluzione è:
....
Questo è il ragionamento che ho fatto io:
a=5 che è >1
b=5 che è >1
T(n) è definito su interi non negativi
la ricorrenza è del tipo T(n)=aT(n/b)+f(n)
Visto che si verificano queste ipotesi allora posso applicare il teorema master applicando il secondo caso dove
f(n)= Θ (n^log_b (a) ) => T(n)=Θ(n^(log_b (a)) *log n) che nel mio caso diventerebbe Θ(nlogn) visto che ho log in base 5 e argomento 5!!Il problema è che la soluzione segnata è O(n^2 logn)    cooosa??Ma come arriva a n^2 Huh?
Logged

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

Posts: 810



WWW
« Reply #1 on: 22-08-2011, 10:00:35 »

Premetto che io non l'ho svolta e faccio riferimento solo a cio' che hai scritto te (che sia giusto o sbagliato)...
Se T(n) = \Theta (n\ \log n)
allora T(n) = O (n^2\ \log n)
per la definizione di \Theta e O 
Logged
callo
Forumista
***
Offline Offline

Gender: Male
Posts: 564


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


« Reply #2 on: 22-08-2011, 10:22:19 »

Premetto che io non l'ho svolta e faccio riferimento solo a cio' che hai scritto te (che sia giusto o sbagliato)...
Se T(n) = \Theta (n\ \log n)
allora T(n) = O (n^2\ \log n)
per la definizione di \Theta e O 

Aspetta....tra le 4 possibili soluzioni c'è sia O(nlogn) sia O(n^2logn)....Mi stai dicendo che se non c'è scritto di prendere il bound più stretto allora devo prendere la soluzione maggiore??Cioè se ci fosse stato O(n^20) avrei dovuto scegliere quella come soluzione??? boh
Logged

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

Gender: Male
Posts: 564


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


« Reply #3 on: 22-08-2011, 11:27:49 »

Forse ho capito.....ditemi se sto commettendo un errore:
Visto che f(n)=nlogn è asintoticamente più grande di n^1 non rientra in nessuno dei 3 casi del teorema master.Inoltre il rapporto tra f(n)/n^log_b (a) =log(n) che è + piccolo di n^ε per qualunque costante ε positiva. Quindi la ricorrenza ricade tra il caso 2 e il caso 3 del teorema.(C'è un esempio che è identico sul libro!!)Ma a questo punto come risolvere???
Logged

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

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #4 on: 22-08-2011, 14:08:43 »

Ci stavo provando anche io, forse si risolve con l' albero di ricorsione. Anche se dal testo ci rimanda ad un esercizio che assomiglia al seconda caso generalizzato del Teorema Master.
Logged

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

Gender: Male
Posts: 564


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


« Reply #5 on: 22-08-2011, 14:48:33 »

Booooo......Ma quando riceve il prof?Nel sito non ho trovato informazioni a riguardo!!Dovrei portargli qualche esercizio che non ho ben chiaro!!
Logged

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

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #6 on: 22-08-2011, 15:23:37 »

Non so dirti, ad agosto mi sembra difficile, anche se l' esame è il 2. Questa si risolve con l' albero, ma ho visto che è parecchio complicata....se non sbaglio è questa:

http://www.matematicamente.it/forum/equazione-di-ricorrenza-t65122.html
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: 22-08-2011, 15:24:21 »


Aspetta....tra le 4 possibili soluzioni c'è sia O(nlogn) sia O(n^2logn)....Mi stai dicendo che se non c'è scritto di prendere il bound più stretto allora devo prendere la soluzione maggiore??Cioè se ci fosse stato O(n^20) avrei dovuto scegliere quella come soluzione??? boh
Come facevo a sapere che avevi tante soluzioni se non lo specifichi? Fino a prova contraria non sono veggente ed il ragionamento fatto e' corretto boh
Inoltre avevo specificato
Premetto che io non l'ho svolta e faccio riferimento solo a cio' che hai scritto te (che sia giusto o sbagliato)...
e in cuor mio sapevo che c'era un errore infatti la ricorrenza ha la seguente soluzione per il 2 caso del teorema Master
T(n) = \Theta(n\ \log^2 n)
adesso sta a te vedere se tra le soluzioni se ce n'e' qualcuna che gli somiglia 
« Last Edit: 22-08-2011, 15:40:29 by shiny » Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #8 on: 22-08-2011, 15:51:46 »

Non so dirti, ad agosto mi sembra difficile, anche se l' esame è il 2. Questa si risolve con l' albero, ma ho visto che è parecchio complicata....se non sbaglio è questa:

http://www.matematicamente.it/forum/equazione-di-ricorrenza-t65122.html
Su matematicamente il tipo ha fatto un errore (orrore) colossale nella sostituzione  testate

T(n)\ =\ 5 T(\frac{n}{5})\ +\ n\log n

T(k)\ \geq\ 5 T(5^{k-1})\ +\ k5^k

S(k)\ \geq\ \frac{S(5^{k-1})}{5^{k-1}}\ +\ k

Q(k)\ \geq\ Q(k-1)\ +\ k

Q(k) \geq k^2 (Serie aritmetica)

T(k) = 5^k S(k) = 5^k Q(k) = k^2 5^k

5^k = n\ \Rightarrow\ T(n)\ \geq\ n (\log_5 n)^2
« Last Edit: 22-08-2011, 15:58:14 by shiny » Logged
callo
Forumista
***
Offline Offline

Gender: Male
Posts: 564


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


« Reply #9 on: 22-08-2011, 16:12:45 »

Perfect......Grazie mille anche se ancora non ho ben capito come sei arrivato al risultato finale......ora me la svolgo nuovamente, confronto con la tua soluzione e vediamo dove sbaglio!!Grazie mille comunque ok
Logged

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

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #10 on: 22-08-2011, 18:00:30 »

Ok ci sono, una curiosità, quando facciamo una cosa come:

\frac{S(m)}{a^m}=R(m)


Segue che S(m)=R(m)a^m

Ma allora se avessi un' espressione come S(m-1) questa diventerebbe R(m-1)a^{m-1} ?
« Last Edit: 22-08-2011, 22:48:35 by Daréios » 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: 23-08-2011, 12:24:54 »

Perfect......Grazie mille anche se ancora non ho ben capito come sei arrivato al risultato finale......ora me la svolgo nuovamente, confronto con la tua soluzione e vediamo dove sbaglio!!Grazie mille comunque ok

Guardati questo topic
bisogna trasformare l'equazione di ricorrenza in modo da applicare il Telescoping
ti consiglio inoltre di vederti le slide del prof.
Ok ci sono, una curiosità, quando facciamo una cosa come:

\frac{S(m)}{a^m}=R(m)


Segue che S(m)=R(m)a^m

Ma allora se avessi un' espressione come S(m-1) questa diventerebbe R(m-1)a^{m-1} ?

L'abbiamo già dimostrato non te lo ricordi che ci siamo stati fino a tardi
Logged

Se trovo qualcosa che non va lo faccio presente subito

Saluti ciaociao ciao

A.C.
corel_86
Forumista
***
Offline Offline

Gender: Male
Posts: 570



« Reply #12 on: 23-08-2011, 12:27:41 »

Se non ti è chiaro qualche passaggio fammelo presente che la risolviamo insieme
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 #13 on: 23-08-2011, 14:13:31 »

Si si infatti riguardando quel post ho capito, non so perchè mi era venuto questo dubbio...potresti dare un' occhiata alla domanda postata da Mimmo? Mi incuriosisce ma non sono riuscito a capirla.
Logged

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

Gender: Male
Posts: 433


We don't need no thought control...


« Reply #14 on: 23-08-2011, 15:25:13 »

Si si infatti riguardando quel post ho capito, non so perchè mi era venuto questo dubbio...potresti dare un' occhiata alla domanda postata da Mimmo? Mi incuriosisce ma non sono riuscito a capirla.
Logged

A strange game. The only winning move is not to play. How about a nice game of chess? [Joshua]
Pages: [1]   Go Up
Print
Jump to: