Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Algoritmi, 9 CFU => Topic started by: Daréios89 on 28-07-2011, 14:23:37



Title: Algoritmo Max-Heapify
Post by: Daréios89 on 28-07-2011, 14:23:37
Nel codice, in particole tra gli appunti del professore è specificato che l' algoritmo viene eseguito a partire da un nodo j e supponendo che i sottoalberi di destra e sinistra siano Max-Heap, ma allora a cosa serve?
L' algoritmo dovrebbe servire a garantire la proprietà di una Max-Heap, ma se io suppongo che al di sotto ho una max-heap, allora il codice sarà eseguito solo una volta?


Title: Re:Algoritmo Max-Heapify
Post by: cock86 on 28-07-2011, 15:04:50
no perché dopo che esegui max-heapify nel primo nodo potresti aver violato la proprietà di max-heap di uno degli alberi sottostanti, e allora dovresti procedere in quello e scendere fino dove è necessario per ripristinare la proprietà.


Title: Re:Algoritmo Max-Heapify
Post by: Daréios89 on 28-07-2011, 16:11:30
Quindi io ho ad esempio:

                                 10
                               /     \
                            7        8
                          /  \      /  \
                       11    6  ...   ....
                      .........


Io parto dal nodo che ha come elemento 7, scambio 11 con il 7 e poi se l' albero avesse un' altezza maggiore allora continuerei sulla foglia a sinistra che in questo caso coincide con il nodo dove metterò 7?


Title: Re:Algoritmo Max-Heapify
Post by: cock86 on 28-07-2011, 16:14:12
praticamente si. Andrai a controllare il 7 ancora con le radici dei sotto alberi sottostanti. In modo da fargli trovare la sua posizione.


Title: Re:Algoritmo Max-Heapify
Post by: Daréios89 on 28-07-2011, 16:22:45
Ti ringrazio, una piccola cosa off-topic, stavo facendo questa ricorrenza:

T(n)=2T(n/2)+n/\log(n)

Mi blocco.....ho sostituito n=2^m

T(2^m)=2T(2^m/2)+2^m/\log(2^m)

Ho pensato di porre S(m)=T(2^m)

S(m)=2S(m/2)+2^m/\log(2^m)

Ma mi sa che non funziona, o sbaglio o conviene fare qualcos' altro....


Title: Re:Algoritmo Max-Heapify
Post by: cock86 on 28-07-2011, 16:43:53
non faccio ste cose da un bel pò (ho dato questa materia un paio di anni fa). Comunque la prima sostituzione può andare, se semplifichi il costo esterno credo che possa aiutarti per la seconda sostituzione.
log(2^m)= m
e quindi il costo esterno :
\frac{2^m}{m}

Però dovrei ragionarci un pò.


Title: Re:Algoritmo Max-Heapify
Post by: cock86 on 28-07-2011, 16:46:10
Ah dimenticavo... quel tipo di sostituzione se non ricordo male va fatta proprio per eliminarsi di torno la divisione per un logaritmo.


Title: Re:Algoritmo Max-Heapify
Post by: corel_86 on 03-08-2011, 22:55:19
Per prima cosa guarda le slide qui (http://www.dmi.unict.it/~cutello/ricorrenza.pdf) cosi capirai i passaggi

Dobbiamo trasformare la ricorrenza in modo da poter applicare il Telescoping

T(n)=2T(n/2)+n/\log(n)
            |        |
            |        |
             a       b

1) pongo n=2^mquindi   m=\log_2(n) in generale n=b^mquindi   m=\log_b(n)

sostituisco e ottengo

T(2^m)=2T(2^{m-1})+\frac{2^m}{\log(2^m)} cioè

T(2^m)=2T(2^{m-1})+\frac{2^m}{m}

2) pongo S(m)=T(2^m)

e sostituendo ottengo

S(m)=2S(m-1)+\frac{2^m}{m}

3) pongo R(m)=S(m)/2^m in generale R(m)=S(m)/a^m

e sostituendo ottengo

R(m)=R(m-1)+\frac{1}{m}

4) Adesso applichiamo il Telescoping che troverai sulle slide e il risultato finale sarà

T(n)=2^m\sum_{i=1}^{m} 1/i

5) sostituendo m si ottiene

T(n)=n \sum_{i=1}^{\log_2n} 1/i

approssimando la sommatoria in \log_2n (Serie armonica)

otteniamo che T(n)=\theta (n\log_2\log_2n)

i passaggi dovrebbero essere giusti


Title: Re:Algoritmo Max-Heapify
Post by: Daréios89 on 03-08-2011, 23:16:46
Scusa una cosa non mi quadra al passaggio 3, quel 2S(m-1), come mai scompare il 2? Per le potenze non diventa 2^{1-m}?


Title: Re:Algoritmo Max-Heapify
Post by: corel_86 on 03-08-2011, 23:20:10
se ti guardi le slide capirai il perchè soprattutto l'esempio


Title: Re:Algoritmo Max-Heapify
Post by: Daréios89 on 04-08-2011, 20:46:13
Mh, non trovo quello che mi serve, a che pagina ti riferisci? A me non quadra quel passaggio  .whistling


Title: Re:Algoritmo Max-Heapify
Post by: corel_86 on 04-08-2011, 21:20:26
pagina 13 puoi constatare che risulta R(m)=R(m-1) +\frac{f(b^m)}{a^m}

il termine a dall'equazione di ricorrenza non c'è più


Title: Re:Algoritmo Max-Heapify
Post by: Daréios89 on 04-08-2011, 21:49:21
Si, giusto, ma non capisco come fa a sparire, dalle proprietà delle potenze mi risulta un' altra cosa......non può scomparire semplicemente così.....se al denominatore nella ricorrenza venisse 2^{m-1} allora siamo d' accordo, ma viene con gli esponenti esattamente al contrario.. .penso


Title: Re:Algoritmo Max-Heapify
Post by: corel_86 on 04-08-2011, 22:17:23
forse dipende dal fatto che c'è S(m-1)
anzichè S(m)

considera che verrebbe in questo modo
R(m)=\frac{S(m)}{a^m} quindi S(m)=R(m) a^m

sostituendo si ottiene

R(m) a^m=a R(m-1) a^{m-1} +f(b^m)

dividendo tutto per a^m si ha

R(m)= R(m-1)+\frac{f(b^m)}{a^m}

penso che sia cosi



Title: Re:Algoritmo Max-Heapify
Post by: Daréios89 on 04-08-2011, 22:24:39
Non mi convince....comunque non mi resta che prenderla per buona.... :boh


Title: Re:Algoritmo Max-Heapify
Post by: corel_86 on 04-08-2011, 22:29:56
invece penso proprio che è come ho detto io, innanzitutto perchè al posto di m sto mettendo m-1 quindi verrebbe cosi

R(m) a^m=a R(m-1) a^{m-1} +f(b^m)

e per la proprietà delle potenze ottengo

R(m) a^m=R(m-1) a^{m} +f(b^m)

e infine dividendo tutto per a^m si ha

R(m)= R(m-1)+\frac{f(b^m)}{a^m}



Title: Re:Algoritmo Max-Heapify
Post by: Daréios89 on 04-08-2011, 22:53:40
Si ho risposto mentre editavi  .rido
Si ora ci siamo, c' è questo piccolo cambiamento che per me era nascosto, ora funziona, ti ringrazio.  .smile

P.S Fare ricorrenze alle 23.53?
ROBA DA INFORMATICI  :-)|


Title: Re:Algoritmo Max-Heapify
Post by: corel_86 on 04-08-2011, 23:53:11
Si ho risposto mentre editavi  .rido
Si ora ci siamo, c' è questo piccolo cambiamento che per me era nascosto, ora funziona, ti ringrazio.  .smile

P.S Fare ricorrenze alle 23.53?
ROBA DA INFORMATICI  :-)|

 .quoto .quoto

comunque lieto di esserti stato di aiuto.......


Title: Re:Algoritmo Max-Heapify
Post by: Daréios89 on 23-08-2011, 14:12:00
EDIT: Ho sbagliato intervento  :boh