Teoria dell’Informazione (Classica)
Andrea G. B. Tettamanzi
Università degli Studi di Milano
Dipartimento di Tecnologie dell’Informazione
Andrea G. B. Tettamanzi, 2001
Lezione 1
3 ottobre 2002
Andrea G. B. Tettamanzi, 2001
Programma del Corso
•
•
•
•
•
•
•
•
•
Che cos’è l’Informazione e che cos’è la T.I.
Richiami di Teoria della Probabilità
Proprietà matematiche utilizzate nella T.I.
Misura dell’informazione: l’Entropia.
Codici
Comunicazione in presenza di rumore
Codici a correzione d’errore
Cenni sulla Teoria della Trasmissione
Cenni di Crittografia
Andrea G. B. Tettamanzi, 2001
Bibliografia
• E. ANGELERI: Informazione: significato e universalità, UTET,
Torino, 2000. (libro di testo)
• J. VAN DER LUBBE: Information Theory, Cambridge University
Press, 1988.
• J. R. PIERCE: An Introduction to Information Theory, Dover,
1980.
Andrea G. B. Tettamanzi, 2001
Che Cos’è l’Informazione?
SINTASSI
SEMANTICA
PRAGMATICA
Andrea G. B. Tettamanzi, 2001
Informazione
informazione
significato
apparato
simbolico
Rilevanza pratica dell’informazione (effetto, scopo, ecc.)
Andrea G. B. Tettamanzi, 2001
Informazione - semantica
• La quantità di informazione di un enunciato è tanto più grande
quante più sono le alternative che esso esclude.
A
Andrea G. B. Tettamanzi, 2001
B
U
Che cos’è la Teoria dell’Informazione?
• Una teoria matematica dell’aspetto simbolico dell’Informazione
• Un approccio quantitativo alla nozione di Informazione
• Risponde alle domande:
– Come immagazzinare e trasmettere informazione in modo
compatto? (compressione)
– Qual’è la massima quantità di informazione che può essere
trasmessa su un canale? (velocità di trasmissione)
– Come posso proteggere la mia informazione:
• dalla corruzione del suo supporto o da errori di trasmissione?
• da sguardi indiscreti?
Andrea G. B. Tettamanzi, 2001
Compressione
Immagazzinamento = Trasmissione
scrittura
t0
x0
invio
lettura
t1
Andrea G. B. Tettamanzi, 2001
x1
ricezione
Funzioni convesse
f ( x1 )  f ( x2 )  f (x1  x2 )
   1
,   0
Diseguaglianza fondamentale:
x
log b x 
1
ln b
Andrea G. B. Tettamanzi, 2001
ln x  x 1
Convessità del valore atteso
g( X )
convessa
E[ g ( X )]  g ( E[ X ])
g( X )
concava
E[ g ( X )]  g ( E[ X ])
Andrea G. B. Tettamanzi, 2001
Misura dell’Informazione
Alfabeto di s simboli
R. V. L. Hartley
C
I
1
2
s
l
A
O
,
M
A
M
M
A
!
l
Messaggi possibili
R. Hartley
H ( s )  log s  l log s
l
Perché il logaritmo? Perché così
Andrea G. B. Tettamanzi, 2001
l
H ( s )  lH ( s )
l
1
Unità di misura dell’Informazione
A
A
1
P ( A)  P ( A ) 
2
La quantità di informazione che permette di distinguere uno
di due eventi equiprobabili e mutuamente esclusivi è l’unità
di misura dell’informazione: il bit.
Un simbolo di un alfabeto di s simboli equiprobabili porterà
un’informazione di
log 2 s bit
Andrea G. B. Tettamanzi, 2001
Entropia informativa di Shannon
n
H ( X )   P( xi ) log P( xi )
i 1
continua
simmetrica (commutativa)
additiva
Andrea G. B. Tettamanzi, 2001
H ( X , Y )  H ( X )  H (Y )
Massimo dell’Entropia
H ( X )  log n
n
n
1
H ( X )  log n   pi log pi  log n   pi log

pi n
i 1
i 1
 1

 n 1 n 
  pi 
 1 log e     pi  log e 
i 1
 i 1 n i 1 
 pi n 
 (1  1) log e  0
n
N.B.: log a b 
Andrea G. B. Tettamanzi, 2001
1
log b a
Entropia delle lingue
Frequenze
dei simboli
testo
P(" A" )

P(" Z" )
"Z"
1
H ( testo )   P( )log 2
P( )
 "A"
Andrea G. B. Tettamanzi, 2001
Ridondanza
R  1 
Efficienza di codifica
H (it )  3,956
H (fr )  3,896
H (de)  4,046
H (en )  4,056
Andrea G. B. Tettamanzi, 2001
H (X )

log 2 M
 (it )  0,887
 (fr )  0,839
 (de)  0,850
 (en )  0,853
Informazione secondo Kolmogorov
Misura assoluta, non utilizza la probabilità
D( y)  x
y
x
Y
X
oggetti
fn.
parziale
ricorsiva
K ( x)  min y
D ( y ) x
Andrea G. B. Tettamanzi, 2001
descrizioni
Equivalenza con entropia di Shannon
x : K ( x)  k  2
k
H ( X n )   p( x n ) K ( x n ) H ( X n )  2 log n  c
xn
H ( X )  nH ( X )
n
n
K (x )
lim
 H(X )
n 
n
Andrea G. B. Tettamanzi, 2001