Alle origini
della scienza dell’informazione /4
Luca Mari
28.3.01
Dove ci siamo lasciati …
Per portare informazione abbiamo bisogno di supporti fisici
 Un supporto fisico può essere usato in modo più o meno
efficiente:

A parità di “quantità di supporto” impegnato, la prima
immagine porta una “quantità di informazione” assai minore!
… e quindi dovrebbe essere possibile ridurre la quantità di
supporto senza perdere informazione: la compressione
10 KB – 10 KB
compressione
0,2 KB – 10 KB
2
Supporti non efficienti?
Il fenomeno per cui un supporto porta meno
informazione di quella che potrebbe si chiama …
ridondanza
… una caratteristica fondamentale per caratterizzare la
relazione tra mondo fisico e mondo dell’informazione,
e assai diffusa nei sistemi che usiamo per comunicare
Ma perché allora la accettiamo?
La ridondanza è sempre e solo motivo di inefficienza,
oppure esiste anche una ridondanza utile?
3
Ridondanza o ridondanze?
Un chiarimento: una comunicazione (per esempio
testuale) può includere “livelli” diversi di ridondanza:
“Ci-ci-ciao a tu-tutti”
nei componenti elementari (singoli
caratteri o fonemi)
“Ciao a tutti”
internamente ai termini lessicali
“Ciao ciao a tutti”
nei termini lessicali
“Ciao a tutti: vi saluto”
nella struttura semantica
cia
o
nella situazione pragmatica
4
Comunicazione: obiettivi e condizioni
Dal nostro punto di vista, l’obiettivo generale della comunicazione è
scambiare informazione
mittente
supporto / canale
destinatario
Un supporto fisico impiegato per questo scopo dovrebbe consentire
al destinatario della comunicazione di ricostruire integralmente
l’informazione inviatagli dal mittente; ma …
“ciao”
“cibo”
… disturbi / rumore a cui il supporto è sottoposto distorcono, in
generale, l’informazione inviata
Come assicurarsi che ciò non accada?
5
Per esempio: un gioco …
Ognuno di noi deve comunicare agli altri il suo
numero di telefono:
1.
2.
3.
4.
e ognuno, al suo turno, ha
e ognuno, al suo turno, ha
in un ambiente rumoroso
e ognuno, al suo turno, ha
e ognuno, al suo turno, ha
in un ambiente rumoroso
10 secondi per parlare
10 secondi per parlare
3 secondi per parlare
3 secondi per parlare
6
Qualche conclusione




Un supporto a k stati porta al più log2(k) biti di informazione
… mentre la quantità minima di informazione che un supporto
può portare è …
0 biti, ovviamente!
Se disponiamo di informazione per x<log2(k) biti su un
supporto a k stati (che quindi è ridondante), possiamo (se
vogliamo eliminare la ridondanza …) ridurre il numero degli
stati (cioè comprimere il supporto) fino a un valore k’ tale che
x=log2(k’) biti
Dunque il limite alla possibilità di compressione di un supporto
è dato (naturalmente!) dalla quantità di informazione che esso
deve portare
7
Il problema, dunque
Come stabilire quanta informazione è portata
effettivamente da un certo supporto?
e quindi qual è il limite alla possibilità di
comprimere quel supporto senza perdere
l’informazione che esso porta?
8
Un esempio
Ho una classe di 100 studenti, e a ognuno devo
comunicare un voto: A, B, C o D …
… e per la comunicazione posso usare solo
dispositivi bistabili, cioè bitm
A priori, per esempio:
A
B
C
D
In questo modo, per comunicare i 100 voti devo
usare 200 bitm: possiamo ridurre questo valore?
9
Un esempio /2
Supponiamo che la distribuzione dei voti non sia
uniforme, ma (voto e frequenza):
A: 1/2
B: 1/4
C: 1/8
D: 1/8
Supponiamo di ri-codificare i voti così :
A
B
C
D
Per cui, per esempio:
B
A D
C
A
Cioè la regola di codifica è corretta, nel senso che
consente di ricostruire univocamente i voti
10
Un esempio /3
Problema: con questa distribuzione e questa codifica:
A: 1/2
B: 1/4
C: 1/8
D: 1/8
quanti bitm sono necessari per comunicare i 100 voti?
Ogni voto richiede in media
1*1/2+2*1/4+3*1/8+3*1/8 = 1,75 bitm
e dato che i voti sono 100 …
… siamo passati da 200 a 175 bitm …
Abbiamo compresso il supporto!
11
Un esempio /4
La codifica che abbiamo adottato:
A: 1/2
B: 1/4
C: 1/8
D: 1/8
ci consente di giungere, per esemplificazione, a un
risultato fondamentale a proposito di (quantità di)
informazione:
quanto meno è frequente / probabile un’entità di
informazione, tanto maggiore è la quantità di
informazione che l’osservazione di tale entità porta
12
13
14
Qualche passo
verso una formalizzazione
Dato l’insieme degli stati riconosciuti come possibili
per il sistema fisico X = {x1, …, xn},
ipotizziamo che nessuno di essi sia certo e nessuno
impossibile
Dunque a ogni xi l’osservatore dovrebbe essere in
grado di associare un grado di (in)certezza
Ci sa come si fa?
Si usa, tipicamente, la funzione PROBABILITA’
15
Qualche idea sulla probabilità
Dato un insieme di stati X = {x1, …, xn},
a ogni xi si associa un “grado di certezza” P(xi)
nell’intervallo (0,1),
tale che:
P(xi)=0 significa che xi è giudicato impossibile
P(xi)=1 significa che xi è giudicato certo
P(xi)>P(xj) significa che xi è giudicato più certo di xj
e tale che:
P(xi oppure xj)=P(xi)+P(xj)
e quindi
SiP(xi)=1
16
Probabilità e informazione
Data la struttura probabilistica del sistema fisico
impiegato come supporto per informazione:
x1, …, xn
P(x1), …, P(xn)
quale relazione ci dovrebbe essere tra la probabilità
di xi e la “quantità di informazione” Qinf(xi) che
l’osservazione dello stato xi porta all’osservatore
?
17
Probabilità e informazione /2
Qualche condizione:
 se P(xi)=1, QInf(xi)=0 (“lo sapevo già …”)
 se P(xi)=0, QInf(xi) è indefinito (“tanto non è
osservabile …”)
… e più in generale:
… e quella fondamentale:
 se P(xi)>P(xj), QInf(xi)<QInf(xj)
18