Esercitazioni - Informatica A
Roberto Tedesco
E-mail: [email protected]
Ufficio: 103, 1° piano DEI
Tel: 02 2399 3667 oppure 02 2399 3668
Ricevimento: venerdì 10.30 – 12.30
Sito web del corso:
http://www.elet.polimi.it/corsi/infoA
Slide mostrate durante l’esercitazione
Raccolte di esercizi
Di regola, le slide saranno disponibili prima
della lezione
-1-
Politecnico
di Milano
Numeri naturali (numeri senza segno)
Il sistema posizionale
L’idea del sistema posizionale: ogni cifra ha un peso
Esempio: 132 = 100 +30 +2
Facciamo un passo indietro…
Un numero generico di m cifre è rappresentato dalla
sequenza di cifre: an, an-1, an-2,..., a0
an cifra più significativa, a0 cifra meno significativa
n = m —1
ai  {0, 1, ..., p—1} insieme delle cifre utilizzabili
ai  {0, 1, ..., 9}
-3-
a0 =
a2 =
a1 =
p è detto base
Di solito noi usiamo la base decimale (p=10)
Esempio: 132  m = 3  1, 3, 2
Rappresentazione in base p
Nel sistema posizionale, un numero naturale N,
composto da m cifre, in base p, si esprime come:
N p  an  p  an 1  p
n
n 1
n
 ...  a1  p  a0  p   ai  p i
1
0
i 0
Esempio in base decimale o base dieci (p=10):
13210 = 1·102+3·101+2·100
Posso rappresentare i numeri nell’intervallo
discreto: [0 , pm — 1] .
-4-
Rappresentazione in base due
Base binaria o base due:
p=2
ai  {0, 1} chiamate bit (binary digit)
Una sequenza di otto bit è detta byte
Esempio, con m=5:
110112 = (1·24+1·23+0·22+1·21+1·20)10 = 2710
Converto dalla base 2 alla base 10
Posso rappresentare i numeri nell’intervallo discreto:
[0 , 2m —1]
Esempio: con m=8, rappresento numeri binari:
[000000002 , 111111112], ovvero [010 , 25510]
28—1 = 255.
-5-
Conversione base dieci  base due
Esempio, 1410:
14 : 2 = 7
7:2=3
3:2=1
1:2=0




resto = 0
resto = 1
resto = 1
resto = 1
1410 = 11102
.
-6-
Somma
Le cifre sono 0 e 1; il riporto può essere solo 1
Riporto
precedente
Somma
Risultato
Riporto
0
0+0
0
0
0
0+1
1+0
1
0
0
1+1
0
1
1
0+0
1
0
1
0+1
1+0
0
1
1
1+1
1
1
-7-
Somma e carry
Esempio:
1  riporto
0101 +
(510)
1001 =
(910)
-----1110
(1410)
111
 riporti
1111 +
1010 =
------carry  11001
-8-
(1510)
(1010)
(2510 se uso 5 bit;
910 se considero 4 bit: errato) .
Base ottale (o base otto)
p=8; ai  {0, 1, 2, 3, 4, 5, 6, 7}
Esempio: 2348 = (2·82+3·81+4·80)10 = 15610
Sapendo che 8 = 23: conversione binario  ottale
Esempio: 1011111002
1012 = (122+021+120 )10 = 510 = 58
1112 = (122+121+120 )10 = 710 = 78
1002 = (122+021+020 )10 = 410 = 48
Quindi, 1011111002 = 5748
Sapendo che 8 = 23: conversione ottale  binario
Esempio: 1268
18 = 110 = 0012
28 = 210 = 0102
68 = 610 = 1102
Quindi, 1268 = 0010101102 .
-9-
Base esadecimale (o base sedici)
p=16; ai  {0, 1, 2, …, 9, A, B, C, D, E, F}
Esempio: B7F16 = (11·162+7·161+15·160)10 = 294310
“B” al posto di “11” e “F” al posto di “15”
Sapendo che 16=24: Conversione binario  esadecimale
Esempio: 1011111012
00012 = (023+022+021+120)10 = 110 = 116
01112 = (023+122+121+120)10 = 710 = 716
11012 = (123+122+021+120)10 = 1310 = D16
Quindi, 1011111012 = 17D16
Sapendo che 16=24: Conversione esadecimale  binario
Esempio: A316
A16 = 1010 = 10102
316 = 310 = 00112
Quindi, A316 = 101000112 .
- 10 -
Politecnico
di Milano
Numeri interi (numeri con segno)
Modulo e segno
Non posso memorizzare il “segno”, uso una codifica
Uso un bit per memorizzare il segno: “1” significa
numero negativo, “0” numero positivo. Esempio m=3:
Num. intero,
base 10
–3
Num. intero, base due,
modulo e segno
111
–2
110
–1
101
–0
100
+0
000
+1
001
+2
010
+3
011
- 12 -
?
Complemento a due (CPL2)
Usando m bit: (–N)CPL2 = (2m — N10)2
Esempio (m=3): (–N)CPL2 = (23 — N10)2
Num. intero base 10
Trasformazione
Num. intero, base 2,
CPL2, m=3
-4
8–4=4
410 = 100
-3
8–3=5
510 = 101
-2
8–2=6
610 = 110
-1
8–1=7
710 = 111
0
nessuna
010 = 000
1
nessuna
110 = 001
2
nessuna
210 = 010
3
nessuna
310 = 011
- 13 -
Complemento a due (CPL2)
Posso rappresentare i numeri nell’intervallo
discreto:
[–2m—1 , 2m—1 — 1]
Asimmetria tra negativi e positivi
Esempio (m=8):
[–128, +127], perché –27 = –128 e 27—1 = +127
Tutti i numeri negativi cominciano con il bit più
significativo posto a “1”, mentre tutti i positivi e lo
zero iniziano con uno “0” .
- 14 -
Calcolo pratico del CPL2
Se m, il numero di bit da utilizzare per memorizzare il
numero intero, è conosciuto:
Il minimo numero negativo che potrò codificare sarà
–2m—1, mentre il massimo numero positivo che potrò
codificare sarà 2m—1 — 1
Se ho N10 e N10  2m—1 — 1, lo codifico in base due così
com’è, su m bit (aggiungendo cioè zeri a sinistra così da
riempire tutti gli m bit disponibili)
Se ho –N10 e –N10  –2m—1, uso la seguente “regola rapida”:
Parto dal numero positivo N10 e lo codifico in base due su m
bit (aggiungo cioè zeri a sinistra così da riempire tutti gli m
bit disponibili)
Modifico ogni “0” in “1” ed ogni “1” in “0” (“complemento”)
Sommo 1, usando le consuete regole dell’addizione binaria .
- 15 -
Calcolo pratico del CPL2
Se m non è conosciuto, lo ricavo nel seguente modo:
Se ho numero positivo N10, prendo il minimo m tale
che N10  2m—1 — 1
Se ho numero negativo –N10, prendo il minimo m tale
che –N10  –2m—1
Quindi eseguo l’algoritmo illustrato nella slide
precedente
Se devo codificare un intervallo [-N10 , +M10]:
Calcolo m’ per –N10
Calcolo m” per +M10
m = max (m’, m”)
.
- 16 -
Calcolo pratico del CPL2
Esempio: –210 con m=8 bit:
210 = 000000102  111111012 +
12 =
--------------111111102
Esempio: –510 con m=? bit:
provo con m=2,3,4 e scopro che –5  –2(4—1), allora
m=4; adesso codifico –5 con m=4 bit:
510 = 01012  10102 +
12 =
--------10112
- 17 -
.
Valore decimale di un numero in CPL2
Se il numero è positivo (bit più significativo posto a
“0”), lo converto usando la solita sommatoria
Se il numero è negativo (bit più significativo posto a
“1”), allora:
Calcolo il modulo del numero, ovvero applico ancora
su di esso il CPL2
Considero il numero risultante N2 come un NATURALE
(cioè come un numero senza segno, l’eventuale
“1” iniziale non indica più il segno) e lo converto
con la solita sommatoria. Ottengo N10
A questo punto, il numero decimale è –N10 .
- 18 -
Valore decimale di un numero in CPL2
Esempio: 10000012 = ?
Numero negativo
Applichiamo CPL2 e otteniamo: 01111112
Consideriamolo un naturale e convertiamolo usando la
solita sommatoria: 01111112 = 6310
Allora 10000012 = –6310
Esempio: 01010012 = ?
Numero positivo
Convertiamolo usando la solita sommatoria:
01010012 = 4110
- 19 -
.
Somma e sottrazione in CPL2
Somma: come per i naturali
Sottrazione: N1 — N2 = N1 + (–N2)CPL2
Carry:
Il bit di carry non viene considerato!
Overflow:
Se, sommando due interi di m bit dotati di segno
concorde, ottengo un risultato di segno discorde
(sempre considerando m bit), allora si ha un overflow
(il risultato non è codificabile su m bit) e l’operazione
è errata
L’overflow non può verificarsi se gli operandi sono di
segno discorde.
- 20 -
Somma e sottrazione in CPL2
Esempi (m=7 cioè da –6410 a +6310):
0000101 +
1111000 =
--------1111101
carry 
1111
 riporti
1111011 +
0001000 =
---------10000011
10000011
(+510)
(–810)
(–310)
(-510)
(+810)
(butto via il carry)
(+310)
.
- 21 -
Somma e sottrazione in CPL2
carry 
1
 riporti
1000000 +
1111000 =
---------10111000
0111000
Overflow: –7210
(–6410)
(–810)
(butto via il carry)
(+5610: sbagliato;
dovrebbe essere –7210)
non è codificabile su 7 bit in CLP2
11111
 riporti
0111111 +
(+6310)
0000010 =
(+210)
--------1000001
(–6310: è sbagliato; dovrebbe essere +6510)
Overflow: +6510 non è codificabile su 7 bit in CPL2
- 22 -
.
I Flag
Insieme di “segnalatori”, calcolati dopo ogni istruzione:
Z (Zero). Vale “1” sse il risultato dell’addizione è zero;
“0” altrimenti
N (Negative). Vale “1” sse il risultato dell’addizione è
negativo; “0” altrimenti
C (Carry). Vale “1” sse l’addizione ha prodotto un carry;
“0” altrimenti
V (oVerflow). Vale “1” sse l’addizione ha prodotto un
overflow; “0” altrimenti
Per esempio, nell’esercizio che aveva per risultato
10000012, avrei ottenuto: Z=0; N=1; C=0; V=1
I Flag sono usati da alcune istruzioni della macchina di
Von Neumann .
- 23 -
Conclusione
Se si opera con numeri che si considerano naturali,
si sta attenti al Flag di carry (C), se si opera con
numeri che si considerano interi, si sta attenti al
Flag di overflow (V)
I Flag sono computati tutti, al termine di ogni
istruzione (escluse le istruzioni di salto)
Come fa a macchina di Von Neumann a sapere se sta
operando su numeri naturali o interi?
Semplicemente, NON LO SA! Le operazioni che la
macchina esegue sono identiche in entrambi i casi,
soltanto l’interpretazione dei risultati cambia .
- 24 -
Politecnico
di Milano
Numeri reali
Parte frazionaria di un numero
Rappresentiamo la parte frazionaria di un numero reale
In base due, un numero frazionario N, composto da n
cifre, si esprime come:
1
2
N 2  a1  2  a 2  2  ...  a n  2
n

1
i
a

2
 i
i  n
Esprimo in realtà l’equivalente in base dieci
Esempio con n=3: 0,1012 = (1·2-1+0·2-2+1·2-3)10 = 0,87510
Date n cifre in base p=2, posso rappresentare numeri
nell’intervallo continuo: [02 , 0,111…12]
ovvero nell’equivalente in base dieci: [0 , 1—2—n]
 è l’errore di approssimazione
 < max = 2—n
.
- 26 -
Parte frazionaria di un numero
Esempio, con n=8:
Codifico i numeri [0,000000002 , 0,111111112]
ovvero i numeri compresi in [0 , 1—2—8 = 0,99609375]
max = 2—8 = 0,00390625
.
- 27 -
Parte frazionaria di un numero
Per passare dalla base dieci alla base due.
Esempio, convertiamo 0,2110 avendo n=6:
0,21 
0,42 
0,84 
0,68 
0,36 
0,72 
2=
2=
2=
2=
2=
2=
0,42 
0,84 
1,68 
1,36 
0,72 
1,44 
parte intera = 0
parte intera = 0
parte intera = 1
parte intera = 1
parte intera = 0
parte intera = 1
parte fraz. = 0,42
parte fraz. = 0,84
parte fraz. = 0,68
parte fraz. = 0,36
parte fraz. = 0,72
parte fraz. = 0,44
Termino quando ho utilizzato gli n bit a disposizione
Prendo le parti intere, dalla prima all’ultima
Allora 0,2110  0,0011012
Riconvertendo: 0,0011012 = 0,20312510
=0,21—0,203125=0,006875;  < max; (max=2—6=0,015625).
- 28 -
Virgola fissa
Uso m bit e n bit per parte intera e frazionaria
Esempio (m=8, n=6, tot. 14 bit): -123,2110
-12310 = 100001012
0,2110  0011012
-123,2110  10000101,0011012
Come scelgo m e n?
Precisione costante lungo R:
R
0
- 29 -
Virgola mobile (floating point)
Il numero è espresso come: r = m·bn
m e n sono in base p
m: mantissa (numero frazionario con segno)
b: base della notazione esponenziale (numero naturale)
n: caratteristica (numero intero)
Esempio (p=10, b=10): -331,6875 = –0,3316875103
m = –0,3316875
n=3
Precisione variabile lungo R. Per es. con 5 cifre per m:
13212,4323 = 0,13212105 = 13212 (ho perso 0,4323)
7,345312 = 0,73453101 = 7,3453 (ho perso 0,000012)
R
0
- 30 -
Virgola mobile (floating point)
Mantissa (m):
Codifico solo la parte a destra della virgola
Codifico il segno
Caratteristica (n):
l2 bit
m con segno (l1 bit)
- 31 -
n (l2 bit)
l1 bit
Virgola mobile (floating point)
Quando la prima cifra a destra della virgola è
diversa da zero, il numero in virgola mobile si dice
normalizzato
Es. –0,3716875103 è normalizzato perché la prima
cifra a destra della virgola è “3”
La normalizzazione permette di avere, a parità di
cifre usate per la mantissa, una maggiore
precisione.
Es. Uso l1=5 cifre per la mantissa:
+45,6768  +0,45676102  +0,00456104
Ho perso
0,0008
Ho perso
0,0768
- 32 -
Politecnico
di Milano
Caratteri
Caratteri
Codifica numerica
ASCII (American Standard Code for Information
Interchange) utilizza 7 bit (estesa a 8 bit)
L’ASCII codifica
I caratteri alfanumerici (lettere maiuscole e
minuscole e numeri), compreso lo spazio
I simboli (punteggiatura, @, ecc)
Alcuni caratteri di controllo (TAB, LINEFEED, RETURN,
BELL, ecc) .
- 34 -
Tabella ASCII (parziale)
DEC
48
CAR
0
DEC
65
CAR
A
DEC
75
CAR
K
DEC
97
CAR
a
DEC
107
CAR
k
49
1
66
B
76
L
98
b
108
l
50
2
67
C
77
M
99
c
109
m
51
3
68
D
78
N
100
d
110
n
52
4
69
E
79
O
101
e
111
o
53
5
70
F
80
P
102
f
112
p
54
6
71
G
81
Q
103
g
113
q
55
7
72
H
82
R
104
h
114
r
56
8
73
I
83
S
105
i
115
s
57
9
74
J
84
T
106
j
116
t
85
U
117
u
86
V
118
v
87
W
119
w
88
X
120
x
89
Y
121
y
90
Z
122
z
- 35 -
Tabella ASCII
Anche le cifre numeriche sono codificate
Le lettere sono in sequenza alfabetica
Per passare dal minuscolo al maiuscolo:
Codicemaiuscolo = Codiceminuscolo – 3210
Alcuni caratteri sulla tastiera italiana:
ALT-123=“{“
ALT-125=”}”
ALT-126=”~”
oppure
oppure
SHIFT-ALTGR-[
SHIFT-ALTGR-]
Sul libro a pag. 403 si trova la tabella ASCII estesa .
- 36 -
Politecnico
di Milano
Algebra di Boole
e
circuiti logici
Algebra di Boole
E’ basata su tre operatori: AND, OR, NOT
Ogni formula può assumere solo due valori: “vero” o
“falso”. Idem per le variabili
Rappresentiamo “vero” con “1” e “falso” con “0”
AND e OR sono operatori binari (come, per esempio,
l’operatore somma “+” dell’algebra)
NOT è un operatore unario (come, per esempio,
l’operatore fattoriale “!” dell’algebra) .
- 38 -
Operatori booleani
Tavole di verità:
A
B
A AND B
A
B
A OR B
0
0
0
0
0
0
0
1
0
0
1
1
1
0
0
1
0
1
1
1
1
1
1
1
A
NOT A
0
1
1
0
- 39 -
Operatori booleani
Gli operatori AND e OR godono delle seguenti
proprietà:
Commutativa:
A OR B = B OR A
A AND B = B AND A
Distributiva di uno verso l’altro:
A OR (B AND C) = (A OR B) AND (A OR C)
A AND (B OR C) = (A AND B) OR (A AND C)
- 40 -
.
Ancora operatori booleani: XOR
Operatore XOR (OR esclusivo):
A
B
A XOR B
0
0
0
0
1
1
1
0
1
1
1
0
A XOR B = (NOT A AND B) OR (A AND NOT B).
- 41 -
Espressioni booleane
Regole di precedenza:
NOT ha la massima precedenza
poi segue AND
infine OR (e XOR)
Se voglio alterare queste precedenze devo usare le
parentesi (a volte usate solo per maggior chiarezza)
Per valutare un espressione booleana si usa la
tabella della verità
Espressioni booleane uguali: sse le tabelle della
verità sono identiche.
- 42 -
Dalla formula alla tabella
Vediamo un esempio, per l’espressione:
D = A AND NOT (B OR C)
A
B
C
D = A AND NOT (B OR C)
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
0
1
0
0
1
1
0
1
0
1
1
0
0
1
1
1
0
- 43 -
Dalla tabella alla formula
Se conosco la tabella della verità, posso ricostruire la
formula logica. Partiamo dalla tabella:
NOT A AND B
A AND NOT B
A AND B
A
B
C1
0
0
0
0
1
1
1
0
1
1
1
1
C1 = (NOT A AND B) OR (A AND NOT B) OR (A AND B) .
- 44 -
Porte logiche
Ogni operatore booleano (AND, OR, NOT) ha un
equivalente elettronico:
A
A
C
B
C
B
C = A AND B
C = A OR B
A
C
C = NOT A
Le porte AND e OR sono “operatori n-ari”:
A
B
C
D
A
D
B
C
D=A AND B AND C
.
- 45 -
Dalla formula al circuito
Esempio: C = NOT (NOT A AND NOT B)
A
C
B
.
- 46 -