Compito A del 30-08-05. Domande teoria.
DOMANDA 1 (punti 6)
Effettuare, illustrando i vari passaggi necessari, la conversione del numero
0.75 in base 10 nella rappresentazione binaria floating point (virgola
mobile) su 32 bit (singola precisione).
DOMANDA 2 (punti 6)
Con riferimento allarchitettura di una macchina MIPS, illustrare e spiegare
il formato I delle istruzioni macchina. Fornire inoltre lesempio di almeno
tre diverse istruzioni macchina con tale formato.
DOMANDA 3 (punti 6)
Dimostrare che la complessità temporale (running time) dellalgoritmo di
Kruskal per la costruzione di un minimum spanning tree di un grafo non
orientato, connesso, pesato, con n vertici e m archi è pari a
O( (n + m) log n ). Prima di iniziare la dimostrazione specificare le
implementazioni supposte per tutte le strutture dati (grafo, coda con
priorità, etc.) utilizzate dallalgoritmo.
DOMANDA 4 (punti 6)
Supposto G un grafo semplice con n vertici e m archi, dire quale relazione
in generale intercorre tra m e n nei casi in cui: (i) G sia non orientato, (ii)
G sia orientato. Fornire la dimostrazione di ciascuna delle due relazioni
indicate.
DOMANDA 5 (punti 6)
Illustrare graficamente, spiegando
dettagliatamente l'algoritmo nei suoi vari passaggi e ridisegnando di volta
in volta l'albero, la rimozione del valore 55 nell'albero Binario di Ricerca
di seguito riportato.
