Next: About this document ...
Fac Simile A
Seconda Provetta
ASD1 2002-2003
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 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?
Next: About this document ...
Romeo Rizzi
2002-10-30