Prova scritta del 24 gennaio 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 di testo contiene un piccolo dizionario dei sinonimi. Ogni riga riporta un elenco di sinonimi (una sola parola ciascuno) preceduti da un numero intero che indica il numero di sinonimi presenti sulla riga.
Per esempio:
4 casa abitazione alloggio dimora 3 lavoro impegno occupazione
6 percorso cammino tragitto viaggio strada itinerario
Ovviamente, ogni riga contiene sempre almeno due sinonimi. Ogni gruppo di sinonimi contiene al massimo 10 parole. Il file è di lunghezza ignota, ma non superiore a 300 righe.
Si vuole sviluppare uno strumento per aiutare l’autore di un testo a scegliere tra i sinonimi dei termini da lui/lei utilizzati. Per fare questo, si vuole aggiungere al testo originale l’elenco dei sinonimi di ogni parola presente nel dizionario dei sinonimi sopra descritto, accodandoli alla parola stessa e separandoli dal carattere '/'. Nota importante: la parola stessa non va ripetuta.
Quindi, se il testo originale è
Ho trovato alloggio in una cittadina lungo il tragitto verso il posto di lavoro Il testo risultante dovrà essere
Ho trovato alloggio/casa/abitazione/dimora in una cittadina lungo il tragitto/percorso/cammino/viaggio/strada/itinerario verso il posto di lavoro/impegno/occupazione NOTE:
- si assuma che il testo originale non contenga simboli di interpunzione - gli “a capo” non sono significativi
- si assuma che il dizionario dei sinonimi contenga declinate esplicitamente tutte le forme verbali, singolari e plurali, maschili e femminili. Quindi è sufficiente controllare la corrispondenza esatta di ciascun termine del testo con i termini nel dizionario.
Si scriva un programma in linguaggio C che riceva sulla linea di comando il nome del file contenente il dizionario dei sinonimi, il nome del file contenente il testo originale e il nome del file di uscita. Il programma deve scrivere nel file di uscita il testo originale modificato come sopra descritto.
Esercizio 2 (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 𝐶.
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);
