Pages: [1] 2 3   Go Down
Print
Author Topic: come si dimostra il numero massimo di nodi ad altezza h?  (Read 7724 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
cristina89
Matricola
*
Offline Offline

Posts: 42


« 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
Logged
nairi
Apprendista Forumista
**
Offline Offline

Posts: 185



« Reply #1 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 Smiley
Logged
nairi
Apprendista Forumista
**
Offline Offline

Posts: 185



« Reply #2 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 Sad ...

Grazie!!!!
Logged
cristina89
Matricola
*
Offline Offline

Posts: 42


« Reply #3 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    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 
Logged
nairi
Apprendista Forumista
**
Offline Offline

Posts: 185



« Reply #4 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  testate !!!!!!
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
Logged
Andrea2990
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 235



WWW
« Reply #5 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.
« Last Edit: 18-12-2012, 09:58:32 by Andrea2990 » Logged
nairi
Apprendista Forumista
**
Offline Offline

Posts: 185



« Reply #6 on: 18-12-2012, 10:21:46 »

ok!!!! mi hai confermato quello che pensavo!!!!! cmq per le altre cosa pensi? *.*
Logged
Il Capitano
Apprendista Forumista
**
Offline Offline

Posts: 409


« Reply #7 on: 18-12-2012, 10:38:14 »

Ciao ragazzi. alla prima cosa avete messo?
Logged
nairi
Apprendista Forumista
**
Offline Offline

Posts: 185



« Reply #8 on: 18-12-2012, 10:41:06 »

la b)
Logged
Il Capitano
Apprendista Forumista
**
Offline Offline

Posts: 409


« Reply #9 on: 18-12-2012, 10:42:46 »

la b)
Mi sai dire i calcoli fatti? Grazie
Logged
Andrea2990
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 235



WWW
« Reply #10 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.
Logged
nairi
Apprendista Forumista
**
Offline Offline

Posts: 185



« Reply #11 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! Sad
Logged
nairi
Apprendista Forumista
**
Offline Offline

Posts: 185



« Reply #12 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.
Logged
milos224
Forumista
***
Offline Offline

Posts: 830


« Reply #13 on: 18-12-2012, 12:31:44 »

Ragazzi per i due nodi rossi? Che ragionamento avete fatto?
Logged
Raro89
Apprendista Forumista
**
Offline Offline

Posts: 121



« Reply #14 on: 18-12-2012, 12:44:20 »

Ragazzi per i due nodi rossi? Che ragionamento avete fatto?
Logged
Pages: [1] 2 3   Go Up
Print
Jump to: