L'informazione e la
sua codifica
Corso di Informatica
CdL: Chimica
Claudia d'Amato
[email protected]
Informatica e telecomunicazione

Cos’è l’informatica?
• lo studio sistematico degli algoritmi che descrivono e
trasformano l’informazione: la loro teoria, analisi,
progetto, efficienza, realizzazione e applicazione
[ACM – Association for Computing Machinery]
• la scienza della rappresentazione e dell’elaborazione
dell’informazione

Cos’è la telecomunicazione?
• la trasmissione rapida a distanza dell’informazione

Attenzione:
• Non si parla di tecnologia dei calcolatori !
• Si attribuisce ruolo centrale al concetto di informazione !
Informatica - Claudia d'Amato
2
Informazione e supporto
 L’informazione
è “portata da”, o “trasmessa
su”, o “memorizzata in”, o “contenuta in”
qualcosa; questo “qualcosa” però non è
l’informazione stessa.
 Ogni
supporto ha le sue caratteristiche in
quanto mezzo su cui può essere scritta
dell’informazione.
Informatica - Claudia d'Amato
3
Informazione e supporti /2
La stessa informazione può essere scritta
su supporti differenti.
11
10
9
8
7
6
10
Informatica - Claudia d'Amato
4
Informazione e supporto /4
 Distinguere
informazione e supporto fisico è
distinguere tra “entità logiche” ed “entità
fisiche”:
• l’informazione richiede un supporto fisico,
fisico ma
non coincide con esso;
• l’informazione è un’entità extra‑fisica,
extra‑fisica non
interpretabile in termini di materia‑energia e
sottoposta alle leggi della fisica solo perché basata
su un supporto fisico.
 L’informazione
Informatica - Claudia d'Amato
si può creare e distruggere.
6
Caratteristiche di un sistema fisico per
supportare informazioni
 CODIFICA:
l'operazione formalizzazione e
scrittura dell'infomazione su supporto fisico
 DECODIFICA:
l'operazione di interpretazione
e lettura dell'informazione da supporto fisico
 Condizione
necessaria perché un supporto
possa portare informazione è che possa
assumere configurazioni differenti, a ognuna
delle quali venga associata una differente
entità di informazione.
Informatica - Claudia d'Amato
7
Supporto fisico: 1 condizione
a

Deve consentire di
potere identificare
delle differenze
• Es: voglio rappresentare 2
alternative

Informatica - Claudia d'Amato
Cosa rappresenta
ciascuna
configurazione?
8
Configurazioni e codici

Per interpretare le differenti configurazioni del
supporto è necessario conoscere il codice (cioè la
regola) che a ogni configurazione ammessa associa
un’entità di informazione.

La definizione di un codice comporta che siano
identificati in modo non ambiguo l’insieme delle
possibili configurazioni del supporto e l’insieme
delle possibili entità di informazione a cui ci si
vuole riferire.

Variando il codice è possibile riferirsi a entità di
informazione differenti utilizzando uno stesso
supporto fisico.
Informatica - Claudia d'Amato
9
Supporto fisico: 2a condizione
Deve essere condivisa una regola per
attribuire un significato a ciascuna
configurazione
Configurazione 1
Configurazione 2
CODICE
Entità di
informazione 1
Informatica - Claudia d'Amato
Entità di
informazione 2
10
Definire un codice

Identificare
• { Configurazioni }
• { Entità informazione }

Associare gli elementi
dei 2 insiemi
Informatica - Claudia d'Amato
11
Il telegrafo...

Supporto fisico: conduttore in cui transita corrente
continua

Entità di informazione: “punti” e “linee”, che
rappresentano le lettere dell’alfabeto

Codice = regola che specifica la corrispondenza:
• passa corrente per 1 s ⇒ punto
• passa corrente per 2 s ⇒ linea
• non passa corrente per 1 s ⇒ separazione tra punti e
linee della stessa lettera
• non passa corrente per 2 s ⇒ separazione tra due
lettere
• “passa corrente per 1 s, non passa per 1 s, passa per
2 s” = “punto linea”.
Informatica - Claudia d'Amato
12
...Il telegrafo

Codice Morse = relazione tra lettere e sequenze di
punti linee:
• punto linea ⇒ lettera “A”
• linea punto punto punto ⇒ lettera “B”
• linea punto linea punto ⇒ lettera “C”
• ecc.

Abbiamo associato simboli ad altri simboli!!
Informatica - Claudia d'Amato
13
Messaggi vs configurazione

Configurazione del supporto fisico (livello fisico, LF):
• passa corrente per 2s, non passa per 1s, passa per 1s, non passa per 2s,
passa per 2s, non passa per 1s, passa per 2s, non passa per 1s, passa
per 2s

messaggio, al livello logico 1 (LL1):
• linea punto, separazione di lettera, linea linea linea

messaggio, al livello Logico 2 (LL2):
• “N” “O”

messaggio, al livello Logico 3 (LL3):
• “NO”, con il significato (per esempio) di “incontro non confermato”

Le relazioni tra questi livelli definiscono ognuna un codice
per interpretare il significato delle entità che compaiono al
livello precedente in termini delle entità del livello
successivo: sono relazioni di significazione.
Informatica - Claudia d'Amato
14
Livelli di informazione

Informazione sintattica
• Rappresentazione in simboli dell'informazione

Informazione semantica
• Determinazione del significato della informazione
rappresentata

Informazione pragmatica
• Determinazione del valore da attribuire
all'informazione, considerata la sua
rappresentazione ed il suo significato
Informatica - Claudia d'Amato
15
La codifica dell’informazione
Informatica - Claudia d'Amato
17
Codifica dati e istruzioni

Algoritmo
• descrizione della soluzione di problema scritta in modo
da poter essere eseguita da un esecutore (eventualmente
diverso dall’autore dell’algoritmo)
• sequenza di istruzioni che operano su dati.
dati

Programma
• algoritmo scritto in modo da poter essere eseguito da un
calcolatore (esecutore automatico)

Per scrivere un programma è necessario
rappresentare istruzioni e dati in un formato tale
che l’esecutore automatico sia capace di
memorizzare e manipolare.
Informatica - Claudia d'Amato
18
Rappresentare dati e istruzioni
per il processing di un esecutore
automatico
 Alfabeto dei simboli
• cifre “0”, “1”, …, “9”, separatore decimale (“,”), separatore delle
migliaia (“.”) e segni positivo (“+”) o negativo (“–”).

Regole di composizione (sintassi), che definiscono le
successioni “ben formate”
• “1.234,5” è la rappresentazione di un numero;
• “1,23,45” non lo è.

Codice (semantica)
• “1.234,5” = 1×103 + 2×102 + 3×101 + 4×100 + 5×10–1
• “1,23,45” = ??

Lo stesso alfabeto può essere utilizzato con codici diversi:
• “123,456” = 1×102 + 2×101 + 3×100 + 4×10–1 + 5×10–2 + 6×10–3, [IT]
• “123,456” = 1×105 + 2×104 + 3×103 + 4×102 + 5×101 + 6×100, [UK]
Informatica - Claudia d'Amato
19
Codifica Binaria


Alfabeto binario: usiamo dispositivi con solo due stati
Problema: assegnare un codice univoco a tutti gli oggetti
compresi in un insieme predefinito

Quanti oggetti posso codificare con k bit:
•
•
•
•
•
1 bit ⇒ 2 stati (0, 1) ⇒ 2 oggetti (e.g. Vero/Falso)
2 bit ⇒ 4 stati (00, 01, 10, 11) ⇒ 4 oggetti
3 bit ⇒ 8 stati (000, 001, …, 111) ⇒ 8 oggetti
…
k bit ⇒ 2k stati ⇒ 2k oggetti

Quanti bit mi servono per codificare N oggetti:

Attenzione:
ipotesi implicita che i codici abbiano tutti la stessa lunghezza
• N ≤ 2k ⇒ k ≥ log2N ⇒ k = log2N (intero superiore)
Informatica - Claudia d'Amato
20
Esempio di codifica binaria

Problema:
assegnare un codice binario univoco a tutti i giorni della
settimana

Giorni della settimana: N = 7 ⇒ k ≥ log27 ⇒ k = 3

Con 3 bit possiamo ottenere 8 diverse configurazioni:
• Ne servono 7, quali utilizziamo?
• Quale configurazione associamo a quale giorno?

Attenzione:
ipotesi che i codici abbiano tutti la stessa lunghezza
Informatica - Claudia d'Amato
21
I giorni della settimana in binario /1
Lunedì
Lunedì
Giovedì
Martedì
0
Martedì
Mercoledì
Domenica
Mercoledì
Sabato
Giovedì
Venerdì
Venerdì
1 bit
2 “gruppi”
Informatica - Claudia d'Amato
00
Giovedì
Mercoledì
Domenica
Sabato
Lunedì
Martedì
1
01
10
Sabato
Venerdì
Domenica
11
2 bit
4 “gruppi”
000
001
010
011
100
101
110
111
Lunedì
Martedì
Mercoledì
Giovedì
Venerdì
Sabato
Domenica
3 bit
8 “gruppi”
22
I giorni della settimana in binario /2
Lunedì
Sabato
Giovedì
Martedì
Domenica
Mercoledì
Sabato
Giovedì
0
Martedì
Domenica
Lunedì
Mercoledì
Venerdì
Venerdì
1 bit
2 “gruppi”
Informatica - Claudia d'Amato
1
Giovedì
00
Martedì
Sabato
01
Mercoledì
Domenica
10
Lunedì
Venerdì
2 bit
4 “gruppi”
11
000
001
010
011
100
101
110
111
Giovedì
Sabato
Martedì
Domenica
Mercoledì
Venerdì
Lunedì
3 bit
8 “gruppi”
23
Codifica binaria dei caratteri

Quanti sono gli oggetti compresi nell’insieme?
•
•
•
•
26 lettere maiuscole + 26 minuscole ⇒ 52
10 cifre
Circa 30 segni d’interpunzione
Circa 30 caratteri di controllo (EOF, CR, LF, …)
circa 120 oggetti complessivi ⇒ k = log2120 = 7

Codice ASCII: utilizza 7 bit e quindi può
rappresentare al massimo 27=128 caratteri
• Con 8 bit (= byte) rappresento 256 caratteri (ASCII esteso)
• Si stanno diffondendo codici più estesi (e.g. UNICODE) per
rappresentare anche i caratteri delle lingue orientali
Informatica - Claudia d'Amato
24
ASCII su 7 bit (alcune configurazioni)
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
010
sp
!
"
#
$
%
&
'
(
)
*
+
,
-
.
/
011
0
1
2
3
4
5
6
7
8
9
:
;
<
=
>
?
100
@
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
101
P
Q
R
S
T
U
V
W
X
Y
Z
[
\
]
^
_
110
`
a
b
c
d
e
f
g
h
I
j
k
l
m
n
o
111
p
q
r
s
t
u
v
w
x
Y
z
{
|
}
~
canc
Informatica - Claudia d'Amato
25
bit, Byte, KiloByte, MegaByte, …
bit = solo due stati, “0” oppure “1”.
Byte = 8 bit, quindi 28 = 256 stati
KiloByte [KB]
= 210 Byte = 1024 Byte ~ 103 Byte
MegaByte [MB] = 220 Byte = 1'048'576 Byte ~ 106 Byte
GigaByte [GB] = 230 Byte ~ 109 Byte
TeraByte [TB] = 240 Byte ~ 1012 Byte
PetaByte [PB] = 250 Byte ~ 1015 Byte
ExaByte [EB]
= 260 Byte ~ 1018 Byte
Informatica - Claudia d'Amato
26
La codifica delle istruzioni

Si segue lo schema presentato per i caratteri
alfanumerici:
• quali e quante sono le istruzioni da codificare?
• qual è la lunghezza delle successioni di bit da utilizzare ?
• qual è la corrispondenza tra istruzioni e successioni di bit ?
Istru zioni
aritm etico-logiche
Cod ice Istru zione
0111 1100
AD D
0111 1101
SUB
0111 1110
AN D
……… ………
Informatica - Claudia d'Amato
Istru zioni p er il
trasferim ento d ati
Cod ice Istru zione
1110 1000 LOAD
1111 1000 STORE
……… ………
……… ………
Istru zioni d i
controllo
Cod ice Istru zione
0100 1001 IF_EQ
0100 1000 GOTO
0100 1100 RETURN
……… ………
27
Oltre al codice operativo

… è necessario far riferimento ai dati necessari per
completare l’esecuzione dell’istruzione,
• e.g. addizione: è necessario che sia specificato (anche implicitamente)
dove leggere i due operandi da sommare e dove scrivere il risultato;

il numero dei dati da specificare è variabile, in funzione
delle istruzioni.
Informatica - Claudia d'Amato
28
Numeri naturali
 Sistema
di numerazione posizionale in base b
• ckck–1…c0 rappresenta ck×bk + ck–1×bk–1 + … + c0×b0
• b=10 ⇒ 1101dieci indica 1×103 + 1×102 + 0×10 + 1×100
 Conversione
binario ⇒ decimale
•basta scrivere il numero secondo la notazione posizionale
utilizzando già il sistema decimale
• b=2 ⇒ 1101due indica 1×23 + 1×22 + 0×2 + 1×20 = 13dieci
decimale ⇒ binario
• Metodo delle divisioni successive
 Conversione
Informatica - Claudia d'Amato
29
Conversione binario ⇒ decimale
101100d u e = 1d ieci×2d5 ieci+ 0d ieci×24d ieci+ 1d ieci×23d ieci+ 1d ieci×22d ieci+ 0d ieci×21d ieci+
+ 0d ieci×20d ieci =
= 1d ieci×32d ieci + 0dieci×16d ieci + 1d ieci×8d ieci + 1d ieci×4d ieci+ 0d ieci×2d ieci
+ 0d ieci×1d ieci =
= 32d ieci + 8d ieci + 4d ieci =
= 44d ieci
101110101d u e = 1d ieci×28d ieci+ 0d ieci×27d ieci+ 1d ieci×26d ieci+ 1d ieci×25d ieci+ 1d ieci×24d ieci+
0d ieci×23d ieci+ 1d ieci×22d ieci+ 0d ieci×21d ieci+ 1d ieci×20d ieci =
= 1d ieci×256d ieci+ 0d ieci×128dieci+ 1d ieci×64d ieci+ 1dieci×32d ieci+
1d ieci×16d ieci+ 0d ieci×8d ieci+ 1d ieci×4d ieci+ 0d ieci×2d ieci+ 1d ieci×1d ieci =
= 256d ieci+ 64d ieci+ 32dieci+ 16d ieci+ 4d ieci+ 1d ieci =
= 373d ieci
Informatica - Claudia d'Amato
30
Conversione decimale ⇒ binario






Sistema di numerazione posizionale in base B che, in questo contesto si può
ipotizzare diversa da dieci
cn–1cn–2…c1c0 = cn–1×Bn–1 + cn–2×Bn–2 + … + c1×B1 + c0×B0
cn–1cn–2…c1c0 = cn–1×Bn–1 + cn–2×Bn–2 + … + c1×B + c0
(infatti B1 = B e B0 = 1)
Dividendo il numero per il valore della base, il risultato che si ottiene è:
(cn–1×Bn–1 + cn–2×Bn–2 + … + c1×B + c0)/B =
= cn–1×Bn–2 + cn–2×Bn–3 + … + c1 + c0/B
che può essere scomposto in modo da evidenziare quoziente e resto:
quoziente = cn–1×Bn–2 + cn–2×Bn–3 + … + c1
resto = c0
Il resto della divisione corrisponde all’ultima cifra della rappresentazione in
base B del numero, ma il suo valore è indipendente dalla base che si utilizza
per effettuare i conti.
Applicando lo stesso procedimento al quoziente si ottiene la penultima cifra
della rappresentazione in base B
Ripetendo la procedura è possibile ottenere tutte le altre cifre.
Informatica - Claudia d'Amato
32
Conversione decimale ⇒ binario
573dieci : 2dieci
286dieci : 2dieci
143dieci : 2dieci
71dieci : 2dieci
35dieci : 2dieci
17dieci : 2dieci
8dieci : 2dieci
4dieci : 2dieci
2dieci : 2dieci
1dieci : 2dieci
⇒
⇒
⇒
⇒
⇒
⇒
⇒
⇒
⇒
⇒
quoziente
quoziente
quoziente
quoziente
quoziente
quoziente
quoziente
quoziente
quoziente
quoziente
1 000 111 101due = 573dieci
Informatica - Claudia d'Amato
(cifra binaria meno significativa)
286dieci
143dieci
71dieci
35dieci
17dieci
8dieci
4dieci
2dieci
1dieci
0dieci
resto 1dieci
resto 0dieci
resto 1dieci
resto 1dieci
resto 1dieci
resto 1dieci
resto 0dieci
resto 0dieci
resto 0dieci
resto 1dieci
(cifra binaria più significativa)
33
Conversione decimale ⇒ binario
Si calcolano i resti delle divisioni per due
18 : 2 = 9
9:2=4
4:2=2
2:2=1
1:2=0
resto 0
resto 1
resto 0
resto 0
resto 1
10010
137 : 2 =
68 : 2 =
34 : 2 =
17 : 2 =
8:2=
4:2=
2:2=
1:2=
68
34
17
8
4
2
1
0
resto 1
resto 0
resto 0
resto 1
resto 0
resto 0
resto 0
resto 1
10001001
Informatica - Claudia d'Amato
34
Numeri binari: operazioni



Operazioni di somma di numeri binari naturali.
Con gli 8 bit utilizzati negli esempi qui riportati si possono
rappresentare i numeri naturali fino a 255dieci.
Operazioni che producono un risultato maggiore provocano
il superamento della capacità di rappresentazione (indicato
in gergo dal termine inglese overflow
).
1
1
Informatica - Claudia d'Amato
35
Ottali ed esadecimali


Utili per rappresentare sinteticamente valori binari
Ottali (base b = 8)
• Alfabeto ottale: cifre comprese tra 0 e 7
• 354otto = 3×82 + 5×81 + 4×80 = 192+40+4 = 236dieci
• 1461otto = 1×83 + 4×82 + 6×81 + 1×80 = 512+256+48+1 = 817dieci
• Ogni cifra ottale corrisponde a tre cifre binarie:
• 11101100due = [11] [101] [100] = 354otto
• 1100110001due = [1] [100] [110] [001] = 1461otto

Esadecimali (base b = 16)
• Alfabeto esadecimale: cifre 0 – 9 + lettere A – F
• ECsedici = 14×161 + 12×160 = 224 + 12 = 236dieci
• 331sedic = 3×162 + 3×161 + 1×160 = 768+48+1 = 817dieci
• Ogni cifra esadecimale corrisponde a quattro cifre binarie:
• 11101100due = [1110] [1100] = ECsedici
• 1100110001due = [11] [0011] [0001] = 331sedici
Informatica - Claudia d'Amato
36
Numeri naturali binari nei
calcolatori
 Per
la codifica dei numeri naturali (interi
positivi) si utilizzano abitualmente successioni
di 32 bit (4 byte) con cui si possono
rappresentare i numeri compresi tra
0 e 232–1 = 4'294'967'295 ≈ 4×109.
Informatica - Claudia d'Amato
37
Numeri interi relativi

Alfabeto binario
• anche il segno è rappresentato da 0 o 1
• è indispensabile indicare il numero k di bit utilizzati

Modulo e segno
• 1 bit di segno (0 positivo, 1 negativo)
• k – 1 bit di modulo
• Esempio:
+6dieci = 0110ms
–6dieci = 1110ms
• si rappresentano i valori da –2k–1+1 a 2k–1–1
• con 4 bit i valori vanno da –7 a +7
• con 8 bit i valori vanno da –127 a +127
• Attenzione: ci sono due rappresentazioni dello 0
• con 4 bit sono +0dieci = 0000ms –0dieci = 1000ms
Informatica - Claudia d'Amato
39
Numeri interi in complemento a 2

Alfabeto binario
• anche il segno è rappresentato da 0 o 1
• è indispensabile indicare il numero k di bit utilizzati

Complemento a 2
• X corrisponde al binario naturale di 2k + X
+6dieci ⇒ 24+6 = 22 ⇒
[1]0110 ⇒ 0110C2
–6dieci ⇒ 24– 6 = 10 ⇒
[0]1010 ⇒ 1010C2
• si rappresentano i valori da –2k–1 a 2k–1–1
• con 4 bit i valori vanno da –8 a +7
• con 8 bit i valori vanno da –128 a +127
• Con 32 bit i valori vanno da –2'147'483'648 fino a +2'147'483'647
• Attenzione: c’è una sola rappresentazione dello 0
• con 4 bit è +0dieci = 0000C2
Informatica - Claudia d'Amato
mentre 1000C2 = –8dieci
40
Il complemento a 2

Metodi alternativi per calcolare la
rappresentazione di –X a partire da quella di X
• Effettuare il complemento 1 di ogni bit di X, poi
aggiungere 1
• rappresentazione di +6dieci = 0110C2 (NB ci vogliono 4 bit!!)
• complemento di tutti i bit ⇒ 1001C2 (corrisponderebbe a -7dieci)
• aggiungere 1 ⇒ 1010C2 (che corrisponde a -6dieci)
• Partendo da destra e andando verso sinistra, lasciare
invariati tutti i bit fino al primo 1 compreso,
complementare tutti gli altri bit.
• rappresentazione di +6dieci = 0110C2 (NB ci vogliono 4 bit!!)
• gli ultimi due bit (_ _ 1 0) rimangono invariati
• gli altri due bit vengono complementati (1 0 1 0C2)
Informatica - Claudia d'Amato
41
Complemento a 2: alcune osservazioni


I valori positivi iniziano con 0, quelli negativi con 1
Data la rappresentazione di un numero su k bit, la
rappresentazione dello stesso numero su k+1 bit si
ottiene aggiungendo (a sinistra) un bit uguale al
primo (estensione del “segno”)
• Rappresentazione di –6 su 4 bit = 1010
• Rappresentazione di –6 su 5 bit = 11010
• Rappresentazione di –6 su 8 bit = 11111010

la sottrazione si effettua come somma algebrica
• 4 – 6 = +4 + (–6) = 0100 + 1010 = 1110 = –2
• 9 – 6 = +9 + (–6) = 01001 + 11010 = [1]00011 = +3
Informatica - Claudia d'Amato
43
C2: operazioni


Operazioni di somma di numeri binari in complemento a
due.
Con gli 8 bit utilizzati negli esempi qui riportati si possono
rappresentare i numeri interi da –128dieci fino a +127dieci
Informatica - Claudia d'Amato
44
C2: operazioni
ATTENZIONE
 Se due operandi dello stesso segno danno un
risultato di segno opposto vuol dire che è stata
superata la capacità di calcolo (overflow).
Informatica - Claudia d'Amato
45
Numeri razionali

Cifre più significative: sono le cifre associate ai pesi maggiori

Se i numeri hanno un valore molto grande o piccolo, si considerano solo
le cifre più significative --> rappresentazione in notazione scientifica:
un numero in base B viene rappresentato come: ±0.m×Be,
• numeri > 1: le cifre più significative sono quelle poste più a sinistra
• es.: 723'456 → cifra più significativa: 7, associata al peso 105, seguita da 2,
con peso 104, e così via;
• numeri < 1: le cifre più significative sono le prime diverse da 0 che si
incontrano, a partire dalla virgola, da sinistra verso destra
• es.: 0.0072345 --> cifra più significativa: 7, con peso 10 –3, seguita da 2, con
peso 10–4, e così via.
•
•
•

segno (+ oppure –),
coefficiente m, detto mantissa,
mantissa che è la parte frazionaria compresa tra 0 e 1
esponente e a cui elevare la base della numerazione, che è un intero ( 0)
Esempi:
• -123'450'000'000 diventa –0.12345×1012,
con segno negativo, mantissa 12345, ed esponente 12;
• +0.000012345, corrisponde a 0.12345×10-5,
con segno positivo, mantissa 12345 ed esponente –5.
Informatica - Claudia d'Amato
46
Rappresentazione binaria

Per esempio +101010000 diventa +0.10101×10 01001,
• segno positivo;
• mantissa 10101 (si noti che la mantissa inizia sempre con 1);
• esponente è 01001C2
(si noti come l’esponente sia un numero intero e per questo sia necessario adottare una
rappresentazione che permetta la codifica anche di valori negativi, come, per esempio,
quella in complemento a due).

Standard IEEE-754 (Institute of Electrical and Electronic Engineers):
• precisione doppia: 64 bit
• precisione singola: 32 bit
Informatica - Claudia d'Amato
47