Fasi della programmazione - Home di homes.di.unimi.it · La presenza di informazione è...
-
Upload
truongdung -
Category
Documents
-
view
219 -
download
0
Transcript of Fasi della programmazione - Home di homes.di.unimi.it · La presenza di informazione è...
![Page 1: Fasi della programmazione - Home di homes.di.unimi.it · La presenza di informazione è condizionata dal fatto che sia ... Sistema di numerazione posizionale in base b c K c K-1 ...](https://reader031.fdocumenti.com/reader031/viewer/2022022113/5c66c5c209d3f2e4308cbe81/html5/thumbnails/1.jpg)
Rappresentazione
dell’informazioneGabriella Trucco
![Page 2: Fasi della programmazione - Home di homes.di.unimi.it · La presenza di informazione è condizionata dal fatto che sia ... Sistema di numerazione posizionale in base b c K c K-1 ...](https://reader031.fdocumenti.com/reader031/viewer/2022022113/5c66c5c209d3f2e4308cbe81/html5/thumbnails/2.jpg)
Simboli e alfabeto
Per formalizzare dati (numeri, caratteri, immagini, suoni, …) si utilizzano
successioni di simboli scelti da un insieme finito detto alfabeto
Alfabeto: {A,B,C,…,Z}, Simboli: A, B, …
Alfabeto: {0,1,2,…,9}, Simboli: 0, 1, …
Alfabeto: {"$%ONM}, Simboli: M%O
Ad ogni alfabeto è associato un insieme di regole di composizione
Regole per la composizione dei numeri
Regole per la composizione delle parole
![Page 3: Fasi della programmazione - Home di homes.di.unimi.it · La presenza di informazione è condizionata dal fatto che sia ... Sistema di numerazione posizionale in base b c K c K-1 ...](https://reader031.fdocumenti.com/reader031/viewer/2022022113/5c66c5c209d3f2e4308cbe81/html5/thumbnails/3.jpg)
Informazione e incertezza
Informazione veicolata da un supporto
La presenza di informazione è condizionata dal fatto che sia possibile
scegliere tra diverse configurazioni
Se la nostra incertezza circa l’effettiva configurazione del supporto viene
ridotta dall’accesso al supporto, allora tale atto ci ha portato
dell’informazione
Se potessimo misurare l’incertezza prima e dopo la lettura, la quantità di
informazione potrebbe essere definita dalla differenza tra tali gradi di
incertezza
![Page 4: Fasi della programmazione - Home di homes.di.unimi.it · La presenza di informazione è condizionata dal fatto che sia ... Sistema di numerazione posizionale in base b c K c K-1 ...](https://reader031.fdocumenti.com/reader031/viewer/2022022113/5c66c5c209d3f2e4308cbe81/html5/thumbnails/4.jpg)
Unità di informazione elementare
Ipotesi
Si conoscono a priori le configurazioni che il supporto può assumere
Non si sa quali di esse sia quella effettivamente assunta
La quantità di informazione che si ottiene selezionando una configurazione
da un insieme che ne contiene due è l’unità di informazione elementare
(bit).
Bit: unità di misura dell’informazione, definito come la quantità di
informazione necessaria per decidere tra due alternative equiprobabili
![Page 5: Fasi della programmazione - Home di homes.di.unimi.it · La presenza di informazione è condizionata dal fatto che sia ... Sistema di numerazione posizionale in base b c K c K-1 ...](https://reader031.fdocumenti.com/reader031/viewer/2022022113/5c66c5c209d3f2e4308cbe81/html5/thumbnails/5.jpg)
Rappresentazione binaria
dell’informazione
Per informazione intendiamo tutto ciò che è manipolabile dal calcolatore:
Numeri (naturali, interi, reali, …)
Caratteri
Immagini, suoni etc.
Programmi
Nel calcolatore, al livello macchina, le informazioni sono rappresentate in
forma binaria: sequenze di 1 e 0.
![Page 6: Fasi della programmazione - Home di homes.di.unimi.it · La presenza di informazione è condizionata dal fatto che sia ... Sistema di numerazione posizionale in base b c K c K-1 ...](https://reader031.fdocumenti.com/reader031/viewer/2022022113/5c66c5c209d3f2e4308cbe81/html5/thumbnails/6.jpg)
Codifica binaria
Alfabeto
2 simboli: {0, 1}, {on, off}, {J, L}
Problema
Assegnare un codice univoco a tutti gli oggetti appartenenti ad un insieme predefinito
Quanti oggetti posso codificare con k bit?
1 bit (0, 1) 2 oggetti
2 bit (00, 01, 10, 11) 4 oggetti
3 bit (000, 001, 010, …, 111) 8 oggetti
…
k bit 2k oggetti
Quanti bit mi servono per codificare N oggetti?
![Page 7: Fasi della programmazione - Home di homes.di.unimi.it · La presenza di informazione è condizionata dal fatto che sia ... Sistema di numerazione posizionale in base b c K c K-1 ...](https://reader031.fdocumenti.com/reader031/viewer/2022022113/5c66c5c209d3f2e4308cbe81/html5/thumbnails/7.jpg)
Giorni della settimana in binario
![Page 8: Fasi della programmazione - Home di homes.di.unimi.it · La presenza di informazione è condizionata dal fatto che sia ... Sistema di numerazione posizionale in base b c K c K-1 ...](https://reader031.fdocumenti.com/reader031/viewer/2022022113/5c66c5c209d3f2e4308cbe81/html5/thumbnails/8.jpg)
Codifica binaria dei caratteri
Quanti sono gli oggetti compresi nell’insieme?
26 lettere maiuscole + 26 lettere 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 28=256 caratteri (ASCII esteso)
UNICODE: codice più esteso per rappresentare anche i caratteri delle lingue orientali
![Page 9: Fasi della programmazione - Home di homes.di.unimi.it · La presenza di informazione è condizionata dal fatto che sia ... Sistema di numerazione posizionale in base b c K c K-1 ...](https://reader031.fdocumenti.com/reader031/viewer/2022022113/5c66c5c209d3f2e4308cbe81/html5/thumbnails/9.jpg)
ASCII su 7 bit
![Page 10: Fasi della programmazione - Home di homes.di.unimi.it · La presenza di informazione è condizionata dal fatto che sia ... Sistema di numerazione posizionale in base b c K c K-1 ...](https://reader031.fdocumenti.com/reader031/viewer/2022022113/5c66c5c209d3f2e4308cbe81/html5/thumbnails/10.jpg)
Numeri naturali
Sistema di numerazione posizionale in base b
cKcK-1…c0 rappresenta cK*bK + cK-1*bK-1 + … + c0*b0
123110= 1*103 + 2*102 + 3*101 + 1*100
Conversione Binario Decimale
Basta scrivere il numero secondo la notazione posizionale utilizzando già il
sistema decimale
11012= 1*23 + 1*22 + 0*21 + 1*20
![Page 11: Fasi della programmazione - Home di homes.di.unimi.it · La presenza di informazione è condizionata dal fatto che sia ... Sistema di numerazione posizionale in base b c K c K-1 ...](https://reader031.fdocumenti.com/reader031/viewer/2022022113/5c66c5c209d3f2e4308cbe81/html5/thumbnails/11.jpg)
Rappresentazione dei numeri naturali
Numero naturale: oggetto matematico che può essere rappresentato
come una sequenza di simboli a partire da un alfabeto (l’alfabeto dei
numeri sono le cifre: 1,2,3, …)
Confrontiamo due rappresentazioni:
1. Additiva (ad es. cifre romane)
2. Posizionale: il valore di ogni cifra dipende dalla posizione che occupa nella
sequenza
![Page 12: Fasi della programmazione - Home di homes.di.unimi.it · La presenza di informazione è condizionata dal fatto che sia ... Sistema di numerazione posizionale in base b c K c K-1 ...](https://reader031.fdocumenti.com/reader031/viewer/2022022113/5c66c5c209d3f2e4308cbe81/html5/thumbnails/12.jpg)
Rappresentazione addizionale dei
numeri
Alfabeto cifre romane: I V X L C D M
I, II, III, IV, V, VI, VII …
X, XX, XXX, XL, L, LX, LXX, LXXX, XC
C, CC, CCC, CD, D, DC, DCC, DCCC, CM
M, MM, MMM
Ruolo posizione: somma o sottrazione
Es: IV e VI
![Page 13: Fasi della programmazione - Home di homes.di.unimi.it · La presenza di informazione è condizionata dal fatto che sia ... Sistema di numerazione posizionale in base b c K c K-1 ...](https://reader031.fdocumenti.com/reader031/viewer/2022022113/5c66c5c209d3f2e4308cbe81/html5/thumbnails/13.jpg)
Rappresentazione posizionale dei
numeri
![Page 14: Fasi della programmazione - Home di homes.di.unimi.it · La presenza di informazione è condizionata dal fatto che sia ... Sistema di numerazione posizionale in base b c K c K-1 ...](https://reader031.fdocumenti.com/reader031/viewer/2022022113/5c66c5c209d3f2e4308cbe81/html5/thumbnails/14.jpg)
Numeri e numerali
![Page 15: Fasi della programmazione - Home di homes.di.unimi.it · La presenza di informazione è condizionata dal fatto che sia ... Sistema di numerazione posizionale in base b c K c K-1 ...](https://reader031.fdocumenti.com/reader031/viewer/2022022113/5c66c5c209d3f2e4308cbe81/html5/thumbnails/15.jpg)
Conversione decimale binario
![Page 16: Fasi della programmazione - Home di homes.di.unimi.it · La presenza di informazione è condizionata dal fatto che sia ... Sistema di numerazione posizionale in base b c K c K-1 ...](https://reader031.fdocumenti.com/reader031/viewer/2022022113/5c66c5c209d3f2e4308cbe81/html5/thumbnails/16.jpg)
Numeri interi
Alfabeto binario
Anche il segno è rappresentato con 0 e 1
E’ indispensabile indicare il numero K di bit utilizzati
Modulo e Segno (MS)
1 bit di segno (0 positivo, 1 negativo)
K-1 bit di modulo
Es. +610 = 0110MS, -610 = 1110MS
Si rappresentano i valori da +2K-1-1 a -2K-1-1
Con 4 bit i valori da -7 a +7
Con 8 bit i valori da -127 a +127
Problema: doppia rappresentazione per lo zero (0000, 1000)
Soluzione alternativa: rappresentazione in complemento
![Page 17: Fasi della programmazione - Home di homes.di.unimi.it · La presenza di informazione è condizionata dal fatto che sia ... Sistema di numerazione posizionale in base b c K c K-1 ...](https://reader031.fdocumenti.com/reader031/viewer/2022022113/5c66c5c209d3f2e4308cbe81/html5/thumbnails/17.jpg)
Diverse codifiche/interpretazioni
![Page 18: Fasi della programmazione - Home di homes.di.unimi.it · La presenza di informazione è condizionata dal fatto che sia ... Sistema di numerazione posizionale in base b c K c K-1 ...](https://reader031.fdocumenti.com/reader031/viewer/2022022113/5c66c5c209d3f2e4308cbe81/html5/thumbnails/18.jpg)
Complemento a 1
Positivi come M.S.
Negativi: complemento alla base meno 1
Complemento bit a bit dei numeri positivi corrispondenti
Rispetto a M.S., per i numeri negativi
Lascio invariato il primo bit
Complemento il resto
Anche qui sono presenti due rappresentazioni dello zero
![Page 19: Fasi della programmazione - Home di homes.di.unimi.it · La presenza di informazione è condizionata dal fatto che sia ... Sistema di numerazione posizionale in base b c K c K-1 ...](https://reader031.fdocumenti.com/reader031/viewer/2022022113/5c66c5c209d3f2e4308cbe81/html5/thumbnails/19.jpg)
Complemento a 2
Metodi per calcolare la rappresentazione di -X a partire da X
Effettuare il complemento di ogni bit di X e aggiungere 1
Rappresentazione di +610=0110C2 (N.B. ci vogliono 4 bit!)
Complemento di tutti i bit 1001C2 (corrisponderebbe a -710)
Aggiungere 1 1010C2 (che corrisponde a -610)
Partendo da destra e andando verso sinistra lasciare invariati tutti i bit fino al
primo 1 compreso, complementare tutti gli altri bit
Rappresentazione di +610=0110C2 (N.B. ci vogliono 4 bit!)
Gli ultimi due bit (_._.1.0) rimangono invariati
Gli altri due bit vengono complementati (1.0.1.0C2)
![Page 20: Fasi della programmazione - Home di homes.di.unimi.it · La presenza di informazione è condizionata dal fatto che sia ... Sistema di numerazione posizionale in base b c K c K-1 ...](https://reader031.fdocumenti.com/reader031/viewer/2022022113/5c66c5c209d3f2e4308cbe81/html5/thumbnails/20.jpg)
Numeri interi in complemento a 2
Si rappresentano i valori da -2K-1 a +2K-1-1
Con 4 bit i valori da -8 a +7
Con 8 bit i valori da -128 a +127
Conversione C2 Decimale
bk bk-1 bk-2... b0 = -bk*2K + (bK-1*2K-1 + … + b0*20)
C’è una sola rappresentazione dello 0
![Page 21: Fasi della programmazione - Home di homes.di.unimi.it · La presenza di informazione è condizionata dal fatto che sia ... Sistema di numerazione posizionale in base b c K c K-1 ...](https://reader031.fdocumenti.com/reader031/viewer/2022022113/5c66c5c209d3f2e4308cbe81/html5/thumbnails/21.jpg)
Diverse codifiche/interpretazioni
![Page 22: Fasi della programmazione - Home di homes.di.unimi.it · La presenza di informazione è condizionata dal fatto che sia ... Sistema di numerazione posizionale in base b c K c K-1 ...](https://reader031.fdocumenti.com/reader031/viewer/2022022113/5c66c5c209d3f2e4308cbe81/html5/thumbnails/22.jpg)
Numeri razionali
Rappresentazione in virgola fissa
0.10112= 1*2-1 + 0*2-2 + 1*2-3 + 1*2-4 = 0.687510
11.1012= 1*21 + 1*20 + 1*2-1 + 0*2-2 + 1*2-3 = 3.62510
Il numero di cifre prima e dopo la virgola è fisso!
Rappresentazione in virgola mobile (notazione scientifica)
Usata per rappresentare numeri o molto grandi o molto piccoli (0.1357*1064)
mantissa: 0.1357
esponente: 64
Utilizza 1 bit per il segno (s), h bit per l’esponente (e) e k bit per la mantissa (m): R
= s * m * be