Pagina 1 di 1

Equazione di ricorrenza

MessaggioInviato: 04/01/2020, 11:52
da sara09
Buongiorno sto cercando di fare questo esercizio...scusate se allego l’immagine ma mi risulta difficile scriverlo, ho dei dubbi sul contributo dei nodi di ogni livello...potete dirmi se è corretto?


Immagine

Re: Equazione di ricorrenza

MessaggioInviato: 05/01/2020, 18:33
da Leyxargon
Se hai davanti quel tipo di ricorrenze (con più chiamate e taglie di input differenti) non è scontato effettuare una stima esatta del contributo dei nodi, in quanto sicuramente ci sarà qualche chiamata che sarà arrivata al caso base prima di altre. In queste situazioni l'albero possiede le foglie a livelli differenti.
Una volta disegnato l'albero puoi decidere se risolvere la ricorrenza ipotizzando una soluzione applicando la sostituzione, altrimenti calcolare la sommatoria dei costi: in tal caso quello che potresti fare è effettuare una stima per eccesso considerando il contributo di foglie dalla "parte" delle chiamate che impiegano più tempo ad arrivare al caso base (più profondi), in altre parole maggiorando la sommatoria effettiva dei costi con una sommatoria "superiore" e ottenere il limite superiore della tua funzione. Nel tuo caso hai dei sottoproblemi di dimensione $\frac{n^2}{2^i}$ e $\frac{n^2}{3^i}$, dove $\frac{n^2}{3^i}$ decresce più rapidamente e arriverà al caso base prima di $\frac{n^2}{2^i}$.

Calcolando i costi dei livelli ottieni
    Livello 0: $n^2$
    Livello 1: $[(\frac{1}{2})^2+(\frac{1}{2})^2+(\frac{1}{3})^2]n^2 = \frac{11}{18}n^2$
    Livello 2: $[4(\frac{1}{4})^2+4(\frac{1}{6})^2+(\frac{1}{9})^2]n^2 = \frac{121}{324}n^2=(\frac{11}{18})^2 n^2$
    ...
    Livello i: $(\frac{11}{18})^i n^2$
Ora sicuramente il costo reale della ricorrenza è minore o uguale di $(\frac{11}{18})^i n^2$, quindi calcolando la sommatoria dell'i-esimo livello ti ricavi un limite superiore.

Re: Equazione di ricorrenza

MessaggioInviato: 06/01/2020, 10:50
da sara09
Leyxargon ha scritto:Se hai davanti quel tipo di ricorrenze (con più chiamate e taglie di input differenti) non è scontato effettuare una stima esatta del contributo dei nodi, in quanto sicuramente ci sarà qualche chiamata che sarà arrivata al caso base prima di altre. In queste situazioni l'albero possiede le foglie a livelli differenti.
Una volta disegnato l'albero puoi decidere se risolvere la ricorrenza ipotizzando una soluzione applicando la sostituzione, altrimenti calcolare la sommatoria dei costi: in tal caso quello che potresti fare è effettuare una stima per eccesso considerando il contributo di foglie dalla "parte" delle chiamate che impiegano più tempo ad arrivare al caso base (più profondi), in altre parole maggiorando la sommatoria effettiva dei costi con una sommatoria "superiore" e ottenere il limite superiore della tua funzione. Nel tuo caso hai dei sottoproblemi di dimensione $\frac{n^2}{2^i}$ e $\frac{n^2}{3^i}$, dove $\frac{n^2}{3^i}$ decresce più rapidamente e arriverà al caso base prima di $\frac{n^2}{2^i}$. Calcolando i costi dei livelli ottieni
    Livello 0: $n^2$
    Livello 1: $(\frac{1}{2}+\frac{1}{2}+\frac{1}{3})n^2 = \frac{4}{3}n^2$
    Livello 2: $(4\frac{1}{4}+4\frac{1}{6}+\frac{1}{9})n^2 = \frac{16}{9}n^2=(\frac{4}{3})^2 n^2$
    ...
    Livello i: $(\frac{4}{3})^i n^2$
Ora sicuramente il costo reale della ricorrenza è minore di $(\frac{4}{3})^i n^2$, quindi calcolando la sommatoria dell'i-esimo livello ti ricavi un limite superiore.

Ma per ogni nodo il suo contributo non va elevato al quadrato?

Re: Equazione di ricorrenza

MessaggioInviato: 06/01/2020, 11:40
da Leyxargon
sara09 ha scritto:Ma per ogni nodo il suo contributo non va elevato al quadrato?

Errore mio, ho corretto i calcoli. La procedura resta la medesima.

Re: Equazione di ricorrenza

MessaggioInviato: 06/01/2020, 19:58
da sara09
Leyxargon ha scritto:
sara09 ha scritto:Ma per ogni nodo il suo contributo non va elevato al quadrato?

Errore mio, ho corretto i calcoli. La procedura resta la medesima.

Va bene e se ho:
$ 3(n/2) $
Nella seconda equazione del sistema allora al secondo livello dell’albero avrei:
$ 9(n/2)^2+9(n/2)^2+(n/3)^2 $
Giusto?

Re: Equazione di ricorrenza

MessaggioInviato: 06/01/2020, 23:08
da Leyxargon
sara09 ha scritto:
Leyxargon ha scritto:
sara09 ha scritto:Ma per ogni nodo il suo contributo non va elevato al quadrato?

Errore mio, ho corretto i calcoli. La procedura resta la medesima.

Va bene e se ho:
$ 3(n/2) $
Nella seconda equazione del sistema allora al secondo livello dell’albero avrei:
$ 9(n/2)^2+9(n/2)^2+(n/3)^2 $
Giusto?

Se ho capito bene, stai supponendo una relazione di questo tipo
\[ T(n) = 3T(\frac{n}{2}) + T(\frac{n}{3}) + n^2 \]
In tal caso lo svolgimento sarebbe il seguente
    Livello 0: $n^2$
    Livello 1: $[3(\frac{1}{2})^2 + (\frac{1}{3})^2]n^2 = \frac{31}{36}n^2$
    Livello 2: $[9(\frac{1}{4})^2 + 6(\frac{1}{6})^2 + (\frac{1}{9})^2]n^2 = \frac{961}{1296}n^2$
    ...
    Livello i: $(\frac{31}{36})^i n^2$