Teorema dell'esperto

[ncc17011]

Salve,

non sono sicuro se ho risolto bene quest'esercizio dove occorre risolvere la ricorrenza:

$T(n) = 15T(n/4)+n^2

Quindi $a = 15$, $b = 4$, $f(n) = n^2$. Il teorema dice che $f(n)$ va confrontato con la funzione $n^(log_b a)$.
In questo caso, $n^2$ risulta essere più grande di $n^(log_4 15)$.

Quindi va applicato il caso tre del metodo, che dice:
Se $f(n) = Omega(n^(log_b a + epsilon))$ per qualche costante $epsilon >0$ e se $af(n/b) <= cf(n)$ per qualche costante $c<1$ e per ogni $n$ sufficientemente grande, allora $T(n) = Theta(f(n))$.

Quindi nel mio caso $T(n) = Theta(n^2)$, o sbaglio?
In un altro esempio (vedi http://www.cs.iitm.ernet.in/theory/mfcs98page/mfcshtml/notes4/master.html), all'ultimo esercizio $T(n) = 4T(n/2) + n^3$, non capisco come viene calcolato il valore per $epsilon = 1/2$.

[Sk_Anonymous]

Nel link che hai inserito, oltre a non capire come è stato calcolato $epsilon$ non ho capito come è stato calcolato c nella ricorrenza $T(n) = 4T(n/2) + n^3$. Il valore c dovrebbe essere minore di 1. Non può essere 2. Dal calcolo infatti risulta $ 1/2 < c < 1$.

Mentre nella tua ricorrenza il valore c è $ 15/16

Cita

Segnala

[ncc17011]

"nochipfritz":

Mentre nella tua ricorrenza il valore c è $ 15/16

Come hai fatto a calcolare c? Il metodo dell'esperto non doveva servire a determinare il limite? Le mia risposta è quindi errata?
Per quanto riguarda $epsilon$, non so come si calcola...

[Sk_Anonymous]

Per dimostrare che puoi applicare il teorema master, devi dimostrare che $af(n/b) <= cf(n)$ per qualche costante $c<1$ ?
sostituendo i valori...e risolvendo rispetto a $c$ ottieni $c > 15/16$. Ciò significa che esiste quel $c$ che ti permette di verificare l'ipotesi e quindi di applicare il teorema master. In questo caso basta scegliere un $c$ compreso tra 15/16 e 1. Rimane il problema dell' epsilon. Credo, comunque, che il tuo risultato sia corretto intuitivamente anche se non riusciamo a dimostrarlo matematicamente.

[bulah]

La ricorrenza T(n) = 15T($n/4$) + n
Per prima cosa:
1) Se f(n) = O($n^{ \log_(b)a - \epsilon }$) per qualche costante $ \epsilon $ > 0, allora T(n) = $\Theta$($n^{ \log_(b)a}$).
2) Se f(n) = $\Theta$($n^{ \log_(b)a}$) allora T(n) = $\Theta$($n^{ \log_(b)a}*log_(2)n$).
3) Se f(n) = $\Omega$($n^{ \log_(b)a + \epsilon }$) per qualche costante $ \epsilon $ > 0, e se per qualche costante c < 1 af($n/b$) $<=$ cf(n) allora T(n) = $\Theta$(f(n)).

il mio valore a = 15, il valore b = 4 quindi $n^{ \log_(b)a }$ = $n^{ \log_(4)15}$ che equivale $n^{1,95}$
Siccome $n^{1,95}$ e maggiore del mio $n^1$ il mio epsilon equivale a $ \epsilon$ = 0,95, e siccome mi trovo nel primo caso il risultato della ricorrenza sara' T(n) = $\Theta$($n^{ \log_(b)a}$) ---> T(n) = $\Theta$($n^{1,95}$)

Spero di essermi fatto abbastanza chiaro, in caso di errori o informazioni contattatememi

[hamming_burst]

Messaggioda ncc1701 » mer 09 ago, 2006 10:29

il caro vecchio necroposting...

comunque due cose non funzionano:

"bulah":La ricorrenza T(n) = 15T($n/4$) + n si puo' risolvere con il teorema dell esperto.
...
T(n) = $\Theta$($n^{ \log_(b)a}$) ---> T(n) = $\Theta$($n^{1,95}$)

dovresti dire:
visto che $f(n) in O(n^{\log_(4)(15)-\epsilon})$ allora $T(n) in \Theta(n^{1,95})$

possiamo aprossimare a $T(n) = \Theta(n^{2})$

poi questo non ha senso, se il master dimostra un'ipotesi, che significato ha approssimarla ad una limitazione maggiore di quella ipotizzata?

[bulah]

Mi scuso per gli errori che ho fatto, in futuro cerchero di fare piu attenzione.
Hamming_burst grazie per avermelo fatto notare.