Compito A del 16-03-04.  Domande  teoria. 

DOMANDA 1  (punti 6)  
Definire il principio di località temporale dei riferimenti, e discuterne le implicazioni nel progetto di un sistema di memoria dotato di cache.

DOMANDA 2  (punti 6) 
Scrivere la tabella di verità (3 ingressi e 2 uscite) di un sommatore ad un bit (full adder). Scrivere un'espressione booleana che  realizzi l'uscita CarryOut.

DOMANDA 3  (punti 6)  
Scrivere il pseudocodice dell’algoritmo BFS(G, s) per l’attraversamento in ampiezza del grafo orientato G, a partire dal vertice s. Dimostrare che la complessità dell’algoritmo è O(n + m), con n numero dei vertici e m numero degli archi di G.

DOMANDA 4  (punti 6) 
Dimostrare che l’algoritmo BFS(G, s) per l’attraversamento in ampiezza del grafo orientato G a partire dal vertice s visita tutti i vertici raggiungibili da s.

DOMANDA 5  (punti 6) 
Illustrare graficamente, spiegando i vari passaggi, l’inserimento del valore 39 (prima) e del valore 73 (dopo) nell’albero AVL di seguito riportato.

Compito B del 16-03-04.  Domande  teoria. 

DOMANDA 1  (punti 6) 
Definire il principio di località spaziale dei riferimenti, e discuterne le implicazioni nel progetto di un sistema di memoria dotato di cache.

DOMANDA 2  (punti 6)
Scrivere la tabella di verità (3 ingressi e 2 uscite) di un sommatore ad un bit (full adder). Scrivere un'espressione booleana che realizza l'uscita Somma.

DOMANDA 3  (punti 6) 
Scrivere il pseudocodice dell’algoritmo DFS(G, s) per l’attraversamento in profondità del grafo non orientato G, a partire dal vertice s. Dimostrare che la complessità dell’algoritmo è O(n + m), con n numero dei vertici e m numero degli archi di G.

DOMANDA 4  (punti 6) 
Dimostrare che l’algoritmo DFS(G, s) per l’attraversamento in ampiezza del grafo non orientato G a partire dal vertice s visita tutti i vertici raggiungibili da s.

DOMANDA 5  (punti 6)
Illustrare graficamente, spiegando i vari passaggi, l’inserimento del valore 47 (prima) e del valore 11 (dopo) nell’albero AVL di seguito riportato.

Compito C  del 16-03-04.  Domande  teoria. 

DOMANDA 1  (punti 6)  
Definire i vari livelli della gerarchia di memoria e discuterne brevemente le caratteristiche.

DOMANDA 2  (punti 6) 
Disegnare la parte di circuito per la generazione del segnale CarryOut in un sommatore ad un bit (full adder).

DOMANDA 3  (punti 6)
Scrivere il pseudocodice dell’algoritmo DFS(G, s) per l’attraversamento in profondità del grafo orientato G, a partire dal vertice s. Dimostrare che la complessità dell’algoritmo è O(n + m), con n numero dei vertici e m numero degli archi di G.

DOMANDA 4  (punti 6)
Dimostrare che se un grafo orientato G=(V,E) ha un ordinamento topologico, allora è aciclico.

DOMANDA 5  (punti 6) 
Illustrare graficamente, spiegando i vari passaggi, l’inserimento del valore 44 (prima) e del valore 42 (dopo) nell’albero AVL di seguito riportato.