Fac Simile A

Seconda Provetta

ASD1 2002-2003

Esercizio 1   Sia $B_k$ un albero binomiale. Dimostrare le seguenti proprietà. Specificare inoltre quale delle seguenti proprietà sia leggermente imprecisa ed indicare perchè.

1.

i nodi di $B_k$ sono $2^k$;

2.

l'altezza di $B_k$ è $k$;

3.

i nodi di $B_k$ sono $2^k$;

4.

la radice dell'albero ha grado $k$;

5.

la radice dell'albero ha grado maggiore di ogni altro nodo;

6.

siano $v_{k-1}, v_k, \ldots, v_0$ i figli della radice come numerati da sinistra verso destra, allora il sottoalbero di $B_k$ radicato in $v_i$ è un albero binomiale $B_i$.

Esercizio 2   Con riferimento al precedente esercizio, sapresti specificare in quale delle seguenti operazione viene utilizzata in modo cruciale la Proprietà 6: Union, Crea, Inserisci, UccidiMinimo, TrovaMinimo, DecrementaChiave. Sapresti dare uno pseudocodice od una descrizione comunque efficace e formale dell'operazione da te individuata?

Esercizio 3   Dare uno pseudocodice per una BFS, dove i nodi siano colorati bianco, grigio e nero, come visto in classe. Dimostrare poi le seguenti invarianti:

1.

ad ogni iterazione, ad uno specifico passo della tua procedura da te indicato, puoi affermare che i nodi grigi sono tutti e soli i nodi nella coda;

2.

i valori di $d(v)$ per i nodi presenti nella coda sono monotoni non decrescenti.

Suggerimento: Per dimostrare la correttezza dell'Invariante 2 ti converrà considerarne un rafforzamento.

Esercizio 4   Con riferimento al precedente esercizio, sapresti dimostrare che la tua BFS costruisce un albero di cammini minimi?