Esercizio 1 (15 punti)

Prova scritta del 7 febbraio 2019 di Fondamenti di Informatica II (prof. Di Gaspero) Per studenti di Ing. Gestionale immatricolati negli anni accademici 2016-17 e precedenti DURATA DELLA PROVA: 2 ORE

A pena di annullamento immediato della prova:

1) Non è possibile consultare libri o appunti (in qualunque forma) né utilizzare calcolatrici, telefoni cellulari, ecc.

2) Non è consentito comunicare (con qualunque mezzo) 3) Non è consentito uscire dall’aula

Esercizio 1 (15 punti)

Una matrice quadrata 𝐴 di valori reali di ordine 𝑛 (cioè con 𝑛 righe e 𝑛 colonne) è detta tridiagonale quando gli unici valori diversi da zero presenti nella matrice stessa possono trovarsi sulla diagonale principale (gli elementi 𝑎

con 𝑖 == 𝑗) oppure sulle “linee” immediatamente al di sopra (𝑎

con 𝑖 = 𝑗 − 1, detta sovradiagonale) e al di sotto di essa (𝑎

con 𝑖 = 𝑗 + 1, detta sottodiagonale). Gli elementi potenzialmente non nulli di una matrice tridiagonale sono 3𝑛 − 2 e sono, dunque, quelli per i quali vale la proprietà |𝑖 − 𝑗| ≤ 1. Si vedano i seguenti esempi (per inciso, 𝐶 = 𝐴 ⋅ 𝐵):

𝐴 = 3

4.5 0.3 0.0 0.0 0.5 0.4 1.8 0.0 0.0 0.2 3.6 4.9 0.0 0.0 2.1 3.4

; 𝐵 = 3

2.5 0.6 0.0 0.0 1.4 3.8 0.4 0.0 0.0 1.3 0.1 4.9 0.0 0.0 0.8 1.6

; 𝐶 = 3

11.25 0.018 0.0 0.0

0.07 1.52 0.072 0.0 0.0 0.026 0.036 24.01

0.0 0.0 1.68 5.44

;

Un modo compatto per rappresentare una matrice tridiagonale è attraverso una sequenza di 3𝑛 − 2 valori 𝑠

che corrispondono agli elementi delle tre diagonali, memorizzando, nell’ordine, prima tutti gli 𝑛 − 1 elementi della sottodiagonale, di seguito gli 𝑛 elementi della diagonale principale, infine gli 𝑛 − 1 elementi della sovradiagonale. Ad esempio, la matrice 𝐴 riportata in precedenza può essere rappresentata dalla seguente sequenza 0.5, 0.2, 2.1, 4.5, 0.4, 3.6, 3.4, 0.3, 1.8, 4.9.

Con questo ordinamento degli elementi della matrice, la funzione 𝜙(𝑖, 𝑗) che fa corrispondere l’elemento 𝑎

della matrice originale con l’elemento 𝑠

della sequenza è definita nel modo seguente:

𝜙(𝑖, 𝑗) = E

𝑖 − 1 se 𝑖 = 𝑗 + 1

𝑛 − 1 + 𝑖 se 𝑖 = 𝑗 2𝑛 − 1 + 𝑖 se 𝑖 = 𝑗 − 1

La funzione di codifica, verifica se l’elemento 𝑎

si trova sulla sottodiagonale (𝑖 = 𝑗 + 1), oppure sulla diagonale (𝑖 = 𝑗) o infine sulla sovradiagonale (𝑖 = 𝑗 − 1) e restituisce l’indice corrispondente nella sequenza.

Si vuole definire una struttura dati in grado di rappresentare una matrice tridiagonale attraverso la rappresentazione appena descritta.

Si definisca un descrittore matrice_tridiagonale per la struttura dati e le eventuali strutture ausiliarie, qualora necessarie, per implementare la rappresentazione.

Inoltre, la struttura dati deve supportare le seguenti operazioni, delle quali si chiede l’implementazione in linguaggio C:

• matrice_tridiagonale crea_matrice_tridigonale(int n) che crea una matrice sparsa di ordine 𝑛 e ne inizializza le tre diagonali con soli zeri.

• float elemento(matrice_tridiagonale A, int i, int j) che restituisce l’elemento 𝑎

della matrice 𝐴 (nella sua rappresentazione canonica).

• void imposta_elemento(matrice_tridiagonale* A, int i, int j, float v) che imposta l’elemento di indici (𝑖, 𝑗) al valore v

• matrice_tridiagonale prodotto_matrici_tridiagonali(matrice_tridiagonale A, matrice_tridiagonale B) che date due matrici 𝐴 e 𝐵 restituisce il contenuto di una terza matrice tridigonale 𝐶 che conterrà il prodotto matriciale di 𝐴 e 𝐵; si ricorda che il prodotto matriciale di due matrici 𝐴 e 𝐵 è espresso dalla seguente formula 𝑐

= ∑

𝑎

KMN

𝑏

e che, ovviamente, nella somma, tutti gli elementi 𝑎

con |𝑖 −

𝑝| > 1 sono nulli così come gli elementi 𝑏

con |𝑝 − 𝑗| > 1.

• matrice_tridiagonale somma_matrici_tridiagonali(matrice_tridiagonale A, matrice_tridiagonale B) che date due matrici 𝐴 e 𝐵 restituisce il contenuto di una terza matrice

tridiagonale che conterrà la somma di 𝐴 e 𝐵.

• void elimina_matrice_tridiagonale(matrice_tridiagonale* A) che elimina le eventuali strutture dati dinamiche utilizzate nella rappresentazione della matrice A.

Si discuta, informalmente, la complessità computazionale delle suddette operazioni espressa in termini dell’ordine 𝑛 della matrice rappresentata.

Esercizio 2 (8 punti)

Scrivere una funzione in linguaggio C verifica_bilanciamento(g, u, v) che, dato un grafo diretto g e due nodi u e v verifica che, la somma dei gradi dei nodi adiacenti ad u , sia uguale alla somma dei gradi dei nodi adiacenti a v . Qualora tale condizione fosse soddisfatta la funzione dovrà restituire il valore booleano true , in caso contrario la funzione dovrà restituire il valore false .

Esercizio (7 punti)

Si consideri un albero binario di ricerca in cui a ciascun nodo n sia associato un valore intero n.chiave . Scrivere un

algoritmo (ricorsivo) in linguaggio C che, dato in input il descrittore di un albero siffatto, e due valori estremi a e b e una

pila p , riempia la pila con il valore di tutti i nodi i cui campi chiave sono o strettamente minori di a oppure strettamente

maggiori di b .