Pages: [1]   Go Down
Print
Author Topic: dubbio su esercizio  (Read 1367 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
James
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 209



« 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 (uppato da beaver)

Grazie mille.
Logged

Whatever people say i am, that's what i'm not
furiaceca
Apprendista Forumista
**
Offline Offline

Posts: 148


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

Gender: Male
Posts: 209



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

Whatever people say i am, that's what i'm not
furiaceca
Apprendista Forumista
**
Offline Offline

Posts: 148


« Reply #3 on: 04-03-2010, 16:36:21 »

si si certo...cmq nn cambia la sostanza  Cheesy
Logged
Pages: [1]   Go Up
Print
Jump to: