Pages: [1]   Go Down
Print
Author Topic: Albero di ricorsione e telescoping  (Read 2121 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
milos224
Forumista
***
Offline Offline

Posts: 830


« on: 23-11-2012, 12:26:20 »

Allora più o meno ho capito quando utilizzare il teorema master, ovvero quando ho una ricorrenza della forma
aT(n/b) + f(n). Gran parte delle ricorrenze di questo tipo posso risolverle facilmente con questo teorema.

Invece per altre, ad esempio
T(n)= 2T(n-1) + 2(n-1) o anche T(n)=T(n/3)+T(n/6)+T(n/9)+n
come si risolvono?

Sto provando a capire l'albero di ricorsione ma mi blocco negli vari passaggi. Ricostruendo ad esempio l'albero della seconda ricorrenza ho:
Link Immagine

ma poi cosa devo scrivere al terzo livello? e arrivato alla fine come trovo il risultato della ricorrenza?Provando a fare il secondo esercizio(che mi sembra più semplice) proverò poi il primo. Grazie!
Logged
milos224
Forumista
***
Offline Offline

Posts: 830


« Reply #1 on: 27-11-2012, 12:39:47 »

Nessuno? 
Logged
corel_86
Forumista
***
Offline Offline

Gender: Male
Posts: 570



« Reply #2 on: 27-11-2012, 23:36:39 »

Per quanto riguarda il primo esercizio parlane con il prof. Cutello perchè non ricordo come risolverla.

Mentre per l'altro esercizio mi spiace dovertelo dire ma non hai preso sul serio la discussione che abbiamo affrontato nel vecchio post.
Se guardi bene è spiegato pari passo come fare l'albero di ricorrenza.
 
Non puoi fare gli esercizi se non conosci la teoria dell'albero di ricorsione; controllati la teoria e dai una spulciata nei vecchi post, troverai moltissimi esercizi.

Comunque per andare avanti n quanti figli ha al secondo livello? Tante quante sono le ricorrenze in questo caso 3
Ogni figlio del secondo livello quanti figli ha? Anziché avere n abbiamo: prima n/3 poi n/6 e infine n/9 quindi...

e cosi via....

Logged

Se trovo qualcosa che non va lo faccio presente subito

Saluti ciaociao ciao

A.C.
milos224
Forumista
***
Offline Offline

Posts: 830


« Reply #3 on: 28-11-2012, 10:38:59 »

è proprio su questo esercizio che non capisco come fare l'albero di ricorsione.. al terzo livello non capisco cosa scrivere e soprattutto nell'ultimo mi confondo con il calcolo dei costi..
Logged
corel_86
Forumista
***
Offline Offline

Gender: Male
Posts: 570



« Reply #4 on: 28-11-2012, 23:42:34 »

Devi fare una semplice somma di frazioni. Al terzo livello abbiamo:

sostituisco n/3 al posto di n

\frac{n}{9}+\frac{n}{18}+\frac{n}{27}


sostituisco n/6 al posto di n

\frac{n}{18}+\frac{n}{36}+\frac{n}{54}


sostituisco n/9 al posto di n

\frac{n}{27}+\frac{n}{54}+\frac{n}{81}

quindi al terzo livello si ha: \frac{n}{9}+\frac{n}{18}+\frac{n}{27}+\frac{n}{18}+\frac{n}{36}+\frac{n}{54}+\frac{n}{27}+\frac{n}{54}+\frac{n}{81}

che è uguale facendo somme e semplificazioni \frac{n}{3}+\frac{n}{36}+\frac{n}{81}

che da come risultato \frac{121}{324}n

Se hai capito il passaggio successivo sei in grado di svolgere il resto. Successivamente postalo cosi altri colleghi possono consultarlo
Logged

Se trovo qualcosa che non va lo faccio presente subito

Saluti ciaociao ciao

A.C.
milos224
Forumista
***
Offline Offline

Posts: 830


« Reply #5 on: 29-11-2012, 10:38:37 »

Devi fare una semplice somma di frazioni. Al terzo livello abbiamo:

sostituisco n/3 al posto di n

\frac{n}{9}+\frac{n}{18}+\frac{n}{27}


sostituisco n/6 al posto di n

\frac{n}{18}+\frac{n}{36}+\frac{n}{54}


sostituisco n/9 al posto di n

\frac{n}{27}+\frac{n}{54}+\frac{n}{81}

quindi al terzo livello si ha: \frac{n}{9}+\frac{n}{18}+\frac{n}{27}+\frac{n}{18}+\frac{n}{36}+\frac{n}{54}+\frac{n}{27}+\frac{n}{54}+\frac{n}{81}

che è uguale facendo somme e semplificazioni \frac{n}{3}+\frac{n}{36}+\frac{n}{81}

che da come risultato \frac{121}{324}n

Se hai capito il passaggio successivo sei in grado di svolgere il resto. Successivamente postalo cosi altri colleghi possono consultarlo
Ok perfetto! Ma devo continuare così? Quando mi devo fermare? Inoltre ad un certo punto sommo tutti i valori dei livelli e poi?
Logged
corel_86
Forumista
***
Offline Offline

Gender: Male
Posts: 570



« Reply #6 on: 29-11-2012, 15:27:37 »

Temo che non hai capito come affrontare l'esercizio.

Te l'abbiamo spiegato in tutte le salse, posso solo dirti adesso di guardare qui, qui e qui per prendere lo spunto e ricorda che questa operazione la puoi fare anche tu.
« Last Edit: 29-11-2012, 15:32:17 by corel_86 » Logged

Se trovo qualcosa che non va lo faccio presente subito

Saluti ciaociao ciao

A.C.
milos224
Forumista
***
Offline Offline

Posts: 830


« Reply #7 on: 29-11-2012, 15:45:27 »

Temo che non hai capito come affrontare l'esercizio.

Te l'abbiamo spiegato in tutte le salse, posso solo dirti adesso di guardare qui, qui e qui per prendere lo spunto e ricorda che questa operazione la puoi fare anche tu.
Capito tutto, ho trovato delle ottime dispense online, si può chiudere.
Logged
Pages: [1]   Go Up
Print
Jump to: