Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Algoritmi, 9 CFU => Topic started by: cristina89 on 17-12-2012, 15:53:43



Title: come si dimostra il numero massimo di nodi ad altezza h?
Post by: cristina89 on 17-12-2012, 15:53:43
Ciao ragazzi,nella domanda dell'esame di oggi,c'era "in un heap,qual ê il numero massimo di nodi ad altezza h"  io ho  risp  n/2^(h+1)),che come soluzione ê giusta,ma non  so come si dimostra.qualcuno puó aiutarmi??!! Grazieee


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: nairi on 18-12-2012, 08:13:14
Ciao!!!! io nei miei appunti ho questa dimostrazione (confermata anche da alcun fonti su internet) :

Parte con la seguente domanda (sta considerando una min heap dei nodi : 1,2,4,3,6,7,8,5):
quanti sono i nodi ad altezza h?

n/2h+1   (il ceiling)

il lavoro è al più O(h) per i nodi a livello h, i livelli sonon da 0 a logn  , dunque ottengo:

SOMMATORIA(h=0 fino longn) ((n/2h+1) O(h)) =

=O (SOMMATORIA(h=0 fino longn) ((n/2h+1) h)=

Togliamo la notazione O grade:

=  n (SOMMATORIA(h=0 fino longn) (h/2h+1))

 il +1 dell'esponente del 2 si può non considerare ottenendo (e per ora la n esterna la lasciamo da parte per risolvere la sommatoria:


(SOMMATORIA(h=0 fino longn)(h/2h))    che è nella forma nota delle serie risolte nel libro a pag 954 Appendice a sotto la voce : Integrazione e differenzazione dellle serie , risultando quindi 2 .

Quindi la sommatoria ha somma 2 * n che avevamo lasciato fuori da parte= theta (n)   LINEARE :)


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: nairi on 18-12-2012, 08:17:41
 Cristina89,mi sai dire le risp corrette alle domande 13, 14  e 15  del compito?

Non ho capito come si può ottenere un UNICO ordinamento topologico
Non so se formandosi un ciclo posso percorrerlo più volte da soddisfare più di una condizione della domanda 
Non so il numero di confronti necessari per ordinare e fondere 4 array di lunghezza n...


Mi puoi dire come hai capito le risp? nel libro non trovo nulla :( ...

Grazie!!!!


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: cristina89 on 18-12-2012, 09:05:34
ciao, riguardo la dimostrazione che mi hai scritto tu,io ho anche quell'esempio,che si usa per dimostrare la complessità della costruzione di una heap però,non per dimostrare perchè il numero massimo di nodi ad altezza h è n/(2)^h+1..anche nel libro fà lo stesso ragionamento...cmq io ho risposto alla 13 la a,cioè esiste almeno un ciclo di lunghezza 2,perchè basta che disegni le due componenti connesse,formate da 5 nodi in tutto,ti accorgi di avere due/o più cicli,in base a come le disegni (non so come spiegartelo bene qui)..poi alla 14 io ho risposto la a perchè non avevo letto "unico" ma la risposta giusta secondo me è la d,poichè il mio grafo non solo deve essere aciclico per poter fare un ordinamento topologico,ma deve essere anche fortemente connesso(cioè esiste un arco per ogni coppia di vertici),per potermi garantire che dopo la visita DFS quando estraggo i vari vertici,mi dia un solo ordinamento (se non fosse fortemente connesso,io potrei avere dopo la visita DFS,uno o piu ordinamenti,in base a come imposto il mio grafo)..non so se riesco a spiegarmi  .huh  poi alla 15 ho risposto d,ho ragionato facendo il MergeSort dei primi due array gia ordinati e quindi hanno complessità O(2n) + mergesort degli ultimi due array=O(2n) e poi ho unito i due array finali..=O(4n),non so se sia giusto il mio ragionamento,anche perche non mi convince il "scegliere la risposta piu stretta"  ..spero di esserti stata utile  .smile


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: nairi on 18-12-2012, 09:28:12
ma se esiste per ogni coppia di nodi un arco si forma il ciclo che contraddice l'ipotesi del grafo aciclico... quindi solo per esclusione punterei alla b) ma non l'ho capita proprio...il cervello si rifiuta  :-)| !!!!!!
Se ho inteso bene le parole, prova questo grafo:

 A-->B--->C--->D--->A 

 così qualunque coppia di nodi ha un solo arco ma forma il ciclo! se togli D--->A hai l'aciclicità ma non soddisfi la condizione "per ogni coppia" perchè la coppia di nodi A-D non ha archi!

Per la 13 se è vera la a) allora la d) è vera pure! l'ho scelta per questo :p ... mah....

Per la 15 mi pare troppo .... ma resta il dubbio di come calcolarlo!!!! io ho fatto questo ragionamento:
Ho preso l'es a lezione di fondere le k liste cn complessità tot nlogk .... 
avendo 4 liste ho fatto nlog4=2n  :boh


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: Andrea2990 on 18-12-2012, 09:50:10
A mio parere, la risposta esatta alla domanda 13 è la d, in quanto se abbiamo 5 vertici e 2 componenti connesse si possono verificare i seguenti casi:

CASO 1: 2 cicli, uno di 2 vertici, l'altro di 3. I due cicli sono due componenti fortemente connesse.
____        _____
|      |       |         |
n     n-----n        n
|      |       |         |
------         ---n---

CASO 2: 1 vertice (prima componente connessa) e un ciclo di 4 vertici (seconda componente connessa).

___n___
|            |
n           n----n
|            |
-----n-----

Spero che si capisca qualcosa dai disegni.
Quindi possiamo avere 2 componenti connesse con 5 vertici con cicli di 2, di 3 o di 4 vertici.
Almeno, credo.


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: nairi on 18-12-2012, 10:21:46
ok!!!! mi hai confermato quello che pensavo!!!!! cmq per le altre cosa pensi? *.*


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: Il Capitano on 18-12-2012, 10:38:14
Ciao ragazzi. alla prima cosa avete messo?


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: nairi on 18-12-2012, 10:41:06
la b)


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: Il Capitano on 18-12-2012, 10:42:46
la b)
Mi sai dire i calcoli fatti? Grazie


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: Andrea2990 on 18-12-2012, 11:19:54
La 14 dovrebbe essere la d, poiché, dagli appunti:
Quote
I grafi aciclici godono della proprietà che un vertice rappresenta un processo e gli archi rappresentano i prerequisiti. Questo modo di serializzare i dati è detto ordinamento topologico. L'ordinamento topologico è un ordinamento tale che per ogni arco uv il vertice u precede il vertice v; il grafo deve essere necessariamente orientato e aciclico. Tali grafi sono utili per indicare le precedenze tra gli eventi.


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: nairi on 18-12-2012, 12:11:42
ok, ma ho trovato diversi esempi (su internet) per cui avendo un grafo con le proprietà descritte nella sol  c)  ci sono diversi ordinamenti topologici!!!!!
Anche dai tuoi appunti non è specificato unico, quindi per me resta sempre l'incertezza! :(


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: nairi on 18-12-2012, 12:15:21
la b)
Mi sai dire i calcoli fatti? Grazie

Devi usare le notazioni theta,omega piccolo,omega grande, o piccolo e o grande.
in particolare ti saranno utili i lim della notazione o piccolo e omega piccolo!!!

se hai il libro vedi pag 44 del cap 3 crescita delle funzioni.


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: milos224 on 18-12-2012, 12:31:44
Ragazzi per i due nodi rossi? Che ragionamento avete fatto?


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: Raro89 on 18-12-2012, 12:44:20
Ragazzi per i due nodi rossi? Che ragionamento avete fatto?


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: equivoco on 18-12-2012, 12:48:03
non sono sicuro che non ho fatto errori, ma ho preso l'insert di un albero rosso nero, e su carta ho creato l'albero scorrendo il codice passo passo alla fine mi restano 2 nodi rossi


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: milos224 on 18-12-2012, 13:16:46
ma se esiste per ogni coppia di nodi un arco si forma il ciclo che contraddice l'ipotesi del grafo aciclico... quindi solo per esclusione punterei alla b) ma non l'ho capita proprio...il cervello si rifiuta  :-)| !!!!!!
Se ho inteso bene le parole, prova questo grafo:

 A-->B--->C--->D--->A 

 così qualunque coppia di nodi ha un solo arco ma forma il ciclo! se togli D--->A hai l'aciclicità ma non soddisfi la condizione "per ogni coppia" perchè la coppia di nodi A-D non ha archi!

Per la 13 se è vera la a) allora la d) è vera pure! l'ho scelta per questo :p ... mah....

Per la 15 mi pare troppo .... ma resta il dubbio di come calcolarlo!!!! io ho fatto questo ragionamento:
Ho preso l'es a lezione di fondere le k liste cn complessità tot nlogk .... 
avendo 4 liste ho fatto nlog4=2n  :boh
Potresti postare questo esempio fatto a lezione?


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: Andrea2990 on 18-12-2012, 13:20:03
2 nodi rossi anche a me, bastava inserire come nei classici alberi binari di ricerca e aggiustare di volta i colori dei nodi secondo le varie regole e i vari casi. Insomma, InsertFixUp.


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: Il Capitano on 18-12-2012, 14:55:33
2 nodi rossi anche a me, bastava inserire come nei classici alberi binari di ricerca e aggiustare di volta i colori dei nodi secondo le varie regole e i vari casi. Insomma, InsertFixUp.

Io ho inserito cosi:

                               1
                      3              5
                 2        4

Non dovrebbe essere soltanto il 3 il nodo rosso? Perchè la radice è nera e le foglie (2,4,5) pure...


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: TheSpecialOne on 18-12-2012, 15:00:32
2 nodi rossi anche a me, bastava inserire come nei classici alberi binari di ricerca e aggiustare di volta i colori dei nodi secondo le varie regole e i vari casi. Insomma, InsertFixUp.

Io ho inserito cosi:

                               1
                      3              5
                 2        4

Non dovrebbe essere soltanto il 3 il nodo rosso? Perchè la radice è nera e le foglie (2,4,5) pure...

Anche io ho fatto questo ragionamento..


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: equivoco on 18-12-2012, 15:07:34
ci sono le rotazioni


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: milos224 on 18-12-2012, 15:09:57
si ci sono le rotazioni.. comunque domanda numero 8? è la c?


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: nairi on 18-12-2012, 15:18:26

Non dovrebbe essere soltanto il 3 il nodo rosso? Perchè la radice è nera e le foglie (2,4,5) pure...

Raga ma le foglie sono I NIL !!!!!!!!!!!!!!!!!!!!

 Quindi secondo me sono 2 i nodi rossi ma non ne ho la certezza assoluta!!!! Pensate anche alla b-altezza e quindi alla 5° proprietà!
 


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: Raro89 on 18-12-2012, 15:26:29
Ho cercato di capire meglio al domanda inserendo i nodi ad uno ad uno seguendo l'ordine dato e ovviamente facendo le opportune rotazioni,  il risultato è stato questo grafo:

                     3
               2           5
          1             4

con 2 nodi rossi (2,5) e 2 nodi neri(1,4) più ovviamente la radice ed i nodi NIL


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: Andrea2990 on 18-12-2012, 15:38:59
Quote
si ci sono le rotazioni.. comunque domanda numero 8? è la c?
Qualcuno lo sa?


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: milos224 on 18-12-2012, 15:45:33
Quote
si ci sono le rotazioni.. comunque domanda numero 8? è la c?
Qualcuno lo sa?
Anche tu nel dubbio vero Andrea? :D


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: Raro89 on 18-12-2012, 15:46:39
dalle slide del prof, capitolo 9-slide 17, sembra intuirsi sia la c,
perchè dice che il tempo totale per ordinare i 5 gruppi per ceeling(n/5) è cn...
poi non so forse sbaglio io nell'interpretare la domanda e relativa spiegazione delle slide


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: milos224 on 18-12-2012, 15:48:32
dalle slide del prof, capitolo 9-slide 17, sembra intuirsi sia la c,
perchè dice che il tempo totale per ordinare i 5 gruppi per ceeling(n/5) è cn...
poi non so forse sbaglio io nell'interpretare la domanda e relativa spiegazione delle slide
nelle slide del prof c'è il select?


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: Raro89 on 18-12-2012, 15:49:13
il tempo totale per ordinare i 5 gruppi per ceeling(n/5)

scusate mi sono spiegato male, dice che il tempo per ordinare i 5 elementi del gruppo deve essere ripetuto per tutti i gruppi, ovvero ceeling (n/5) volte


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: equivoco on 18-12-2012, 15:50:52
secondo me il tempo per ordinare il gruppi è O(1) esattamente 7 confronti e quindi la risposta è c


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: milos224 on 18-12-2012, 15:52:31
qualcuno potrebbe mandarmi via mail in formato zip tutte le slide del prof? a quanto vedo non si sono solo quelle sul suo sito.. o sbaglio?


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: Raro89 on 18-12-2012, 15:57:31
ti posso passare quelle che ho io, ma premetto che sono un pò vecchiotte perchè a me le hanno passate quanto do seguito il corso, non so se ora ha aggiunto cose o tolte delle altre...mandami la tua e-mail che te le mando


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: cristina89 on 18-12-2012, 16:04:04
Scusa raro89 potresti farmi tt i passaggi per quanto riguarda l albero?


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: Raro89 on 18-12-2012, 16:14:27
allora, prima inserisci il nodo 1(nero)

         
poi dovrai inserire il nodo 3 (rosso)            1
                                                                   3
a questo punto inserisci il 5 (nero)

                       1
                              3
                                    5

ti ritrovi in questa situazione, e già si deve fare la prima rotazione facendo diventare 3 radice

                    3
               1          5

che sara (nera) il nodo 1(rosso) e il nodo 5(nero)

inserisci il 2 , che andrà a prendere il posto e quindi colore del nodo 1
                         3
                    2        5
                1
il nodo 1 diventa nero, a questo punto inserisci il nodo 4(nero)

                      3
               2          5
          1            4

si colora di rosso il nodo 5 che era nero e ci sono 2 nodi rossi...
ma non sono tanto sicuro del mio ragionamento, ho ritenuto però fosse quello più sensato da fare, possibilmente mi sbaglio


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: milos224 on 18-12-2012, 16:17:55
ti posso passare quelle che ho io, ma premetto che sono un pò vecchiotte perchè a me le hanno passate quanto do seguito il corso, non so se ora ha aggiunto cose o tolte delle altre...mandami la tua e-mail che te le mando
mail mandata in privato :)


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: cristina89 on 18-12-2012, 16:28:59
Guarda che nn so se sia giusto che o meno perché alcune rotazioni nn mi convincono, nel codice di libro mi risultano diverse, poi, non so, mi sto confondendo troppo .huh


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: Raro89 on 18-12-2012, 16:32:45
per essere sicuri aspettiamo la risposta di qualche ragazzo/a che sa la soluzione con certezza...
ti ripeto neanche io sono sicuro al 100%, è un mio personale ragionamento...


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: cristina89 on 18-12-2012, 16:38:38
Sì certo figurati  .arrossisco


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: Andrea2990 on 18-12-2012, 18:00:25
Quote
Non ho ancora finito la correzione. Vi anticipo intanto che inizio gli orali domani alle 10:00. Faremo orali anche giovedì mattina se necessario. In nottata o domattina prima delle 10:00 (ovviamente) pubblicherò i risultati.
Per chi non avesse letto.


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: milos224 on 18-12-2012, 19:04:18
ragazzi qualcuno che spieghi in breve la prima domanda? so che è facile, per cui per non avere dubbi all'orale chiedo..


Title: Re:come si dimostra il numero massimo di nodi ad altezza h?
Post by: Il Capitano on 18-12-2012, 19:07:16
ragazzi qualcuno che spieghi in breve la prima domanda? so che è facile, per cui per non avere dubbi all'orale chiedo..
.quoto