Università degli Studi di Udine
Fondamenti di Programmazione + Architettura dei calcolatori / Fondamenti di Informatica II (prof. Montessoro)
22 gennaio 2018
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. (2 punti) Indicare le associazioni ritenute corrette
codici polinomiali [ ] compressione [ ] controllo errori [ ] correzione errori singolo bit di parità [ ] compressione [ ] controllo errori [ ] correzione errori RLE [ ] compressione [ ] controllo errori [ ] correzione errori LZW [ ] compressione [ ] controllo errori [ ] correzione errori
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. (7 punti) Nei montaggi video, l’effetto di transizione tra due immagini detto “tendina orizzontale” (“wipe”, in inglese) consiste in una linea verticale che si sposta dall'estremità sinistra a quella destra dello schermo rivelando la nuova immagine.
Si scriva un programma che generi il fotogramma centrale di tale transizione, in cui le due immagini compaiono per metà.
Il programma deve ricevere sulla riga di comando, nell’ordine, i seguenti parametri:
• nome del file contenente la prima immagine
• nome del file contenente la seconda immagine (di dimensioni identiche alla prima)
• nome del file di uscita
Si assuma che le due immagini di ingresso abbiano le stesse dimensioni.
La figura riporta un esempio.
Prima immagine Seconda immagine Immagine di uscita (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) Facendo uso delle indicazioni presenti nei commenti, si completi il seguente programma in linguaggio assembly, che scambia il contenuto delle variabili X e Y
X: word 0AAAA Y: word 0BBBB
START: _________ ; R1 <- valore della variabile X _________ ; R2 <- valore della variabile Y _________ ; variabile X <- valore di R2 _________ ; variabile Y <- valore di R1 HLT
4. (3 punti) Si descriva brevemente il funzionamento di un sistema operativo time-sharing (rispondere sul retro)
5. (14 punti) Una rete di distributori automatici comunica periodicamente alla sede del gestore, tramite un collegamento internet, il numero di esemplari ancora disponibili di ciascun prodotto onde pianificare il necessario approvvigionamento. I dati vengono tutti raccolti in un file di testo il cui formato può essere dedotto dal seguente esempio:
RIZZI_02 4: KITKAT 3, OREO 7, OROSAIWA 9, CHIPSCHILI 12.
MANTICA_01 3: OROSAIWA 19, CHIPSTER 0, OREO 5.
KOLBE_01 5: CHIPSCHILI 10, OROSAIWA 9, OREO 0, CHIPSTER 1, KITKAT 4.
Si osservi che:
• i nomi in codice dei distributori e i nomi dei prodotti sono sempre scritti con una sola parola;
• il codice del distributore è seguito dal numero dei prodotti in vendita in quel distributore e poi dal carattere due punti;
• ogni nome di prodotto è seguito dal numero di esemplari ancora disponibili e poi dal carattere virgola o punto.
Un secondo file contiene l’elenco dei prodotti venduti dal gestore e, per ciascuno, il numero di esemplari di cui ogni distributore che abbia in vendita tale prodotto deve essere rifornito (cioè il numero totale di esemplari che devono trovarsi nel distributore quando è appena stato riempito).
Un esempio di tale file è riportato nel riquadro a lato.
Scopo dell’esercizio è calcolare per ogni prodotto il numero di esemplari che devono essere caricati
sul furgone che, facendo il giro di tutti i distributori elencati nel primo file, li rifornisce in base ai dati presenti nel secondo file.
Per esempio, facendo riferimento agli esempi sopra riportati, il furgone dovrà caricare 33 esemplari di KITKAT: 17 per il distributore RIZZI_02 e 16 per il distributore KOLBE_01.
Non è noto il massimo numero di distributori. Il massimo numero di prodotti, invece, è 500. Si assuma che tutti i prodotti dei distributori siano presenti nell’elenco del secondo file.
Si scriva un programma in linguaggio C che riceva sulla riga di comando i nomi di due file come sopra descritto (il primo il file che riporta lo stato attuale dei distributori, il secondo il numero di esemplari richiesto) e stampi sul monitor l’elenco dei prodotti (in un ordine qualsiasi) con il numero totale di esemplari da caricare sul furgone e, per ciascuno, il numero presente nel secondo file come istruzione per l’addetto al rifornimento.
Relativamente agli esempi sopra riportati, il programma dovrà stampare: (rispondere sul retro) KITKAT 33 (riempire il distributore fino a 20)
OREO 33 (riempire il distributore fino a 15) OROSAIWA 38 (riempire il distributore fino a 25) CHIPSCHILI 8 (riempire il distributore fino a 15) CHIPSTER 63 (riempire il distributore fino a 32)
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)
KITKAT 20 OREO 15 OROSAIWA 25 CHIPSCHILI 15 CHIPSTER 32
