Equazione di ricorrenza

Messaggioda sara09 » 04/01/2020, 11:52

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
sara09
Junior Member
Junior Member
 
Messaggio: 148 di 170
Iscritto il: 11/02/2019, 19:04

Re: Equazione di ricorrenza

Messaggioda Leyxargon » 05/01/2020, 18:33

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.
Ultima modifica di Leyxargon il 06/01/2020, 11:50, modificato 3 volte in totale.
Leyxargon
Starting Member
Starting Member
 
Messaggio: 9 di 11
Iscritto il: 06/11/2019, 12:44

Re: Equazione di ricorrenza

Messaggioda sara09 » 06/01/2020, 10:50

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?
sara09
Junior Member
Junior Member
 
Messaggio: 149 di 170
Iscritto il: 11/02/2019, 19:04

Re: Equazione di ricorrenza

Messaggioda Leyxargon » 06/01/2020, 11:40

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.
Leyxargon
Starting Member
Starting Member
 
Messaggio: 10 di 11
Iscritto il: 06/11/2019, 12:44

Re: Equazione di ricorrenza

Messaggioda sara09 » 06/01/2020, 19:58

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?
sara09
Junior Member
Junior Member
 
Messaggio: 150 di 170
Iscritto il: 11/02/2019, 19:04

Re: Equazione di ricorrenza

Messaggioda Leyxargon » 06/01/2020, 23:08

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$
Leyxargon
Starting Member
Starting Member
 
Messaggio: 11 di 11
Iscritto il: 06/11/2019, 12:44


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 9 ospiti