Università degli Studi di Udine
Fondamenti di Programmazione + Architettura dei calcolatori / Fondamenti di Informatica II (prof. Montessoro)
24 gennaio 2019
Prova scritta per studenti di Ing. Elettronica e Ing. Gestionale immatricolati negli anni accademici 2016-17 e precedenti – DURATA DELLA PROVA: 3 ORE
Matricola __________________
Nome _____________________
Cognome __________________
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.
1. (4 punti) Si descriva la modalità di controllo dell’overflow nella una somma in complemento a due discutendo le quattro possibili combinazioni.
(svolgere sul retro)
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);
2. (5 punti) Un metodo abbastanza semplice per evidenziare i contorni di un’immagine bitmap consiste nel sostituire ogni pixel con il modulo del gradiente della luminosità in quel punto (il gradiente è un’estensione del concetto di derivata – mi perdonino i colleghi matematici per l’estrema approssimazione…). In pratica, più la luminosità nell’intorno del punto cambia rapidamente e più elevato sarà il valore del pixel, disegnando così un contorno chiaro su sfondo scuro. Per esempio, si osservino le due immagini a lato.
Il calcolo del gradiente si basa su una procedura simile a quella del filtro per ammorbidire l’immagine discusso nell’esercitazione di laboratorio sui file multimediali. In prima approssimazione si può considerare soltanto la luminosità dei pixel e non le singole componenti di colore.
La procedura di calcolo del gradiente richiede di calcolare le componenti Lx e Ly come somma pesata dei pixel dell’intorno secondo i pesi riportati nella figura a lato. Quindi, Lx = luminosità del pixel [i-1, j-1] - luminosità del pixel [i-1, j+1] + 2 * luminosità del pixel [i, j-1] - 2* luminosità del pixel [i, j+1] ecc.
Al termine, alle componenti di colore del pixel [i, j] dell’immagine di uscita va assegnato il modulo del gradiente calcolato come radice quadrata della somma di Lx e Ly al quadrato.
Si scriva una funzione in linguaggio C che riceva come argomento un’immagine bitmap e restituisca l’immagine bitmap rappresentante i contorni generata come sopra descritto. La prima e l’ultima riga dell’immagine e la prima e l’ultima colonna, non permettendo il calcolo del gradiente, vanno ricopiate dall’immagine originale.
Si assuma già disponibile la funzione double lum (BITMAP bmp, int i, int j) che restituisce la luminosità del pixel di coordinate i, j nell’immagine bmp.
(svolgere sul retro)
Un elaboratore (il modello didattico SimCPU visto a lezione) dispone di CPU (a 16 bit) con 16 registri di uso generale (R0, R1, ..., R15) più il Program Counter, l’Instruction Register, lo Stack Pointer e 4 flag Z (zero), N (negative), C (carry) e V (overflow).
Si ricorda che il linguaggio assembler di tale elaboratore dispone delle seguenti istruzioni:
3. (4 punti) Si traduca in linguaggio assembly il frammento di codice in linguaggio C a fianco, supponendo che le variabili R0, R1 e R2 siano memorizzate nei registri omonimi:
(svolgere sul retro)
4. (2 punti) Si scriva un’espressione, da inserire nella cella A1 di un foglio elettronico, che richieda l’abilitazione della modalità di calcolo iterativo.
5. (15 punti) SINONIMI
Un file di testo contiene un piccolo dizionario dei sinonimi. Ogni riga riporta un elenco di sinonimi (una sola parola ciascuno), separati da virgole. L’elenco è terminato da un punto.
Per esempio:
casa, abitazione, alloggio, dimora.
lavoro, impegno, occupazione.
percorso, cammino, tragitto, viaggio, strada, itinerario.
Ovviamente, ogni riga contiene sempre almeno due termini. Ogni gruppo di sinonimi contiene al massimo 10 parole. Il file contiene al massimo 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.
assembly inst. name machine code action LDWI d X load word 00010000dddd0000 DATA(16) d <- X LDWA d A load word 00100000dddd0000 ADDR(16) d <- mem[A]
LDWR d a load word 00110000ddddaaaa d <- mem[a]
LDBI d X load byte 00010001dddd0000 DATA(8) d <- X LDBA d A load byte 00100001dddd0000 ADDR(16) d <- mem[A]
LDBR d a load byte 00110001ddddaaaa d <- mem[a]
STWA s A store word 00100010ssss0000 ADDR(16) mem[A] <- s STWR s a store word 00110010ssssaaaa mem[a] <- s STBA s A store byte 00100011ssss0000 ADDR(16) mem[A] <- s STBR s a store byte 00110011ssssaaaa mem[a] <- s MV s d move 00000100ssssdddd d <- s PUSH s push 00001000ssss0000 push (s) POP d pop 00001001dddd0000 d <- pop () SPRD d read SP 00001101ssss0000 d <- SP SPWR s write SP 00001110ssss0000 SP <- s ADD s d add 01000000ssssdddd d <- d + s SUB s d subtract 01000001ssssdddd d <- d - s NOT r bitwise NOT 01000010rrrr0000 r <- ~r AND s d bitwise AND 01000011ssssdddd d <- d & s OR s d bitwise OR 01000100ssssdddd d <- d | s XOR s d bitwise XOR 01000101ssssdddd d <- d ^ s INC r increment 01001000rrrr0000 r <- r + 1 DEC r decrement 01001001rrrr0000 r <- r + 1 LSH r left shift 01001010rrrr0000 r <- r << 1 RSH r right shift 01001011rrrr0000 r <- r >> 1
assembly inst. name machine code action INW d A input word 10000000dddd0000 IN_ADDR(16) d <- read[A]
INB d A input byte 10000001dddd0000 IN_ADDR(16) d <- read[A]
OUTW s A out word 10000010ssss0000 OUT_ADDR(16) out[A] <- s OUTB s A out byte 10000011ssss0000 OUT_ADDR(16) out[A] <- s
TSTI A test input 1000010000000000 IN_ADDR(16) if completed then Z <- 1 else Z <- 0
TSTO A test output 1000010100000000 OUT_ADDR(16) if completed then Z <- 1 else Z <- 0
BR A branch 1100000000000000 ADDR(16) PC <- A JMP F jump 11000001FFFFFFFF PC <- PC + F
JMPZ F jump if zero 11000010FFFFFFFF if (z == 1) PC <- PC + F JMPNZ F jump if not zero 11000011FFFFFFFF if (z == 0) PC <- PC + F JMPN F jump if negative 11000100FFFFFFFF if (N == 1) PC <- PC + F JMPNN F jump if not neg. 11000101FFFFFFFF if (N == 0) PC <- PC + F JMPC F jump if carry 11000110FFFFFFFF if (C == 1) PC <- PC + F JMPV F jump if overflow 11000111FFFFFFFF if (V == 1) PC <- PC + F CALL A subroutine call 1100100000000000 ADDR(16) push (PC); PC <- A RET return from sub. 1100100100000000 PC <- pop() HLT halt 1100111100000000 halt LEGENDA:
- lettere minuscole = registri; lettere maiuscole = dati numerici - ‘r’ = registro letto e modificato
- ‘s’ = registro soltanto letto - ‘d’ = registro modificato
- ‘a’ = registro il cui contenuto è usato come indirizzo - FFFFFFFF = offset (in complemento a 2)
while (R1 > R2) {
R1--;
R2++;
}
if (R1 == R2) R0 = 0;
else R0 = 1;
