Pages: [1]   Go Down
Print
Author Topic: Esercizi algoritmi  (Read 3068 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« on: 04-03-2010, 19:34:54 »

Salve ragazzi ho fatto questo esercizio sul teorema master..

T(n) = T(9n/10) + n , la soluzione dovrebbe essere T(n) = theta(n).

ma non capisco come possiamo trovarci tale soluzione con il teorema mastera dato che non esiste il valore "a".

E poi avrei un dubbio , attuare il telescoping sarebbe la stessa cosa di trovarci una soluzione tramite albero di ricorsione?
Logged
Innuendo85
Apprendista Forumista
**
Offline Offline

Posts: 222



« Reply #1 on: 04-03-2010, 19:38:04 »

Ciao,collega.Sei proprio sicuro che "non esiste" il valore "a"?...Pensaci bene:quali sono le condizioni del teorema master?
Logged

You can be anything you want to be, just turn yourself into anything you think that you could ever be...Be free with your tempo, be free, be free...Surrender your ego - be free, be free to yourself...
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« Reply #2 on: 04-03-2010, 19:44:17 »

cioè volevo dire che il valore di a è 1 , ma un pò è quel 9n/10 che non capisco , come dovremmo porre la condizione?
Logged
Psycho
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 497



« Reply #3 on: 04-03-2010, 19:55:50 »

a=1
b=10/9

e fai i calcoli 
Logged

Segnate le date, cancellate gli altri impegni, chiudete i libri e i quaderni e per un attimo accorgetevi che la vita non è piatta ma può essere... 3d!
Innuendo85
Apprendista Forumista
**
Offline Offline

Posts: 222



« Reply #4 on: 04-03-2010, 19:56:39 »

Perfetto,riguardo alla "a" ci sei arrivato da solo!   Quanto alla "b"... beh,tieni in considerazione che nell'equazione di ricorrenza del teorema master il termine T(n/b) è uguale a T(n*1/b). Quindi,nel caso in questione, T(n*1/b) = T(n*9/10) ---> Da cui segue che 1/b=9/10 e quindi b=10/9. Spero di essere stato chiaro.  
Logged

You can be anything you want to be, just turn yourself into anything you think that you could ever be...Be free with your tempo, be free, be free...Surrender your ego - be free, be free to yourself...
Innuendo85
Apprendista Forumista
**
Offline Offline

Posts: 222



« Reply #5 on: 04-03-2010, 19:58:08 »

Qualcuno molto più succinto di me mi ha anticipato nella risposta! 
Logged

You can be anything you want to be, just turn yourself into anything you think that you could ever be...Be free with your tempo, be free, be free...Surrender your ego - be free, be free to yourself...
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« Reply #6 on: 04-03-2010, 20:00:37 »

grazie per le risposte raga^^ , per quanto riguarda l'ultima domanda che ho fatto nel mio primo post ovvero..

Code:
E poi avrei un dubbio , attuare il telescoping sarebbe la stessa cosa di trovarci una soluzione tramite albero di ricorsione?

P.S: potreste rispondere ai pm che vi ho mandato^^
Logged
Psycho
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 497



« Reply #7 on: 04-03-2010, 20:04:49 »

credo di poter affermare che sono sostanzialmente la stessa cosa..i calcoli col telescoping comunque ti facilitano il lavoro di molto in alcuni casi.il metodo dell'albero di solito si usa quando non puoi ricavare la complessità col teorema master e cerchi un guess iniziale da dimostrare poi col metodo di sostituzione  
« Last Edit: 04-03-2010, 20:06:24 by Psycho » Logged

Segnate le date, cancellate gli altri impegni, chiudete i libri e i quaderni e per un attimo accorgetevi che la vita non è piatta ma può essere... 3d!
Psycho
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 497



« Reply #8 on: 04-03-2010, 20:05:58 »

Qualcuno molto più succinto di me mi ha anticipato nella risposta! 

la tua risposta però è molto più chiara  ok ok
Logged

Segnate le date, cancellate gli altri impegni, chiudete i libri e i quaderni e per un attimo accorgetevi che la vita non è piatta ma può essere... 3d!
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« Reply #9 on: 04-03-2010, 20:11:14 »

Ma se abbiamo un esercizio del genere , ovvero..

T(n) = T(n-1) + n    dobbiamo effettuare il telescoping effettuando una serie del tipo sommatoria di f(i)??

« Last Edit: 04-03-2010, 20:15:17 by Alex_47 » Logged
Psycho
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 497



« Reply #10 on: 04-03-2010, 20:14:06 »

il telescoping in questo caso si applica in questo modo:
devi sommare n-1 volte il valore n per ottenere il costo totale...
quindi fai la sommatoria per i che va da 0 a n di i, la risolvi e ottieni la complessità di questa equazione di ricorrenza  yoh
Logged

Segnate le date, cancellate gli altri impegni, chiudete i libri e i quaderni e per un attimo accorgetevi che la vita non è piatta ma può essere... 3d!
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« Reply #11 on: 04-03-2010, 20:15:47 »

benissimo grazie^^

ti ho mandato un altro pm
Logged
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« Reply #12 on: 05-03-2010, 09:38:48 »

invece per quanto riguarda questo esercizo..

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

Dovremmo risolverlo usando la dimostrazione induttiva , ma come possiamo farlo??
Logged
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« Reply #13 on: 05-03-2010, 09:55:57 »

sulle slide che trovi sul sito del Prof. Cutello relative alle equazioni di ricorrenza c'è il "Lemma 1" (pag.15) che dice che tutte le equazioni di ricorrenza del tipo T(n)=aT(n/a + k)+n con "k" costante e "a">1 hanno soluzione T(n)=\Theta(nlog n)

Successivamente viene spiegato come procedere con la dimostrazione per induzione.
Logged
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« Reply #14 on: 05-03-2010, 09:58:09 »

SI , ma non ho capito bene come si effettua la dimostrazione induttiva in quel caso.
« Last Edit: 05-03-2010, 10:01:29 by Alex_47 » Logged
Pages: [1]   Go Up
Print
Jump to: