Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Algoritmi, 9 CFU => Topic started by: Daréios89 on 26-08-2011, 19:10:14



Title: Altra ricorrenza
Post by: Daréios89 on 26-08-2011, 19:10:14
T(n)=8T(n/2)+n^2\log(n)

Ho posto m=\log_2(n)

T(2^m)=2^3T(2^{m-1})+2^{2m}m

R(m)=\frac{T(2^m)}{2^{m}}

R(m)=4R(m-1)+m

Se fin qui vi quadra, adesso dovrei risolvere questa con l' albero, i costi sono:

m
4m-4
16m-16
.
.
.

Non riesco come al solito a formalizzare questo costo, perchè ovviamente si tratta di 4^i però non riesco a formalizzarlo correttamente perchè mi manca qualcosa sempre....
Ma con il teorema Master si può risolvere? Non mi risulta.


Title: Re:Altra ricorrenza
Post by: corel_86 on 26-08-2011, 23:27:42
T(n)=8T(n/2)+n^2\log(n)

Ho posto m=\log_2(n)

T(2^m)=2^3T(2^{m-1})+2^{2m}m

R(m)=\frac{T(2^m)}{2^{m}}

R(m)=4R(m-1)+m

Se fin qui vi quadra, adesso dovrei risolvere questa con l' albero, i costi sono:

m
4m-4
16m-16
.
.
.

Non riesco come al solito a formalizzare questo costo, perchè ovviamente si tratta di 4^i però non riesco a formalizzarlo correttamente perchè mi manca qualcosa sempre....
Ma con il teorema Master si può risolvere? Non mi risulta.

hai sbagliato il risultato applicato il telescoping è questo
T(n)=8^m \sum_{i=1}^m (\frac{i}{2^i})

e sostituendo m si ottiene

T(n)=n^3 \sum_{i=1}^{log(n)} (\frac{i}{2^i})

risolvendo la sommatoria ottieni il risultato finale

riguardati i passaggi che abbiamo scritto qui (http://forum.sdai.unict.it/index.php?topic=13430.0)


Title: Re:Altra ricorrenza
Post by: Daréios89 on 26-08-2011, 23:32:50
Che significa ho sbagliato il risultato? Sapresti indicarmi il punto dove ho sbagliato?

EDIT: Si credo di avere trovato, forse devo sostituire R(m)=\frac{T(m)}{2^{2m}} sarà da queste parti l' errore, vediamo se domani lo becco.


Title: Re:Altra ricorrenza
Post by: corel_86 on 26-08-2011, 23:40:51
ti posto tutti i passaggi

T(n)=8T(n/2)+n^2\log(n)

n=2^m \rightarrow m=\log_2(n)

T(2^m)=8T(2^{m-1})+4^{m}m
--------------------------------------------------------------------
S(m)=T(2^m)

T(m)=8T(m-1)+4^{m}m
--------------------------------------------------------------------
R(m)=S(m)/8^m

R(m)=R(m-1)+\frac{4^m}{8^m}m

R(m)=R(m-1)+(\frac{1}{2})^m m
--------------------------------------------------------------------
applico la regola del telescoping e ottengo

T(n)=8^m \sum_{i=1}^{m} (\frac{i}{2^i})

T(n)=n^3 \sum_{i=1}^{log(n)} (\frac{i}{2^i})

trovata la sommatoria ottengo il risultato finale


Title: Re:Altra ricorrenza
Post by: Daréios89 on 26-08-2011, 23:43:04
Grazie, provo domani a rifarla e in caso dò un' occhiata se ho problemi, per ora non guardo, grazie corel  .smile


Title: Re:Altra ricorrenza
Post by: callo on 27-08-2011, 01:27:43
corel_86 noto con profondo piacere che ci stai aiutando veramente parecchio......e di questo ti ringrazio veramente tanto!! .applausi
Volevo chiedere ma in questo caso questa ricorrenza non si poteva fare usando il teorema master??perchè:
a=8 , b=2, -> n^log_2 ( 8 )  = n^3 -> f(n)=Θ( n^3 )
Visto che si verificano queste ipotesi non possiamo applicare il secondo caso del teorema master?e quindi T(n)=O(n^3\log(n) )??


Title: Re:Altra ricorrenza
Post by: shiny on 27-08-2011, 03:03:08
Io l'ho svolta cosi'...

  • applicando il teo master, per il primo caso, la complessita' e'
    T(n)\ =\ \Theta(n^3)
  • dal risultato di corel
    T(n)\ =\ n^3 \sum_{i=1}^{log(n)} (\frac{i}{2^i})\ \leq\ n^3 \sum_{i=1}^{\infty} (\frac{i}{2^i})\ \leq\ n^3\ O(1)\ =\ \Theta(n^3)




Title: Re:Altra ricorrenza
Post by: corel_86 on 27-08-2011, 09:15:11
corel_86 noto con profondo piacere che ci stai aiutando veramente parecchio......e di questo ti ringrazio veramente tanto!! .applausi
Volevo chiedere ma in questo caso questa ricorrenza non si poteva fare usando il teorema master??perchè:
a=8 , b=2, -> n^log_2 ( 8 )  = n^3 -> f(n)=Θ( n^3 )
Visto che si verificano queste ipotesi non possiamo applicare il secondo caso del teorema master?e quindi T(n)=O(n^3\log(n) )??

Il teorema master si applica alle equazioni di ricorrenza che si presentano nella forma

T(n)=aT(n/b) + f(n)

quindi si può applicare a quella ricorrenza

proprio come ha fatto shiny che ha applicato il 1° Teorema Master

Comunque cambiando discorso per me aiutare è un piacere dato che io ho già dato questa materia non vedo perchè non debba aiutare quelli che ne hanno bisogno......

Sono sempre a disposizione....o quasi   :[Emoticon] Asd: :[Emoticon] Asd:


Title: Re:Altra ricorrenza
Post by: Daréios89 on 27-08-2011, 11:02:57
Io avrei:

n^2\log(n)    e  n^3

Dovrei trovare un \epsilon>0 tale che f(n)=O(n^{\log_b(a)})

Per esempio se scelgo \frac{1}{2} mi sembra funzioni, giusto?

Invece con il metodo di corel arrivo a conclusioni diverse, perchè io ho:

R(m)=R(m-1)+(\frac{1}{2})^m*m

Il telescoping io sapevo si applica quando si ha una sola funzione, abbiamo un prodotto noi, comunque ho pensato:

\sum_{i=0}^{m-1}(\frac{1}{2})^i*m

E' sbagliato far partire da zero la serie?
che comunque mi risulta 2, e con m a moltiplicare 2m.
Poi rifacendo le sostituzioni, e trascurando la costante 2, mi risulta come aveva postato un utente T(n)=O(n^3\log(n))  :-)|


Title: Re:Altra ricorrenza
Post by: shiny on 27-08-2011, 13:28:18


\sum_{i=0}^{m-1}(\fr<br />che comunque mi risulta 2, e con [tex]m a moltiplicare 2m.
Poi rifacendo le sostituzioni, e trascurando la costante 2, mi risulta come aveva postato un utente T(n)=O(n^3\log(n))  :-)|

Non so come hai svolto la serie o come ci arrivi ma cio' che ha scritto corel e' coretto e inoltre io ti ho espletato i passaggi per la risoluzione e in particolare ti sara' sfuggito questo passaggio n^3 \sum_{i=1}^{\infty} (\frac{i}{2^i})\ \leq\ n^3\ O(1) che ho svolto applicando il criterio del rapporto alla serie, la quale essendo convergente posso sostituirla con O(1)


Title: Re:Altra ricorrenza
Post by: corel_86 on 27-08-2011, 15:30:49
per Dareidos tu hai scritto la serie in questo modo

\sum_{i=0}^{m-1}(\frac{1}{2})^i*m

quando invece la serie è così

8^m\sum_{i=1}^{m}(\frac{1}{2})^i\times i non per m come hai scritto tu

e come ha detto shiny la serie è convergente.......inoltre la serie risulta
\frac{1}{2} +\frac{2}{4} +\frac{3}{8}+\frac{4}{16}+......... questo valido per m

comunque i passaggi sono giusti gli ho verificati due volte ho applicato il metodo che c'è sulle slide


Title: Re:Altra ricorrenza
Post by: callo on 27-08-2011, 17:56:23
Io avrei:

n^2\log(n)    e  n^3

Dovrei trovare un \epsilon>0 tale che f(n)=O(n^{\log_b(a)})

Per esempio se scelgo \frac{1}{2} mi sembra funzioni, giusto?

Invece con il metodo di corel arrivo a conclusioni diverse, perchè io ho:

R(m)=R(m-1)+(\frac{1}{2})^m*m

Il telescoping io sapevo si applica quando si ha una sola funzione, abbiamo un prodotto noi, comunque ho pensato:

\sum_{i=0}^{m-1}(\frac{1}{2})^i*m

E' sbagliato far partire da zero la serie?
che comunque mi risulta 2, e con m a moltiplicare 2m.
Poi rifacendo le sostituzioni, e trascurando la costante 2, mi risulta come aveva postato un utente T(n)=O(n^3\log(n))  :-)|

epsilon deve essere un numero compreso tra 0 e 1 ma  1/2 ancora non va bene......con valori di epsilon però maggiori di 0.5 vai tranquillo!!
Comunque pensandoci bene non può essere il secondo caso(come avevo detto precedentemente) perché f(n)=O(n^...) e non come avevo detto io f(n)=theta(n^....) ....che errore!!anzi...che ORRORE!!  .rido  .rido quindi per valori di epsilon >0.5>0 T(n)=theta(n^3)


Title: Re:Altra ricorrenza
Post by: Daréios89 on 27-08-2011, 18:09:36
Quote
epsilon deve essere un numero compreso tra 0 e 1 ma  1/2 ancora non va bene

Se \epsilon=\frac{1}{2} avrei n^2\log(n)  e  n^{\frac{5}{2}}

Se considero il limite:

\frac{n^2\log(n)}{n^{\frac{5}{2}} dovrebbe diventare \frac{\log(n)}{\sqrt{n}}

Che fa 0, quindi il numeratore è infinito di ordine inferiore rispetto al denominatore e quindi ci ritroveremmo nel primo caso del teorema master.... .penso

corel non metto in dubbio il tuo, ma il mio procedimento  :-)|

Non capisco:

T(n)=8^m \sum_{i=1}^{m} (\frac{i}{2^i})

Perchè se avevamo R(m) hai sostituito prima mettendo T(n)? Come mai c' è quell'8^m prima della somma? Nella ricorrenza c' era un m a moltiplicare......riseguendo il classico ragionamento che abbiamo fatto l' altra volta non riesco a seguirti. Cioè 8^m equivale ad n^3 ma all' interno della sommatoria avremmo \frac{1}{2}^m che moltiplica m, non capisco proprio come sei arrivato a fare quella cosa.


Title: Re:Altra ricorrenza
Post by: shiny on 28-08-2011, 02:00:19
Ad un certo punto, corel, ha usato questa sostituzione

R(m)\ =\ S(m)/8^m\ \Longrightarrow\ 8^mR(m)=S(m)=T(n)\quad\quad (1)

da cui se

R(m)\ =\ \sum_{i=1}^{m} (\frac{i}{2^i})

allora per la (1)

T(n)=S(m)=8^mR(m)=8^m\sum_{i=1}^{m} (\frac{i}{2^i})

Spero di essere stato chiaro perche' meglio di cosi' non lo saprei spiegare .ciaociao


Title: Re:Altra ricorrenza
Post by: Daréios89 on 28-08-2011, 10:36:25
Si ora si, ho capito, mi mancava una sostituzione, resta solo una cosa.
Il telescoping si applica ad esempio in

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

E diventa \sum_{i}{}f(i)

Ma prima ancora di quella sostituzione di cui mi hai parlato, la sommatoria, o meglio la ricorrenza è:

R(m)=R(m-1)+(\frac{1}{2})^mm

Allora che si possa usare il telescoping si, perchè abbiamo la serie geometrica, ma come facciamo a liberarci della m a moltiplicare?


Title: Re:Altra ricorrenza
Post by: shiny on 28-08-2011, 11:45:00
Nota bene che la m non e' una costante ma e' l'argomento di una funzione (ovvero puo' assumere qualsiasi valore all'interno del dominio della funzione)...

R(m)=R(m-1)+m(\frac{1}{2})^m

R(m-1)=R(m-2)+(m-1)(\frac{1}{2})^{m-1}

R(m-2)=R(m-3)+(m-2)(\frac{1}{2})^{m-2}

... e cosi' via. Quindi hai questa somma

\sum_{i=1}^{m} (\frac{i}{2^i})

e non questa

\sum_{i=1}^{m} m(\frac{1}{2^i})



Title: Re:Altra ricorrenza
Post by: Daréios89 on 28-08-2011, 12:13:27
Ah...quindi lo facciamo perché non influisce sul nostro calcolo...

P.S. una parentesi che non c' entra, se nel calcolo di una ricorrenza avessi \sum_{i=0}^{\log_5(n)-1}n\log(n) come andrebbe trattata?

(\log(n)-1)(n\log(n)) ?