[Generico]Ricorrenze

[domenico88]

Ciao a tutti!

Allora sto imparando la complessità computazionale di alcuni algoritmi noti.
Alcuni come quick sort oppure merge sort, usano la tecnica del divide et impera.
Per calcolare la complessità di questi si usano le equzioni di ricorrenza...

es merge sort nel caso peggiore è descritto da questa ricorrenza

t(n) = c1 per n = 1
2T(n/2) + nc2 per n > 1

quindi t(n) = O(nlogn)

Il prof ha spiegato nel corso soltanto il metodo iterativo...ora come dovrei procedere per dimostrare che t(n) = O(nlogn) ?:help: :help:

[:.Blizzard.:]

Uno dei metodi migliori per risolvere questo genere di equazioni di ricorrenza è l'uso di alberi di ricorsione:

http://www.dsi.unifi.it/~costa/lucidi_fondII_ing_06_07/24b.AlberoRicorsione.pdf


Come ultima spiaggia c'è il Teorema dell'esperto, non sempre applicabile, che rappresenta una scorciatoia che è meglio evitare di prendere almeno quando si è all'inizio dello studio di equazioni di ricorrenza.


Mi auguro soltanto che il fatto che tu non abbia accennato a questi metodi sia solo perchè il corso non è finito e il professore deve ancora spiegarteli :stordita:

Cmq, dai un occhio alle slide. Se non ti torna chiedi pure.

[domenico88]

grazie per la risp:D

Il metodo dell'albero, correggimi se sbaglio, è la rappresentazione grafica del metodo iterativo?
Cmq ho studiato un pò anche il metodo di sostituzione che procede per induzione matematica...
Il teorema dell'esperto lo conosco superficialmente, ho letto delle cose sul libro però non ho voluto addentrarmi troppo in questa strada per via dei numerosi calcoli matematici che bisogna svolgere.:doh:

Non li ho mensionati perchè all'esame ho sentito dire che fanno svolgere le ricorrenze appunto con il metodo iterativo....che mi sembra anche il più facile...Ora è un pò tardi....domani vedrò meglio le slide che mi hai proposto....

[domenico88]

uhm qui non ho capito

n^2 Sommatoria da i=0 a lg n 1/2^i < n^2 Somatoria i=0...infinito 1/2 ^i = 2 n^2
come si ricava 2 n^2 ??:confused:

poi per calcolare l'altezza dell'albero non ho capito i vari passaggi che fà:

n --> 1/2n --> (1/2)^2 --> (1/2)^3 --> 1 :confused:

perchè (1/2)^i n = 1 ???

[domenico88]

:help: :help:

[:.Blizzard.:]

Le equazioni di ricorrenza sono sempre espresse dalla seguente formula generica:

http://operaez.net/mimetex/T%28n%29=%20aT%28%5Cfrac%7Bn%7D%7Bb%7D%29%20+%20f%28n%29

Ovvero il mio problema si evolve in a sottoproblemi di dimensione n/b e per ciascun livello pago un dato costo f(n).

L'equazione di ricorrenza del Mergesort è :

http://upload.wikimedia.org/math/6/b/2/6b2ec2916fd7e37481326ec8a72df4ac.png

Quindi due sottoproblemi di dimensione n/2 e a ogni livello paghi un costo theta di n , ovvero un costo pari alla dimensione del problema stesso.

Risolviamo con l'albero di ricorsione che, come hai detto te, altro non è che la visualizzazione sotto forma di albero del metodo iterativo (che sinceramente è molto scomodo e non si usa quasi mai).

http://digilander.libero.it/unno2/sort/merge_tree.gif

Quindi come vedi è molto facile costruire l'albero a partire dall'equazione. Metti semplicemente in ogni nodo la dimensione del problema a seconda del livello. Adesso:

Quanto è alto l'albero?

La prima cosa da fare per rispondere a questa domanda è capire con che "logica" si sviluppa la dimensione del tuo problema ed esprimerla in funzione dell'altezza.

Livello 0 -> dimensione n
livello 1-> dimensione n/2
livello 2 -> dimensione n/4
livello 3 -> dimensione n/8

e così via

Che legame c'è tra il livello e la dimensione? Se ci fai caso, al livello i-esimo il tuo problema ha sempre dimensione

http://operaez.net/mimetex/%5Cfrac%7Bn%7D%7B2%5Ei%7D

Trovare l'altezza dell'albero significa capire a che profondità stanno le foglie. Le foglie sono all'interno dell'albero di ricorsione dei nodi il cui problema ha dimensione 1.

Quindi se tu usi la regola generale che hai ricavato prima (in cui esprimevi la dimensione del problema in funzione del livello dell'albero), basta porre la formula che hai ricavato uguale ad 1 (perchè di fatto vuoi sapere quand'è che hai raggiunto la foglia).

http://operaez.net/mimetex/%5Cfrac%7Bn%7D%7B2%5Ei%7D=1

E risolvi l'equazione con i incognita. Se trovi quanto vale i per ottenere 1 trovi il livello delle foglie.

http://operaez.net/mimetex/2%5Ei%20=%20n

Da cui, usando la definizione di logaritmo ( i infatti è il numero a cui devi elevare 2 per ottenere n) ottieni:

http://operaez.net/mimetex/i%20=%20log%28n%29

Le foglie sono quindi al livello log(n)

Ora puoi procedere con i calcoli per capire il costo dell'albero.


La formula per trovare il costo dell'intero albero è:
COSTO TOTALE = COSTO NODI INTERNI + COSTO FOGLIE



COSTO NODI INTERNI

Il costo dei nodi interni è dato dal costo di tutti i nodi escluse le foglie che, come vedi dall'equazione di ricorrenza da te scritta, hanno costo O(1).

Ogni livello paghi O(dimensione dle problema) moltiplicato il numero dei nodi che hai in quel livello. Nel caso dell'equazione di ricorrenza del mergesort però i conti sono ancora più facili perchè se ci fai caso a ogni livello paghi theta di n.

Infatti al livello 0 paghi n.

Al livello 1 hai due nodi di dimensione (n/2), quindi paghi

http://operaez.net/mimetex/2%5Cfrac%7Bn%7D%7B2%7D

Al livello 2 paghi

http://operaez.net/mimetex/4%5Cfrac%7Bn%7D%7B4%7D

e così via ... fino a raggiungere le foglie (escluse).

Quante volte sommi O(n)? Tante quante l'altezza dell'albero -1, perchè escludi il livello delle foglie. Ma quanto è alto l'albero? L'hai calcolato prima, è alto log(n). Da qui la sommatoria:

http://operaez.net/mimetex/%5Csum_%7Bi=0%7D%5E%7Blog%28n%29-1%7D%5Ctheta%28n%29

il cui costo è http://operaez.net/mimetex/%5Ctheta%28nlogn%29

NOTA: Quì è facile risolvere la sommatoria, ma nel 99% dei casi non è così. Quasi sempore infatti escono fuori queste serie notevoli:

http://upload.wikimedia.org/math/f/f/b/ffb48a991daf5a551f5c80ac710fcd5a.png

che per valori |q|<1 vale http://upload.wikimedia.org/math/1/9/5/19509774dc9b660e6d9c01a2f6193cfe.png

Queste ( ed altre due o tre ) devi saperle come il padre nostro :D


COSTO FOGLIE
Il costo delle foglie è dato da O(1) moltiplicato il numero delle foglie.
Ma quante sono le foglie di questo albero?

Livello 0 --> 1 nodo
Livello 1 --> 2 nodi
livello 2 --> 4 nodi
livello 3 --> 8 nodi

La regola generale è : al livello i-esimo ho http://operaez.net/mimetex/2%5Ei nodi.

Però sai anche che le foglie sono al livello log(n). Quindi per scoprire quante foglie ha quest'albero basta usare la regola generale di prima per vedere che al livello log(n) hai

http://operaez.net/mimetex/2%5E%7Blog_2n%7D foglie.

(nei conti precedenti non ho mai scritto la base perchè è ininfluente ai fini del costo)

Esiste una regola matematica che ti permette di invertire la base con l'argomento del logaritmo qualora l'esponente si tratti appunto di un logaritmo.
http://operaez.net/mimetex/a%5E%7Blog_bc%7D%20=%20c%5E%7Blog_ba%7D%20=

Quindi ottieni:

http://operaez.net/mimetex/2%5E%7Blog_2n%7D%20=%20n%5E%7Blog_22%7D%20=%20n%5E1%20=%20n

Hai cioè n foglie, per un costo totale di
http://operaez.net/mimetex/O%281%29*n%20=%20O%28n%29


COSTO TOTALE

COSTO NODI INTERNI + COSTO FOGLIE

http://operaez.net/mimetex/%5Ctheta%28nlogn%29+O%28n%29%20=%20%5Ctheta%28nlogn%29

Abbiamo infatti una somma, e nlogn è sempre più grande di n (ragioni sempre con valori di n grandi).

Ecco che hai risolto.

[domenico88]

grazie mille ora mi è molto più chiaro...

quando ricavo la sommatoria

http://operaez.net/mimetex/%5Csum_%7Bi=0%7D%5E%7Blog%28n%29-1%7D%5Ctheta%28n%29

come faccio a ricavare O(nlogn)?

poi un'altra cosa....

Quando ho questa ricorrenza

Divido la struttura dati in due parti e applico la ricorsione su una sola delle due

t(n) = t(n/2) + O(n) Non la posso sviluppare con un albero di ricorsione??

Grazie cmq Gentilissimo:D

[:.Blizzard.:]

http://operaez.net/mimetex/%5Csum_%7Bi=0%7D%5E%7Blog%28n%29-1%7D%5Ctheta%28n%29

E' una sommatoria indipendente dall'indice i. Se la leggi è come se ci fosse scritto "somma n per logn volte". Cioè logn*n.



t(n) = t(n/2) + O(n) la sviluppi con l'albero di ricorsione esattamente come hai fatto per il merge. Però con l'unica differenza che invede di due nodi ne hai uno solo. Con questo esempio però i calcoli sono diversi, perchè non paghi più come nel merge theta di n per ogni livello (che ti usciva fuori sommando tutti i costi dei singoli nodi presenti sullo stesso livello).
In questo esempio infatti, per quanto riguarda i costi hai:

livello 0 --> costo n
livello 1 --> costo n/2
livello 2 --> costo n/4
livello 3 --> costo n/8

Sempre il solito "trucchetto". Quanto paghi per ogni livello? Che regola generale hai?

Ad ogni livello paghi http://operaez.net/mimetex/%5Cfrac%7Bn%7D%7B2%5Ei%7D

Se rifai i conti come hai fatto prima per studiare la profondità e tutto il resto, vedrai che anche qui l'albero ha altezza http://operaez.net/mimetex/log_2n. E quando calcoli il costo dei nodi interni avrai:

http://operaez.net/mimetex/%5Csum_%7Bi=0%7D%5E%7Blogn%20-1%7D%20%5Cfrac%7Bn%7D%7B2%5Ei%7D%20=%20%20%20%20n%5Csum_%7Bi=0%7D%5E%7Blogn%20-1%7D%20%5Cfrac%7B1%7D%7B2%5Ei%7D%20=%20n%5Csum_%7Bi=0%7D%5E%7Blogn%20-1%7D%20%7B%5Cfrac%7B1%7D%7B2%7D%7D%5Ei%20%5Cle%20n%5Csum_%7Bi=0%7D%5E%7B%5Cinfty%7D%20%7B%5Cfrac%7B1%7D%7B2%7D%7D%5Ei%20=%20n%5Cfrac%7B1%7D%7B1-1/2%7D%20=%20O%28n%29

Che è proprio la serie geometrica che ti ho scritto prima, con ragione |X| < 1 (in questo caso è 1/2).

http://upload.wikimedia.org/math/1/9/5/19509774dc9b660e6d9c01a2f6193cfe.png

e vale O(1) perchè hai comunque un numero, una costante dentro. Moltiplicato per n che hai portato fuori prima ottieni O(n).

Matematicamente , durante i passaggi che ti ho riportato qui sopra, ho usato il maggiore uguale perchè utilizzi una maggiorazione per riportare la serie che hai a serie notevole.