Andrea G. B. Tettamanzi, 2001

Teoria dell’Informazione (Classica)Teoria dell’Informazione (Classica)

Andrea G. B. Tettamanzi

Università degli Studi di MilanoDipartimento 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

significato

Informazione

informazione

apparatosimbolico

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.

UA B

Andrea G. B. Tettamanzi, 2001

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

lettura

t0

t1

invio ricezione

x0 x1

Andrea G. B. Tettamanzi, 2001

Funzioni convesse

)()()( 2121 xxfxfxf

0,1

Diseguaglianza fondamentale:

1ln xx1ln

log bxxb

Andrea G. B. Tettamanzi, 2001

Convessità del valore atteso

convessa

concava

)(Xg ])[()]([ XEgXgE

)(Xg ])[()]([ XEgXgE

Andrea G. B. Tettamanzi, 2001

Misura dell’Informazione

R. V. L. Hartley Alfabeto di s simboli

C I A O M M MA A, !

1 2 l

Messaggi possibilils

slssH ll loglog)( R. Hartley

)()( 1slHsH l Perché il logaritmo? Perché così

Andrea G. B. Tettamanzi, 2001

Unità di misura dell’Informazione

A A 21)()( APAP

La quantità di informazione che permette di distinguere unodi 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 s2log bit

Andrea G. B. Tettamanzi, 2001

Entropia informativa di Shannon

n

iii xPxPXH

1

)(log)()(

continua

simmetrica (commutativa)

additiva )()(),( YHXHYXH

Andrea G. B. Tettamanzi, 2001

Massimo dell’Entropia

nXH log)(

n

i

n

i iiii nppnppnXH

1 1

1loglogloglog)(

0log)11(

log1log11111

e

epn

enp

pn

ii

n

i

n

i ii

ab

ba log

1log N.B.:

Andrea G. B. Tettamanzi, 2001

Entropia delle lingue

testo

)Z""(

)A""(

P

P

Frequenzedei simboli

Z""

A""2 )P(

1)logP()testo(

H

Andrea G. B. Tettamanzi, 2001

Ridondanza

1R Efficienza di codificaMXH

2log)(

056,4)en(046,4)de(

896,3)fr(956,3)it(

HHHH

853,0)en(850,0)de(839,0)fr(887,0)it(

Andrea G. B. Tettamanzi, 2001

Informazione secondo KolmogorovMisura assoluta, non utilizza la probabilità

X Y

xyD )(x y

descrizionioggetti

yxKxyD

)(

min)(

fn.parzialericorsiva

Andrea G. B. Tettamanzi, 2001

Equivalenza con entropia di Shannon

kkxKx 2)(:

cnXHxKxpXH n

x

nnn

n

log2)()()()(

)()( XnHXH n

)()(lim XHnxK n

n