Esercizi di Informatica Generale

Esercizi di
Informatica
Generale
Edizione 1 – Gennaio 2010
di
Luca Andrea Ludovico
Insegnamento di Informatica Generale
Scienze e tecnologie per i Beni Culturali
SOMMARIO
SOMMARIO ............................................................................................................. 1 1 | Circuiti digitali sequenziali................................................................................. 6 1.1 | Operatori logici ............................................................................................ 6 1.1.1 | Operatore NOT.................................................................................... 6 1.1.2 | Operatore AND ................................................................................... 7 1.1.3 | Operatore OR ....................................................................................... 8 1.1.4 | Operatore XOR .................................................................................... 9 1.1.5 | Operatore NAND .............................................................................. 10 1.1.6 | Operatore NOR.................................................................................. 11 1.1.7 | Operatore XNOR .............................................................................. 12 1.2 | Equazioni e circuiti.................................................................................... 13 1.2.1 | Esercizio .............................................................................................. 14 1.2.2 | Esercizio .............................................................................................. 15 1.2.3 | Esercizio .............................................................................................. 16 1.3 | Tabelle della verità ..................................................................................... 17 1.3.1 | Esercizio .............................................................................................. 18 1.3.2 | Esercizio .............................................................................................. 19 1.3.3 | Esercizio .............................................................................................. 20 1.4 | Studio di funzioni logiche ........................................................................ 21 1.4.1 | Esercizio .............................................................................................. 22 1.4.2 | Esercizio .............................................................................................. 24 2 | Bit e Byte ........................................................................................................... 26 2.1 | Dimensionamento delle stringhe ............................................................ 27 1
2.1.1 | Esercizio .............................................................................................. 27 2.2 | Calcoli su bit e byte ................................................................................... 28 2.2.1 | Esercizio .............................................................................................. 28 2.2.2 | Esercizio .............................................................................................. 29 2.2.3 | Esercizio .............................................................................................. 30 2.2.4 | Esercizio .............................................................................................. 31 3 | Memorie di massa............................................................................................. 32 3.1 | Prestazioni delle unità disco ..................................................................... 32 3.1.1 | Esercizio .............................................................................................. 32 3.1.2 | Esercizio .............................................................................................. 34 3.1.3 | Esercizio .............................................................................................. 35 3.1.4 | Esercizio*............................................................................................. 36 3.2 | Capacità dei dischi magnetici ................................................................... 38 3.2.1 | Esercizio .............................................................................................. 39 3.2.2 | Esercizio .............................................................................................. 40 4 | Rappresentazione dei numeri ......................................................................... 41 4.1 | Conversioni da base n a base 10 .............................................................. 41 4.1.1 | Esercizio .............................................................................................. 42 4.1.2 | Esercizio .............................................................................................. 43 4.1.3 | Esercizio .............................................................................................. 44 4.1.4 | Esercizio*............................................................................................. 45 4.1.5 | Esercizio .............................................................................................. 46 4.2 | Conversioni da base 10 a base n .............................................................. 47 4.2.1 | Esercizio .............................................................................................. 48 4.2.2 | Esercizio .............................................................................................. 49 4.2.3 | Esercizio .............................................................................................. 50 2
4.2.4 | Esercizio .............................................................................................. 52 4.2.5 | Esercizio .............................................................................................. 53 4.3 | Conversioni da base m a base n ............................................................... 55 4.3.1 | Esercizio .............................................................................................. 56 4.3.2 | Esercizio .............................................................................................. 57 4.3.3 | Esercizio .............................................................................................. 58 4.3.4 | Esercizio .............................................................................................. 59 4.3.5 | Esercizio .............................................................................................. 60 4.3.6 | Esercizio*............................................................................................. 61 4.4 | Operazioni aritmetiche ............................................................................. 62 4.4.1 | Esercizio .............................................................................................. 63 4.4.2 | Esercizio .............................................................................................. 65 4.4.3 | Esercizio .............................................................................................. 67 4.4.4 | Esercizio .............................................................................................. 70 4.5 | Numeri negativi ......................................................................................... 72 4.5.1 | Esercizio .............................................................................................. 73 4.5.2 | Esercizio .............................................................................................. 74 4.5.3 | Esercizio .............................................................................................. 75 4.5.4 | Esercizio .............................................................................................. 77 4.6 | Somme in complemento a 2 .................................................................... 79 4.6.1 | Esercizio .............................................................................................. 80 4.6.2 | Esercizio .............................................................................................. 82 5 | Extensible markup language ........................................................................... 83 5.1 | Correttezza della forma ............................................................................ 83 5.1.1 | Esercizio .............................................................................................. 83 5.1.2 | Esercizio .............................................................................................. 84 3
5.1.3 | Esercizio .............................................................................................. 85 5.1.4 | Esercizio .............................................................................................. 86 5.1.5 | Esercizio .............................................................................................. 87 5.2 | Documenti XML ....................................................................................... 88 5.2.1 | Esercizio .............................................................................................. 88 5.2.2 | Esercizio .............................................................................................. 89 5.2.3 | Esercizio .............................................................................................. 90 5.3 | Interpretazione di DTD ........................................................................... 91 5.3.1 | Esercizio .............................................................................................. 92 5.3.2 | Esercizio .............................................................................................. 93 5.3.3 | Esercizio .............................................................................................. 94 5.3.4 | Esercizio .............................................................................................. 95 5.3.5 | Esercizio .............................................................................................. 97 5.4 | Formulazione di DTD .............................................................................. 99 5.4.1 | Esercizio ............................................................................................100 5.4.2 | Esercizio ............................................................................................101 5.4.3 | Esercizio ............................................................................................102 5.4.4 | Esercizio ............................................................................................103 6 | Gestione degli errori ......................................................................................104 6.1 | Rilevamento degli errori .........................................................................104 6.1.1 | Esercizio ............................................................................................105 6.1.2 | Esercizio ............................................................................................106 6.1.3 | Esercizio ............................................................................................107 6.2 | Correzione degli errori............................................................................108 6.2.1 | Esercizio ............................................................................................109 6.2.2 | Esercizio ............................................................................................109 4
6.2.3 | Esercizio ............................................................................................110 6.2.4 | Esercizio ............................................................................................111 6.2.5 | Esercizio ............................................................................................112 7 | Database ..........................................................................................................113 7.1 | Algebra relazionale ..................................................................................114 7.1.1 | Esercizio ............................................................................................115 7.1.2 | Esercizio ............................................................................................116 7.2 | Structured Query Language ...................................................................118 7.2.1 | Esercizio ............................................................................................118 7.2.2 | Esercizio ............................................................................................120 5
1 | CIRCUITI DIGITALI SEQUENZIALI
In questo primo capitolo verrà affrontato lo studio dei circuiti digitali
sequenziali tramite tabelle della verità e si introdurrà il metodo delle mappe di
Karnaugh per giungere all’ottimizzazione delle equazioni logiche nella prima
forma canonica (POS, product of sums) e nella seconda forma canonica (SOP,
sum of products).
1.1 | O PERATORI LOGICI
1.1.1 | O PERATORE NOT
Si tratta di un operatore unario, che accetta un unico ingresso e produce
un’uscita. Rappresenta la negazione logica, o il complemento.
Equazione logica:
z = NOT a
[informatica]
z= a
[algebra]
z = a
[logica]
Simbolo circuitale:
a
z
Tabella della verità:
a
0
1
6
z
1
0
1.1.2 | O PERATORE AND
Si tratta di un operatore binario, che accetta due ingressi e produce un’uscita.
Rappresenta il prodotto logico.
Equazione logica:
z = a AND b
[informatica]
z=ab=a·b=ab
[algebra]
z =a b
[logica]
Simbolo circuitale:
a
z
b
Tabella della verità:
a
0
0
1
1
b
0
1
0
1
z
0
0
0
1
Si osservi che è sufficiente la presenza di uno 0 in ingresso per produrre
un’uscita pari a 0. L’unico caso in cui l’uscita è posta a 1 è che la coppia di
ingressi sia posta a 1.
Esiste una versione n-aria dell’operatore, ossia con n ingressi. In tal caso,
l’uscita è pari a 1 se e solo se tutti gli ingressi sono posti a 1.
7
1.1.3 | O PERATORE OR
Si tratta di un operatore binario, che accetta due ingressi e produce un’uscita.
Rappresenta la somma logica.
Equazione logica:
z = a OR b
[informatica]
z=ab
[algebra]
z =a b
[logica]
Simbolo circuitale:
a
z
b
Tabella della verità:
a
0
0
1
1
b
0
1
0
1
z
0
1
1
1
Si osservi che è sufficiente la presenza di un 1 in ingresso per produrre
un’uscita pari a 1. L’unico caso in cui l’uscita è posta a 0 è che la coppia di
ingressi sia posta a 0.
Esiste una versione n-aria dell’operatore, ossia con n ingressi. In tal caso,
l’uscita è pari a 0 se e solo se tutti gli ingressi sono posti a 0.
8
1.1.4 | O PERATORE XOR
Si tratta di un operatore binario, che accetta due ingressi e produce un’uscita.
Rappresenta l’OR esclusivo (aut aut) ed è un operatore di disuguaglianza.
Equazione logica:
z = a XOR b
[informatica]
z=ab
[algebra]
Simbolo circuitale:
a
z
b
Tabella della verità:
a
0
0
1
1
b
0
1
0
1
z
0
1
1
0
Si osservi che l’uscita viene posta a 1 se e solo se gli ingressi sono differenti.
9
1.1.5 | O PERATORE NAND
Si tratta di un operatore binario, che accetta due ingressi e produce un’uscita.
Rappresenta la negazione del prodotto logico.
Equazione logica:
z = a NAND b = NOT (a AND b)
z = a  b = ab
[algebra]
Simbolo circuitale:
a
z
b
Tabella della verità:
a
0
0
1
1
10
b
0
1
0
1
[informatica]
z
1
1
1
0
1.1.6 | O PERATORE NOR
Si tratta di un operatore binario, che accetta due ingressi e produce un’uscita.
Rappresenta la negazione della somma logica.
Equazione logica:
z = a NOR b = NOT (a OR b)
z = ab
[algebra]
Simbolo circuitale:
a
z
b
Tabella della verità:
a
0
0
1
1
11
b
0
1
0
1
[informatica]
z
1
0
0
0
1.1.7 | O PERATORE XNOR
Si tratta di un operatore binario, che accetta due ingressi e produce un’uscita.
Rappresenta la negazione dell’OR esclusivo (aut aut) ed è un operatore di
uguaglianza.
Equazione logica:
z = a XNOR b
[informatica]
z=ab
[algebra]
Simbolo circuitale:
a
z
b
Tabella della verità:
a
0
0
1
1
b
0
1
0
1
z
1
0
0
1
Si osservi che l’uscita viene posta a 1 se e solo se gli ingressi sono uguali.
12
1.2 | E QUAZIONI E CIRCUITI
Data un’equazione logica, è sempre possibile fornire una rappresentazione
grafica dello schema circuitale sotteso. Analogamente, è possibile partire dallo
schema circuitale per ricavare la corrispettiva equazione logica.
Nelle nostre convenzioni grafiche, i segnali si propagano da sinistra verso
destra, pertanto gli ingressi saranno posti sul lato sinistro e le uscite su quello
destro.
Volendo rappresentare lo schema circuitale di un’equazione logica, si parte
dagli operatori con massima priorità che agiscono direttamente sugli ingressi,
per poi procedere nel disegnare gli operatori con priorità più bassa, fino a
giungere all’uscita o alle uscite.
Si ricorda che l’operatore con priorità più alta è il NOT, seguito dall’AND e
infine dall’OR. Per modificare l’ordine naturale di valutazione degli operatori,
si possono introdurre le parentesi tonde. Le versioni negate a NAND b e
a NOR b ai fini della priorità possono essere rispettivamente considerate
come NOT (a AND b) e NOT (a OR b).
13
1.2.1 | E SERCIZIO
Testo
Si eliminino le parentesi superflue dalle seguenti equazioni logiche:
z1 = (a AND (NOT b)) OR c
z2 = (NOT a) AND (b OR c)
z3 = NOT ((a AND b) NOR c)
Soluzione
Le parentesi in z1 inducono a valutare dapprima il NOT, poi l’AND e infine
l’OR. Ma questo è proprio l’ordine dettato dalla priorità degli operatori in
questione, pertanto
z1 = (a AND (NOT b)) OR c = a AND NOT b OR c
Per quanto concerne z2, le parentesi danno priorità massima alla valutazione
di (NOT a) e di (b OR c). Nel primo caso, le parentesi possono essere
omesse, mentre nel secondo sono strettamente necessarie, altrimenti
(NOT a) AND b avrebbe la priorità. Dunque:
z2 = (NOT a) AND (b OR c) = NOT a AND (b OR c)
Per valutare la parentetizzazione di z3, espandiamo l’operatore NOR in NOT
OR.
z3 = NOT ((a AND b) NOR c) =
= NOT (NOT((a AND b) OR c))
L’ordine imposto dalle parentesi è: innanzi tutto la valutazione dell’AND più
interno, seguito dall’OR, dal NOT interno e dal NOT esterno. L’unica
parentesi eliminabile è quella che abbraccia (a AND b). Stabilito questo, e
ricordando che NOT(NOT(x)) = x:
z3 = NOT (NOT(a AND b OR c)) = a AND b OR c
14
1.2.2 | E SERCIZIO
Testo
Si fornisca una rappresentazione grafica del circuito relativo alla seguente
equazione logica:
z = ab + ( a + c ) = a AND b OR (NOT(a) OR NOT(c))
Soluzione
I primi operatori da valutare sono

x1 = a AND b

x2 = NOT(a)

x3 = NOT(c)
Al secondo livello viene valutato y = x2 OR x3.
Al terzo livello, si giunge infine a z = x1 OR y.
Graficamente:
a
x2
x1
z
b
y
c
15
x3
1.2.3 | E SERCIZIO
Testo
Si fornisca una rappresentazione grafica del circuito relativo alla seguente
equazione logica:
z = a + (b  (a · b)) = a OR (b XNOR (a AND b))
Soluzione
Gli operatori vanno valutati nell’ordine:
1. x = a AND b
2. y = b XNOR x
3. z = a OR y
Graficamente:
a
z
x
y
b
16
1.3 | T ABELLE DELLA VERITÀ
La tabella della verità descrive l’uscita o le uscite di un circuito in funzione di
tutte le possibili combinazioni in ingresso. In un sistema binario, ingressi e
uscite possono assumere solo i valori 0 e 1.
Nella rappresentazione grafica tabellare, escludendo la riga di intestazione, la
tabella della verità di una funzione con m ingressi ed n uscite contempla:

2m righe

m + n colonne
Ad esempio, la tabella della verità dell’operatore NOT presenta 1 ingresso, e
dunque 21 combinazioni, e 1 uscita: è una tabella 22 (2 righe e 2 colonne).
La tabella della verità dell’operatore AND nella versione binaria presenta 2
ingressi, e dunque 22 = 4 combinazioni, e 1 uscita: è una tabella 43 (4 righe e
3 colonne).
Per funzioni più complesse rispetto agli operatori logici elementari, è
possibile (e talvolta auspicabile) introdurre colonne aggiuntive che tengano in
considerazione i risultati parziali. Queste non appartengono strettamente alla
tabella della verità che descrive la funzione logica.
Una funzione logica è descritta da una e una sola tabella della verità.
Viceversa, la stessa tabella della verità può corrispondere a più funzioni
logiche (a questo proposito, si vedano gli esercizi successivi). Due funzioni
che presentano la stessa tabella della verità sono equivalenti.
Si osservi che una tabella della verità dà una descrizione
della funzione logica in stile black box (scatola nera), ossia
osservandone solo il comportamento esterno: all’applicazione
di certi valori in ingresso corrisponde un dato valore in
uscita.
17
1.3.1 | E SERCIZIO
Testo
Si verifichi tramite confronto delle tabelle della verità la proprietà
commutativa dell’operatore AND, e poi si faccia altrettanto per l’operatore
OR.
Soluzione
Per verificare la proprietà commutativa, è necessario provare che:
a AND b = b AND a
Questo si può fare spezzando l’equazione logica nei suoi due membri:
z1 = a AND b
z2 = b AND a
e confrontando le 2 tabelle della verità. Se esse saranno identiche, significa
che le due equazioni logiche sono equivalenti. Facendo corrispondere le
combinazioni di ingressi nelle due tabelle e applicando quanto mostrato in
1.1.2:
a
0
0
1
1
b
0
1
0
1
z1
0
0
0
1
b
0
1
0
1
a
0
0
1
1
z2
0
0
0
1
In modo analogo, per quanto riguarda l’operatore OR:
w1 = a OR b
w2 = b OR a
a
0
0
1
1
18
b
0
1
0
1
w1
0
1
1
1
b
0
1
0
1
a
0
0
1
1
w2
0
1
1
1
1.3.2 | E SERCIZIO
Testo
Si verifichi tramite confronto delle tabelle della verità il primo teorema di De
Morgan, che afferma:
NOT (a AND b) = (NOT a) OR (NOT b)
Si verifichi poi il secondo teorema di De Morgan, che afferma:
NOT (a OR b) = (NOT a) AND (NOT b)
Soluzione
Siano:
z1 = NOT (a AND b)
z2 = (NOT a) OR (NOT b)
a
0
0
1
1
b
0
1
0
1
a AND b
0
0
0
1
z1
1
1
1
0
a
0
1
0
1
b
0
0
1
1
NOT a
1
0
1
0
NOT b
1
1
0
0
z2
1
1
1
0
Il confronto tra le due colonne relative all’uscita, a parità di combinazioni in
ingresso, mostra che z1 = z2.
Ora siano invece:
w1 = NOT (a OR b)
w2 = (NOT a) AND (NOT b)
a
0
0
1
1
b
0
1
0
1
a OR b
0
1
1
1
w1
1
0
0
0
a
0
1
0
1
b
0
0
1
1
NOT a
1
0
1
0
NOT b
1
1
0
0
w2
1
0
0
0
Anche in questo caso, il confronto tra le due colonne relative all’uscita, a
parità di combinazioni in ingresso, mostra che w1 = w2.
19
1.3.3 | E SERCIZIO
Testo
Si verifichi tramite confronto delle tabelle della verità la possibilità di
rappresentare gli operatori logici AND, OR e NOT utilizzando solo porte
logiche NAND, come mostrato sotto:
NOT a = a NAND a
a AND b = (a NAND b) NAND (a NAND b)
a OR b = (a NAND a) NAND (b NAND b)
Soluzione
Si confrontino l’ultima colonna (che contiene la tabella della verità
dell’operatore sostituito) con la penultima (che contiene la tabella della verità
con soli operatori NAND). L’identità delle uscite a parità di valori in ingresso
prova le equazioni logiche sopra riportate.
a
0
1
20
a AND a
0
1
a
b
0
0
1
1
0
1
0
1
a
b
0
0
1
1
0
1
0
1
a NAND a
1
0
w
=
a NAND b
1
1
1
0
w1
=
a NAND a
1
1
0
0
NOT a
1
0
w NAND w
a AND b
0
0
0
1
0
0
0
1
w2
=
b NAND b
1
0
1
0
w1 NAND w2
a OR b
0
1
1
1
0
1
1
1
1.4 | S TUDIO DI FUNZIONI LOGICHE
Nel presente paragrafo verranno mostrati esercizi di applicazione delle tabelle
della verità al fine di studiare il comportamento delle uscite dei circuiti in
funzione degli ingressi.
Verrà inoltre introdotto il metodo delle mappe di Karnaugh per sintetizzare
le reti combinatorie a uno o più livelli.
Una mappa di Karnaugh è un metodo grafico che ha come obiettivo quello
di ridurre la complessità delle funzioni booleane espresse in forme canoniche.
Essa si costruisce a partire dalla tabella della verità di una funzione booleana,
nel processo di sintesi di una rete combinatoria.
Le mappe di Karnaugh permettono di costruire in modo semplice la forma
minima di una funzione come somma di prodotti logici (forma congiuntiva)
o come prodotto di somme logiche (forma disgiuntiva) e quindi
semplificazioni della funzione booleana spesso più immediate di quelle
ottenibili con modifiche algebriche.
Le mappe di Karnaugh risultano applicabili efficacemente solo a funzioni con
al più 5 - 6 variabili.
21
1.4.1 | E SERCIZIO
Testo
Si consideri la seguente equazione logica:
z = NOT ((NOT a AND b AND c) OR b OR (NOT a AND b AND NOT c))
Si studi il comportamento dell’uscita z in funzione degli ingressi a, b e c
tramite tabella della verità.
Si proceda alla semplificazione del circuito tramite mappe di Karnaugh,
giungendo all’equazione logica nella forma SOP (prima forma canonica).
Soluzione
Il presente esercizio può essere risolto per via tradizionale, ossia studiando le
singole funzioni logiche partendo da quelle più interne nel livello di
parentetizzazione (ossia quelle più vicine agli ingressi nello schema circuitale)
per poi porre i risultati ottenuti come ingressi degli operatori più esterni.
Procedendo in tal senso, si ha:
z = NOT ((NOT a AND b AND c) OR b OR (NOT a AND b AND NOT c)) =
[detti e = NOT a e f = NOT c]
= NOT ((e AND b AND c) OR b OR (e AND b AND f)) =
[detto g = e AND b]
= NOT ((g AND c) OR b OR (g AND f)) =
[detti h = g AND c e i = g AND f]
= NOT (h OR b OR i) =
[detto l = h OR b]
= NOT (l OR i) =
[detto m = l OR i]
= NOT m
a
0
0
0
0
1
1
1
1
22
b
0
0
1
1
0
0
1
1
c
0
1
0
1
0
1
0
1
e
1
1
1
1
0
0
0
0
f
1
0
1
0
1
0
1
0
g
0
0
1
1
0
0
0
0
h
0
0
0
1
0
0
0
0
i
0
0
1
0
0
0
0
0
l
0
0
1
1
0
0
1
1
m
0
0
1
1
0
0
1
1
z
1
1
0
0
1
1
0
0
Pertanto:
z = 1 per
a = 0, b = 0, c = 0
a = 0, b = 0, c = 1
a = 1, b = 0, c = 0
a = 1, b = 0, c = 1
z=0
altrimenti.
Una soluzione più rapida si basava sull’analisi del contenuto della parentesi
esterna, che è un OR tra tre blocchi, rispettivamente:
1. (NOT a AND b AND c)
2. b
3. (NOT a AND b AND NOT c)
Si ricorda che la caratteristica dell’OR è dare uscita 0 se e solo se tutti i suoi
ingressi sono 0. Dobbiamo quindi verificare quando questo avvenga.
Il blocco 1 è un AND a tre ingressi, ed è falso in tutti i casi salvo:
a = 0, b = 1, c = 1.
Il blocco 3 è un AND a tre ingressi, ed è falso in tutti i casi salvo:
a = 0, b = 1, c = 0.
Con queste osservazioni, la tabella di verità risultava molto semplificata:
a
0
0
0
0
1
1
1
1
b
0
0
1
1
0
0
1
1
c
0
1
0
1
0
1
0
1
blocco 1
0
0
0
1
0
0
0
0
blocco 3
0
0
1
0
0
0
1
0
OR a 3 ingressi
0
0
1
1
0
0
1
1
z
1
1
0
0
1
1
0
0
Mappa di Karnaugh:
ab
c
23
00 01 11 10
Per la prima forma canonica (SOP, Sum of
Products) è necessario raggruppare gli 1. Ne
0
0
1
1
0
consegue:
1
0
1
1
0
z = NOT b
1.4.2 | E SERCIZIO
Testo
Si considerino le seguenti equazioni logiche:
x = f1(a, b, c) = ((a NAND b) OR c) AND (b XOR c)
y = f2(a, b, c) = (b XOR c) OR (a OR NOT b)
Se ne fornisca una rappresentazione circuitale grafica congiunta. Si studino
singolarmente i comportamenti delle uscite x e y in funzione degli ingressi a, b,
c tramite tabelle della verità. Si proceda infine alla semplificazione dei circuiti
tramite mappe di Karnaugh, mostrando il procedimento per via grafica e il
risultato ottenuto e scegliendo la forma canonica più opportuna in ciascun
caso.
Soluzione
a
d
f
x
b
e
c
y
g
a
0
0
0
0
1
1
1
1
b
0
0
1
1
0
0
1
1
c
0
1
0
1
0
1
0
1
d
1
1
1
1
1
1
0
0
e
0
1
1
0
0
1
1
0
Pertanto:
x = 1 per
a = 0, b = 0, c = 1
a = 0, b = 1, c = 0
a = 1, b = 0, c = 1
x = 0 altrimenti
24
h
f
1
1
1
1
1
1
0
1
x
0
1
1
0
0
1
0
0
d = a NAND b
e = b XOR c
f = d OR c
x = f AND e
a
0
0
0
0
1
1
1
1
b
0
0
1
1
0
0
1
1
c
0
1
0
1
0
1
0
1
e
0
1
1
0
0
1
1
0
g
1
1
0
0
1
1
0
0
h
1
1
0
0
1
1
1
1
y
1
1
1
0
1
1
1
1
e = b XOR c
g = NOT b
h = a OR g
y = e OR h
Pertanto:
y = 0 solo per a = 0, b = 1, c = 1
y = 1 altrimenti
Mappa di Karnaugh per x:
ab
c
00 01 11 10
0
0
1
0
0
1
1
0
0
1
Essendoci un numero esiguo di 1, è conveniente
scegliere la prima forma canonica (SOP, Sum of
Products).
Raggruppando gli 1 come in figura:
x = (NOT a AND b AND NOT c) OR (NOT b AND c)
Mappa di Karnaugh per y:
ab
c
00 01 11 10
0
1
1
1
1
1
1
0
1
1
Essendoci un solo 0, è conveniente scegliere la
seconda forma canonica (POS, Product of Sums).
Raggruppando gli 0 come in figura:
y = a OR NOT b OR NOT c
25
2 | BIT E BYTE
In questo capitolo verranno proposti esercizi assortiti al fine di prendere
dimestichezza con le unità di misura fondamentali nella rappresentazione
dell’informazione.
A questo proposito, ricordiamo che l’unità atomica è data dal bit, che può
assumere solo il valore 0 o il valore 1. Proprio da tale caratteristica deriva il
nome bit, che è la contrazione di binary digit (cifra binaria). I bit vengono
convenzionalmente raggruppati a gruppi di otto, a formare i byte. Pertanto,
una stringa di 8 bit è una stringa da 1 byte. Ma il byte stesso è un’unità di
misura sovente troppo piccola per gli usi pratici.
I multipli comunemente adottati per il byte sono:

1 KB (Kilobyte) = 210 byte = 1024 byte

1 MB (Megabyte) = 220 byte = 1024 KB

1 GB (Gigabyte) = 230 byte = 1024 MB

1 TB (Terabyte) = 240 byte = 1024 GB
Per ogni altra unità di misura, il prefisso kilo indica 103, il prefisso mega sta
per 106 e via dicendo. Nel campo dell’Informatica, tali potenze di 10 sono
approssimazioni (non sempre accettabili) delle potenze di 2 sopra citate.
Ad esempio, un hard disk della capacità di 80 GB contiene esattamente
85˙899˙345˙920 byte, ossia 5˙899˙345˙920 byte in più rispetto al suo valore
approssimato.
26
2.1 | D IMENSIONAMENTO DELLE STRINGHE
In generale, quando si ha il problema di rappresentare x oggetti tramite
stringhe binarie, si deve prevedere un numero n di bit tale che:
2n ≥ x con n .
Infatti, tramite n bit è possibile rappresentare 2n differenti combinazioni di
valori binari, cui si possono far corrispondere i più svariati significati. Alcune
di queste combinazioni possono anche non venire assegnate: è il caso tipico
di quando i diversi valori da rappresentare non sono potenze di 2.
Si veda al riguardo il seguente esercizio.
2.1.1 | E SERCIZIO
Testo
Si dimensionino correttamente le stringhe di bit atte a contenere le seguenti
informazioni:

i semi delle carte da gioco napoletane;

i nomi delle note della scala musicale;

i mesi dell’anno;

i codici prodotto di un distributore automatico con 100 scomparti.
Soluzione
Nel caso dei semi, x = 4 e dunque n = 2. Ad esempio:
00 ↔ bastoni, 01 ↔ denari, 10 ↔ spade e 11 ↔ coppe.
Nel caso delle note, x = 7 e dunque n = 3. Una delle 8 combinazioni risulterà
inutilizzata.
Nel caso dei mesi dell’anno, x = 12 e dunque n = 4. Quattro delle sedici
combinazioni risulteranno inutilizzate.
Infine, per identificare x = 100 prodotti servono almeno n = 7 bit.
27
2.2 | C ALCOLI SU BIT E BYTE
2.2.1 | E SERCIZIO
Testo
Sapendo che una canzone ha durata media t = 3' 18'' e viene compressa in
formato MP3 a 256 kbps1 (1 kbit = 103 bit), si determini quante canzoni
possono trovare posto su un supporto CD-ROM di dimensione pari a 800
MB (1 MB = 220 byte). E quante canzoni possono stare su una chiavetta USB
da 4 GB?
Soluzione
t = 3’ 18’’ = (3 · 60 + 18) s = 198 s
La codifica di ogni secondo della canzone richiede 256˙000 bit, e dunque
ogni canzone mediamente occupa 50˙688˙000 bit = 6˙336˙000 byte =
= 6,04 MB.
Dunque un CD-ROM da 800 MB può contenere circa 800 / 6,04 = 132
canzoni.
Per quanto riguarda la chiavetta, essa contiene 4096 MB e dunque circa 678
canzoni di tale durata media.
1
28
1 kbps = 1 kbit / s = 1000 bit al secondo.
2.2.2 | E SERCIZIO
Testo
Si consideri il formato del CD-DA da 74 minuti, che codifica ogni secondo di
musica con 44100 campioni da 16 bit/campione e in stereo, ossia su 2 canali.
Si calcoli la capacità di tale supporto in termini di MB.
Soluzione
Un secondo di musica in formato CD-DA contiene 88200 campioni (44100
per il canale destro, 44100 per il sinistro), ognuno dei quali è costituito da una
sequenza di 16 bit (ossia 2 byte) che ne individua il valore.
Quindi, un secondo di musica occupa
2 · 44100 · 2 byte = 176˙400 byte = 172,3 KB
e un minuto occupa 10˙584˙000 byte (10,1 MB).
In un CD-DA da 74 minuti sono contenuti 747,4 MB (74 minuti · 10,1 MB).
Nota: i CD-R da 74 minuti contengono circa 650 MB di
dati o circa 747,4 MB di audio. Il formato CD-ROM
impiega i 100 MB di differenza per codici di correzione
d'errore supplementari, vista la delicatezza del formato. Per
questo motivo i MB disponibili all'utente risultano solo
650.
29
2.2.3 | E SERCIZIO
Testo
Si calcoli quanta memoria occupa in un calcolatore un’immagine A di
dimensione 640 × 480 pixel e in bianco e nero.
Si ripeta il calcolo per un’immagine B avente uguali dimensioni in pixel e
profondità di colore sufficiente a rappresentare una palette di 16 colori.
Si consideri infine un’immagine C di dimensioni quadrate, profondità di
colore pari a 24 bit e occupazione in memoria pari a 12 KB. Quali sono le
sue dimensioni in pixel?
Soluzione
L’immagine A è formata da (640 · 480) pixel = 307˙200 pixel.
Poiché il numero di colori da rappresentare è pari a 2, ad ogni pixel è
sufficiente riservare un unico bit per l’informazione di colore. Dunque
l’immagine occupa 307˙200 bit = 38˙400 byte = 37,5 KB.
L’immagine B è a 16 colori, e ciò significa che occorrono log216 = 4 bit per
ogni singolo pixel. Dunque un’immagine di 640 × 480 pixel a 16 colori
occupa (640 · 480 · 4) bit = 1˙228˙800 bit, cioè 153˙600 byte o 150 KB.
Infine si procede per C in modo inverso. Dalla dimensione d in MB e dalla
profondità di colore p (ossia dal numero di bit necessari per codificare
l’informazione di colore di ciascun pixel) si risale a n, numero complessivo di
pixel che formano l’immagine, secondo la formula:
n=d/p
avendo però cura di usare unità di misura omogenee.
n = (12 · 1024 · 8 / 24) pixel = 4096 pixel
Essendo l’immagine quadrata, le sue dimensioni lineari a e b espresse in pixel
sono date da:
a = b = √ = 64 pixel
30
2.2.4 | E SERCIZIO
Testo
Si consideri un supporto magnetico quale il floppy disk da 1,44 MB la cui
capacità esatta è pari a 1˙474˙560 byte.
Si calcoli quanti caratteri codificati in ASCII esteso vi possono essere salvati,
ricordando che tale codifica richiede 8 bit per carattere.
Si effettui nuovamente il calcolo considerando una codifica in UTF-32
supponendo che il testo sia disposto in 10 file. Nota: si ricorda che UTF-32
rappresenta ciascun carattere su 32 bit, e richiede la scrittura della stringa
esadecimale 00 00 FE FF (di lunghezza 4 byte, come si vedrà nel Capitolo 4)
come prefisso di ogni file.
Soluzione
In ASCII esteso, ogni carattere occupa 8 bit = 1 byte. Ne consegue che un
floppy delle caratteristiche citate possa contenere
nASCII = 1˙474˙560 caratteri
In UTF-32, ogni carattere occupa 32 bit = 4 byte.
Per quanto concerne il prefisso dei file, lo spazio complessivamente
impiegato è pari a 10 file · 4 byte/file = 40 byte.
Ora il numero di caratteri contenuti è
nUTF-32 = (1˙474˙560 - 40) / 4 = 368˙630 caratteri
31
3 | MEMORIE DI MASSA
3.1 | P RESTAZIONI DELLE UNITÀ DISCO
3.1.1 | E SERCIZIO
Testo
Si consideri un disco fisso con le seguenti caratteristiche:2

capacità totale c = 80 GB;

velocità di trasferimento dati (o data transfer rate) vtrasf = 150 MB/s;

tempo medio di posizionamento tpos = 9 ms;

velocità di rotazione vrot = 7200 rpm.
Si calcoli il tempo complessivamente richiesto per leggere e trasferire 320 KB
di dati, ricordando che 1 K = 210 e 1 M = 220.
Soluzione
Il computo del tempo complessivo ttot passa per la valutazione di tre addendi:
ttot = tpos + tlat + ttrasf
ove:

tpos è il tempo di posizionamento, ossia il tempo necessario per
spostare le testine di lettura/scrittura da una traccia a un’altra;

tlat rappresenta il tempo di latenza, detto anche ritardo di rotazione,
pari a metà del tempo necessario al disco per eseguire una rotazione
completa. In altri termini, questo è il tempo medio perché i dati
richiesti giungano sotto la testina di lettura/scrittura;
2
32
Queste sono le caratteristiche reali del disco fisso Maxtor SATA2 2M da 80 GB.

infine, ttrasf è il tempo richiesto per il solo trasferimento dei dati alla
velocità determinata da vtrasf.
Si presti attenzione, nei calcoli, a utilizzare le medesime unità di misura per i
tre addendi.
Nel caso delle unità disco, solitamente l’unità più
appropriata è il millisecondo, abbreviato in ms.
Dal testo, si evince che il tempo di posizionamento tpos = 9 ms.
Il tempo di latenza tlat si calcola sulla base della velocità di rotazione
vrot = 7200 rpm (revolutions per minute, rotazioni al minuto).
Al secondo,
vrot = (7200 / 60) rps = 120 rps.
Per definizione, si deve determinare il tempo richiesto per eseguire mezza
rotazione. Pertanto si imposta la seguente proporzione:
120 : 1 = 0,5 : tlat
tlat = (0,5 / 120) s = 0,00417 s = 4,17 ms
Infine è necessario calcolare il tempo necessario per trasferire 320 KB di dati.
150 · 220 : 320 · 210 = 1 : ttrasf
ttrasf = (320 / (150 · 1024)) s = 0,00208 s = 2,08 ms
In definitiva:
ttot = tpos + tlat + ttrasf = (9 + 4,17 + 2,08) ms = 15,25 ms
Si osservi che la capacità totale del disco, che pure è uno dei
parametri fondamentali per descriverne le caratteristiche,
non ha alcun impatto sulla soluzione dell’esercizio.
33
3.1.2 | E SERCIZIO
Testo
Si consideri un disco fisso con le seguenti caratteristiche:3

capacità totale c = 150 GB;

velocità di trasferimento dati vtrasf = 3 Gb/s;4

tempo medio di posizionamento in lettura tpos = 4,2 ms;

velocità di rotazione vrot = 10000 rpm.
Si calcoli il tempo complessivamente richiesto per leggere e trasferire 2 MB di
dati, considerando 1 MB = 220 byte e 1 Gb = 109 bit.
Soluzione
Il computo del tempo complessivo ttot passa per la valutazione di tre addendi:
ttot = tpos + tlat + ttrasf
Dal testo, si evince che il tempo di posizionamento tpos = 4,2 ms.
Il tempo di latenza tlat si calcola sulla base della velocità di rotazione
vrot = 10000 rpm (revolutions per minute, rotazioni al minuto).
Al secondo,
vrot = (10000 / 60) rps = 166,67 rps.
Ora si imposta la seguente proporzione:
166,67 : 1 = 0,5 : tlat
tlat = 0,003 s = 3 ms
Infine è necessario calcolare il tempo necessario per trasferire 2 MB di dati.
vtrasf = 3 Gb/s = 3/8 · 109 byte/s = 0,375 · 109 byte/s
0,375 · 109 : 221 = 1 : ttrasf
ttrasf = 0,00559 s = 5,59 ms
Infine:
ttot = tpos + tlat + ttrasf = (4,2 + 3 + 5,59) ms = 12,79 ms
Queste sono le caratteristiche reali del disco fisso Western Digital VelociRaptor SATA2 da
150 GB.
4 Attenzione: si tratta di gigabit per secondo.
3
34
3.1.3 | E SERCIZIO
Testo
Si consideri un unità floppy con le seguenti caratteristiche:5

velocità di trasferimento dati vtrasf = 500 KB/s;

tempo di posizionamento = 3 ms per traccia;

velocità di rotazione vrot = 300 rpm.
Si calcoli il tempo complessivamente richiesto per spostare la testina di
lettura di 10 tracce e trasferire 250 KB di dati, considerando 1 K = 210.
Soluzione
Si osservi che un floppy disk è significativamente più lento di un hard disk,
innanzi tutto per il diverso regime di rotazione (max 300 rpm contro max
15000 rpm). Anche i restanti tempi hanno ordini di grandezza superiori.
Pertanto, potrebbe risultare più agevole esprimere il risultato in secondi.
Il calcolo del tempo complessivo ttot passa sempre per la valutazione di tre
addendi:
ttot = tpos + tlat + ttrasf
Tempo di posizionamento tpos = 3 ms/traccia · 10 tracce = 30 ms = 0,03 s.
Il tempo di latenza tlat si calcola sulla base della velocità di rotazione
vrot = 300 rpm = 5 rps. Pertanto:
5 : 1 = 0,5 : tlat
tlat = 0,1 s
Infine è necessario calcolare il tempo necessario per trasferire 250 KB di dati.
500 · 210 : 250 · 210 = 1 : ttrasf
ttrasf = 0,5 s
Dunque si ottiene:
ttot = tpos + tlat + ttrasf = (0,03 + 0,1 + 0,5) s = 0,63 s
5
35
Queste sono le caratteristiche reali del floppy drive Nec FD1231H da 1.44 MB, 3.5 pollici.
3.1.4 | E SERCIZIO *
Testo
La velocità di rotazione è uno dei parametri che incidono di più sulle
prestazioni generali. Un’elevata velocità di rotazione dei piatti significa che un
numero superiore di dati passa sotto la testina di lettura/scrittura nell'unità di
tempo.
L’unità di misura in cui si è soliti esprimere il regime di rotazione sono le
revolutions per minute, abbreviate in rpm e traducibili come rotazioni al minuto.
Gli hard disk da 3.5” per server e workstation ruotano a 10000 o 15000 giri al
minuto, mentre quelli per desktop solitamente lavorano a 7200 giri al minuto.
I drive per notebook tipicamente sono più lenti; in questo settore troviamo
principalmente drive da 5400 o 4200 rpm, anche se esistono modelli da 7200
rpm. Una ragione per la velocità inferiore riguarda il consumo energetico che
aumenta con l'aumentare della velocità di rotazione, e – come è noto – la
durata della batteria è un aspetto particolarmente caro ai costruttori di
portatili.6
Si consideri un disco magnetico con le seguenti caratteristiche:

velocità di trasferimento dati vtrasf = 1 Gb/s;

tempo medio di posizionamento in lettura tpos = 4 ms;
Si voglia trasferire 4 KB di dati, con 1 K = 210.
Si valutino le prestazioni del disco al variare della velocità di rotazione vrot,
considerando rispettivamente i valori 4200 rpm, 5400 rpm, 7200 rpm,
10000 rpm e infine 15000 rpm.
Si calcoli infine di quanto è più veloce il disco da 15000 rpm rispetto a quello
da 4200 rpm.
Si osservi che questo esercizio, pur considerando regimi di
rotazione reali, ha carattere più teorico che pratico. Infatti,
tipicamente anche i restanti parametri del disco, quali il
6
36
I dati riportati nel testo fanno riferimento all’anno 2009.
tempo di posizionamento e la velocità di trasferimento,
vengono progettati a seconda delle caratteristiche desiderate.
Soluzione
Il calcolo della somma:
ttot = tpos + tlat + ttrasf
per questo esercizio è fatto di due addendi fissi (tpos e ttrasf) e di uno variabile
(tlat). Cominciamo dal calcolo dei primi due.
Dal testo, si evince che il tempo di posizionamento è in ogni caso tpos = 4 ms.
Per quanto riguarda il tempo di trasferimento:
vtrasf = 1 Gb/s = (1/8) · 109 byte/s = 0,125 · 109 byte/s
0,125 · 109 : 212 = 1 : ttrasf
ttrasf = 0,000032768 s = 0,03 ms
Procediamo al calcolo dei tempi di latenza al variare dei regimi di rotazione.
vrot,4200 = 70 rps; tlat,4200 = (0,5 / 70) s = 7,14 ms; ttot,4200 = 11,17 ms
vrot,5400 = 90 rps; tlat,5400 = (0,5 / 90) s = 5,56 ms; ttot,5400 = 9,59 ms
vrot,7200 = 120 rps; tlat,7200 = (0,5 / 120) s = 4,17 ms; ttot,7200 = 8,2 ms
vrot,10000 = 166,67 rps; tlat,10000 = (0,5 / 166,67) s = 3 ms; ttot,10000 = 7,03 ms
vrot,15000 = 250 rps; tlat,15000 = (0,5 / 250) s = 2 ms; ttot,15000 = 6,03 ms
Per calcolare di quanto è più veloce il disco da 15000 rpm rispetto a quello da
4200 rpm, si può impostare la proporzione:
11,17 ms : 6,03 ms = 1 : x
x = 1,85 = 185%
Tale risultato mostra che il disco con regime di rotazione più alto ha
prestazioni poco meno che doppie rispetto all’altro.
Potrebbe sorprendere che un disco in grado di ruotare 3,5
volte più velocemente ottenga tempi meno che dimezzati, ma
si tenga in opportuna considerazione l’impatto notevole
dell’addendo fisso tpos.
37
3.2 | C APACITÀ DEI DISCHI MAGNETICI
I dischi magnetici sono caratterizzati dai seguenti parametri:

numero di piatti (platters) np – il numero di dischi magnetici vincolati a
ruotare assieme attorno a un perno centrale. Per i floppy, np = 1;

numero di testine (heads) nh – normalmente nh = 2·np dato che i piatti
hanno 2 superfici;

numero di tracce (tracks) o cilindri (cylinders) nc per lato – il numero di
tracce concentriche presenti su ciascuna faccia del disco e su cui le
testine possono leggere/scrivere i dati;

numero di settori (sectors) per traccia ns – il numero di archi in cui è
suddiviso
ciascuna
traccia
del
disco.
Nelle
nostre
ipotesi
semplificative, i dischi avranno lo stesso numero di settori su ogni
traccia, indipendentemente dalla distanza della traccia dal centro;

numero di byte per settore nb – storicamente tale valore è quasi
sempre di 512 byte/settore.
La capacità C di un hard disk composto fisicamente da più dischi è data
dalla relazione:
C = (nh · nc · ns · nb ) byte
38
3.2.1 | E SERCIZIO
Testo
Si calcoli la capacità di un disco magnetico con le seguenti caratteristiche:7
nc = 80 cilindri; nh = 2 testine; ns = 18 settori/traccia; nb = 512 byte/settore;
Si risolva poi l’esercizio ponendo nc = 40 cilindri e ns = 9 settori/traccia.8
Soluzione
C1 = (80 · 2 · 18 · 512) byte = 1474560 byte = 1440 KB ≈ 1,44 MB
C2 = (40 · 2 · 9 · 512) byte = 368640 byte = 360 KB
Qui sotto è riportata una tabella con i più comuni formati dei floppy disk.9
Platform
Size
Density
Bytes/sector
Sectors/track
Tracks/side
Sides
Capacity
RPM
IBM
(3740 format)
8 in
single
128
26
74
1
250.25 KB
360
1
113.75 KB
2
227.50 KB
1
140 KB
2
280 KB
1
400 KB
2
800 KB
2
1440 KB
1
170 KB
2
340 KB
13
Apple II
5¼ in
double
256
35
16
Apple II,
Apple
Macintosh
3½ in
(90 mm)
double
512
Variable
(8-12)
80
high
512
18
80
Commodore
(8-bit)
5¼ in
double
Commodore
Amiga
3½ in
(90 mm)
double
5¼ in
IBM PC
compatibles
3½ in
(90 mm)
high
double
256
512
Atari 8-bit
3½ in
(90 mm)
5¼ in
11
22
35
80
2
150
1
160/180 KB
2
320/360 KB
2
1200 KB
high
15
80
9
80
720 KB
18
80
1440 KB
21
80
21
82
1720 KB
36
80
2880 KB
512
15
1024
8
single
128
18
enhanced
128
26
double
256
18
high
80
2
2
300
300
double
512
300
880 KB
40
high
CLV
1760 KB
8/9
512
extended
NEC PC98
Variable
(17-21)
300
1680 KB
1200 KB
1280 KB
300
360
300
360
90 KB
40
1
127 KB
288
180 KB
Queste sono le caratteristiche reali del floppy disk da 3.5’’ a doppia faccia e alta densità per
PC IBM compatibili.
8 Queste sono le caratteristiche reali del floppy disk da 5.25’’ a doppia faccia e doppia densità
per PC IBM compatibili.
9 Fonte: http://en.wikipedia.org/wiki/Floppy_disk_format
7
39
3.2.2 | E SERCIZIO
Testo
Si calcoli la capacità dei seguenti dischi:
 Disco 1: Western Digital Caviar AC2170
o nh = 6 testine;
o nc = 1010 cilindri;
o ns = 55 settori/traccia;
o nb = 512 byte/settore;
 Disco 2: Quantum Fireball 1080AT
o nh = 16 testine;
o nc = 2112 cilindri;
o ns = 63 settori/traccia;
o nb = 512 byte/settore;
Soluzione
C1 = (6·1010·55·512) byte = 170649600 byte = 162,7 MB
C2 = (16·2112·63·512) byte = 1089994752 byte = 1039,5 MB ≈ 1 GB
40
4 | RAPPRESENTAZIONE DEI NUMERI
4.1 | C ONVERSIONI DA BASE N A BASE 10
Nel corso del presente paragrafo e dei seguenti, si adotterà la notazione a
pedice per indicare esplicitamente la base in cui è scritto un numero. Ad
esempio, la notazione x = 1012 significa che il numero x è espresso in base 2
e pertanto le cifre 101 devono essere interpretate in base 2, e non lette come
“centouno”.
Gli esercizi contrassegnati con un asterisco sono da considerarsi di
approfondimento.
41
4.1.1 | E SERCIZIO
Testo
Si svolgano i seguenti esercizi di conversione da base 2 a base 10:
x = 11012
y = 100101012
z = 1010010112
Soluzione
x = 11012 =
= (1·23 + 1·22 + 0·21 + 1·20)10 =
= (8 + 4 + 0 + 1)10 =
= 1310
y = 100101012 =
= (1·27 + 0·26 + 0·25 + 1·24 + 0·23 + 1·22 + 0·21 + 1·20)10 =
= (128 + 16 + 4 + 1)10 =
= 14910
z = 1010010112 =
= (1·28 + 0·27 + 1·26 + 0·25 + 0·24 + 1·23 + 0·22 + 1·21 + 1·20)10 =
= 33110
42
4.1.2 | E SERCIZIO
Testo
Si svolgano i seguenti esempi di conversione da base 16 a base 10:
x = CD16
y = 10A16
z = B7F16
Soluzione
x = CD16 =
= (12·161 + 13·160)10 =
= 20510
y = 10A16 =
= (1·162 + 0·161 + 10·160)10 =
= 26610
z = B7F16 =
= (11·162 + 7·161 + 15·160)10 =
= 294310
43
4.1.3 | E SERCIZIO
Testo
Si svolgano i seguenti esempi di conversione da base n a base 10:
x = 3415
y = 1526
z = 5348
Soluzione
x = 3415 =
= (3·52 + 4·51 + 1·50)10 =
= 9610
y = 1526 =
= (1·62 + 5·61 + 2·60)10 =
= 6810
z = 5348 =
= (5·82 + 3·81 + 4·80)10 =
= 34810
44
4.1.4 | E SERCIZIO *
Testo
Si determinino due possibili basi a e b tali da rendere verificata la seguente
uguaglianza: 32a = 22b
Soluzione
Portando entrambi i membri dell’uguaglianza in base 10, si ha:
32a = (3·a1 + 2·a0)10 = (3a + 2)10
e
22b = (2·b1 + 2·b0)10 = (2b + 2)10
Di conseguenza:
a = (2/3)b
Convenzionalmente, le basi sono numeri interi maggiori di 1. Ad esempio la
scelta b = 2 sarebbe accettabile su b, ma non su a (che risulterebbe non
intera). Per rispettare tali vincoli, va scelto per b un qualsiasi valore intero
positivo multiplo di 3. In termini matematici:
b = 3k, con k 
Ad esempio, per b = 3 e dunque a = 2) si ha:
32a = 322 = 810
22b = 223 = 810.
Analogamente, per b = 6 e dunque a = 4, si ha:
32a = 324 = 1410
22b = 226 = 1410.
45
4.1.5 | E SERCIZIO
Testo
Si svolgano i seguenti esempi di conversione da base n a base 10, aventi per
soggetto numeri frazionari:
x = 100,1012
y = 1202,113
z = 32,024
Soluzione
x = 100,1012 =
= (1·22 + 1·2-1 + 1·2-3)10 =
= (4 + 1/2 + 1/8)10 =
= 4,62510
y = 1202,113 =
= (1·33 + 2·32 + 2·30 + 1·3-1 + 1·3-2)10 =
= (27 + 18 + 2 + 1/3 + 1/9)10 ≈
≈ 47,4310
z = 32,024 =
= (3·41 + 2·40 + 2·4-2)10 =
= (12 + 2 + 2/16)10 =
= 14,12510
46
4.2 | C ONVERSIONI DA BASE 10 A BASE N
Nel corso del presente paragrafo saranno proposti esercizi di conversione da
base 10 a base n su numeri interi e su numeri frazionari in virgola fissa. Nel
primo caso sarà sufficiente l’applicazione del cosiddetto metodo delle
divisioni successive. Invece, per quanto riguarda la sola parte frazionaria dei
numeri (ove presente), sarà richiesta l’applicazione del metodo delle
moltiplicazioni successive.
47
4.2.1 | E SERCIZIO
Testo
Si utilizzi il metodo delle divisioni successive per convertire da base 10 a base
3 il numero intero x = 4610. Si utilizzi in seguito il processo di conversione da
base 3 a base 10 come verifica del risultato ottenuto.
Soluzione
Il metodo delle divisioni successive impone di dividere ripetutamente per la
base, mantenendo traccia tanto del quoziente intero (cui va applicata la
divisione successiva) quanto del resto della divisione intera. Il processo ha
termine quando si ottiene un valore 0 come quoziente. A questo punto, il
risultato della conversione è dato dalla lettura ordinata dei resti, ove la cifra
più significativa è data dall’ultimo resto ottenuto e la meno significativa dal
primo. Nel caso di una rappresentazione grafica come quella sotto proposta,
la colonna di destra va letta dal basso verso l’alto.
46 3
15 1
5 0
1 2
0 1
x = 12013 = (1·33 + 2·32 + 1·30)10 = (27 + 18 + 1)10 = 4610
48
4.2.2 | E SERCIZIO
Testo
Si utilizzi il metodo delle divisioni successive per convertire da base 10 a base
8 il numero intero x = 648. Si utilizzi in seguito il processo di conversione da
base 8 a base 10 come verifica del risultato ottenuto.
Soluzione
Tramite il metodo delle divisioni successive:
64 8
8 0
1 0
0 1
x = 1008 = (1 · 82)10 = 6410
Osservazione di carattere generale: quando il numero da convertire è una
potenza esatta della base, il risultato sarà dato dalla cifra 1 seguita da un
numero di cifre 0 pari all’esponente di tale potenza.
Ad esempio, si voglia esprimere x = 4910 in base 7. Come è noto, 4910 = (72)10
pertanto il numero risultate sarà dato da una cifra 1 seguita da 2 zeri. In
effetti: x = 1007 = (1 · 72)10 = 4910
Analogamente, y = 6410 = (26)10 = 10000002
49
4.2.3 | E SERCIZIO
Testo
Si utilizzi il metodo delle moltiplicazioni successive per convertire da base 10
a base 2 il numero frazionario x = 0,562510. Si utilizzi in seguito il processo di
conversione da base 2 a base 10 come verifica del risultato ottenuto.
Soluzione
Il metodo delle moltiplicazioni successive si applica alla sola parte frazionaria
di un numero. Si osservi che in questo caso il numero x da convertire
presenta solo parte frazionaria.
L’algoritmo richiede di moltiplicare per la nuova base (in questo caso per 2)
la parte frazionaria, ottenendo così un numero virtualmente composto da una
parte intera (non sempre presente) e una frazionaria. Le due parti vengono
scorporate in vista del passaggio successivo. Nella rappresentazione grafica
sotto riportata, la parte intera trova posto nella colonna di sinistra e quella
frazionaria nella colonna di destra. Se il risultato della moltiplicazione
presenta solo parte frazionaria, nella prima colonna si segna uno zero. Al
passaggio successivo, si effettua nuovamente la moltiplicazione della sola
parte frazionaria ottenuta al passaggio precedente.
L’algoritmo ha termine quando:
1. la parte frazionaria risultante è pari a 0, oppure
2. si è svolto il numero di passaggi richiesto (si osservi che ogni
passaggio calcola una nuova cifra dopo la virgola).
Infine, il risultato è dato dalla sequenza delle sole parti intere (nella nostra
rappresentazione la colonna di sinistra). Queste vanno lette dalla prima, che
dà la cifra più significativa, all’ultima, che fornisce la meno significativa (nel
nostro caso, dall’alto verso il basso).
50
0,5625 2
0,5625 · 2 = 1,125 = 1 + 0,125
1 0,125 0,125 · 2 = 0,25 = 0 + 0,25
0 0,25
0,25 · 2 = 0,5 = 0 + 0,5
0 0,5
0,5 · 2 = 1 = 1 + 0
1 0
x = 0,10012 = (1/2 + 1/16)10 = 0,562510
Si osservi che in questo caso specifico l’algoritmo ha termine in quanto
compare uno zero nella colonna di destra dopo un numero finito di passaggi.
Questo peraltro garantisce che la parte frazionaria sia esprimibile nella nuova
base senza commettere alcun errore di arrotondamento.
51
4.2.4 | E SERCIZIO
Testo
Si converta da base 10 a base 5 il numero frazionario x = 29,2410. Si utilizzi in
seguito il processo di conversione da base 5 a base 10 come verifica del
risultato ottenuto.
Soluzione
In questo caso, il numero x presenta una parte intera ed una parte frazionaria.
E’ dunque necessario procedere scomponendo x nella sola componente
intera x1 = 2910 e nella sola parte frazionaria x2 = 0,2410.
Su x1 si utilizzerà il metodo delle divisioni successive, mentre su x2 il metodo
delle moltiplicazioni successive.
Tramite il metodo delle divisioni successive:
29 5
5 4
1 0
0 1
x1 = 1045 = (1·52 + 4·50)10 = 2910
Tramite il metodo delle moltiplicazioni successive:
0,24 5
1 0,2
0,24 · 5 = 1,2 = 1 + 0,2
0,2 · 5 = 1 = 1 + 0
1 0
x2 = 0,115 = (1·5-1 + 1·5-2)10 = (1/5 + 1/25)10= 0,2410
In definitiva x = x1 + x2 = 104,115
La controprova di conversione da base 5 a base 10 è già stata effettuata sulle
singole componenti. Ovviamente, poteva essere eseguita in un unico
passaggio anche dopo il calcolo del risultato finale.
52
4.2.5 | E SERCIZIO
Testo
Si converta da base 10 a base 2 il numero frazionario x = 13,310 fermandosi
all’ottava cifra dopo la virgola. Si utilizzi in seguito il processo di conversione
da base 2 a base 10 per calcolare e1, ossia l’errore di arrotondamento
introdotto. Si valuti infine l’errore e2 che si sarebbe commesso fermandosi alla
sola seconda cifra dopo la virgola.
Soluzione
Anche in questo caso, il numero x presenta una parte intera ed una parte
frazionaria. E’ dunque necessario procedere scomponendo x nella sola
componente intera x1 = 1310 e nella sola parte frazionaria x2 = 0,310.
Tramite il metodo delle divisioni successive:
13 2
6 1
3 0
1 1
0 1
x1 = 11012
Si osservi che qualsiasi numero intero, in qualsiasi base, è
sempre esprimibile tramite un numero finito di cifre. Infatti,
la cifra meno significativa del risultato ha la granularità
delle unità.
53
Tramite il metodo delle moltiplicazioni successive:
0,3 2
0,3 · 2 = 0,6 = 0 + 0,6
0 0,6
0,6 · 2 = 1,2 = 1 + 0,2
1 0,2
0,2 · 2 = 0,4 = 0 + 0,4
0 0,4
0,4 · 2 = 0,8 = 0 + 0,8
0 0,8
0,8 · 2 = 1,6 = 1 + 0,6
1 0,6
0,6 · 2 = 1,2 = 1 + 0,2
1 0,2
0,2 · 2 = 0,4 = 0 + 0,4
0 0,4
0,4 · 2 = 0,8 = 0 + 0,8
0 0,8
0,8 · 2 = 1,6 = 1 + 0,6
x2 = 0,010011002
Si osservi che, in mancanza dell’indicazione sul numero di cifre da calcolare
(e dunque sul numero di passaggi da effettuare), l’algoritmo non avrebbe mai
raggiunto un punto finale. Ad esempio, confrontando il II e il VI passaggio,
si nota il ripetersi di un’identica situazione (parte intera = 1, parte
frazionaria = 0,2). Pertanto il risultato ottenibile sarà sempre approssimato, e
l’approssimazione sarà via via migliore procedendo nel calcolo.
x = x1 + x2 ≈ 1101,010011002 = (13 + 1/4 + 1/32 + 1/64)10 = 13,29687510
Errore e1 = x - xapprox = 13,3 - 13,296875 = 0,003125.
Errore e2 = 13,3 - 13,25 = 0,05 ossia un errore assai più rilevante rispetto a e1.
54
4.3 | C ONVERSIONI DA BASE M A BASE N
Poiché rappresentare un numero in una base piuttosto che in un’altra non ne
varia il significato semantico (ossia la quantità sottesa dal numero) ma solo la
scrittura, è sempre possibile convertire un numero da una base m a una base n
con m ed n generici.
Un primo metodo, puramente basato su quanto visto in precedenza, consiste
nell’utilizzare la base 10 come passaggio intermedio. In altri termini, il
numero x viene prima convertito da base m a base 10, per poi essere
nuovamente convertito da base 10 a base n.
In alcuni casi, è invece possibile (e particolarmente semplice) effettuare una
conversione diretta, senza passare dalla base 10: ciò avviene quando
n = mk oppure m = nk, con k 
In altri termini, se le basi di origine e di destinazione sono l’una potenza
dell’altra, è applicabile un metodo di conversione diretta. Questa può essere
svolta per sostituzione di gruppi di cifre invece che con algoritmi di divisione.
Se n = mk, allora k cifre del numero nella base originaria m vengono sostituite
con singole cifre nella nuova base n. E’ il caso di m = 2 ed n = 16, ad
esempio.
Viceversa, se m = nk, allora ogni singola cifra del numero nella base originaria
m viene espansa in k cifre nella nuova base n. E’ il caso di m = 9 ed n = 3, ad
esempio.
Nel seguito si proporranno anche esercizi di conversione diretta.
55
4.3.1 | E SERCIZIO
Testo
Si converta x = 249 in binario.
Soluzione
La soluzione prevede una doppia conversione: da base 9 a base 10, quindi da
base 10 in base 2.
x = 249 = (2·91 + 4·90)10 = 2210
Con il metodo delle divisioni successive:
22 2
11 0
5 1
2 1
1 0
0 1
x = 249 = 101102
56
4.3.2 | E SERCIZIO
Testo
Si converta x = 102345 in base 7.
Soluzione
La soluzione prevede una doppia conversione: da base 5 a base 10, quindi da
base 10 in base 7.
x = 102345 = (1·54 + 2·52 + 3·51 + 4·50)10 = 69410
Con il metodo delle divisioni successive:
694 7
99 1
14 1
2 0
0 2
x = 102345 = 20117
57
4.3.3 | E SERCIZIO
Testo
Si converta il numero binario x = 110110002 in esadecimale utilizzando il
metodo diretto.
Allo stesso modo si converta il numero esadecimale x = AD0216 in binario.
Soluzione
Le basi di origine e destinazione sono rispettivamente m = 2 ed n = 16, ed n è
una potenza di m. In particolare, n = m4 il che rende possibile operare la
conversione tramite un algoritmo di sostituzione: 4 cifre del numero in base
m verranno sostituite da 1 cifra del numero in base n, secondo lo schema:
2
16
0000
0
0001
1
0010
2
0011
3
0100
4
0101
5
0110
6
0111
7
1000
8
1001
9
1010
A
1011
B
Per evidenziare graficamente i gruppi di cifre da sostituire, si utilizzeranno
delle linee verticali.
Pertanto:
x = 110110002 = 11012|10002 = D816
Procedendo invece per espansione, si ottiene:
y = A16|D16|016|216 = 10102|11012|00002|00102 = 10101101000000102
58
1100
C
1101
D
1110
E
1111
F
4.3.4 | E SERCIZIO
Testo
Si converta il numero binario x = 10010112 in ottale utilizzando il metodo
diretto.
Soluzione
Le basi di origine e destinazione sono rispettivamente m = 2 ed n = 8, ed n è
una potenza di m. In particolare, n = m3 il che suggerisce di raggruppare le
cifre in gruppi da 3 ed applicare lo schema di sostituzione:
2
8
000
0
001
1
010
2
011
3
100
4
101
5
110
6
111
7
Procediamo ora all’evidenziazione dei gruppi da sostituire. Si osservi che in
questo caso il numero di cifre di x in base 2 non è un multiplo di 3.
Sarebbe errato procedere a un raggruppamento di questo tipo:
x = 1002|1012|12
in quanto tale scrittura sottende implicitamente y = 1001010012 ed è
immediato verificare (ad esempio convertendo entrambi in base 10) che
x ≠ y.
Il modo corretto di procedere è il seguente: aggiungere le cifre necessarie ad
arrivare a un multiplo di 3 ponendo degli zeri come cifre più significative, in
quanto:
10010112 = 0010010112
Ragionando in base 10, sarebbe come riscrivere il numero
45 come 045 o 0045: ne cambia la rappresentazione
grafica, ma non la semantica. Diverso sarebbe riscrivere 45
come 405 o 4500!
A questo punto, si può procedere nel raggruppamento:
x = 0012|0012|0112 = 1138
59
4.3.5 | E SERCIZIO
Testo
Si converta il numero x = 2123 in base 9, ed il numero y = 8319 in base 3.
Soluzione
Nel caso di x, le basi di origine e destinazione sono rispettivamente m = 3 ed
n = 9, con n = m2. Di conseguenza è necessario raggruppare le cifre in gruppi
da 2, aggiungere eventuali zeri all’inizio ed applicare lo schema di
sostituzione:
3
9
00
0
01
1
02
2
10
3
11
4
12
5
20
6
21
7
22
8
Ne risulta:
x = 2123 = 023|123 = 259
Come verifica, è sempre possibile convertire entrambe le rappresentazioni in
base 10 e verificarne l’uguaglianza.
x = 2123 = (2·32 + 1·31 + 2·30)10 = (18 + 3 + 2)10 = 2310
x = 259 = (2·91 + 5·90)10 = (18 + 5)10 = 2310
Per quanto riguarda y:
y = 8319 = 223|103|013 = 2210013
Verifica:
y = 8319 = (8·92 + 3·91 + 1·90)10 = (648 + 27 + 1)10 = 67610
y = 2210013 = (2·35 + 2·34 + 1·33 + 1·30)10 = (486 + 162 + 27 + 1)10 =
= 67610
60
4.3.6 | E SERCIZIO *
Testo
Si consideri la codifica US-ASCII dei caratteri alfanumerici.
Si codifichi la parola “Computer” in esadecimale sfruttando la seconda
colonna della tabella sotto riportata, e si provveda quindi a rappresentarla in
base 2 come una stringa di 8 bit.
Soluzione
Sfruttando la tabella della codifica ASCII si giunge alla seconda riga della
tabella sotto riportata. Infine, la terza riga è ottenuta per espansione dei
caratteri esadecimali.
C
4 3
o
6 F
6
m
D
p
7 0
u
7 5
t
7 4
e
6 5
r
7 2
01000011 01101111 01101101 01110000 01110101 01110100 01100101 01110010
61
4.4 | O PERAZIONI ARITMETICHE
In questo paragrafo verrà affrontato l’argomento delle operazioni aritmetiche
elementari in base 2. Tali operazioni sono:

addizione o somma

sottrazione o differenza

moltiplicazione o prodotto

divisione
Si rammenta che la scelta della base non influenza le proprietà delle
operazioni aritmetiche, che pertanto si mantengono anche in base 2. Ad
esempio, le proprietà commutativa e associativa della somma sono
indipendenti dalla base, così come il fatto che lo 0 ne sia l’elemento neutro10
(in qualunque base lo si rappresenti).
Analogamente, i procedimenti appresi nei propri studi primari potranno
essere applicati alla nuova base, considerando però che il numero di regole da
imparare per ciascun operatore aritmetico è limitato a 22. Infatti, per ogni
operatore a 2 ingressi, l’uscita generica è data dallo studio di tutte le
combinazioni in ingresso, che nell’algebra binaria sono 2 per ciascun
ingresso.
In base 10, la determinazione di tutte le combinazioni in
ingresso porta allo studio di 102 casi differenti. Ad esempio,
le regole dell’addizione (operatore +) contemplano:
0 + 0 ; 0 + 1 ; 0 + 2; … ; 9 + 7 ; 9 + 8 ; 9 + 9.
Nel corso del presente paragrafo si prenderanno in considerazione i numeri
non negativi (sia come operandi che come risultati delle operazioni
aritmetiche), rimandando al prossimo paragrafo la rappresentazione dei valori
negativi e le relative operazioni.
Il risultato della somma di un qualsiasi numero n con lo 0 (elemento neutro) dà il numero
n stesso. L’elemento neutro della moltiplicazione è l’1.
10
62
4.4.1 | E SERCIZIO
Testo
Una volta convertiti gli addendi dalla base 10 alla base 2, si effettui
l’operazione di addizione in base 2 avendo cura di evidenziare gli eventuali
riporti; infine si verifichi il risultato riconvertendolo in base 10.
v = a + b = 1310 + 610
w = c + d = 910 + 710
x = e + f = 7310 + 1010
y = g + h = 9110 + 4610
z = i + l = 5,7510 + 2,510
Soluzione
Le quattro regole da applicare sono le seguenti:

0+0=0

0+1=1

1+0=1

1 + 1 = 0 con il riporto di 1
Alla luce di queste semplici regole, è possibile procedere nel calcolo seguendo
i procedimenti appresi nei propri studi primari lavorando in base 10.
a = 1310 = 11012
1101 +
110 =
b = 610 = 1102
1
v = 100112 = (1·2 + 1·2 + 1·2 )10 = 1910
4
1
0
10011
c = 910 = 10012
1001 +
111 =
d = 710 = 1112
1 1 1
w = 100002 = (1·2 )10 = 1610
4
e = 7310 = 10010012
f = 1010 = 10102
x = 10100112 = (1·26 + 1·24 + 1·21 + 1·20)10 = 8310
63
10000
1001001 +
1010 =
1
1010011
g = 9110 = 10110112
1011011 +
101110 =
h = 4610 = 1011102
1 1 1 1 1 1
y = 100010012 = (1·27 + 1·23 + 1·20)10 = 13710
10001001
Attenzione: considerando i riporti, sulla quarta cifra da destra si verifica la
necessità di calcolare 1 + 1 + 1, che non è immediatamente risolvibile
applicando le quattro regole elementari sopra esposte. In questo caso,
intuitivamente, si può estendere la regola “1 + 1 = 0 con il riporto di 1”
considerando “1 + 1 + 1 = 1 con il riporto di 1”. Però, in generale serve
saper gestire la somma di un numero arbitrario di 1 in colonna.11 In casi
particolarmente complessi, è possibile applicare la proprietà associativa della
somma:
a + b + c = (a + b) + c
In tal modo, l’operazione può essere suddivisa in più operazioni elementari,
ove risultano sempre applicabili le regole base dell’addizione.
i = 5,7510 = 101,112
101,11 +
10,10 =
l = 2,510 = 10,12
1 1 1 1
z = 1000,012 = (1·23 + 1·2-2)10 = 8,2510
1000,01
La somma di numeri espressi in virgola fissa segue le stesse regole sopra
esposte,
con
l’accortezza
di
allineare
le
virgole
e
aggiungere
conseguentemente degli 0 come cifre meno significative ove richiesto.
Si vedano a questo proposito gli esercizi sulla moltiplicazione, che per essere risolti
manualmente richiedono la somma di tanti addendi quante sono le n cifre non nulle del
secondo fattore. In tal caso, si potrebbero trovare fino a n 1 da sommare in colonna.
11
64
4.4.2 | E SERCIZIO
Testo
Una volta convertiti i valori dalla base 10 alla base 2, si effettui l’operazione
di sottrazione in base 2 avendo cura di evidenziare gli eventuali prestiti; infine
si verifichi il risultato riconvertendolo in base 10.
v = a - b = 1310 - 410
w = c - d = 2310 - 1310
x = e - f = 2610 - 510
y = g - h = 910 - 710
z = i - l = 12, 510 - 110
Soluzione
Le quattro regole da applicare sono le seguenti:

0-0=0

0 - 1 = 1 con il prestito di 1

1-0=1

1-1=0
Alla luce di queste semplici regole, è possibile procedere nel calcolo seguendo
i procedimenti appresi nei propri studi primari lavorando in base 10.
a = 1310 = 11012
1101 100 =
1001
b = 410 = 1002
v = 10012 = (1·23 + 1·20)10 = 910
c = 2310 = 101112
10111 +
1101 =
d = 1310 = 11012
1
w = 10102 = (1·2 + 1·2 )10 = 1010
3
1
e = 2610 = 110102
f = 510 = 1012
x = 101012 = (1·24 + 1·22 + 1·20)10 = 2110
65
1010
11010 +
101 =
1
1
10101
g = 910 = 10012
1001 +
111 =
h = 710 = 1112
1
y = 102 = (1·21)10 = 210
0010
Attenzione: considerando i prestiti, sulla terza cifra da destra si verifica la
necessità di calcolare 0 – (1 + 1), che non è immediatamente risolvibile
applicando le quattro regole elementari sopra esposte. In questo caso, si può
tenere presente che (1 + 1)2 = 102 e procedere da qui in avanti ponendo le 2
cifre più significative di h a 10. In casi più complessi, è possibile applicare la
proprietà:
a – (b + c) = (a – b) – c
In tal modo, l’operazione può essere suddivisa in più operazioni elementari,
ove risultano sempre applicabili le regole base della sottrazione.
i = 12,510 = 1100,12
1100,1 +
1,0 =
l = 110 = 12
1 1
z = 1011,12 = (1·2 + 1·2 + 1·2 + 1·2 )10 = 11,510
3
1
0
-1
1011,1
La differenza di numeri espressi in virgola fissa segue le stesse regole sopra
esposte,
con
l’accortezza
di
allineare
le
virgole
e
aggiungere
conseguentemente degli 0 come cifre meno significative ove richiesto.
L’introduzione della notazione in complemento a 2 per
rappresentare i valori negativi renderà sostanzialmente
inutile l’operazione di differenza, che verrà implementata
come operazione di somma tra valori con segno. Ad
esempio, l’operazione
a=b–c
verrà gestita come
a = b + (-c)
66
4.4.3 | E SERCIZIO
Testo
Una volta convertiti i fattori dalla base 10 alla base 2, si effettui l’operazione
di moltiplicazione in base 2; infine si verifichi il risultato riconvertendolo in
base 10.
v = a · b = 910 · 210
w = c · d = 9210 · 410
x = e · f = 2810 · 510
y = g · h = 2310 · 710
z = i · l = 2,510 · 310
Soluzione
Le quattro regole da applicare sono le seguenti:

0·0=0

0·1=0

1·0=0

1·1=1
Tali regole possono anche essere sintetizzate come segue: qualsiasi cifra
moltiplicata per 0 dà 0, e qualsiasi cifra moltiplicata per 1 dà la cifra stessa.
Nell’ottica del procedimento manuale di risoluzione, si osservi che in
generale qualsiasi numero moltiplicato per 0 dà 0, e qualsiasi numero
moltiplicato per 1 dà il numero stesso. Queste regole rendono
particolarmente agevole la costruzione degli addendi che poi portano al
risultato finale. Graficamente, nell’addizione conclusiva si utilizzerà un
trattino (che rappresenta più propriamente una cifra 0) come segno di
spaziatura.
a = 910 = 10012
b = 210 = 102
v = 100102 = (1·24 + 1·21)10 = 1810
67
1001 ×
10 =
0
100110010
c = 9210 = 10111002
d = 410 = 1002
w = 1011100002 = (1·28 + 1·26 + 1·25 + 1·24)10 =
= 36810
1011100 ×
100 =
0
01011100-101110000
Dall’analisi dei risultati in binario ottenuti per v e w,
enunciamo una regola generale: moltiplicando una stringa di
bit arbitraria per un’altra stringa costituita da un solo 1
seguito da n 0 (che chiaramente corrisponde a una potenza
di 2), si ottiene uno shift verso sinistra della prima stringa
per un numero di posizioni n (riempite con altrettanti 0 nel
risultato).
Dal punto di vista matematico, questo è facilmente
deducibile. Ragionando in base 10 sul primo esempio:
10012·102 = ((1 · 23 + 1 · 20) · 21)10 =
= (1 · 23 · 21 + 1 · 20 · 21)10 =
= (1 · 24 + 1 · 21)10 =
= 100102
e = 2810 = 111002
f = 510 = 1012
x = 100011002 = (1·27 + 1·23 + 1·22)10 = 14010
11100 ×
101 =
11100
011100-1 1 1
10001100
g = 2310 = 101112
h = 710 = 1112
y = 102 = (1·21)10 = 210
10111 ×
111 =
10111
1011110111-1
?????01
68
In questo caso sulla terza colonna si verifica la necessità di sommare quattro
1. Applicando la proprietà distributiva della somma, è possibile computare il
risultato spezzando la somma in due operazioni di addizione:
t = (10111 + 101110)2
y = t + 10111002 = 101000012 = 16110
i = 2,510 = 10,12
l = 310 = 112
z = 111,12 = (1·22 + 1·21 + 1·20 + 1·2-1)10 = 7,510
69
10,1 ×
11 =
10 1
101 111,1
4.4.4 | E SERCIZIO
Testo
Una volta convertiti dividendi e divisori dalla base 10 alla base 2, si effettui
l’operazione di divisione intera in base 2; infine si verifichi il risultato
riconvertendolo in base 10.
x = a / b = 2510 / 510
y = c / d = 2310 / 710
z = e / f = 13410 / 210
Soluzione
Le regole da applicare si riconducono a soli 2 casi:

o il divisore è contenuto 1 volta nel dividendo, e il resto è dato da
dividendo meno divisore;

oppure il divisore è contenuto 0 volte nel dividendo, e il resto è dato
dall’intero dividendo.
x = a / b = 2510 / 510 = 110012 / 1012
I passaggio: quante volte sta 101 in 1? 0
11001 / 101 = 00101
volte con il resto di 1 – 0 = 1.
11
II passaggio: aggiungo in coda al resto la
110
seconda cifra del dividendo, ossia 1.
10
Quante volte sta 101 in 11? 0 volte con il
101
resto di 11 – 0 = 11.
0
III passaggio: aggiungo in coda al resto la terza cifra del dividendo, ossia 0.
Quante volte sta 101 in 110? 1 volta con il resto di 110 – 101 = 1.
IV passaggio: aggiungo in coda al resto la quarta del dividendo, ossia 0.
Quante volte sta 101 in 10? 0 volte con il resto di 10 – 0 = 10.
V passaggio: aggiungo in coda al resto la quinta cifra del dividendo, ossia 1.
Quante volte sta 101 in 101? 1 volta con il resto di 101 – 101 = 0.
x = 110012 / 1012 = 1012 = 510 con resto 0.
70
y = c / d = 2310 / 710 = 101112 / 1112
I passaggio: quante volte sta 111 in 1? 0
10111 / 111 = 00011
volte con il resto di 1 – 0 = 1.
10
II passaggio: aggiungo in coda al resto la
101
seconda cifra del dividendo, ossia 0.
1011
Quante volte sta 111 in 10? 0 volte con il
1001
resto di 10 – 0 = 10.
10
III passaggio: aggiungo in coda al resto la terza cifra del dividendo, ossia 1.
Quante volte sta 111 in 101? 0 volte con il resto di 101 – 0 = 101.
IV passaggio: aggiungo in coda al resto la quarta del dividendo, ossia 1.
Quante volte sta 111 in 1011? 1 volta con il resto di 1011 – 111 = 100.
V passaggio: aggiungo in coda al resto la quinta cifra del dividendo, ossia 1.
Quante volte sta 111 in 1001? 1 volta con il resto di 1001 – 111 = 10.
x = 110012 / 1012 = 112 = 310 con resto 102 = 210.
z = e / f = 13410 / 210= 100001102 / 102
10000110 / 10 = 01000011
10
00
00
00
01
11
10
0
z = 100001102 / 102 = 10000112 = 6710 con resto 0.
71
4.5 | N UMERI NEGATIVI
Esistono differenti metodi alternativi per rappresentare i numeri negativi in
binario. Tra questi, ricordiamo:
1. Segno e modulo;
2. Complemento a 1;
3. Complemento a 2;
4. Notazione in eccesso n.
Nei primi tre casi, il bit più significativo è utilizzato per la codifica del segno:
0 denota il segno positivo e 1 denota il segno negativo. Si osservi che i
numeri non negativi presentano la stessa codifica in segno e modulo,
complemento a 1 e complemento a 2.
Nel quarto caso, invece, le stringhe binarie il cui bit più significativo è posto
a 1 indicano valori non negativi, mentre le stringhe che iniziano per 0
rappresentano valori negativi.
72
4.5.1 | E SERCIZIO
Testo
Si indichi esplicitamente l’intervallo di valori rappresentabili con i 4 metodi
sopra esposti quando il numero di bit n che compone la stringa binaria è pari
a 5.
Soluzione
Ricordiamo che in segno e modulo ed in complemento a 1 l’intervallo di
valori rappresentabili è:
[–(2n - 1 – 1) … +(2n - 1 – 1)]
Pertanto, per n = 5:
[–(24 – 1) … +(24 – 1)]
[–15 … +15]
In complemento a 2 e in notazione eccesso x, l’intervallo di valori
rappresentabili diventa:
[–2n - 1 … +(2n - 1 – 1)]
Pertanto, per n = 5:
[–16 … +15]
Attenzione: in questo caso, il quarto metodo non prende il
nome di notazione eccesso 5. Infatti, il valore numerico che
segue la parola “eccesso” è dato dalla differenza tra il valore
positivo normalmente codificato dalla stringa 10000
(quindi ignorando il bit di segno)12 e quello attribuito
arbitrariamente a tale combinazione di bit, ossia lo 0. Con
5 bit, si parla di notazione eccesso 16.
12 Più genericamente, da una stringa di n bit in cui il solo bit più significativo è posto a 1 e
tutti i successivi bit sono posti a 0.
73
4.5.2 | E SERCIZIO
Testo
Si considerino i quattro metodi di rappresentazione dei numeri negativi sopra
esposti. Sia n = 4 il numero di bit disponibile per la codifica dei valori
numerici. Si dica quali metodi consentono di rappresentare il valore +7, e
quali il valore -8.
Soluzione
Applicando le formule dell’esercizio precedente, si evince che gli intervalli di
valori rappresentabili con 4 bit sono rispettivamente

Segno e modulo: [–7 … +7]

Complemento a 1: [–7 … +7]

Complemento a 2: [–8 … +7]

Notazione eccesso 8: [–8 … +7]
Di conseguenza, tutti i metodi sono in grado di rappresentare il valore +7,
mentre solo gli ultimi due presentano all’interno dell’intervallo il valore –8.
Tentare di rappresentare il valore –8 in segno e modulo o in complemento a
1 provocherebbe un errore di overflow, ossia di travalicamento dell’intervallo di
valori rappresentabili.
74
4.5.3 | E SERCIZIO
Testo
Si rappresentino i seguenti valori rispettivamente nelle notazioni in segno e
modulo, complemento a 1 e complemento a 2. Si utilizzino 8 bit per le
stringhe binarie così ottenute.
a = 1310
b = –310
c = –1510
d = –2010
e = –7210
Soluzione
a ha valore positivo, per cui la sua rappresentazione è identica in tutte le
notazioni. E’ sufficiente preporre come bit più significativo lo 0 (segno +) e
quindi rappresentare sui restanti 7 bit il modulo di a. Utilizzando ad esempio
il metodo delle divisioni successive, si ottiene |a| = 1310 = 11012. Pertanto:
a= 0 0 0 0 1 1 0 1
Nel caso di valori negativi, è comunque necessario calcolare la
rappresentazione binaria su n bit del modulo.
|b| = 310 = 112
In segno e modulo:
b= 1 0 0 0 0 0 1 1
In complemento a 1, la rappresentazione su 8 bit del modulo va
complementata.
|b|= 0 0 0 0 0 0 1 1
b= 1 1 1 1 1 1 0 0
Infine, il complemento a 2 condivide i primi passi della procedura del
complemento a 1, ma infine è necessario sommare 1 al complemento.
|b|= 0 0 0 0 0 0 1 1
b= 1 1 1 1 1 1 0 1
Si osservi qual è il legame tra |b| e b in complemento a 2:
la stringa binaria, letta da destra verso sinistra, è identica
75
fino al primo 1 compreso, e viene complementata per i
restanti bit. Tale regola è del tutto generale, e può essere
utilizzata validamente come scorciatoia nei calcoli o come
verifica della correttezza del risultato.
Ripetiamo ora il procedimento per c.
|c| = 1510 = 11112
In segno e modulo:
c=
1 0 0 0 1 1 1 1
In complemento a 1:
|c|=
0 0 0 0 1 1 1 1
c= 1 1 1 1 0 0 0 0
Infine, il complemento a 2 condivide i primi passi della procedura del
complemento a 1, ma infine è necessario sommare 1 al complemento.
|c|=
0 0 0 0 1 1 1 1
c= 1 1 1 1 0 0 0 1
Analogamente:
|d| = 2010 = 101002
In segno e modulo:
d= 1 0 0 1 0 1 0 0
In complemento a 1:
|d|= 0 0 0 1 0 1 0 0
d= 1 1 1 0 1 0 1 1
In complemento a 2:
|d|= 0 0 0 1 0 1 0 0
d= 1 1 1 0 1 1 0 0
Infine:
|e| = 7210 = 10010002
In segno e modulo:
e=
1 1 0 0 1 0 0 0
In complemento a 1:
|e|=
0 1 0 0 1 0 0 0
e= 1 0 1 1 0 1 1 1
In complemento a 2 :
|e|=
76
0 1 0 0 1 0 0 0
e= 1 0 1 1 1 0 0 0
4.5.4 | E SERCIZIO
Testo
Si considerino le seguenti stringhe di 4 bit. Le si interpreti come valori interi
espressi rispettivamente in segno e modulo, complemento a 1, complemento
a 2 e notazione in eccesso 8.
a = 01112
b = 11012
c = 10102
Soluzione
Secondo i primi tre metodi, a ha valore positivo dato che il suo bit di segno è
posto a 0. Pertanto, una volta scorporato il bit di segno13, nelle tre notazioni
a = (1·22 + 1·21 + 1·20)10 = 710.
Per valutare il valore in eccesso 8, è necessario calcolare di quanto la stringa
in oggetto preceda o segua la rappresentazione convenzionale dello 0, che in
questo caso (con 4 bit) è 1000.
0000
-8
0001
-7
0010
-6
0011
-5
0100
-4
0101
-3
0110
-2
0111
-1
1000
0
1001
1
1010
2
1011
3
La stringa 0111 precede immediatamente la stringa 1000, e dunque a = –110.
Considerando ora b = 11012, il bit più significativo è posto a 1 e pertanto si
tratta di un numero negativo in tutte le notazioni. Fa eccezione l’eccesso 8 in
cui, come si evince dalla tabella sopra, b = 510.
In segno e modulo, scorporando il bit più significativo dai restanti 3 si evince
che
|b| = 1012 = 510
e dunque
b = –510.
13
77
Scorporare il bit di segno non è strettamente necessario, essendo posto a 0.
1100
4
1101
5
1110
6
1111
7
In complemento a 1, è necessario complementare i 4 bit per determinare il
modulo.
|b| = 00102 = 210
e dunque
b = –210.
Infine, in complemento a 2 è necessario dapprima sottrarre 1 per poi
complementare i 4 bit risultanti al fine di determinare il modulo.
|b| = 00112 = 310
e dunque
b = –310.
Considerando infine c = 10102, il bit più significativo è posto a 1 dunque si
tratta ancora una volta di un numero negativo in tutte le notazioni tranne che
in eccesso 8, ove b = 210.
In segno e modulo, scorporando il bit più significativo dai restanti 3 si evince
che
|c| = 0102 = 210
e dunque
c = –210.
In complemento a 1, è necessario complementare i 4 bit per determinare il
modulo.
|c| = 01012 = 510
e dunque
c = –510.
Infine, in complemento a 2 è necessario dapprima sottrarre 1 per poi
complementare i 4 bit risultanti al fine di determinare il modulo.
|c| = 01102 = 610
e dunque
c = –610.
78
4.6 | S OMME IN COMPLEMENTO A 2
Negli elaboratori viene solitamente adottata la notazione in complemento a 2.
Tra i suoi vantaggi più rilevanti:

lo 0 ha una sola rappresentazione (0|00…00), in quanto la sequenza
1|00…00 rappresenta l’intero -2n-1;

la sottrazione viene trattata esattamente come la somma, a patto di
codificare i valori con il loro segno.
L’operazione
a=b+c
viene eseguita dallo stesso circuito che si occupa di calcolare
a = b – c = b + (–c)
oppure
a = –b – c = (–b) + (–c)
In termini implementativi, è un grande vantaggio avere un unico circuito
sommatore in grado di effettuare anche l’operazione di differenza.
Per eseguire la somma tra due interi in complemento a 2 con n bit si esegue la
somma bit a bit dei due numeri ignorando sempre l’eventuale riporto che
cade oltre il bit più significativo. Questo può originare problemi di overflow,
quando il risultato dell’operazione di somma travalichi il limite superiore o
inferiore dell’intervallo di valori rappresentabili.
Si noti che solo una somma tra valori negativi o tra valori
positivi può portare a situazioni di overflow. L’overflow
invece non ha mai luogo quando si somma un valore
negativo x a un valore positivo y, in quanto il risultato
rientrerà matematicamente nell’intervallo [x … y], che è di
certo contenuto in [-2n-1…2n-1-1] dato che x e y possono
essere rappresentati su n bit.
In complemento a 2 gli errori di overflow sono rilevabili in
quanto due addendi di segno positivo originano un risultato
di segno negativo, o viceversa.
79
4.6.1 | E SERCIZIO
Testo
Si effettuino le seguenti addizioni rappresentando gli addendi con 4 bit in
complemento a 2. Si curi di mostrare tutti i riporti e di evidenziare eventuali
situazioni di overflow.
w = a + b = (–7 + 2)10
x = c + d = (7 – 2)10
y = e + f = (7 + 2)10
z = g + h = (7 + 2)10
Soluzione
Innanzi tutto, osserviamo che in complemento a 2 l’intervallo di valori
rappresentabili con n bit è:
[–2n - 1 … +(2n - 1 – 1)]
Pertanto, per n = 4:
[–8 … +7]
Di conseguenza, esistono almeno 2 motivi a priori per cui è lecito aspettarsi
che w e x non originino overflow:
1. si tratta di somme tra addendi rappresentabili con 4 bit e di segno
opposto;
2. il risultato dell’operazione in base 10 non valica i limiti dall’intervallo.
Per gli stessi motivi, y e z potrebbero generare overflow (punto 1) e il calcolo
del risultato in base 10 (punto 2) ce lo conferma.
a = –710 = 10012
1001 +
0010 =
1011
b = 210 = 102
w = 10112 = –510
c = 710 = 01112
d = –210 = 11102
x = 01012 = 510
80
0111 +
1110 =
1
1 1
(1)0101
Si noti che aver scartato il riporto oltre i 4 bit non inficia il risultato
dell’operazione, e non va considerata una situazione di overflow.
e = 710 = 01112
0111 +
0010 =
f = 210 = 00102
1 1
y = 10012 = –710 (overflow)
1001
Della situazione di overflow ci si può accorgere semplicemente confrontando
i bit di segno degli addendi, che pur essendo concordi generano un risultato
di segno opposto.
g = –710 = 10012
h = –210 = 11102
z = 01112 = 710 (overflow)
1001 +
1110 =
1
1 1
(1)0111
L’overflow non è dato dalla necessità di scartare il bit più significativo in
quinta colonna, bensì dal fatto che i bit di segno sulla quarta colonna siano
concordi per gli addendi e diversi da quello del risultato.
81
4.6.2 | E SERCIZIO
Testo
Si effettuino le seguenti addizioni rappresentando gli addendi con 6 bit in
complemento a 2. Si curi di mostrare tutti i riporti e di evidenziare eventuali
situazioni di overflow.
w = a + b = (30 + 2)10
x = c + d = (24 – 16)10
y = e + f = (–19 – 1)10
z = g + h = (–12 + 8)10
Soluzione
a = 3010 = 0111102
011110 +
000010 =
b = 210 = 0000102
1 1 1
w = 1000002 = –3210 (overflow)
100000
c = 2410 = 0110002
011000 +
110000 =
d = –1610 = 1100002
x = 10002 = 810
1
e = –1910 = 1011012
f = –110 = 1111112
w = 1011002 = –2010
g = –1210 = 1101002
h = 810 = 0010002
z = 1111002 = –410
82
1
(1)001000
101101 +
111111 =
1
1 1 1 1 1
(1)101100
110100 +
001000 =
111100
5 | EXTENSIBLE MARKUP LANGUAGE
Nei paragrafi di questo capitolo verranno considerati dapprima i documenti
in XML, di cui si dovrà studiare la correttezza della forma (well formedness), per
poi analizzare le Document Type Definition, legate ai concetti di classe di
documenti e di validità (validity).
5.1 | C ORRETTEZZA DELLA FORMA
Negli esercizi proposti di seguito si richiede di concentrarsi unicamente sugli
aspetti sintattici dell’XML, ignorando eventuali implicazioni semantiche
(ossia relative al significato intrinseco della codifica dell’informazione).
5.1.1 | E SERCIZIO
Testo
Si provveda a evidenziare e correggere gli errori nel seguente blocco XML:
<agenzia codice="M13">
<titolare><NOME>Pippo</titolare></NOME>
</agenzia>
Soluzione
L’ordine di chiusura dei tag deve essere inverso rispetto a quello di apertura.
Dunque il tag <NOME> va chiuso prima della chiusura di <titolare>.
<agenzia codice="M13">
<titolare><NOME>Pippo</NOME></titolare>
</agenzia>
83
5.1.2 | E SERCIZIO
Testo
Si descrivano e correggano i 3 errori di well formedness che si presentano nel
seguente blocco XML.
<libro>
<TITOLO>Appunti</TITOLO lingua="ita">
<autore nome=Luca Ludovico />
</Libro>
Soluzione
Procedendo dall’esterno verso l’interno, il primo errore consiste nella
chiusura del tag <libro> con l’iniziale maiuscola. Si ricorda che l’XML è case
sensitive, dunque fa distinzione tra maiuscole e minuscole. Anche se può dar
origine a una scrittura poco elegante, non dà problemi usare indistintamente
tag con identificatori tutti minuscoli, o tutti maiuscoli, o con la sola iniziale
maiuscola; è però fondamentale mantenere la coerenza tra tag di apertura e di
chiusura.
In secondo luogo, l’elemento TITOLO presenta un attributo nel tag di
chiusura, sintassi non consentita dall’XML.
Infine, il valore dell’attributo nome dell’elemento autore non è incluso tra
apici doppi o singoli.
<libro>
<TITOLO lingua="ita">Appunti</TITOLO>
<autore nome="Luca Ludovico" />
</libro>
84
5.1.3 | E SERCIZIO
Testo
Si dica se il seguente blocco di codice XML è ben formato, in caso contrario
si evidenzino e correggano gli errori.
<archivio>
<scheda id="32">ABCDEF</scheda>
<scheda id="33">123456</scheda>
<scheda id="34"></scheda>
<scheda id="35" />
<scheda id="36">
</archivio>
Soluzione
Analizzando la sintassi XML, l’unico errore che emerge è la mancanza del tag
di chiusura per l’ultima occorrenza dell’elemento scheda. Tale errore può
essere corretto imitando la sintassi della scheda 34 o della scheda 35. Non è
invece errato (almeno da un punto di vista sintattico) avere degli elementi
vuoti, scritti in modo esteso (vedi scheda 34) o compatto (vedi scheda 35).
<archivio>
<scheda id="32">ABCDEF</scheda>
<scheda id="33">123456</scheda>
<scheda id="34"></scheda>
<scheda id="35" />
<scheda id="36" />
</archivio>
85
5.1.4 | E SERCIZIO
Testo
Si evidenzino e correggano gli eventuali errori di correttezza della forma nel
seguente blocco XML.
<negozio>
<cuccioli>
<animale></animale>
<animale specie="gatto">Fufi</animale>
<animale specie='cane'>"Pongo</animale>
</cuccioli>
</negozio>
Soluzione
Nel blocco XML riportato non vi sono errori, e dunque si tratta di XML ben
formato. Non dà problemi (dal punto di vista sintattico) la presenza di un
elemento vuoto e privo di attributi; non dà problemi nemmeno l’uso di apici
singoli anziché doppi per delimitare il valore degli attributi.
Infine, la presenza di un apice doppio aperto e non chiuso come contenuto
dell’ultima occorrenza di animale anch’essa non genera errore, in quanto il
contenuto testuale di un elemento può essere una qualsiasi combinazione di
caratteri alfanumerici, compresi i segni di interpunzione. Il nome dell’animale
Pongo preceduto da un apice doppio rappresenterà presumibilmente un
errore, ma non dal punto di vista sintattico.
86
5.1.5 | E SERCIZIO
Testo
Si evidenzino e correggano gli errori di correttezza della forma nel seguente
blocco XML.
<appunto>In data <data formato=gg/mm/aaaa>12/11/2000<data>
la
gara
d’appalto
è
stata
vinta
da
<impresa>Asfalti
&
Bitumi S.p.A.</impresa ragione_sociale="spa">. Gli importi
concordati
ammontano
a
<importi
valuta="euro"
cifra="120000" valuta="dollari" cifra="3495" /></appunto>.
Soluzione
Nel blocco in esame, non costituisce un problema il fatto che il contenuto
dell’elemento appunto sia misto (ossia una combinazione di testo semplice e
di sottoelementi).
Un primo errore è dato dalla mancanza di apici attorno al valore dell’attributo
formato.
Inoltre, l’elemento data non viene chiuso da un end tag.
L’attributo ragione_sociale è stato erroneamente inserito in un tag di
chiusura.
Infine vengono duplicati i nomi degli attributi valuta e cifra all’interno di
uno stesso tag.
Si noti che l’elemento importi non viene usato propriamente da un punto di
vista semantico, in quanto il suo contenuto non marchia un blocco di testo
dell’appunto (in altre parole, leggendo l’intero testo senza tag, l’ultima frase
diventa “Gli importi concordati ammontano a”). In ogni caso, questo non
costituisce un errore sintattico.
87
5.2 | D OCUMENTI XML
Gli esercizi proposti di seguito hanno l’obiettivo di codificare informazione
in XML tramite l’elaborazione di un documento ben formato. Si tratta di casi
di studio singoli, pertanto non viene richiesta l’analisi di una classe di
documenti né l’implementazione sotto forma di DTD (si veda il prossimo
paragrafo).
Implicitamente, ciascun esercizio si presta a una molteplicità di soluzioni
tutte accettabili. Per verificare la well formedness di soluzioni differenti rispetto
a quelle proposte, si suggerisce di risolvere i testi proposti all’interno di un
editor XML e di invocare la verifica della correttezza della forma.
5.2.1 | E SERCIZIO
Testo
Si rappresenti in sintassi XML ben formata la descrizione di un CD audio dal
titolo “One” e contenente le tracce “Help” e “Yesterday”.
Possibili soluzioni
<cd titolo="One">
<traccia titolo="Help" />
<traccia titolo="Yesterday" />
</cd>
<cd titolo="One">
<traccia>Help</traccia>
<traccia>Yesterday</traccia>
</cd>
<cd>
<titolo>One</titolo>
<tracce>
<traccia>Help</traccia>
<traccia>Yesterday</traccia>
</tracce>
</cd>
e via dicendo…
88
5.2.2 | E SERCIZIO
Testo
Si crei un documento XML ben formato contenente le informazioni su un
rivenditore di auto usate.
Il rivenditore dispone di più autovetture.
Le auto devono essere raggruppate per casa automobilistica tramite
un’opportuna marcatura.
Ogni auto, infine, è caratterizzata da una targa, un colore, un anno di
immatricolazione e un chilometraggio attuale (esprimibile in km o in miglia).
Il documento XML deve contenere almeno un attributo e almeno un
elemento vuoto.
Si dia esempio di tale documento ipotizzando un totale di 3 auto, di cui due
della stessa casa automobilistica.
Possibile soluzione
<rivenditore>
<casa nome="FIAT">
<auto targa="BJ324TT">
<colore>rosso</colore>
<anno>2000</anno>
<chilometraggio unità="km" valore="20000" />
</auto>
<auto targa="AD766FG">
<colore>grigio</colore>
<anno>2005</anno>
<chilometraggio unità="km" valore="72000" />
</auto>
</casa>
<casa nome="Rover">
<auto targa="HG721RE">
<colore>verde</colore>
<anno>1999</anno>
<chilometraggio unità="miglia" valore="33100" />
</auto>
</casa>
</rivenditore>
89
5.2.3 | E SERCIZIO
Testo
Si voglia creare un documento XML di esempio per descrivere una singola
canzone. In particolare:

la canzone è caratterizzata da uno e un solo titolo;

la canzone presenta un anno di pubblicazione;

la canzone può avere uno o più autori, ciascuno associabile a un ruolo
specifico;

la canzone può avere uno o più interpreti, ciascuno associabile a un ruolo
specifico.
Si esemplifichi quanto richiesto tramite codice ben formato, facendo uso di
almeno un elemento vuoto e di elementi con uno o più attributi.
Nella risoluzione dell’esercizio si utilizzino i seguenti dati:

Titolo: Volare;

Anno di pubblicazione: 1958;

Autori: Domenico Modugno (musica), Franco Migliacci (testo);

Interpreti: D. Modugno (voce).
Possibile soluzione
<canzone>
<titolo>Nel blu dipinto di blu</titolo>
<pubblicazione anno="1958"/>
<autori>
<autore ruolo="musica">Domenico Modugno</autore>
<autore ruolo="testo">Franco Migliacci</autore>
</autori>
<interpreti>
<interprete ruolo="voce">D. Modugno</interprete>
</interpreti>
</canzone>
90
5.3 | I NTERPRETAZIONE DI DTD
Nel presente paragrafo verrà richiesto di esaminare la sintassi di una DTD
per giungere a proporre un esempio di documento XML valido rispetto alla
DTD stessa.
Negli esercizi in cui si richiede di esemplificare tramite un documento quanto
stabilito nella DTD, si sottolinea che non è fondamentale comprenderne il
significato semantico; è sufficiente un’applicazione pedissequa delle regole
codificate. Allo stesso modo, i valori assegnati agli attributi o il contenuto
degli elementi testuali possono essere stringhe di esempio, quali “abc123”, o
eventualmente abbreviate con i puntini di sospensione.
Ogni esercizio si presta a una molteplicità di soluzioni corrette. Questo
aspetto influenza tanto la struttura del documento (ad esempio, quante volte
annidare un sottoelemento la cui cardinalità nella DTD è 0..n) quanto
l’inserimento di valori di prova per gli attributi e per gli elementi testuali (ad
esempio, quale stringa inserire come valore dell’attributo Autore).
Per testare la corretta risoluzione di un esercizio, si suggerisce di copiare
all’interno di un editor XML dotato di funzioni di validazione sia il DTD
(testo dell’esercizio) sia il documento (soluzione), sfruttando la possibilità
sintattica dell’XML di utilizzare i DTD interni. Il documento risultante avrà il
seguente aspetto:
<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE Prova [
<!ELEMENT Prova (ElementoA,ElementoB)>
<!ELEMENT ElementoA EMPTY>
<!ELEMENT ElementoB (#PCDATA)>
<!ATTLIST ElementoA Attributo1 CDATA #IMPLIED>
]>
<Prova>
<ElementoA Attributo1="Prova" />
<ElementoB>Prova</ElementoB>
</Prova>
ove si nota la coesistenza della sintassi DTD e della sintassi propria del
documento XML. Tale codice può essere non solo verificato rispetto alla
correttezza della forma, ma anche validato.
91
5.3.1 | E SERCIZIO
Testo
Dato il seguente DTD, si proponga un documento di esempio.
<!DOCTYPE NEWSPAPER [
<!ELEMENT NEWSPAPER (ARTICLE+)>
<!ELEMENT ARTICLE (TITLE,BODY)>
<!ELEMENT BODY (#PCDATA)>
<!ATTLIST ARTICLE AUTHOR CDATA #REQUIRED>
<!ATTLIST ARTICLE EDITOR CDATA #IMPLIED>
<!ATTLIST ARTICLE DATE CDATA #IMPLIED>
<!ATTLIST ARTICLE EDITION CDATA #IMPLIED>
]>
Possibile soluzione
<NEWSPAPER>
<ARTICLE AUTHOR="Luca" DATE="5/2/2010">
<TITLE>Botti di capodanno</TITLE>
<BODY>Anche quest'anno il numero di feriti...</BODY>
</ARTICLE>
<ARTICLE AUTHOR="Giovanni" EDITOR="Marco">
<TITLE>Inter in fuga</TITLE>
<BODY>Il campionato sta per...</BODY>
</ARTICLE>
</NEWSPAPER>
Osservazioni
Tutti gli identificatori (elementi ed attributi) vanno scritti completamente in
caratteri maiuscoli, come imposto dal DTD.
L’attributo AUTHOR di ARTICLE è richiesto, dunque deve esistere per ogni
occorrenza di ARTICLE. Gli altri attributi invece sono tutti opzionali, e si è
scelto arbitrariamente di esemplificare DATE e EDITOR, ma si sarebbero potuti
inserire tutti in ogni occorrenza di ARTICLE così come si sarebbero potuti
sempre omettere.
I sottoelementi TITLE e BODY devono comparire esattamente in quest’ordine.
92
5.3.2 | E SERCIZIO
Testo
Dato il seguente DTD, si proponga un documento di esempio.
<!DOCTYPE Legge [
<!ELEMENT Legge (TitoloLegge,Articolato) >
<!ELEMENT TitoloLegge (#PCDATA)>
<!ELEMENT Articolato (Capo+)>
<!ELEMENT Capo (Rubrica?,Articolo+)>
<!ELEMENT Rubrica (#PCDATA)>
<!ELEMENT Articolo (Rubrica?,Comma+)>
<!ELEMENT Comma (#PCDATA)>
<!ATTLIST Capo Num CDATA #REQUIRED>
<!ATTLIST Articolo Num CDATA #REQUIRED>
<!ATTLIST Comma Num CDATA #REQUIRED>
]>
Possibile soluzione
<Legge>
<TitoloLegge>Disciplina delle associazioni</TitoloLegge>
<Articolato>
<Capo Num="I">
<Rubrica>DISPOSIZIONI GENERALI</Rubrica>
<Articolo Num="1">
<Rubrica>Finalità e oggetto della legge</Rubrica>
<Comma Num="1">La Repubblica...</Comma>
</Articolo>
</Capo>
<Capo Num="II">
<Articolo Num="1">
<Comma Num="1">La Repubblica...</Comma>
<Comma Num="2">I soggetti...</Comma>
</Articolo>
</Capo>
</Articolato>
</Legge>
93
5.3.3 | E SERCIZIO
Testo
Dato il seguente DTD, si proponga un documento di esempio.
<!DOCTYPE Catalogo [
<!ELEMENT Catalogo (Dipinto|Scultura)+>
<!ELEMENT Dipinto (Autore,Titolo)>
<!ELEMENT Scultura (Autore,Titolo)>
<!ELEMENT Autore EMPTY>
<!ELEMENT Titolo (#PCDATA)>
<!ATTLIST Catalogo UltimoAggiornamento CDATA #REQUIRED>
<!ATTLIST Dipinto Tecnica (acquerello|tempera|olio|mista)
#REQUIRED>
<!ATTLIST Autore Nome CDATA #REQUIRED>
<!ATTLIST Autore Cognome CDATA #REQUIRED>
<!ATTLIST Autore Alias CDATA #IMPLIED>
]>
Possibile soluzione
Ricordando che la sintassi (Dipinto|Scultura)+ significa scegliere da 1 a n
volte uno dei due sottoelementi:
<Catalogo UltimoAggiornamento="12/10/2009">
<Scultura>
<Autore Nome="Antonio" Cognome="Canova"/>
<Titolo>Amore e Psiche</Titolo>
</Scultura>
<Dipinto Tecnica="acquerello">
<Autore Nome="Giovanni Antonio" Cognome="Canal"
Alias="Canaletto"/>
<Titolo>Veduta di Piazza San Marco</Titolo>
</Dipinto>
<Scultura>
<Autore Nome="Donato" Cognome="di Niccolò di Betto
Bardi" Alias="Donatello"/>
<Titolo>David</Titolo>
</Scultura>
</Catalogo>
94
5.3.4 | E SERCIZIO
Testo
Osservando il DTD e i documenti XML sotto riportati, si evidenzino gli
errori di validazione per ciascuno di essi.
<!DOCTYPE ESEMPIO [
<!ELEMENT ESEMPIO (P1, P2)>
<!ELEMENT P1 EMPTY>
<!ELEMENT P2(#PCDATA)>
<!ATTLIST P1 attributo CDATA #REQUIRED>
]>
Documento 1:
<Esempio>
<p1 attributo="valore" />
<p2>Bla bla bla</p2>
</Esempio>
Documento 2:
<ESEMPIO>
<P2>Bla bla bla</P2>
</ESEMPIO>
Documento 3:
<ESEMPIO>
<P1 />
<P2>Bla bla bla</P2>
</ESEMPIO>
Documento 4:
<ESEMPIO>
<P2>Bla bla bla</P2>
<P1 attributo="valore" />
</ESEMPIO>
Documento 5:
<ESEMPIO>
<P1 attributo="valore">Bli bli bli</P1>
<P2>Bla bla bla</P2>
</ESEMPIO>
95
Soluzione
Documento 1 non viene validato in quanto i tag non rispettano maiuscole e
minuscole imposte dalla DTD. Si ricorda che XML è case sensitive. Si osservi
che invece un semplice controllo della correttezza della forma non avrebbe
dato errore, in quanto i tag vengono aperti e chiusi in modo coerente.
Più in generale, si osservi che tutti i documenti proposti nella
soluzione risultano ben formati ma non validi. Essi non
violano regole sintattiche dell’XML, bensì le regole
aggiuntive imposte dalla specifica DTD.
Documento 2 non viene validato in quanto manca il sottoelemento P1, la cui
presenza è richiesta prima dell’occorrenza di P2.
Documento 3 non viene validato poichè in P1 manca l’attributo richiesto.
Documento 4 non viene validato in quanto P1 e P2, correttamente compilati,
si trovano però in posizione invertita rispetto a quanto richiesto dalla DTD.
Infine, Documento 5 presenta del contenuto testuale all’interno di P1, che
invece era stato dichiarato con empty content.
96
5.3.5 | E SERCIZIO
Testo
Osservando il DTD e il documento XML sotto riportato, si provveda a
renderlo ben formato e valido evidenziando gli errori dell’uno e dell’altro
tipo.
<!DOCTYPE FAMIGLIA [
<!ELEMENT FAMIGLIA (PERS*)>
<!ELEMENT PERS (#PCDATA)>
<!ATTLIST PERS NP ID #REQUIRED>
<!ATTLIST PERS PADRE IDREF #IMPLIED>
<!ATTLIST PERS MADRE IDREF #IMPLIED>
]>
<FAMIGLIA>
<PERS NP="a1">Susanna</PERS>
<pers NP=a2>Carlo</pers>
<PERS NP='a3' MADRE="a1">Maria</PERS>
<PERS NP="a4" PADRE="a2">Luca</PERS>
<PERS NP="a4" PADRE="a5">Stefano
</Famiglia>
Soluzione
Evidenziamo e risolviamo dapprima gli errori sintattici che portano il
documento a non essere ben formato secondo i dettami dell’XML.
<FAMIGLIA>
<PERS NP="a1">Susanna</PERS>
<pers NP=_a2_>Carlo</pers>
<PERS NP='a3' MADRE="a1">Maria</PERS>
<PERS NP="a4" PADRE="a2">Luca</PERS>
<PERS NP="a4" PADRE="a5">Stefano___
</Famiglia>
che pertanto diventa:
<FAMIGLIA>
<PERS NP="a1">Susanna</PERS>
<PERS NP="a2">Carlo</PERS>
<PERS NP='a3' MADRE="a1">Maria</PERS>
<PERS NP="a4" PADRE="a2">Luca</PERS>
<PERS NP="a4" PADRE="a5">Stefano</PERS>
</FAMIGLIA>
97
Analizzando ora il documento alla luce del DTD, si osserva innanzi tutto che
a4 è utilizzato due volte come valore di NP, il che non è ammesso per un
tokenized attribute di tipo ID.
Analogamente, l’attributo PADRE nell’ultima occorrenza di PERS è di tipo
IDREF, ma non punta ad alcun valore specificato per attributi di tipo ID.
Una possibile soluzione è la seguente:
<FAMIGLIA>
<PERS NP="a1">Susanna</PERS>
<PERS NP="a2">Carlo</PERS>
<PERS NP='a3' MADRE="a1">Maria</PERS>
<PERS NP="a4" PADRE="a2">Luca</PERS>
<PERS NP="a5" PADRE="a2">Stefano</PERS>
</FAMIGLIA>
Si osservi che un validatore effettua solo controlli di correttezza della forma e
di validità, ma non di coerenza semantica.
Dunque, non darebbe problema una riga quale
<PERS NP="a5" PADRE="a5">Stefano</PERS>
che afferma che Stefano è padre di se stesso, oppure quale
<PERS NP="a5" MADRE="a2">Stefano</PERS>
che individua implicitamente Carlo come madre di Stefano.
98
5.4 | F ORMULAZIONE DI DTD
Nel presente paragrafo verrà richiesto di studiare una classe di documenti per
giungere alla formulazione sintattica di una DTD. L’obiettivo dunque non
sarà più codificare in XML ben formato una ricetta di cucina, un brano di
musica o la nota relativa ad un appuntamento, bensì scrivere una DTD per
poter codificare (secondo i requisiti specificati) qualsiasi ricetta di cucina,
qualsiasi brano di musica o qualsiasi nota.
I documenti XML che rispettano queste regole aggiuntive potranno essere
verificati non solo per quanto concerne la well formedness, ma anche contro la
rispettiva DTD al fine di testarne la validity.
99
5.4.1 | E SERCIZIO
Testo
Si consideri il problema di progettare una DTD per codificare in XML le
singole e-mail. Ogni e-mail deve avere un singolo mittente, deve avere uno o
più destinatari in chiaro, può avere da 0 a molti destinatari in copia carbone
(CC), può avere da 0 a molti destinatari invisibili (BCC), può avere
un’intestazione e può avere un corpo testuale. Tutti gli elementi citati hanno
contenuto alfanumerico.
Inoltre, l’e-mail presenta alcuni attributi:

la lingua, che è di tipo testuale e la cui specificazione è opzionale;

la priorità, il cui valore è uno a scelta tra NORMAL, LOW e HIGH e
il cui valore predefinito è NORMAL.
Soluzione
<!DOCTYPE EMAIL [
<!ELEMENT EMAIL (FROM, TO+, CC*, BCC*, SUBJECT?, BODY?)>
<!ATTLIST EMAIL
LANGUAGE CDATA #IMPLIED
PRIORITY (NORMAL|LOW|HIGH) "NORMAL">
<!ELEMENT TO (#PCDATA)>
<!ELEMENT FROM (#PCDATA)>
<!ELEMENT CC (#PCDATA)>
<!ELEMENT BCC (#PCDATA)>
<!ELEMENT SUBJECT (#PCDATA)>
<!ELEMENT BODY (#PCDATA)>
]>
100
5.4.2 | E SERCIZIO
Testo
Si consideri il problema di progettare una DTD per rappresentare i metadati
di catalogo di una canzone. Ogni canzone deve avere un titolo, può non
avere autore o può averne più d’uno, può appartenere o meno a un singolo
album. Tutti gli elementi citati hanno contenuto alfanumerico.
Tramite un attributo, è necessario specificare quale sia il ruolo dell’autore,
scegliendo tra i valori “musica”, “testo” e “altro”.
Se la canzone appartiene a un album, è possibile (ma non richiesto)
specificarne la posizione tramite un attributo dell’elemento album.
Inoltre, ogni canzone si presta a una catalogazione opzionale in generi
musicali. I generi devono essere raggruppati all’interno di un sottoelemento
di canzone. Ogni genere è un elemento vuoto il cui valore (ad esempio
“pop”, “dance”, “rock”) viene specificato tramite un attributo richiesto.
Soluzione
<!DOCTYPE canzone [
<!ELEMENT canzone (titolo, autore*, album?, generi?)>
<!ELEMENT titolo (#PCDATA)>
<!ELEMENT autore (#PCDATA)>
<!ATTLIST autore
ruolo CDATA (musica|testo|altro) #REQUIRED>
<!ELEMENT album (#PCDATA)>
<!ATTLIST album
posizione CDATA #IMPLIED>
<!ELEMENT generi (genere+)>
<!ELEMENT genere EMPTY>
<!ATTLIST genere
descrizione CDATA #REQUIRED>
]>
Si osservi che la cardinalità di
luogo al più una sola volta.
101
generi
è 0..1, in quanto la catalogazione ha
5.4.3 | E SERCIZIO
Testo
Si consideri il problema di progettare una DTD per rappresentare le
informazioni di un corso prematrimoniale. Al corso possono partecipare solo
coppie di futuri sposi, in numero che varia da 0 a n coppie.
Di ciascuna persona si devono indicare come sottoelementi il nome e il
cognome, mentre l’età viene codificata come attributo richiesto.
Si proponga una soluzione in cui l’elemento
corso
e un’altra soluzione in cui invece
direttamente annidati nell’elemento
corso,
coppia
fidanzato
Soluzione
<!DOCTYPE corso [
<!ELEMENT corso (coppia*)>
<!ELEMENT coppia (fidanzato, fidanzata)>
<!ELEMENT fidanzato (nome, cognome)>
<!ELEMENT fidanzata (nome, cognome)>
<!ELEMENT nome (#PCDATA)>
<!ELEMENT cognome (#PCDATA)>
<!ATTLIST fidanzato
età CDATA #REQUIRED>
<!ATTLIST fidanzata
età CDATA #REQUIRED>
]>
<!DOCTYPE corso [
<!ELEMENT corso (fidanzato, fidanzata)*>
<!ELEMENT fidanzata (nome, cognome)>
<!ELEMENT nome (#PCDATA)>
<!ELEMENT cognome (#PCDATA)>
<!ATTLIST fidanzato
età CDATA #REQUIRED>
<!ATTLIST fidanzata
età CDATA #REQUIRED>
]>
102
e
fidanzata
siano
pur mantenendo la logica della
presenza consecutiva di entrambi.
<!ELEMENT fidanzato (nome, cognome)>
sia figlio dell’elemento
5.4.4 | E SERCIZIO
Testo
Si crei una DTD per rappresentare una classe di documenti incentrata sulla
singola automobile. L’automobile presenta una marca, un modello, una targa,
un colore della carrozzeria e un anno di immatricolazione:

marca, modello
e
anno
sono sottoelementi richiesti, da porre esattamente
in questo ordine, e di tipo alfanumerico;

targa

colore
è un attributo richiesto di automobile;
della carrozzeria è un attributo opzionale di automobile.
 Infine un'auto può aver avuto un elenco di proprietari, di numero
compreso tra 0 e n. I proprietari sono sottoelementi vuoti con attributi
richiesti nome e cognome.
Si presenti infine un esempio di documento XML conforme a tale DTD.
Possibile soluzione
DTD
<!DOCTYPE automobile [
<!ELEMENT automobile (marca, modello, anno, proprietario*)>
<!ELEMENT marca (#PCDATA)>
<!ELEMENT modello (#PCDATA)>
<!ELEMENT anno (#PCDATA)>
<!ELEMENT proprietario EMPTY>
<!ATTLIST automobile
targa CDATA #REQUIRED
colore CDATA #IMPLIED >
<!ATTLIST proprietario
nome CDATA #REQUIRED
cognome CDATA #REQUIRED >
]>
Documento
<automobile targa="AB123CD">
<marca>Opel</marca>
<modello>Corsa</modello>
<anno>1998</anno>
<proprietario nome="Mario" cognome="Rossi" />
<proprietario nome="Giovanni" cognome="Bianchi" />
</automobile>
103
6 | GESTIONE DEGLI ERRORI
Nei paragrafi di questo capitolo verranno analizzate ed applicate le principali
tecniche per il semplice rilevamento e per la correzione degli errori nei
dispositivi di trasmissione e memorizzazione dell’informazione digitale.
6.1 | R ILEVAMENTO DEGLI ERRORI
Negli esercizi proposti verrà adottata la tecnica del bit di parità, che consente
la rilevazione di un numero dispari di errori (tipicamente errori singoli). La
tecnica comunemente consiste nell’aggiungere un bit alla stringa originaria,
costituita da un numero arbitrario di bit, al fine di ottenere una stringa
risultante contenente:

un numero pari di 1 (bit di parità pari)

oppure un numero dispari di 1 (bit di parità dispari).
Il valore del bit aggiuntivo serve per l’appunto a rendere pari (nel primo caso)
oppure dispari (nel secondo caso) il numero complessivo di bit posti a 1 nella
stringa. Tale valore può essere posto a 0 o a 1 a seconda delle esigenze.
Si affronti il primo esercizio proposto per comprendere come la tecnica
opera.
104
6.1.1 | E SERCIZIO
Testo
Si consideri un canale trasmissivo che pone in collegamento un mittente A a
un destinatario B. A e B concordano la trasmissione di stringhe binarie sotto
forma di singoli pacchetti da 8 bit cui viene aggiunto un bit di parità dispari.
Si consideri il pacchetto 00110101, si aggiunga il bit di parità dispari, si
ipotizzi un errore sul canale di trasmissione per quanto riguarda un singolo
bit e si illustri il processo di rilevamento dell’errore.
Si ha anche correzione dell’errore?
Cosa avverrebbe se gli errori sul pacchetto fossero 2?
Soluzione
Alla stringa 00110101 viene aggiunto il bit di parità posto a 1, di modo che il
numero complessivo di bit posti a 1 sia dispari. Supponiamo che questo
abbia luogo nella posizione più significativa, generando dunque la stringa
100110101.
Un errore singolo sulla stringa implica che un bit originariamente posto a 1
venga erroneamente trasmesso come uno 0, o viceversa. Si osservi che tale
errore potrebbe aver luogo anche sul bit di parità stesso, senza però inficiare
la validità della tecnica.
Quando la stringa giunge a B, il destinatario (che si aspetta una parità dispari)
analizza il numero di 1 e scopre che è diventato pari. Questo avviene per
qualsiasi bit si sia deciso di alterare, tramutando uno 0 in un 1 o viceversa.
Inoltre, ciò ha luogo per qualsiasi numero di alterazioni dispari della stringa
originaria. Pertanto B desume che si sia verificato un errore in fase di
trasmissione, e chiede la ritrasmissione della stringa.
B non ha modo di sapere su quale bit si sia verificato l’errore, e dunque quella
del bit di parità è solo una tecnica di rilevamento, ma non di correzione
dell’errore.
Con un numero pari di errori, la tecnica avrebbe fallito in quanto non
sarebbe stata alterata la proprietà di parità/disparità degli 1.
105
6.1.2 | E SERCIZIO
Testo
Si aggiunga un bit di parità dispari alle seguenti stringhe, ponendolo come bit
più significativo.
0110
11100
10010
00000
10000000
Soluzione
10110
011100
110010
100000
010000000
106
6.1.3 | E SERCIZIO
Testo
Si aggiunga un bit di parità pari alle seguenti stringhe, ponendolo come bit
più significativo.
11
100
0011
100010
01101110
Soluzione
011
1100
00011
0100010
101101110
107
6.2 | C ORREZIONE DEGLI ERRORI
Gli esercizi proposti utilizzano i codici di Hamming per il rilevamento e la
correzione degli errori.
Nella teoria dell'informazione, la distanza di Hamming tra due stringhe di
ugual lunghezza è il numero di posizioni nelle quali i simboli corrispondenti
sono diversi. In altri termini, la distanza di Hamming misura il numero di
sostituzioni necessarie per convertire una stringa nell'altra, o il numero di
errori che hanno trasformato una stringa nell'altra.
Ad esempio, è pari a 2 la distanza di Hamming tra le due stringhe seguenti:
1011101
1001001
Nei codici di Hamming, i simboli da trasmettere sono codificati con stringhe
ridondanti di bit proprio per supportare la robustezza agli errori.
Detta dmin la minima distanza di Hamming, calcolata tra tutte le diverse
combinazioni di simboli, si ricava che
Numero di errori rilevabili er = dmin – 1
Numero di errori correggibili ec =  (dmin – 1) / 2 
ove i simboli  e  stanno a indicare l’arrotondamento all’intero
immediatamente inferiore.
108
6.2.1 | E SERCIZIO
Testo
Nella tecnica di rilevamento e correzione degli errori basata su codici di
Hamming, quanti errori permette di rilevare e quanti errori consente di
correggere una distanza di Hamming minima dmin = 3? E se dmin = 5?
Soluzione
Considerando le formule precedentemente introdotte, per dmin = 3 il numero
di errori rilevabili è pari a 2 mentre il numero di errori correggibili è pari a 1.
Per dmin = 5 il numero di errori rilevabili è pari a 4 mentre il numero di errori
correggibili è pari a 2.
6.2.2 | E SERCIZIO
Testo
Si consideri un dizionario di 4 simboli rappresentati su stringhe di 4 bit. Si
debba garantire una distanza di Hamming minima dmin = 2 bit. Date le
stringhe s1 = 1100, s2 = 0011 e s3 = 0000, si proponga una combinazione di
bit per s4.
Soluzione
Per garantire dmin = 2 bit, la nuova configurazione deve avere almeno 2 bit
differenti rispetto a qualsiasi altra stringa già presente.
Soluzioni ammissibili (alternative tra loro)
1111
0101
1010
1001
0110
109
6.2.3 | E SERCIZIO
Testo
Sia dato il seguente codice di Hamming:
Simbolo
Codifica
A
100
B
010
C
001
Si ipotizzi che, per un errore sul canale trasmissivo, un dispositivo riceva la
stringa X = 110. Applicando il codice di Hamming sopra riportato, il
dispositivo si accorge dell’errore?
Il dispositivo riesce a correggere l’errore?
Se sì, con quale carattere viene interpretata la stringa X?
Soluzione
Da una rapida analisi, si evince che dmin = 2 bit, pertanto er = 1 ed ec = 0.
La stringa contiene presumibilmente un singolo errore, e proviene dalla
trasmissione della codifica di A o di B. Non si può però escludere che si tratti
di 3 errori di trasmissione sulla stringa C.
In ogni caso, X viene riconosciuta come errata in quanto non ha controparte
tra le codifiche ammesse dal codice in uso.
Non è possibile ricondurre X a una delle codifiche ammesse, in quanto essa
presenta distanza di Hamming minima pari a 1 tanto rispetto ad A quanto a
B.
110
6.2.4 | E SERCIZIO
Testo
Si consideri il seguente codice di Hamming per rappresentare le cifre
utilizzate in base 10.
Simbolo
0
1
2
3
4
5
6
7
8
9
Codifica
11000
10100
10010
10001
01100
01010
01001
00110
00101
00011
Se ne calcoli la distanza minima di Hamming, e si proceda a determinare il
numero massimo di errori rilevabili e correggibili.
Come agirebbe il sistema se giungesse una stringa quale 00000? E se
giungesse 10000?
Soluzione
dmin = 2 bit, pertanto er = 1 ed ec = 0.
Si noti che la stringa 00000 implica certamente un duplice errore di
trasmissione, in quanto nel dizionario iniziale tutte le stringhe contengono
due 1 e tre 0. Il sistema in questo caso si accorge dell’errore, nonostante
teoricamente er = 1, dato che la stringa non ha una controparte nel dizionario
supportato. Però si osservi che in generale la compresenza di 2 errori di
trasmissione potrebbe non essere rilevata: si pensi ad esempio alla doppia
alterazione di 11000 in 10100 (secondo e terzo bit), che manda la codifica del
simbolo 0 sul simbolo 1 e non viene pertanto rilevato l’errore.
Invece, in caso di alterazione di un solo bit l’errore è certamente rilevato. E’ il
caso della stringa 10000, che potrebbe derivare dall’alterazione di un solo bit
tra le stringhe che seguono:

11000 (secondo bit)

10100 (terzo bit)

10010 (quarto bit)

10001 (quinto bit)
In accordo con la teoria, però, tale errore non è correggibile. Infatti, la stringa
errata è equidistante da tutte quelle citate.
111
6.2.5 | E SERCIZIO
Testo
Si consideri il seguente codice di Hamming per rappresentare quattro simboli
differenti.
Simbolo
giallo
verde
rosso
blu
Codifica
00000000
10100110
01011001
11111111
Se ne calcoli la distanza minima di Hamming, e si proceda a determinare il
numero massimo di errori rilevabili e correggibili.
Si alteri un solo bit di una delle stringhe originarie e si mostri come agisce la
tecnica di correzione.
Soluzione
dmin = 4 bit, pertanto er = 3 ed ec = 1.
Dunque è lecito aspettarsi che, qualunque stringa si scelga e comunque la si
alteri (a patto di modificare solo un bit), l’algoritmo sia in grado di risolvere
l’errore.
Consideriamo ad esempio la stringa relativa al rosso e modifichiamone il
primo bit. La stringa alterata diventa 11011001. Calcoliamone la distanza
rispetto a tutti i simboli.

Distanza rispetto a giallo: 5 bit

Distanza rispetto a verde: 7 bit

Distanza rispetto a rosso: 1 bit

Distanza rispetto a blu: 3 bit
Pertanto è univocamente fissato il simbolo più vicino alla stringa ricevuta.
Infine, per via del tutto empirica, si noti che questo risultato generale non si
sarebbe ottenuto supportando la modifica di 2 bit. Consideriamo
nuovamente la stringa del rosso e modifichiamo il quarto e il quinto bit. La
stringa risultante è ora 01000001, che dista per costruzione 2 bit dalla codifica
del rosso ma 2 bit anche dalla codifica del blu.
112
7 | DATABASE
Nei paragrafi di questo capitolo si tratteranno 3 argomenti:
113

Algebra relazionale

Structured Query Language

Progettazione di database con il formalismo E-R
7.1 | A LGEBRA RELAZIONALE
Gli esercizi proposti nel corso di questo paragrafo implicano l’applicazione
della teoria sull’Algebra relazionale ai database relazionali.
Nel seguito verranno utilizzate le seguenti convenzioni:

gli insiemi sono rappresentati da lettere maiuscole (ad esempio A) o
da etichette dall’iniziale maiuscola (ad esempio Studenti);

si farà altrettanto per le relazioni, che sono in effetti insiemi dato che
rappresentano sottoinsiemi del prodotto cartesiano;

i nomi degli attributi saranno indicati in lettere minuscole (ad esempio
nome);

i valori degli attributi saranno indicati tra apici doppi quando questi
rappresentano delle stringhe (ad esempio “Luigi”).
Per quanto concerne gli operatori, dati gli insiemi D1, D2, … , Dn:

prodotto cartesiano: D1×D2×…×Dn

relazione R sugli insiemi D1, D2, … , Dn: R ⊆ D1×D2×…×Dn

unione U degli insiemi D1(X) e D2(X): U = D1(X)  D2(X) ove i due
insiemi presentano lo stesso insieme di attributi X;

intersezione I degli insiemi D1(X) e D2(X): U = D1(X)  D2(X) ove i
due insiemi presentano lo stesso insieme di attributi X;

differenza A tra gli insiemi D1(X) e D2(X): A = D1(X) – D2(X) ove i
due insiemi presentano lo stesso insieme di attributi X;

ridenominazione di un attributo dell’insieme D:
nuova etichetta  vecchia etichetta (D)

selezione in base a una condizione sull’insieme D: condizione (D)

proiezione su uno o più attributi dell’insieme D: lista attributi (D)

join sulla base di un predicato tra gli insiemi D1 e D2: D1 predicato D2

join naturale tra gli insiemi D1 e D2: D1  D2
Infine, gli operatori logici avranno le seguenti forme: (AND),  (OR),
 (NOT).
114
7.1.1 | E SERCIZIO
Testo
Si calcoli la cardinalità del prodotto cartesiano P = A × B ove A è l’insieme
dei punti cardinali mentre B è l’insieme dei colori di un semaforo. Si
provveda quindi a verificare il risultato ottenuto mostrando il risultato
dell’operazione di prodotto cartesiano.
Soluzione
A = {Nord, Sud, Ovest, Est}
B = {Rosso, Giallo, Verde}
La cardinalità di P = A × B è |P| = |A| × |B| = 12.
Come controprova, mostriamo il risultato del prodotto cartesiano:
A
Nord
Sud
Ovest
Est
Nord
Sud
Ovest
Est
Nord
Sud
Ovest
Est
B
Rosso
Rosso
Rosso
Rosso
Giallo
Giallo
Giallo
Giallo
Verde
Verde
Verde
Verde
Si ricordi che l’ordine in cui vengono presentate le tuple è del tutto
indifferente ai fini del risultato.
115
7.1.2 | E SERCIZIO
Testo
Si considerino le tabelle sotto riportate, ove la chiave primaria risulta
sottolineata.
Deputati
codice
cognome
nome
commissione
provincia
collegio
SG01
Silvestro
Giuseppe
bil
PZ
1
RM02
Rossi
Mario
cul
TO
2
FF03
Filippi
Francesca
cul
TO
1
SA04
Stabile
Angelo
aff
PZ
2
BR05
Biase
Roberto
bil
PZ
1
BR06
Biase
Roberto
bil
PZ
2
Collegi
provincia
numero
nome
PZ
1
Melfi
PZ
2
Lagonegro
TO
1
Settimo Torinese
TO
2
Ivrea
Commissioni
codice
nome
presidente
bil
Bilancio
BR06
aff
Affari Costituzionali
SA04
cul
Cultura
FF03
Si risponda ai seguenti quesiti in termini di algebra relazionale:
1. elencare i soli nomi e cognomi dei deputati;
2. elencare i nomi di tutte le commissioni, rinominando l’attributo “nome”
in “commissione”;
3. estrarre i codici e i cognomi dei deputati eletti in collegi della provincia
PZ;
116
4. estrarre le intere tuple relative a deputati che operano in commissione
“bil” o il cui numero di collegio sia superiore a 1;
5. estrarre il nome e il codice delle commissioni in cui operano deputati
provenienti da uno dei collegi della provincia TO;
6. si ricavi il nome di tutti i collegi dei deputati elencati in Deputati,
osservando che (provincia, numero) sono chiavi esterne della tabella
Deputati verso la tabella Collegi.
Soluzione
1. nome, cognome (Deputati)
2. commissione  nome (nome (Commissioni))
3. provincia=“PZ” (codice, cognome (Deputati))
4. commissione = “bil”  collegio > 1 (Deputati)
5. nome, codice (Commissioni codice = commissione (provincia = “TO” (Deputati)))
Analizzando la soluzione dall’interno verso l’esterno, la prima operazione
eseguita è la selezione dei soli deputati provenienti dalla privincia “TO”.
Nel nostro caso, è una tabella T il cui numero di colonne rimane
invariato rispetto a Deputati, mentre il numero di righe è ridotto a solo
due. Si procede poi a effettuare il join tra la tabella così ottenuta e la
tabella Commissioni, imponendo che
Commissioni.codice = T.commissione
L’uso della notazione puntata avrebbe evitato le possibilità di confusione
tra colonne che presentano lo stesso nome in tabelle differenti.
Infine, della tabella S risultante interessano solo le colonne nome e
codice, per cui si procede a operare una proiezione.
6. nome (Collegi provincia = provincia  numero = collegio (nome_dep  nome (Deputati)))
La ridenominazione dell’attributo Deputati.nome è opportuna in quanto
esso andrebbe a configgere con il nome del collegio, altro attributo
presente nella tabella derivante dal join. In alternativa, sarebbe stato
possibile filtrare gli attributi “utili” di Deputati (in questo caso provincia e
collegio) tramite una proiezione su tali colonne.
117
7.2 | S TRUCTURED Q UERY L ANGUAGE
In questo paragrafo si affronteranno alcuni costrutti alla base delle
interrogazioni (o query) SQL.
7.2.1 | E SERCIZIO
Testo
Data la tabella Automobili qui riportata
casa
modello
targa
anno
chilometri
Fiat
Multipla
DA265GF
2007
50000
Fiat
Ritmo
BJ342ND
1983
160000
Ferrari
Scaglietti
CB732AK
2007
12500
Ferrari
Testarossa
AH223TJ
1985
43000
Lancia
Delta
AT729YJ
1998
80200
Alfa Romeo
Mito
DE172HK
2009
2000
si scrivano le interrogazioni SQL per estrarre:
1. le tuple complete relative ad automobili Fiat;
2. il modello e la targa di tutte le vetture del parco auto;
3. le targhe delle automobili il cui anno di immatricolazione è successivo al
2000;
4. i modelli delle automobili immatricolate prima del 2009 e con un numero
di chilometri minore di 30000;
5. il numero di vetture presenti nel parco auto e di marca Ferrari;
6. il numero di vetture la cui targa inizia per “A”;
7. l’elenco dei valori distinti (senza ripetizioni) delle case automobilistiche
rappresentate nel parco auto;
8. l’elenco dei modelli in ordine alfabetico inverso;
9. l’elenco di casa, modello e targa delle auto che rispettino le seguenti
condizioni: avere una targa che termina per J, un chilometraggio
superiore a 20000 e anno di immatricolazione diverso dal 1985;
10. il chilometraggio massimo presente nella tabella.
118
Soluzione
1.
Questa query può essere considerata a tutti gli effetti una pura selezione
(nei termini dell’Algebra relazionale).
SELECT * FROM Automobili WHERE casa = "Fiat";
2.
Questa query può essere considerata a tutti gli effetti una pura proiezione
(nei termini dell’Algebra relazionale).
SELECT modello, targa FROM Automobili;
3. SELECT targa FROM Automobili WHERE anno > 2000;
4. SELECT modello FROM Automobili WHERE anno < 2000 AND
chilometri < 30000;
5. SELECT COUNT(*) FROM Automobili WHERE casa = "Ferrari";
6. SELECT COUNT(*) FROM Automobili WHERE targa LIKE "A%";
7. SELECT DISTINCT casa FROM Automobili;
si osservi che l’assenza della clausola DISTINCT avrebbe portato a
ripetizioni nell’elenco dei risultati;
8. SELECT modello FROM Automobili ORDER BY modello DESC;
9. SELECT casa, modello, targa FROM Automobili WHERE
targa LIKE "%J" AND chilometri > 20000 AND anno <> 1985;
10. SELECT MAX(chilometri) AS massimo FROM Atuomobili;
119
7.2.2 | E SERCIZIO
Testo
Date le tabelle sotto riportate:
Cantanti
id
nome
cognome
data_nascita
luogo_nascita
1
Vasco
Rossi
07/02/1952
Zocca
2
Eros
Ramazzotti
28/10/1963
Roma
3
Laura
Pausini
16/05/1974
Faenza
Album
id
titolo
anno
etichetta
cantante
1
Liberi liberi
1989
EMI
1
2
Primavera in anticipo
2008
Atlantic Records
3
3
Dove c’è musica
1996
BMG Ricordi
2
4
Gli spari sopra
1993
EMI
1
5
Io canto
2006
Atlantic Records
3
6
Stupido hotel
2001
EMI
1
si scrivano le interrogazioni SQL per estrarre:
1. tutti gli album incisi dall’etichetta EMI, in ordine di anno di
pubblicazione;
2. tutti i titoli degli album al cui interno compare la stringa “ri” oppure la
stringa “ho”;
3. tutti i titoli degli album di cantanti il cui cognome inizia per “R”;
4. i soli identificativi degli album (ridenominati come colonna album)
composti dopo il 2000 e il cui cantante abbia un cognome che inizia per
“P”;
Soluzione
1. SELECT * FROM Album WHERE etichetta = "EMI" ORDER BY anno;
2. SELECT titolo FROM Album WHERE titolo LIKE "%ri%"
OR titolo LIKE "%ho%";
3. SELECT titolo FROM Album, Cantanti WHERE
Album.cantante = Cantanti.id AND cognome LIKE "R%";
120
4. SELECT Album.id AS album FROM Album, Cantanti WHERE
Album.cantante = Cantanti.id
AND anno > 2000
AND cognome LIKE "P%";
Nella soluzione del terzo e del quarto quesito, si è scelto di eseguire il JOIN
eguagliando in modo esplicito gli attributi coinvolti.
In alternativa, il JOIN si sarebbe potuto ottenere con la sintassi:
SELECT * FROM Album JOIN Cantanti ON Album.cantante = Cantanti.id
Si osservi che in generale, quando la soluzione richiede un join tra due
tabelle, appare una condizione ulteriore rispetto a quelle elencate nelle
richieste. Si tratta della condizione di JOIN, che permette di associare tuple
dell’una e dell’altra tabella secondo una certa logica. In assenza della
condizione di JOIN, si otterrebbe come risultato un prodotto cartesiano tra
le tuple delle due tabelle, eventualmente filtrate secondo le condizioni della
clausola WHERE.
Ad esempio, in mancanza della condizione di JOIN:
SELECT titolo FROM Album, Cantanti WHERE cognome LIKE "R%";
avrebbe ridotto la tabella Cantanti a sole 2 tuple, non avrebbe filtrato la
tabella Album (6 tuple) e come risultato avrebbe restituito il prodotto
cartesiano tra le due relazioni, per un totale di 12 tuple.
In generale, se le tabelle da porre in JOIN sono n allora compariranno n-1
condizioni di JOIN.
Nell’esprimere le condizioni di JOIN si è utilizzata la notazione puntata per
evitare ambiguità, in quanto il campo
id
esiste in entrambe le tabelle. Non
sarebbe stato strettamente necessario esplicitare
Album.cantante,
in quanto
l’attributo cantante è già univocamente definito tra le tabelle coinvolte dal
JOIN.
121