3 Rappresentazione Info 15

Rappresentazione dell’informazione

Roberto SerraUniversità di Modena e Reggio Emilia &

European Centre for Living Technology, Venice

quale informazione?quale informazione? finora abbiamo parlato di informazione in termini molto generali

ma cosa vorremmo rappresentare?

numeri

lettere, parole

immagini

suoni

segnali

…

Continuo vs Continuo vs discretodiscreto

luce

ticchettio

Continuo vs Continuo vs discretodiscreto

le grandezze continue sono quelle che di solito associamo ai sistemi fisici e chimici spontanei

lunghezze, velocità, concentrazioni…

sono tipicamente rappresentate da numeri reali, che costituiscono un continuum

le grandezze discrete sono quelle che possono assumere solo solo alcuni valori ad esempio, un prezzo di vendita non può

avere una granularità minore di 1/100 di euro il ticchettio di un telegrafo Morse …

la meccanica quantistica ha mostrato che molte variabili che pensavamo continue sono in realtà discrete alcuni ipotizzano che in realtà siano tutte

così, ma la nostra attuale descrizione del mondo si basa in larga misura su variabili continue

un calcolatore digitale opera con variabili discrete

quindi per rappresentare variabili continue in un calcolatore digitale è necessario approssimarle con variabili discrete

le variabili “continue” sono tipicamente associate a valori reali anche i numeri complessi sono coppie di reali

in un sistema digitale non possono possono essere rappresentati valori irrazionali (non esprimibili come rapporto di due interi come p.es. , e, √2, etc.

una bella dimostrazione: dimostriamo che √2 non può essere pari al rapporto rapporto di due interi. Ragionamento per assurdo: √2=p/q primi fra loro (altrimenti semplifichiamo)

√2=p/q => p2=2q2 => p2 è pari => p è pari quindi p=2p’

p2=2q2 => 4p’2=2q2 => 2p’2=q2 => anche q è pari – contrario all’ipotesi! QED

in un calcolatore abbiamo sempre a che fare con sistemi finiti, quindi non è possibile esprimere in forma decimale numeri periodici

p.es. 1/3=0.333333…. 2/3=0.666666…,

ma è necessario approssimarli con un numero finito di cifre

p.es. 1/3=0.3333

2/3=0.6667,

reali

realirazionali

rappresentabili su macchina digitale finita

calcolatori calcolatori analogici?analogici?

La competizione fra calcolatori analogici e digitali nel XX secolo

I primi rappresentano le variabili in gioco mediante grandezze fisiche che evolvono in opportuni circuiti, dando una risposta P.es. calcolo di integrali Il circuito “simula fisicamente” il processo da descrivere si possono rappresentare numeri reali

I calcolatori digitali invece usano variabili discrete che cambiano nel tempo secondo regole opportune

fino circa alla metà del 900 i calcolatori analogici erano concorrenti pericolosi, ma nella seconda metà si sono affermati decisamente i calcolatori digitali

per ora?

calolatori digitalicalolatori digitali I calcolatori digitali usano variabili discrete che

cambiano nel tempo secondo regole opportune

Il programma “simula logicamente” il processo da descrivere

Quanti diversi valori delle variabili discrete sono necessari?

sono possibili diverse soluzioni, ma la più semplice è quella che si basa solo su due valori

questa scelta rende molto semplice distinguere i valori dal punto di vista circuitale

Rappresentazione Rappresentazione binariabinaria

Due soli simboli

Nel mondo fisico la più semplice è la presenza o assenza

di un fenomeno

Nel mondo logico i concetti di vero e falso

Un sistema binarioUn sistema binario imporre una scelta binaria (tertium non datur) non è privo di conseguenze

vi sono domande a cui non si può rispondere con un semplice sì/no mi ami? sei felice?

possono richiedere risposte più articolate: vedremo però che è possibile esprimere mediante due soli simboli tutto quello che può essere espresso dal linguaggio

vi sono però anche domande “fisiche” che non ammettono proprio una risposta binaria da quale fenditura è passato l’elettrone?

Un sistema binarioUn sistema binario come fare se vi sono più di due alternative? esprimere le diverse possibili situazioni come combinazioni di stati elementari binari

esempio: i numeri (Sistema binario)

L ’unità base di è il bit abbreviazione di binary digit

numeri decimali e numeri decimali e numeri binarinumeri binari

numeri decimali: 165 significa 1*100+6*10+5*1

165 = 5*100 + 6*101 + 1*102

analogamente, il numero binario 100110 corrisponde a

0*20 + 1*21 + 1*22+ 0*23+ 0*24+ 1*25

quindi, in base 10, a 2+4+32 = 38

Un sistema binarioUn sistema binario combinando diversi bit in maniera opportuna si possono rappresentare molte cose

L’adozione di un sistema binario, ovvero di due soli simboli, presenta notevoli vantaggi tecnologici

La memoria di un computer è organizzata come una sequenza di bit ogni posizione registra la presenza o l’assenza “leggibile” successivamente

Un gruppo di 8 bit costituisce un byte

AnalogiaAnalogia Un sentiero di blocchi di cemento

su ogni blocco può esserci un sasso

Se su un blocco c ’è un sasso: rappresenta 1 non c’è un sasso: rappresenta 0

EsempioEsempio

10100010

Uno strano Uno strano computer…computer…

Codifica del CD-ROMCodifica del CD-ROM

lato etichetta

lato trasparente

strato riflettente

raggio laser

Combinare più bitCombinare più bit Come rappresentare simboli più numerosi?

Una sequenza di bit rappresenta abbastanza simboli per codificare dati complessi 2 valori, con sequenze di lunghezza n ,

possiamo creare 2n simboli Esempio con 2 simboli: le basi del DNA 00 A 01 C 10 G 11 T

non solo numerinon solo numeri una sequenza di bit può rappresentare lo stato di un sistema

N biglie numerate 1, 2 …N

2 urne lo stato della biglia i-esima è

lo stato dell'intero sistema è

informazioneinformazioneN stati W nr. bit

(I)1 0,1 2 12 00, 01,

10, 114 2

3 000,001,010..

8 3

N 2N NW è il numero di stati diversi

un altro approccioun altro approccio supponiamo di avere due giocatori; uno sceglie a caso un numero, l'altro deve indovinarlo in altri termini: che probabilità ho di

scegliere a caso un particolare numero?

p=1/W

quindi

legame fra informazione e probabilità

la formula in questa versione vale se le scelte sono equiprobabili

cosa succede?cosa succede? se al posto delle biglie consideriamo delle molecole

che possono stare in uno dei due comparti?

la descrizione dello stato del sistema è la stessa

descrizione descrizione macroscopicamacroscopica

noi potremmo essere interessati a sapere solo quante molecole stanno da una parte e quante dall'altra

ovvero a una descrizione macroscopica

uno stato macro corrisponderà a diversi stati micro

quanti?

draft - not for quotation

probabilità dei probabilità dei macrostatimacrostati

esiste un solo modo per realizzare il macrostato N1=0 (0,0,0 …0)

esistono N modi diversi per realizzare N1=1 (1,0,0 …0,0), (0,1,0…0,0), (0,0,1…0,0) … (0,0,0 …0,1)

esistono N(N-1)/2 modi per realizzare N1=2 una volta fissata la posizione di uno degli “1” restano N-1

posti possibili per la seconda (si divide per due per evitare di contare due volte la stessa coppia, p.es. 2,3 e 3,2)

esistono N(N-1)(N-2)/(2*3) modi per realizzare N1=3 ...


numero di numero di microstati per un microstati per un certo valore di Ncerto valore di N11

esistono N(N-1)…(N-k+1)/(2*3*..*k) modi per realizzare N1=k

…

esistono N modi diversi per realizzare N1=N-1

esiste un solo modo per realizzare il macrostato N1=N

121111

11

11

1

11

1

11

!!!

)!(!!)(

1*2)...1)((1*2)...1)((*

!)1)...(1()(

!)1)...(1()(

NN

NNN

NNNNN

NNNNNNNN

NNNNNN

NNNNNN


macrostatimacrostati Per calcolare la probabilità di un dato macrostato M, è necessario:

Conoscere le probabilità dei singoli microstati

Sommare tutte le probabilità dei microstati che corrispondono allo stesso macrostato M

In assenza di informazioni specifiche, l’ ipotesi più fair è quella di supporre che tutti i microstati abbiano la stessa probabilità


se tutti i microstati sono equiprobabili, la probabilità di un macrostato è pari al numero di microstati corrispondenti, diviso per il numero totale di microstati possibili (2N) N

N NNNNNNp

2

)!(!!

2)()(

11

11


p(N1); N=6

00,05

0,10,15

0,20,25

0,30,35

0 1 2 3 4 5 6

p(N1); N=20

0

0,05

0,1

0,15

0,2

0 5 10 15 20

p(N1); N=50

-0,02

0

0,02

0,04

0,06

0,08

0,1

0,12

0 10 20 30 40 50

entropiaentropia il macrostato corrispondente al maggior numero di microstati è quello più probabile

se un sistema si trova in uno stato diverso, tenderà ad evolvere verso quello più probabile

legame col secondo principio della termodinamica!

cosa succede se gli cosa succede se gli stati non sono stati non sono equiprobabili?equiprobabili?

partiamo dal caso di un sistema con soli due stati: 1 o 0

se sono equiprobabili, come abbiamo visto:

W=2, p=1/2; I=logW=-logp=1

se però i due stati non sono equiprobabili, e la cosa è nota, allora il compito di chi deve indovinare è più facile

quindi l’informazione associata alla conoscenza di un valore “vale di meno”, è minore della precedente

in questo caso l’informazione è data da una formula simile alla precedente (-logp), ma riferita al valore atteso (-<logp>)

come si calcola <>?

per ogni funzione f vale la stessa formula

<f>=f1p1+f0p0

dove f1 (f0) è il valore di f quando il risultato del lancio è 1 (0)

e p1 (p0) è la probabilità che il risultato del lancio sia 1 (0)

come si calcola <>? supponiamo di fare tanti lanci, e che per ogni 1 io guadagni g1=10, e ad ogni 0 io guadagni soltanto g0=2

e supponiamo che la probabilità di ottenere 1 sia x in media, in M lanci otterrò xM volte 1, (1-x)M volte 0 il mio guadagno atteso è quindi 10xM+2(1-x)M =g1xM+g0(1-x)M il guadagno atteso per ogni lancio è <g>=g1x+g0(1-x)

=g1p1+g0p0

<g> è proprio il valore atteso del guadagno g la formula è scritta in maniera da essere indipendente

dai valori effettivi del guadagno e delle probabilità, è del tutto generale

per ogni funzione f vale quindi la stessa formula

<f>=f1p1+f0p0

dove f1 (f0) è il valore di f quando il risultato del lancio è 1 (0)

quindi adesso possiamo chiederci qual è il valor medio dell’informazione, ovvero del logaritmo della probabilità

<I>=-<logp>= -p1logp1 - p0logp0 = -pilogpi

l’espressione ha valore generale, quindi non sempre trasmettere il risultato di una scelta binaria corrisponde a un bit di informazione


a rigore: un bit è la quantità di informazione associata ad una scelta fra due alternative equiprobabili

in generale noi assoceremo comunque un bit ad una scelta binaria, supponendo implicitamente l’equiprobabilità come si fa di solito in informatica il bit diventa una “cosa” che può avere

due stati tenete però presente anche la def. più

generale di informazione


È utilizzata per la codifica di numeri e di caratteri

Anche per digitalizzare i suoni, i video e altro

per codificare TUTTO!

vediamo ad esempio i simboli che usiamo per scrivere (lettere, numeri, segni di punteggiatura)

I caratteri da I caratteri da codificarecodificare

95 caratteri (lingua inglese) 26 lettere minuscole e 26 maiuscole, 10 cifre numeriche, 10 segni aritmetici, 20 segni di interpunzione (spazi

inclusi) 3 caratteri non stampabili (a capo,

tabulazione, …)

sono necessari 7 bit 27=128

Codifica ASCIICodifica ASCII American Standard Code for Information Interchange rappresentazione a 7 bit

l’importanza degli standard condivisi

Limiti non basta per rappresentare i caratteri

dei linguaggi diversi dall’inglese lingue latine, nord europee, …

Extended ASCIIExtended ASCII Estensione di ASCII a 8 bit (256 simboli) la prima metà è l’ASCII originale

con 0 alla MSD di ogni gruppo di bit

Vantaggi codifica quasi tutti i linguaggi

occidentali include molti altri simboli utili

Un gruppo di 8 bit costituisce un byte

Codifica UNICODECodifica UNICODE Utilizza 32 bit

Rappresenta anche i caratteri di alfabeti non europei p.e.: asiatici, arabi, ebraici,

cirillici, …

I primi 256 caratteri sono quelli di extended ASCII

I nuovi standard generalizzano quelli vecchi, non li contraddicono facilita i programmi di conversione

Champernowne numberChampernowne number a proposito di numeri binari e di informazione

questa è una versione modificata del numero di Cx…

0.

0.01

0.0100011011

0.0100011011000001010011100101110111

…

iterando all'infinito, questo numero < 1 contiene tutte le possibili sequenze di bit

quindi anche tutti i libri che sono stati scritti (e quelli che non sono stati scritti!)

la biblioteca di Babele!

contiene anche il genoma di ogni individuo di ogni specie mai comparso sulla terra e tanti che non si sono mai visti dipende dalla codifica…

Codifica numero Codifica numero telefonicotelefonico

Il numero telefonico 888 555 1212 come sarà rappresentato nella memoria di un

computer?

Nota che il “numero” telefonico è una sequenza di simboli – ma in effetti noi non usiamo mai in questi casi le proprietà dei numeri

Codifica ogni cifra in un byte ASCII

Codifica ridondanteCodifica ridondante Il codice per telecomunicazioni

lettere intelligibili anche in presenza di rumore

necessariamente inefficiente

Es.: alfabeto NATO

Codifica NATOCodifica NATOA Alpha H Hotel O Oscar V Victor

B Bravo I India P Papa W Whiskey

C Charlie J Juliet Q Quebec X X-ray

D Delta K Kilo R Romeo Y Yankee

E Echo L Lima S Sierra Z Zulu

F Foxtrot M Mike T Tango

G Golf N November U Uniform

un altro codice un altro codice ridondante: il ridondante: il

codice geneticocodice genetico

Rappresentazione Rappresentazione dei numeridei numeri

Il caso più semplice è quello dei numeri naturali Compreso lo zero interi senza segno

Vengono rappresentati come numeri binari

Esempio: 10100 =0*20+0*21+1*22+0*23+1*24 =

=4+16= 20

di solito esiste una lunghezza massima ammessa della codifica di un numero, che determina il valore massimo che può essere rappresentato dipende dalla macchina (e a volte dal linguaggio)

Conversioni fra Conversioni fra sistema binario e sistema binario e

decimaledecimale Il sistema binario può descrivere tutti i numeri come quello decimale, anche se in maniera meno concisa

Entrambi sono sistemi posizionali Non tutti sono così, p.es. il sistema romano

3*104 + 0*103 + 5*102 + 5*101 + 2*100 = 30.000 + 500 + 50 + 2

3 0 5 5 2104 103 102 101 100

Conversioni fra Conversioni fra sistema binario e sistema binario e

decimaledecimale Sistema posizionale a base p ha p cifre: 0,…p-1; un numero generico Np è rappresentato in questa base da una sequenza cifre an, an-1…a0

Abbiamo visto come convertire un numero binario in decimale

Per effettuare la conversione da decimale a binario possiamo usare un semplice algoritmo

qui descritto in linguaggio naturale

Dividi il numero per due e registra il valore del resto; poi dividi il quoziente per due e registra il resto; ripeti queste operazioni finchè il quoziente non si annulla; a quel punto scrivi le cifre dei resti in successione, partendo dall’ultima – questo è il risultato

Esempio: il numero Esempio: il numero 165165

165:2 = 82 resto 1

82:2 = 41 resto 0

41:2 = 20 resto 1

20:2 =10 resto 0

10:2 = 5 resto 0

5:2 = 2 resto 1

2:2 = 1 resto 0

1:2 = 0 resto 1

16510=101001012

perché funziona?perché funziona? lo si capisce meglio applicandolo al familiare sistema decimale

165:10 = 16 resto 5

16:10 = 1 resto 6

1:10 = 0 resto 1

mettendo in ordine i resti (dall’ultimo al primo) ottengo proprio 165!

Numeri interiNumeri interi La rappresentazione più semplice riserva il primo bit per il segno (0 <-> +, 1 <-> -)

Se sono disponibili m bit potremo rappresentare gli interi compresi fra –(2m-

1-1) e +(2m-1-1)

Quindi con un byte potremmo rappresentare i numeri fra -127 e +127

A destra un esempio con tre bit Si noti la doppia rappresentazione dello 0 Altre rappresentazioni meno intuitive

consentono di evitare questo “spreco”

-3 111-2 110-1 101-0 100+0 000+1 001+2 010+3 011

La memoria di un calcolatore è divisa in byte da 8 bit E in parole da 16 o 32 bit

Questo spiega perché in informatica si sia fatto largo uso di sistemi di numerazione a base 8 e soprattutto 16

Il sistema esadecimale consente di descrivere con un unico simbolo il contenuto di una parola da 16 bit

Come fa il sistema a sapere se la successione di 1 e 0 in una data posizione rappresenta un carattere Ascii o un numero intero?

O addirittura, come vedremo, una istruzione di programma?

Di questo si occupa il controllo, che studieremo in futuro

Per ora vediamo altre rappresentazioni

Numeri realiNumeri reali Possono avere un numero infinito di cifre decimali P.es. , e, numero aureo, √2 …

Ma un calcolatore ha una memoria finita In generale per ogni numero è definita una

dimensione massima della porzione di memoria che può essere impiegata

Quindi in un calcolatore un numero reale è approssimato da un numero razionale Con un numero limitato di cifre decimali

numero aureonumero aureo

è il rapporto fra due numeri, di cui il maggiore è medio proporzionale fra la loro somma e il minore dei due

chiamato anche sezione aurea o divina proporzione (Leonardo, Luca Pacioli)

scoperto dai pitagorici o prima?

è il limite del rapporto fra due termini successivi della successione di Fibonacci

Fk = Fk-1 + Fk-2

architettura (p.es. rettangolo aureo), forme naturali …

Numeri frazionariNumeri frazionari Sono numeri reali compresi fra 0 e 1

approssimati con numeri razionali Espressione in base p

Anche in questo caso esistono regole per passare da base 2 a base 10

Rappresentazione Rappresentazione dei numeri realidei numeri reali

In virgola fissa: si definisce una volta per tutte quanti bit sono dedicati alla parte decimale P.es. 00101001011.10110 Richiede di allocare un numero fisso di

posizioni per la parte decimale Non sempre è necessario

Risente delle consuete limitazioni sui valori massimi esprimibili per la parte intera

Fra –(2m-1-1) e +(2m-1-1) se vi sono m bit per la parte intera

Rappresentazione in Rappresentazione in virgola mobilevirgola mobile

Notazione esponenziale 345,67 = 0,34567*103

Il primo elemento, compreso fra -1 e 1, è detto mantissa Ed è un numero frazionario

L’esponente è detto caratteristica Ed è un numero intero

In questo caso si riserva un numero fisso di cifre alla mantissa e alla caratteristica

Lo stesso può essere fatto in binario Per passare alla notazione decimale si

operano le due conversioni indipendentemente

La rappresentazione in virgola mobile consente di rappresentare con lo stesso numero di bit numeri più grandi Perché la notazione esponenziale consente di

rappresentare numeri elevati con poche cifre

Sebbene con granularità non uniforme I numeri sono più fitti attorno allo 0 e più

radi alle estremità dell’intervallo

I linguaggi di programmazione consentono di scegliere il tipo di rappresentazione numerica più appropriato

vedremo in seguito altre rappresentazioni

Rappresentazione di Rappresentazione di segnali sonori (p.es. segnali sonori (p.es.

musica)musica) Le onde di pressione sonora fanno vibrare i nostri timpani

La forza o intensità della pressione determina il volume

La frequenza (numero di onde al secondo) è il tono

il caso più il caso più semplice: notasemplice: nota

una nota pura corrisponde a un'onda sinusoidale

frequenza : numero di cicli al secondo un ciclo al secondo <-> un Hertz

lunghezza d'onda : distanza fra due creste

velocità (di gruppo) V=

infatti se un'onda è lunga 10m, e ne passano 100 al secondo, il sistema percorre 10*100=1000 m al secondo

stessa frequenza, stessa frequenza, diversa intensitàdiversa intensità

sovrapposizione di sovrapposizione di ondeonde

in un segnale complesso è possibile distinguere i singoli componenti sinusoidali mediante la tecnica dell'analisi di Fourier

Da analogico a Da analogico a digitaledigitale

Digitalizzare informazioni continue

I valori della pressione andranno registrati a certi intervalli

e i risultati andranno espressi in maniera digitale

Quando eseguire le misure? non possiamo registrare ogni punto

dell’onda

ConversioniConversioni

CampionamentoCampionamento Si prendono le misure a intervalli regolari

Frequenza di campionamento il numero di misurazioni al secondo maggiore è la frequenza, più accurata

sarà la registrazione

la frequenza di campionamento non coincide con quella dell'onda sonora ma occorrono alcune cautele per evitare

disastri!

Esempio di Esempio di campionamentocampionamento

tempo

pressione del suono

Quale frequenza?Quale frequenza? Frequenza di campionamento legata a quella dell’onda una frequenza di campionamento troppo

bassa potrebbe interpretare in maniera errata i punti campionati (aliasing)

Regola di NyquistRegola di Nyquist Frequenza di campionamento

almeno il doppio di quella dell’onda da registrare

l ’uomo può percepire suoni fino a 20.000Hz, un campionamento di 40.000Hz è sufficiente

la frequenza CD standard è 44.100Hz

Quanti bit per Quanti bit per campione?campione?

Quanto dev’essere accurato un campione? i bit devono rappresentare i valori sia

positivi che negativi più bit ci sono, più è accurato il

campione

Campione CDCampione CD La rappresentazione digitale dei CD audio utilizza 16 bit registra 65.536 livelli, la metà per i valori positivi e

altrettanti per quelli negativi

Il campionamento converte il segnale in una sequenza di numeri, ognuno dei quali indica il valore del segnale in una specifica finestra

Una conversione simile viene operata in numerosi altri casi

Segnali radar e sonar

Serie temporali di dati meteo

Serie temporali finanziarie …

3 Rappresentazione Info 15

Documents

Transcript of 3 Rappresentazione Info 15