Prova scritta del 7 febbraio 2019 di Fondamenti di Programmazione e Strutture Dati e Algoritmi

(1)

Prova scritta del 7 febbraio 2019 di Fondamenti di Programmazione e Strutture Dati e Algoritmi

Per studenti di Ing. Elettronica e Ing. Gestionale immatricolati a partire dall’anno 2017-18, che hanno superato la prova di esonero

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.

Lo studente è tenuto a scrivere, correggere, compilare ed eseguire su computer (a casa o in laboratorio) gli esercizi di programmazione prima della prova orale. Alla prova orale lo studente deve portare una memory pen USB contenente i sorgenti dei programmi corretti e le stampe dei relativi file.

Esercizio 1 (17 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 𝑠

_D($,%)

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(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 𝑐

$%

= ∑

L

𝑎

$K

KMN

𝑏

PK

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

$K

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

K%

con |𝑝 − 𝑗| > 1.

• vettore_dinamico prodotto_matrice_vettore(matrice_tridiagonale A,

vettore_dinamico x) che data una matrice tridiagonale 𝐴 e un vettore dinamico 𝑥 restituisce il contenuto di un vettore dinamico 𝑦 che conterrà il prodotto matrice vettore di 𝐴 e 𝑥; si ricorda che il prodotto matrice vettore 𝐴 𝑥 è espresso dalla seguente formula 𝑦

_$

= ∑

^L_KMN

𝑎

_$K

𝑥

_K

con le medesime considerazioni viste in precedenza sugli indici degli elementi non nulli.

• matrice_tridiagonale somma_matrici(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.

(2)

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

Esercizio 2 (5 punti)

Si consideri la libreria in linguaggio C per manipolare file bitmap vista a lezione, così definita:

typedef unsigned char byte;

typedef unsigned short int word;

typedef unsigned long int dword;

#define BMPFILETYPE 0x4D42 typedef struct tagCOLORTRIPLE {

byte blue;

byte green;

byte red;

} COLORTRIPLE;

typedef struct tagFILEHEADER {

word ImageFileType;

dword FileSize;

word Reserved1;

word Reserved2;

dword ImageDataOffset;

} FILEHEADER;

typedef struct tagBMPHEADER { dword HeaderSize;

dword ImageWidth;

dword ImageHeight;

word NumberOfImagePlanes;

word BitsPerPixel;

dword CompressionMethod;

dword SizeOfBitmap;

dword HorizonalResolution;

dword VerticalResolution;

dword NumberOfColorsUsed;

dword

NumberOfSignificantColors;

} BMPHEADER;

typedef struct tagBITMAP { dword width;

dword height;

COLORTRIPLE *pixel;

FILEHEADER fileheader;

BMPHEADER bmpheader;

} BITMAP;

#define PIXEL(image, row, column) \ image.pixel [(row( * image.width +

(column)]

BITMAP ReadBitmap (FILE *fp);

void WriteBitmap (BITMAP bitmap, FILE *fp);

BITMAP CreateEmptyBitmap

(dword height, dword width);

void ReleaseBitmapData (BITMAP *bitmap);

La stampa delle fotografie mediante pellicola fotografica faceva uso del “negativo”, dove la luminosità dei punti era invertita rispetto all’immagine che si voleva ottenere.

Si vuole ora simulare l’effetto del negativo in bianco e nero partendo da un’immagine digitale a colori. Per farlo, è necessario convertire ciascun pixel in bianco e nero, come visto a lezione, e poi sostituire i valori dei colori primari con il complemento al massimo valore rappresentabile. Il risultato è quello illustrato nell’esempio a lato.

Si scriva un programma in linguaggio C che riceva sulla linea di comando il nome di un file bitmap di ingresso e il nome di un file bitmap di uscita, e generi nel file di uscita l’immagine negativa come sopra descritto.

Esercizio 3 (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 .

Si simuli l’esecuzione dell’algoritmo sull’albero riportato nella figura seguente con i valori a = 4 e b = 20. Quale sarà il contenuto della pila al termine dell’esecuzione (si indichi esplicitamente la testa della pila).

20

12

8

1

14

9 13

24

22 a = 4 b = 20

30