Forum Informatica Unict

Vecchi ordinamenti ad esaurimento => Algoritmi 2 => Topic started by: James on 19-02-2010, 18:03:37



Title: dubbio su esercizio
Post by: James on 19-02-2010, 18:03:37
Salve a tutti, ho un dubbio riguardante un esercizio dell'ultima prova d'esame

Al punto 'b' dell'esercizio 1 si chiede, di dimostrare che l'albero riportato in figura abbia grado minimo 3. In linea di massima io ho capito che l'albero ha grado minimo 3, in quanto:

- il nodo con più chiavi ha esattamente 2t-1=2*3-1=5 chiavi
- il nodo con meno chiavi ha esattamente t-1=3-1=2 chiavi

Ora mi chiedo, questa risposta basta a dimostrare che il grado minimo sia 3, oppure manca qualcos'altro?

Inoltre, al punto c, si chiede di determinare una minorazione e una maggiorazione dell'altezza h di un B-tree di grado minimo t contenente n chiavi. Per fare ciò, mi basterebbe dimostrare che:

- h<= f(n) per la maggiorazione
- h>=f(n) per la minorazione

oppure manca qualcos'altro?

Qui c'è il testo del compito: https://galileo.dmi.unict.it/utenti/beaver/alg2.jpg (https://galileo.dmi.unict.it/utenti/beaver/alg2.jpg) (uppato da beaver)

Grazie mille.


Title: Re:dubbio su esercizio
Post by: furiaceca on 03-03-2010, 19:44:40
per il grado minimo, in base a ciò che è stato fatto dal prof a lezione, dovrebbe calcolarsi così:
(M+1)/2 <= t <= m+1
dove M è il numero di chiavi massimo che un nodo possiede
ed m è il numero di chiavi minimo che un nodo possiede
quindi nell'esercizio diventa: (5+1)/2 <=t<= 2+1 quindi 3<=t<=3 cioè t=3.

Per quanto riguarda minorazione e maggiorazione ci sto studiando...tu hai saputo qualcosa?


Title: Re:dubbio su esercizio
Post by: James on 04-03-2010, 11:32:15
Ma non dovrebbe essere il contrario? Cioè (m+1)<= t <=(M+1)/2 ?
Per la maggiorazione e la minorazione non ho avuto nessuna notizia.
Ah, grazie per la risposta  .rido


Title: Re:dubbio su esercizio
Post by: furiaceca on 04-03-2010, 16:36:21
si si certo...cmq nn cambia la sostanza  :D