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
DURATA DELLA PROVA: 3 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 (12 punti)
Un file contiene l’elenco dei film in cui hanno recitato, in ruoli principali, alcuni attori. Ciascuna riga contiene il nome del film seguito dell’elenco di attori.
Il formato del file può essere dedotto dal seguente esempio:
"Avatar": Sam Worthington, Zoe Saldana, Sigourney Weaver, Stephen Lang, Michelle Rodriguez.
"Everest": Josh Brolin, Jason Clarke, John Hawkes, Robin Wright, Emily Watson, Keira Knightley.
"Pirati dei Caraibi Ai confini del mondo": Johnny Depp, Orlando Bloom, Keith Richards.
"Una donna in carriera": Sigourney Weaver, Melanie Griffith, Joan Cusack.
Si osservi che:
• i nomi dei film sono sempre racchiusi tra apici;
• i nomi degli attori sono sempre scritti su due parole (nome e cognome, esattamente in questo ordine e cisacuno di essi non contiene spazi al proprio interno) e sono separati da virgole;
• tutti gli elenchi sono terminati da un punto.
Non è noto il numero di attori presenti nel file né il numero di film.
Si scriva un programma in linguaggio C, opportunamente organizzato in funzioni, che riceva sulla riga di comando il nome di un file nel formato sopra descritto e il nome e cognome di un attore. Il programma deve stampare l’elenco dei film in cui tale attore compare, in ordine qualunque (e senza doppi apici).
Per esempio, nel caso del file riportato in precedenza e dell’invocazione del programma con la seguente riga di comando,
# stampa_elenco_film database_film.dat Sigourney Weaver il programma dovrebbe stampare
Avatar
Una donna in carriera
Esercizio 2 (13 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_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 𝑐
$%= ∑
LKMN𝑎
$K𝑏
PKe che, ovviamente, nella somma, tutti gli elementi 𝑎
$Kcon |𝑖 − 𝑝| > 1 sono nulli così come gli elementi 𝑏
K%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 3 (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);
