Università degli Studi di Udine
Fondamenti di Programmazione + Architettura dei calcolatori / Fondamenti di Informatica II (prof. Montessoro)
19 luglio 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) Si scriva il numero -1
10su 16 bit nelle tre rappresentazioni modulo e segno, complemento a uno e complemento a due.
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. (6 punti) La figura a fianco rappresenta l’iperbole di equazione x = 1/y nel primo quadrante.
L’immagine è grande 1000 x 1000 pixel e ogni unità del grafico è rappresentata da 100 pixel (quindi, l’intera immagine rappresenta uno spazio di 10 x 10 unità nelle coordinate del grafico dell’equazione).
Come è noto, a causa della rappresentazione discreta dei punti dell’immagine soltanto alcuni soddisfano esattamente l’equazione dell’iperbole. Pertanto, per poter evidenziare meglio
l’andamento della curva, sono stati colorati in nero tutti i punti appartenenti al luogo geometrico che soddisfa l’equazione a meno di un errore di 0,03 unità. Lo sfondo è un grigio di luminosità pari a 3/4 della luminosità massima (bianco).
Si scriva un programma in linguaggio C che riceva sulla linea di comando il nome di un file bitmap di uscita e crei l’immagine sopra descritta.
(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. (3 punti) Nel seguito sono riportate due versioni quasi identiche della funzione FIBO, che calcola la successione di Fibonacci in modo ricorsivo. Individuare quale delle due è corretta e spiegare perché.
; int fibonacci (int R1) ; {
FIBO: MV R1 R2
JMPNZ CONT_1 ; if (R1 == 0) XOR R0 R0 ; return 0;
RET CONT_1: LDWI R2 1 SUB R1 R2
JMPNZ CONT_2 ; if (R1 == 1) LDWI R0 1 ; return 1;
RET CONT_2: DEC R1 PUSH R1
CALL FIBO ; /* fibonacci (R1-1); */
POP R1 MV R0 R2 DEC R1 PUSH R1 PUSH R2
CALL FIBO ; /* fibonacci (R1-2); */
POP R1 POP R2 ADD R2 R0
RET ; return fibonacci (R1-1) + fibonacci (R1-2);
; int fibonacci (int R1) ; {
FIBO: MV R1 R2
JMPNZ CONT_1 ; if (R1 == 0) XOR R0 R0 ; return 0;
RET CONT_1: LDWI R2 1 SUB R1 R2
JMPNZ CONT_2 ; if (R1 == 1) LDWI R0 1 ; return 1;
RET CONT_2: DEC R1 PUSH R1
CALL FIBO ; /* fibonacci (R1-1); */
POP R1 MV R0 R2 DEC R1 PUSH R1 PUSH R2
CALL FIBO ; /* fibonacci (R1-2); */
POP R2 POP R1 ADD R2 R0
RET ; return fibonacci (R1-1) + fibonacci (R1-2);
(svolgere sul retro)
4. (4 punti) Quali sono le tecniche che permettono di realizzare sistemi operativi multitasking? Spiegare brevemente gli scopi e le principali funzionalità di ciascuna di esse.
(svolgere sul retro)
5. (15 punti) I risultati parziali di un torneo di tiro a segno sono memorizzati in un file il cui formato può essere dedotto dall’esempio seguente:
Francesco Lorenzo, Rivoira Della Spina: 4 5 7 19 21 3 Ludovica Ferdinanda Rosa, Gri: 15 15 15 15 15
Mario, Rossi: 3 22 9
Federica, Della Valle: 24 18 9 8 22 3
Il numero di punteggi conseguiti da ogni concorrente è variabile e non ne è noto il numero massimo. La lunghezza di ogni riga, però, non è mai superiore a 255 caratteri. Il numero massimo di concorrenti è 100.
Si scriva un programma in linguaggio C che riceva sulla linea di comando il nome di un file come sopra descritto e stampi la classifica del torneo. Relativamente all’esempio il programma dovrà stampare:
Della Valle Federica: 84
Gri Ludovica Ferdinanda Rosa: 75
Rivoira Della Spina Francesco Lorenzo: 59 Rossi Mario: 34
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)
