ESAME SCRITTO TAMC 7 Marzo 2002

Domanda 1 (4pt)

Descrivere scopo e funzionamento del gestore della memoria.

Domanda 2 (4pt)

Descrivere tipologia e funzionalita' dei motori di ricerca per il web.
Formulate in modo appropriato le query per cercare le seguenti informazioni:
- indirizzo del negozio Mare Mare;

Soluzione: cerco "Mare Mare" (utilizzando le virgolette)

- pagine web relative al termine laterna che non hanno a che fare con Genova.

Soluzione: lanterna -Genova

Esercizio 1 (5pt)
Supponiamo di lavorare su una Macchina di Von Neumann avente le seguenti caratteristiche:

RAM= 100 celle
PC     = registro Program Counter
ACC = registro Accumulatore
 
Codice Specifica Effetto
0 READ  Muove un valore letto dall'input nel registro ACC 
(cancella il suo valore precedente)
1 MOVE  C Muove il valore contenuto nel registro ACC nella 
C-esima cella della RAM 
(cancella il valore precedente della cella)
2 LOAD  C Muove il valore contenuto nella cella C della RAM nel 
registro ACC 
(cancella il valore precedente di ACC)
3 INC Incrementa di uno il valore contenuto nel registro ACC
4 DEC Decrementa  di uno il valored del reg. ACC
5 TEST L Se il valore del reg. ACC e' uguale a ZERO assegna al 
registro PC il valore L; 
altrimenti va all'istruzione seguente 
Nota: non modifica il  valore del reg. ACC
6 SUM C  Somma al valore contenuto nel reg. ACC il valore contenuto nella C-esima cella della RAM
(il valore precedente dell'accumulatore va perso)
7 GOTO  L  Assegna il valore  L al reg. PC 
Nota: non modifica il  valore del reg. ACC
8 END Termina il programma 

Considerate ora il seguente programma in linguaggio macchina

RAM[0]=  READ
RAM[1]=  MOVE 20
RAM[2]=  READ
RAM[3]=  MOVE 21
RAM[4]=  LOAD 20
RAM[5]=  TEST  13
RAM[6]=  DEC
RAM[7]=  MOVE 20
RAM[8]=  LOAD 21
RAM[9]=  TEST 15
RAM[10]=DEC
RAM[11]=MOVE 21
RAM[12]=GOTO 4
RAM[13]=LOAD 20
RAM[14]=TEST 16
RAM[15]=GOTO 18
RAM[16]=INC
RAM[17]=MOVE 19
RAM[18]=END
RAM[19]=0
RAM[20]=0
RAM[21]=0

(1.1)  Data la sequenza di input (ordinata da sinistra a destra)
 
3
2

qual e' il valore delle celle RAM[19], RAM[20] e RAM[21] alla fine dell'esecuzione del programma?

Soluzione:

RAM[19]=0, RAM[20]=0, RAM[21]=0

(1.2) Piu' in generale data la sequenza di input
 
x1
x2

con x1, x2>=0 qual e' il valore delle celle RAM[19], RAM[20] e RAM[21] alla fine dell'esecuzione del programma?

Soluzione:

Siano X1 e X2 due valori maggiori o uguali a 0.
Il programma calcola il test X1=X2 utilizzando la cella 19 come output per la risposta (1=si, 0=no)
cioe'  RAM[19]=1 se X1=X2; RAM[19]=0 altrimenti
Per effettuare il test si decrementano in parallelo i due valori partendo da X1.
Quindi:
- RAM[20]= X1-X2-1 se X1>X2,   = 0 altrimenti
- RAM[21]=X2-X1 se X2>X1,         = 0 altrimenti


Esercizio 2 (3pt)

Rappresentate i seguenti numeri interi  su 1 byte ed utilizzando la rappresentazione sia
in complemento a 1 che in complemento a 2:
 
0
37
 -12

Soluzione:

            Complemento a 1         Complemento a 2
0              00000000                         00000000
37            00100101                         00100101
-12         11110011                         11110100


Esercizio 3 (4pt)

Considerate il seguente programma LP

Program P
var A: array 1..100 of integer;
        i, j,N: integer;
        ok: Boolean;
begin
        i:=1;
        read(N);
        while (i=<N) do
           begin
                read(A[i]);
                i:=i+1;
           end;
        endw;
        ok:=true;
        i:=(N/2)+1;
        j:=i-1;
        while ((i=<N) and (j>=1) and ok) do
           begin
                 if  not(A[i] = A[j]) then ok:=false endif;
                 i:=i+1;
                 j:=j-1;
           end;
       endw;
       if ok then write(1) else write(0);
end:

(2.1)
Data la sequenza in input
 
6
 2
1
 4 2 1 4

qual è l'output del programma?

Soluzione: l'output e' 0

(2.2)
In generale dato l'input
 
N
x1
...
 xM

con M>=N, N numero pari e positivo, qual è l'output del programma?

Soluzione:

Il programma legge N =numero di valori da memorizzare nell'array.
Quindi controlla che se gli N valori letti da input formano una sequenza palindrome
(cioe' che presenta la stessa sequenza di caratteri se letta da sinistra a destra o da destra a sinistra)
il programma restituisce 1 se la condizione e' vera, 0 altrimenti
Ad es. output e' 1 su 6 2 1 3 3 1 2 ma e' 0 su 6 2 1 3 3 2 1

(2.3)
Supponete che N/2 restituisca la parte intera inferiore della divisione (e.g. 5/2=2).
Come cambia l'output del programma (nel caso generale) se N e' dispari?

Soluzione:
Il programma si comporta come in precedenza ignorando pero' l'ultimo numero memorizzato nell'array:
Ad es.: output e' 1 su  5 2 1 1 2 6