Informatica Generale
Marzia Buscemi IMT Lucca
email: [email protected]
Ricevimento:
Giovedì ore 16.00-18.00
presso
Dipartimento di Informatica, Largo Pontecorvo, 3
stanza 306 PS (lab. Global Computing) Tel. 050.2213102
o per posta elettronica
Pagina web del corso:
http://www.di.unipi.it/~buscemi/IG07.htm
1
Di cosa abbiamo parlato finora

L’architettura di Von Neumann
Memoria
(RAM,dischi, etc)
Mantiene
Dati e Programmi
Processore
(CPU)
E’ un esecutore capace
di interpretare i singoli passi
richiesti dai programmi
(istruzioni elementari)
Sottosistema
di Interfaccia
Permette di comunicare
dati e programmi alla
macchina e di ottenere i
risultati (tastiera, microf.
stampante, schermo, etc)
2
Hardware - Software
Struttura di un calcolatore

Hardware
hw e sw
Processore
Memoria
Sottosistema
di Interfaccia
bus
Mantiene
Dati e Programmi
Software
3
Algoritmi e programmi
Dati di
ingresso
Codificati
opportunamente
Elaborazione
Dati di
uscita
Trasformazione dei dati di ingresso e esecuzione
passi specificati da un opportuno algoritmo
Ovvero la descrizione dell’algoritmo
secondo un linguaggio comprensibile al
calcolatore
Umano
(che conosce
l’algoritmo)
Calcolatore
programma
(che conosce alcune azioni elementari:
es confrontare due numeri, eseguire
semplici operazioni aritmetiche
4
Codifica e Rappresentazione
dell’informazione

Cosa vedremo :
Rappresentazione binaria
Codifica dei numeri
Codifica dei caratteri
Codifica delle immagini
Compressione dei dati
Codifica dei suoni
5
Perché è necessario codificare
le informazioni?


Tutta l’informazione interna ad un
calcolatore (digitale) deve essere
codificata in forma numerica.
La rappresentazione usata dai calcolatori
è binaria, cioè fatta di sequenze di due
soli numeri: 0 e 1


è facile realizzare dispositivi elettronici che
distinguere fra due stati, molto meno se gli
stati sono tanti
L’unità elementare di informazione si
chiama bit da‘binary digit’
6
Rappresentazione binaria (2)
byte : la sequenza di 8 bit
 word (parola) : 2 o 4 byte (dipende
dalla macchina) unità minima che
può essere fisicamente letta o scritta
nella memoria

7
Rappresentazione binaria (2)

Vedremo prima come rappresentare
(codificare) i numeri decimale come
sequenze di 0 e 1

E poi discuteremo la rappresentazione
di insiemi di oggetti finiti (caratteri,
testi, immagini, suoni)
8
Notazione posizionale in base 10

Un numero (es. 5) può essere rappresentato
in molti modi:


Rappresentazioni diverse hanno proprietà
diverse


cinque, five, 5, V,
moltiplicare due numeri in notazione romana è
molto più difficile che moltiplicare due numeri in
notazione decimale…
Noi siamo abituati a lavorare con numeri
rappresentati in notazione posizionale in
base 10
9
Notazione posizionale in base 10
(2)



La rappresentazione di un numero intero in
base 10 è una sequenza di cifre scelte fra
0123456789
es: 23, 118, 4
Il valore di una rappresentazione cN-1…c0 è dato
da cN-1 * 10N-1 + cN-2 * 10N-2 ….+ c1 * 101
+ c0 * 100
esempi :
23= ...
118 = ...
10
Notazione posizionale in base
10 (3)
Vediamo alcune proprietà di questa
notazione :
 Il massimo numero rappresentabile con
N cifre è 99….9 (N volte 9, la cifra che
vale di più), pari a 10N-1

es: su tre cifre il massimo numero
rappresentabile è 999 pari a
103-1 =1000-1
11
Notazione posizionale in base
10 (4)

Quindi se voglio rappresentare K
diversi numeri (cioè 0 1 2 …K-1) mi
servono almeno x cifre dove 10x è la
più piccola potenza di 10 che supera K

es : se voglio 25 numeri diversi mi servono
almeno 2 cifre perché 102=100 è la più
piccola potenza di 10 maggiore di 25
es : se voglio 110 numeri?
12
Notazione posizionale in base 2

La rappresentazione di un numero intero in
base 2 è una sequenza di cifre scelte fra 0 1:


es: 10, 110, 1
Il valore di una rappresentazione cN…c0 è
dato da:
cN-1 * 2N-1 + cN-2 * 2N-2 ….+ c1 * 21 + c0 * 20
esempi :



10 = 1*21 + 0 *20 = 2
110 = 1*22 + 1*21 + 0 * 20 = 4 + 2 + 0 = 6
1 = 1 *20 = 1
1001 = ?
13
Notazione posizionale in base 2(2)
Per la base due valgono proprietà
analoghe a quelle viste per la base 10 :
 Il massimo numero rappresentabile con
N cifre è 11….1 (N volte 1, la cifra che
vale di più), pari a 2N-1

es: su tre cifre il massimo numero
rappresentabile è?
14
Notazione posizionale in base 2(3)
Per la base 2 valgono proprietà analoghe a
quelle viste per la base 10 (cont.):
 Quindi se voglio rappresentare K diversi
numeri (cioè 0 1 2 …K-1) mi servono almeno
almeno x cifre dove 2x è la più piccola
potenza di 2 che supera K
 es : se voglio 25 numeri diversi mi servono
almeno 5 cifre perché 25=32 è la più
piccola potenza di 2 maggiore di 25
15
Notazione posizionale in base
2(4)

Somma binaria (somma mod 2):
0100 +
0110 =
1010
Qual è la somma di 01 e 111?
16
Conversione da base 10 a
base 2
Dato un numero X si cerca la sua
rappresentazione in base 2 cN-1…c0
 Conversione per divisione :
si divide ripetutamente X per 2
 il resto ottenuto nella divisione i-esima è la
i-esima cifra (ci) della rappresentazione
binaria

17
Conversione da base 10 a
base 2 (2)
Come si converte X nella sua
rappresentazione in base 2 cN…c0
usando il metodo della divisione
 Es : convertiamo il numero 13




13 / 2 da quoziente 6 e resto 1 (c0)
6 / 2 da quoziente 3 e resto 0 (c1)
3 / 2 da quoziente 1 e resto 1 (c2)
1 / 2 da quoziente 0 e resto 1 (c3)
La rappresentazione di 13 è 1101
 Qual è la rappr. di 10? E di 26?

18
Conversione da base 10 a
base 2 (3)
Nella conversione da base 10 a base 2
l’adozione della notazione
posizionale permette di definire:
 MSB (most significant bit): il bit più
a sinistra della rappresentazione
 LSB (least significant bit): il bit più a
destra
19
Multipli delle unità
fondamentali
Multiplo
Sigla
Valore
Kilo
K
210=1024
Mega
M
220=1024K
Giga
G
230=1024M
20
Rappresentazione di un
insieme finito di oggetti

Vogliamo rappresentare i giorni della
settimana :
{Lu, Ma, Me, Gio, Ve, Sa, Do}
usando sequenze 0 e 1
• Questo significa costruire un ‘codice’, cioè una
tabella di corrispondenza che ad ogni giorno
associa una opportuna sequenza

In principio possiamo scegliere in modo
del tutto arbitrario….
21
Rappresentazione di un
insieme finito di oggetti (3)

Una possibile codifica binaria per i
giorni della settimana
Di
Lunedì
Martedì
Mercoledì
Giovedì
Venerdì
Sabato
Domenica
0100010001
001
1100000
1
101010
111111
000001
solito si usa un numero di bit uguale per tutti:
il minimo
indispensabile
D
22
Rappresentazione di un
insieme finito di oggetti (4)

Per rappresentare 7 oggetti diversi
servono almeno 3 bit (minima
potenza di due che supera 7 è 8=
23) quindi :
000
001
010
100
Lunedì
Martedì
Mercoledì
Venerdì
110 Domenica
111 non ammesso
011 Giovedì
101 Sabato
23
Rappresentazione di caratteri
e stringhe
I caratteri sono un insieme finito di
oggetti e seguono la strategia vista
per i giorni della settimana
 Perché due diversi calcolatori si
possano parlare correttamente è
necessario che usino lo stesso
codice

24
Rappresentazione di
caratteri e stringhe (2)

Codifiche di uso comune :
il codice ASCII (American Standard code
For Information Interchange) su 7
(128=27) o 8 bit (256=28)
 il codice UNICODE su 16 bit (più
recente, permette di rappresentare
anche alfabeti diversi e simboli per la
scrittura di lingua orientali)
Le stringhe sono generalmente sequenze
di caratteri terminate in modo particolare


25
Rappresentazione di
immagini



Le immagini sono un ‘continuo’ e non
sono formate da sequenze di oggetti
ben finiti come i numeri e i testi
Bisogna quindi prima ‘discretizzarle’
ovvero trasformarle in un insieme di
parti distinte che possono essere
codificate separatamente con sequenze
di bit
Bisogna definire il termine informale di
“elemento d’informazione”
26
Rappresentazione di immagini
(2)

Immagini ‘bitmap’ :
1. l’immagine viene scomposta in una griglia
di elementi detti pixel (da picture element)
000000000000000000000000
000000000011111111000000
000000000010000010000000
000000000010000100000000
000000000010001000000000
000000000010010000000000
000000000010100000000000
000000000011000000000000
000000000010000000000000
codifica
immagine
27
Rappresentazione di immagini
(3)

Immagini ‘bitmap’ :
2. Ogni pixel è rappresentato da uno o più bit
Rappresentazione
di un pixel
000000000000000000000000
000000000011111111000000
000000000010000010000000
000000000010000100000000
000000000010001000000000
000000000010010000000000
000000000010100000000000
000000000011000000000000
000000000010000000000000
28
Rappresentazione di immagini (4)

Rappresentazioni dei pixel :


la rappresentazione in ‘toni di grigio’ : un byte
per pixel, con 256 gradazioni di grigio per ogni
punto (immagini bianco e nero), o più byte
per pixel, per avere più gradazioni possibili
rappresentazione a colori RGB (red, green,blu)
: comunemente 3 byte per pixel che
definiscono l’intensità di ciascun colore base.
In questo modo ho circa 16 milioni di colori
diversi definibili
29
Rappresentazione di immagini (5)

Problema :

la rappresentazione accurata di una
immagine dipende
• dal numero di pixel (definizione)
• dalla codifica del pixel

molta memoria, ad esempio :
tipo imm.
televisiva
SVGA
foto
Defin.
numero colori
720x625
1024x768
15000x10000
256
65536
16milioni
num.byte
440 KB
1.5MB
430 MB
30
Rappresentazione di immagini (6)

Quindi si cerca di ‘risparmiare’ memoria :



con l’uso di una ‘tavolozza’ (palette) che contiene il
sottoinsieme dei colori rappresentabili che compare
in una foto
• ogni pixel codifica un indice all’interno della
tavolozza
con tecniche di compressione che non codificano
ogni pixel in modo autonomo ma cercano di
raggruppare le aree che hanno caratteristiche
comuni
Formati più usati : TIFF (tagged image file
format), GIF (graphics interchange format),
JPEG (Joint photographers expert group)
31