Lezioni7 - Dipartimento di Matematica

Alcuni esercizi e domande
per il compitino
• quali sono le parti principali
dell’architettura di von Neumann?
• citare le caratteristiche salienti della RAM
• quali sono le parti essenziali della CPU
• descrivere il ciclo che la CPU ripete in
continuazione?
• a cosa servono i registri P e IP della
CPU?
• quali sono gli esempi più comuni di
memoria secondaria e perchè essa si
chiama sequenziale?
• dare alcuni esempi di dispositivi di
input e di output.
• determinare la tavola di verità del
seguente circuito:
A
B
R
è una tavola
nota?
• Utilizzando le porte logiche fondamentali
AND, OR e NOT disegnare il circuito che
realizza la formula logica :
(B  A)  [(NOT B)  (NOT A)]
• Formalizzare la seguente asserzione con
una formula logica:
“Siccome un rettangolo non è un quadrato
se l'altezza è diversa dalla base allora un
rettangolo con base e altezza uguali è un
quadrato”
e calcolarne la tavola di verità.
• partendo dalla tavola di verità
dell’esercizio precedente, costruite un
circuito che la realizza seguendo il
metodo di costruzione generale.
• usando la rappresentazione in
complemento a 2, quali valori interi si
possono rappresentare con 5 bit?
• con 5 bit, realizzare la somma: -5-8,
come si controlla se c’è overflow o no?
• con 5 bit, realizzare 10+8. Come si
controlla se c’è overflow o no?
• dare la rappresentazione in virgola
mobile normalizzata dei valori 0.5, 1.5 e
10.543 avendo 8 bit per l’esponente e 8
per la mantissa.
• usando 8 bit per l’esponente e 8 per la
mantissa quale numero è rappresentato da
1 01001011 00010111
•quali sono le novità principali
dell’Assembler rispetto al linguaggio
macchina?
•in un programma assembler, perchè si
attaccano delle etichette a certe istruzioni?
•come si chiama in Assembler l’istruzione
che trasferisce una parola dalla RAM ad un
registro della CPU? E quella che compie il
trasferimento inverso?
•In Assembler a cosa servono gli
identificatori?
•scrivere un programma Assembler che
legge due numeri reali e stampa il
maggiore dei due.
•Scrivere un programma Assembler che
legge due numeri interi e stampa la
somma dei loro valori assoluti.
•Scrivere un programma Assembler che
legge 10 numeri reali e stampa il
massimo.
Mercoledì Laboratorio Guidato
Via Marzolo
Via Paolotti
Lab.
Via Belzoni
Presso il Laboratorio del Dip. Matematica
11.30-12.30 Chimica Industriale
12.30-13.30 Sc. Materiali e Sc. Geologiche
16.00-17.00 Chimica
Cose da Fare
1) Per chi non le ha già chiedere un nome di
utenza (Username) ed una parola di
accesso (Password) che permettono di
accedere al laboratorio. Ricopiarle su di un
foglio di carta e conservarle. Se le si perde
non si può più accedere al laboratorio.
2) Usando username e password entrare nel
sistema operativo Linux
3) Aprire una shell di Linux
4) Aprire emacs per scrivere un programma
Assembler nel file medvar usando il
comando:
emacs medvar &
Il programma deve:
• leggere un intero n
• leggere n numeri reali e calcolarne la
media e la varianza
• stampare media e varianza.
Prepararsi il programma assembler
scritto su di un foglio di carta.
La media m e la varianza 2 di n numeri
reali x1,x2,…,xn sono date dalle formule:
x1  x2  ...  xn
m
n
2
2
2
(
x

m
)

(
x

m
)

...

(
x

m
)
2
2
n
  1
n
2
2
2
x1  x2  ...  xn

 m2
n
5) Eseguire tale programma nella shell usando
il comando:
interprete medvar
6) Correggere eventuali errori e rieseguirlo
finchè funziona.
7) Salvare il file medvar ed uscire da Linux.
Facciamo un esercizio dello stesso tipo:
• leggere un intero n
• leggere n numeri reali e calcolarne il
minimo min e il massimo max
• stampare il valore dei due prodotti n  min
ed n  max.
n
: INT ;
zero : INT 0;
uno : INT 1;
x
: FLOAT ;
npermin : FLOAT ;
npermax : FLOAT ;
nf
: FLOAT 0;
unof : FLOAT 1.0;
READ STINP n;
LOAD R0 zero;
LOAD R2 n;
Controllo che n > 0.
COMP R2 R0 ;
Se non è così non si può
BRGT OK;
calcolare
minimo
e
massimo.
WRITE STOUT n;
STOP;
OK: READ STINP x;
LOAD R3 nf;
LOAD R4 unof;
FADD R3 R4;
LOAD R1 uno;
SUB R2 R1;
LOAD R5 x;
LOAD R6 x;
n > 0 : posso leggere il primo
R3 è il numero di valori letti
rappresentato come FLOAT
R2 è il numero di valori
rimasti da leggere
R5 è il minimo ed R6 il
massimo dei valori letti
Ciclo: COMP R2 R0; R2 è il numero di valori
BRLE Esci;
rimasti da leggere
READ STINP x;
R3 è il numero di valori letti
FADD R3 R4;
rappresentato come FLOAT
SUB R2 R1;
LOAD R7 x;
R7 è l’ultimo valore letto
FCOMP R7 R5;
R5 è il minimo ed R6 il
BRGE NonMin;
massimo dei valori letti
LOAD R5 x;
BRANCH Ciclo;
NonMin : FCOMP R7 R6;
BRLE Ciclo;
LOAD R6 x;
BRANCH Ciclo;
R3 è il numero di valori letti
rappresentato come FLOAT
R5 è il minimo ed R6 il
massimo dei valori letti
Esci: FMULT R5 R3;
FMULT R6 R3;
STORE R5 npermin;
STORE R6 npermax;
WRITE STOUT npermin;
WRITE STOUT npermax;
STOP;
Complessità
Leggere un reale x ed un intero
positivo n e calcolare la potenza xn
Esempio potenza
X: FLOAT ;
N: INT ;
Ris: FLOAT ;
Uno : INT 1;
Unofl: FLOAT 1.0;
READ STINP X;
READ STINP N;
LOAD R0 Uno;
SUB R0 R0;
LOAD R1 Uno;
LOAD R2 X;
LOAD R3 N;
LOAD R4 Unofl;
X:
N:
Ris:
Uno:
Unofl:
3,0
4
?
1
1,0
R0:
R1:
R2:
R3:
R4:
0
1
3,0
4
1,0
RC:
?
All’inizio del ciclo: R4 = XN-R3
Ciclo: COMP R3 R0;
BREQ Esci;
FMULT R4 R2;
SUB R3 R1;
BRANCH Ciclo;
Esci: STORE R4 Ris;
WRITE STOUT Ris;
STOP;
X:
N:
Ris:
Uno:
Unofl:
3,0
4
81,0
?
1
1,0
R0:
R1:
R2:
R3:
R4:
0
Durante il ciclo: R4 = XN-R3
Alla fine del ciclo: R3=0 ed R4 = XN RC:
1
3,0
4
3
2
1
0
27,0
81,0
1,0
3,0
9,0
?
1
0
flowchart
READ STINP X;
READ STINP N;
LOAD R0 Uno;
SUB R0 R0;
LOAD R1 Uno;
LOAD R2 X;
LOAD R3 N;
LOAD R4 Unofl;
Ciclo:
R3 = R0?
SI
NO
FMULT R4 R2;
SUB R3 R1;
Esci: STORE R4 Ris;
WRITE STOUT Ris;
STOP
Nel programma precedente, per calcolare
xn, il ciclo viene ripetuto n volte.
Il numero di operazioni eseguite, e quindi
il tempo calcolo richiesto, aumenterà
proporzionalmente con l’aumentare di n.
Diciamo che il programma ha complessità
tempo O(n).
Vediamo un altro modo per calcolare xn.
Useremo un metodo più veloce che usa la
rappresentazione binaria bk-1bk-2 …b1b0 di
N per scomporre la potenza come segue
X X
N
X
bk 1 2 k 1  bk 2 2 k 2 ...  b1 21  b0 20
bk 1 2 k 1
dove X
bi 2i
X
bk 2 2 k 2
1
  2i
X
 ...  X
b1 21
se bi  0
se bi  1
X
b0 20
Per calcolare:
X
N
X
bk 1 2 k 1
X
bk 2 2 k 2
 ...  X
R4  1.0
R4  X
R4  X
R4  X
b0 2 0
b1 21
b2 2 2
b1 21
X
R2  X
se b0  0
 R4

R4  R2 se b0  1
X
X
b0 20
b1 21
se b1  0
 R4

R4  R2 se b1  1
X
b0 20
20
b0 20
1
 X1  X
R2  X  X 2  R2  R2
21
R2  X
22
 X 4  R2  R2
se b2  0
 R4

R4  R2 se b2  1
R2  X  X 8  R2  R2
23