Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Algoritmi, 9 CFU => Topic started by: Edgarpoe on 08-03-2012, 19:22:19



Title: Come risolvere questa ricorrenza? (compito di oggi 08/03)
Post by: Edgarpoe on 08-03-2012, 19:22:19
T(n) = 3T(n/5) + T(n/2) + n


L'albero di ricorsione dovrebbe essere una cosa del genere:



                               n
                           /        \
                       /                \
                   /                        \
           3(n/5)                        n/2                           ->11/10n
          /         \                      /      \
3(n/25)        n/10        3(n10)     (n/4)                   ->77/100n



Sto sbagliando qualcosa? non mi riesce di stabilire una regola per il costo dell'iesimo livello.



Title: Re:Come risolvere questa ricorrenza? (compito di oggi 08/03)
Post by: Edgarpoe on 08-03-2012, 19:33:31
Ho trovato dove sbagliavo:



                               n
                           /        \
                       /                \
                   /                        \
           3(n/5)                        n/2                           ->11/10n
          /                               /      \
3[(n/25)  n/10]        3(n10)        (n/4)                   ->121/100n



Il costo è n(11/10)^i


Title: Re:Come risolvere questa ricorrenza? (compito di oggi 08/03)
Post by: ExEcUtIvE on 08-03-2012, 19:35:56
Ciao, non riesci a stabilirla perché a profondità 2 hai 9(n/25)+6(n/10)+n/4=121/100 e quindi [(11/10)^i]n
Come soluzione ho messo O(n), seguendo i vari passaggi intermedi..

EDIT: Come non detto :-)


Title: Re:Come risolvere questa ricorrenza? (compito di oggi 08/03)
Post by: Flyer on 08-03-2012, 19:38:14
Ciao, non riesci a stabilirla perché a profondità 2 hai 9(n/25)+6(n/10)+n/4=121/100 e quindi [(11/10)^i]n
Come soluzione ho messo O(n), seguendo i vari passaggi intermedi..

EDIT: Come non detto :-)
Potresti scrivere i passaggi che hai fatto?  .penso


Title: Re:Come risolvere questa ricorrenza? (compito di oggi 08/03)
Post by: ExEcUtIvE on 08-03-2012, 19:47:55

Potresti scrivere i passaggi che hai fatto?  .penso
Credo che ti interessa sapere maggiormente il punto in cui si capisce che è lineare...Svolgendoti la sommatoria come serie geometrica di ragione q>1, arrivi a calcolare (11/10)^(log(n)+1)=(11/10)*(11/10)^log(n)=(11/10)*(n)^log(11/10)
poiché log(11/10) è 0,(qualcosa) hai n^0 che è 1 quindi dalla sommatoria ottieni una costante che poi moltiplicata ad n che sta fuori dalla sommatoria ottieni una eq. di ricorrenza del tipo T(n)= n*(qualche costante)+n
Quindi da questo ragionamento deduci che è O(n)...Se ho fatto correttamente..
Scusate se non ho utilizzato latex e se non ho scritto tutti i vari passaggi, ma vado molto di fretta..spero di esserti stato utile..


Title: Re:Come risolvere questa ricorrenza? (compito di oggi 08/03)
Post by: Edgarpoe on 08-03-2012, 19:54:27
non vorrei aver preso un granchio, ma 11/10, essendo > di 1 non porta la serie a crescere indefinitamente?


Title: Re:Come risolvere questa ricorrenza? (compito di oggi 08/03)
Post by: ExEcUtIvE on 08-03-2012, 19:55:49
non vorrei aver preso un granchio, ma 11/10, essendo > di 1 non porta la serie a crescere indefinitamente?
si scusa mi sono confuso un attimo il procedimento che ho fatto è per la serie con ragione >1 XD ...corretto!!


Title: Re:Come risolvere questa ricorrenza? (compito di oggi 08/03)
Post by: Edgarpoe on 08-03-2012, 20:15:19

Potresti scrivere i passaggi che hai fatto?  .penso
Credo ti interessa sapere maggiormente il punto in cui si capisce che è lineare...Svolgendoti la sommatoria come serie geometrica di ragione q>1, arrivi a calcolare (11/10)^(log(n)+1)=(11/10)*(11/10)^log(n)=(11/10)*(n)^log(11/10)
poiché log(11/10) è 0,(qualcosa) hai n^0 che è 1 quindi dalla sommatoria ottieni una costante che poi moltiplicata ad n che sta fuori dalla sommatoria ottieni una eq. di ricorrenza del tipo T(n)= n*(qualche costante)+n
Quindi da questo ragionamento deduci che è O(n)...Se ho fatto correttamente..
Scusate se non ho utilizzato latex e se non ho scritto tutti i vari passaggi, ma vado molto di fretta..spero di esserti stato utile..


E' la parte in grassetto a non essermi chiara, se qualcuno vorrà aiutarmi gliene sarò infinitamente grato


Title: Re:Come risolvere questa ricorrenza? (compito di oggi 08/03)
Post by: ExEcUtIvE on 08-03-2012, 21:45:05
E' la parte in grassetto a non essermi chiara, se qualcuno vorrà aiutarmi gliene sarò infinitamente grato
ecco qui quella parte, scritta bene..è lo svolgimento della serie..
http://www.image-share.com/ijpg-1338-66.html
non l'ho svolta tutta, però questo è il pezzo più "complesso"..


Title: Re:Come risolvere questa ricorrenza? (compito di oggi 08/03)
Post by: Edgarpoe on 08-03-2012, 21:52:36
Grazie davvero  .leggo .applausi


Title: Re:Come risolvere questa ricorrenza? (compito di oggi 08/03)
Post by: ExEcUtIvE on 08-03-2012, 22:37:11
Grazie davvero  .leggo .applausi
Figurati, se non ci si aiuta tra colleghi...  ;-)


Title: Re:Come risolvere questa ricorrenza? (compito di oggi 08/03)
Post by: chernobyl on 09-03-2012, 10:46:01
Ragazzi ma allora la risposta esatta è O(n)?


Title: Re:Come risolvere questa ricorrenza? (compito di oggi 08/03)
Post by: eLis on 09-03-2012, 10:50:01
No la risposta è O(n^2). La sommatoria dà O(n) ma questa è moltiplicata per n


Title: Re:Come risolvere questa ricorrenza? (compito di oggi 08/03)
Post by: chernobyl on 09-03-2012, 10:51:51
allora ho risposto giusto!


Title: Re:Come risolvere questa ricorrenza? (compito di oggi 08/03)
Post by: Vincenzo Cutello on 09-03-2012, 17:51:03
No la risposta è O(n^2). La sommatoria dà O(n) ma questa è moltiplicata per n
Ok, finalmente qualcuno che corregge  .smile


Title: Re:Come risolvere questa ricorrenza? (compito di oggi 08/03)
Post by: ExEcUtIvE on 09-03-2012, 18:09:11
Grazie ragazzi, ho capito dove sbagliavo... Approssimavo un po troppo  :-K !!
P.S.: non ho detto che quella era la soluzione, ma che quella era la soluzione che ho messo io spiegando quali passaggi mi ci hanno portato.


Quindi da questo ragionamento deduci che è O(n)...Se ho fatto correttamente..



Title: Re:Come risolvere questa ricorrenza? (compito di oggi 08/03)
Post by: corel_86 on 20-07-2012, 06:18:01
Un mio collega mi aveva chiesto aiuto su questo esercizio dicendomi che non aveva capito bene i passaggi, spero che in modo o nell'altro riceva questo messaggio con la speranza che gli sia di aiuto.

Allora premetto che algoritmi l'ho data 2 anni quindi possono esserci degli errori. In caso correggetemi:

                                                                                           n

                     
                  (n/5)                                    (n/5)                                       (n/5)                                     (n/2)                        ->11/10n



                                       
(n/25) (n/25) (n/25) (n/10)    (n/25) (n/25) (n/25) (n/10)    (n/25) (n/25) (n/25) (n/10)   (n10) (n/10) (n/10) (n/4)         ->121/100n

il cammino più lungo è dato dal percorso n -> n/2 -> n/4 ->.......-> 1

poichè (\frac{1}{2})^in=1

allora

i=log_2n

una volta effettuato questo calcolo si fa la sommatoria

\sum_{i=0}^{log_2n } (\frac{11}{10})^i n

n \sum_{i=0}^{log_2n } (\frac{11}{10})^i

ricordando che

\sum_{i=0}^{n} x^i\begin{Bmatrix} n &&& se &&& x=1 \\ \frac{1-x^{n+1}}{1-x} &&& &&& altrimenti\end{Bmatrix}

il risultato di tutto è

n \sum_{i=0}^{log_2n } (\frac{11}{10})^i=n\frac{1-(11/10)^{log_2n +1 }}{1-(11/10)}

applicando poi le regole degli logaritmi e facendo alcuni passaggi semplici il risultato sarà

\Theta(n^2)

E' questo è tutto gente (http://www.moviesoddity.com/wp-content/uploads/2009/11/porky-pig.jpg)