• Non ci sono risultati.

Esercizio 1 (13 punti) Una

N/A
N/A
Protected

Academic year: 2021

Condividi "Esercizio 1 (13 punti) Una"

Copied!
2
0
0

Testo completo

(1)

Prova scritta del 24 gennaio 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 (13 punti)

Una matrice quadrata di valori reali di dimensione 𝑛 × 𝑛 (detta, anche, di ordine 𝑛) è detta sparsa quando il numero di valori diversi da zero presenti nella matrice stessa sono dell’ordine di 𝑂(𝑛) invece che 𝑂(𝑛2). In altre parole, una matrice è sparsa quando è costituita da pochi valori diversi da zero. Ad esempio, le seguenti matrici sono sparse:

Un modo compatto per rappresentare una matrice sparsa è attraverso una sequenza di triple che indicano, per ciascun valore diverso da zero: (i) gli indici matriciali (𝑖, 𝑗) e (ii) il valore (diverso da zero) contenuto nell’elemento con quegli indici.

Ad esempio, la matrice 𝐴 riportata in precedenza può essere rappresentata dalla seguente sequenza di triple ⟨0,0,1.0⟩,

⟨0,4,3.5⟩, ⟨1,1,2.2⟩, ⟨1,3,4.1⟩, ⟨3,1, −1.7⟩, ⟨4,2,7.2⟩.

Si vuole definire una struttura dati in grado di rappresentare una matrice sparsa attraverso la sequenza dei suoi elementi diversi da zero come appena descritto.

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

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

matrice_sparsa crea_matrice_sparsa(int n) che crea una matrice sparsa di ordine 𝑛

“costituita” da soli zeri

void imposta_elemento(matrice_sparsa* A, int i, int j, float v) che imposta l’elemento di indici (𝑖, 𝑗) al valore v (ovviamente v può anche assumere il valore 0 e in tal caso la rappresentazione deve rimanere coerente con l’impostazione dell’elemento a tale valore)

matrice_sparsa somma_matrici(matrice_sparsa A, matrice_sparsa B) che date due matrici 𝐴 e 𝐵 restituisce il contenuto di una terza matrice 𝐶 che conterrà la somma di 𝐴 e 𝐵; si ricorda che gli elementi 𝑐𝑖𝑗 della matrice 𝐶 sono calcolati come somma degli elementi 𝑎𝑖𝑗 e 𝑏𝑖𝑗 di indici corrispondenti.

void elimina_matrice_sparsa(matrice_sparsa* 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 di 𝑚, numero di elementi diversi da zero presenti nella matrice (alternativamente 𝑚 sarà anche la lunghezza della sequenza di

rappresentazione). Nel caso della funzione somma_matrici() si esprima la complessità in termini di 𝑚𝐴 e 𝑚𝐵, numero di elementi diversi da zero, rispettivamente delle matrici 𝐴 e 𝐵.

Suggerimento: prima di iniziare ad implementare la funzione somma_matrici() si scrivano (e si analizzino) anche le rappresentazioni delle sequenze delle matrici 𝐵 e 𝐶.

(2)

Esercizio 2 (9 punti)

Scrivere una funzione in linguaggio C verifica_bilanciamento_grado(g) che, dato un grafo diretto g verifica se, dato un vertice sorgente s, tutti i nodi rimanenti siano raggiungibili da s. Qualora tale condizione fosse soddisfatta la funzione dovrà restituire il valore booleano true, in caso contrario la funzione dovrà restituire il valore false.

Esercizio (8 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, due valori estremi a e b e una coda q, riempia la coda con il valore di tutti i nodi i cui campi chiave sono compresi fra a e b (estremi inclusi).

Dire, inoltre, se la seguente affermazione è vera o falsa, spiegandone le motivazioni e fornendo, nel caso in cui sia falsa, un controesempio: > “Al termine dell’esecuzione dell’algoritmo da me realizzato la coda q conterrà i valori delle chiavi compresi fra a e b disposti in ordine crescente”.

A titolo d’esempio, si considerino le seguenti due esecuzioni in un dato albero binario con valori diversi per a e b. I valori dei nodi grigi sono quelli che dovranno essere memorizzati nella coda.

Riferimenti

Documenti correlati

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

Suggerimento: si copi in una variabile temporanea l’ultimo elemento del vettore, si copi poi ogni elemento del vettore nella posizione immediatamente seguente, si copi

Si completi il seguente frammento di codice che inizializza tutti gli n elementi di un vettore v di numeri reali di tipo double ad un valore che rappresenti

double importo_iniziale, int anni) riportata nel seguito, che dovrebbe calcolare l’importo finale applicando l’interesse composto all’importo iniziale per il numero di

Il calcolo dell’interesse composto, detto anche montante, di una somma richiede che per ogni anno venga calcolato l’importo disponibile all’inizio

Per ciò che riguarda la funzione di ricerca, invece, l’esecuzione di cerca_prima_posizione(v, 1) sul vettore riportato in esempio dovrebbe restituire il valore 2, che è l’indice

Il campo rango conterrà il rango del valore x nell’insieme i, ovvero il numero di elementi minori di x (alternativamente, la posizione di x nella sequenza ordinata), mentre il

Scrivere una funzione in linguaggio C verifica_dispari(g, s) che, dato un grafo diretto gnei cui vertici v è memorizzato un dato intero v.dato, verifica se, dato un vertice sorgente