Pages: [1]   Go Down
Print
Author Topic: Testo prova in itinere 5/12/08  (Read 1230 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
KingDavid
Forumista
***
Offline Offline

Posts: 788


Alla fine [...] tutta la realtà è binaria.


« on: 06-12-2008, 12:00:38 »

ESERCIZIO 1
a)Si definisca la struttura dati dei B-Tree
b) Sia T l'insieme dei valori t €N per i quali l'albero T in figura
                                                 25         43
                                       5 19       31 37      51 57 63
possa essere considerato un B-Tree di grado minimo t e si ponga

m = min T, M= maxT

(b.1) Quanto valgono m ed M?  (Motivare la risposta.)
(b.2)Si illustri l'inserimento delle chiavi 55,53 e 54 in T, considerato come B-tree di grado minimo m.
(b.3) Si illustri la cancellazione delle chiavi 37, 43 e 57 da T, considerato come B-tree di grado minimo M.


ESERCIZIO 2
Dopo aver definito i concetti di sottosequenza di una sequenza data e di sottosequenza comune di due sequenze date, si enunci il problema della più lunga sottosequenza comune e si enunci per tale problema la proprietà della sottostruttura ottima.


ESERCIZIO 3
Sia G=(V,E) un grafo orientato, i cui nodi sono coppie (i,j), con i<=i,j <= n e i cui archi connettono il generico nodo (i, j) con i nodi (i,j+1),(i,j+2),...,(i,n) (se presenti) e con i nodi (i+1,j),(i+2,j),...,(n,j) (se presenti). Si supponga che il costo per passare dal nodo (i,j) ad un nodo (i,k) (con k > j) ad esso adiacente sia f1(i,j,k)  e quello per passare dal nodo (i, j) ad un nodo (k, j) (con k > i) si f2(i,j,k), dove f1 e f2 siano due funzioni date, calcolabili in tempo O(1).

a) Dopo aver verificato che il problema di determinare un percorso consentito di costo minimo dal nodo (1,1) al nodo (n,n) in G gode della proprietà della sottostruttura ottima, si descriva un algoritmo iterativo per il calcolo del costo di un siffatto cammino minimo e lo si analizzi dal punto di vista della complessità computazionale.

b)Si descriva come estendere il precedente algoritmo in modo da poter calcolare effettivamente un percorso di costo minimo in G dal nodo (1,1) al nodo (n,n).
« Last Edit: 06-12-2008, 12:24:43 by KingDavid » Logged

Basti pensare che un ipotetico quadrato di specchi, lungo 200 chilometri per ogni lato, potrebbe produrre tutta l'energia necessaria all'intero pianeta.
(Carlo Rubbia)
Pages: [1]   Go Up
Print
Jump to: