Operazioni su numeri binari
• Addizione:
0
0
1
1
+
+
+
+
0
1
0
1
=
=
=
=
0
1
1
0
con
con
con
con
riporto 0
riporto 0
riporto 0
riporto 1
• Esempi:
1+
1=
10
101+
11=
1000
10110101+
1000110=
11111011
111+
11=
1010
Overflow (il sistema decimale)
• Consideriamo la base dieci: con tre cifre decimali si
possono rappresentare i numeri compresi tra 0 e 999
– Il numero successivo (1000) richiede una quarta cifra che
non abbiamo
– In questo caso si dice che si ha un problema di overflow; si
genera un errore perché il numero 1000 non può essere
rappresentato
• Poiché il numero 999 può essere scritto come 103-1
(ossia 1000-1), possiamo enunciare la seguente
regola:
con N cifre decimali si possono
rappresentare i numeri da 0 a 10N-1
Overflow (il sistema decimale)
• Esempio: alla rappresentazione decimale si
possono applicare le operazioni aritmetiche
• Vogliamo usare solo tre cifre decimale
–
–
–
–
–
–
325
6
12
678
560
999
+ 158 = 483
+ 98 =
104
+
45 =
57
+ 421
= 1099
+ 923 = 1483
+ 1
= 1000
Tre cifre
sono sufficiente
Tre cifre non
sono sufficiente:
overflow
Overflow (il sistema binario)
•
Consideriamo la base due: con tre cifre
binarie si possono rappresentare i numeri
compresi tra 0 e 23-1 (ossia 8-1), possiamo
enunciare la seguente regola:
con N cifre binarie si possono
rappresentare i numeri da 0 a 2N-1
Overflow (il sistema binario)
•
Esempio di overflow nel sistema binario
dovuto a operazioni aritmetiche:
– 5+4 = 9
(in sistema decimale)
– abbiamo usato solo un cifre decimale per il
risulto
•
Ricordiamo: 510 = 1012
101+
100=
1001
,
410 = 1002
Errore: overflow
(non può essere codificato
910 = 10012 con tre bit)
(in sistema binario)
Rappresentazione dei numeri
• In realtà, una semplice codifica binaria come
quella discussa fino ad ora non è sufficiente,
per due motivi:
– numeri negativi
– numeri con la virgola
• Per questi numeri vengono utilizzate delle
rappresentazioni differenti
Codifica dell’informazione
• Quanti bit si devono utilizzare per
rappresentare 300 simboli?
• Quanti byte occupa la parola “psicologia” se
la si codifica utilizzando il codice ASCII?
• Dati 12 bit per la codifica, quante
informazioni distinte si possono
rappresentare?
Codifica delle immagini
• Quanti byte occupa un’immagine di 100 x 100
pixel in bianco e nero?
• Quanti byte occupa un’immagine di 100 x 100
pixel a 256 colori?
• Se un’immagine a 16,7 milioni di colori
occupa 2400 byte, da quanti pixel sarà
composta?
Codifica dei suoni
• Quanto spazio occupa un suono della duranta
di 10 secondi campionato a 100 Hz (100
campioni al secondo), in cui ogni campione
occupa 4 byte?
Codifica dei numeri
• Codificare il numero 13210 nella
corrispondente rappresentazione binaria.
• Ordinare in modo crescente i sequente
numeri: 10410 , 128 , 1000100002 , 1001110
Strutturazione logica dei dati:
i file
• Informazione più complesse possono essere
composte a partire da informazioni elementari
• Esempio di una banca (Console e Ribaudo)
– Supponiamo di voler mantenere all’interno di un computer
tutte le informazioni riguardanti i clienti
– Per ogni cliente dovremo registrare
•
•
•
•
•
•
Il cognome
Il nome
L’indirizzo
Il numero di conto
La disponibilità sul conto
La foto
Strutturazione logica dei dati:
i file
• I dati riguardanti ciascun cliente devono
essere raggruppati, mentre i dati riguardanti
clienti diversi devono essere mantenuti
separati tra di loro
• Le informazioni devono essere organizzate in
modo tale che il loro reperimento e il loro uso
risultino semplici
• È necessario introdurre dei meccanismi per la
strutturazione dei dati, costruendo strutture
di codifica delle informazioni composte
Strutturazione logica dei dati:
i file
• Per l’esempio della banca
– Tutte le informazioni riguardanti un cliente
possono essere viste come un blocco le cui
componenti possono eventualmente essere
analizzate independentemente
File, record e campi
• Un file è un meccanismo di strutturazione
delle informazioni che permette di aggregare
informazioni elementari in strutture più
complessse
• Un file può essere definito introducendo i
concetti di campo e record
File, record e campi
• Un campo è costituito da un insieme di byte
– Serve per codificare una singola informazione che
può essere:
• numerico
• alfabetica o alfanumerico
• un’immagine o un suono
• Un record è constituito da un insieme di
campi logicamente correlati tra di loro (quindi
è un insieme di byte)
• Un file è costituito da una sequenza di record
file
record
campo
campo
campo
00101100 00111101 10100000 00101100
…
11101100
• Un campo è costituito da un insieme di byte
• Un record è constituito da un insieme di campi
logicamente correlati tra di loro
– quindi è un insieme di byte
• Un file è costituito da una sequenza di record
– quindi è un insieme di byte
File, record e campi
• Nell’esempio della banca le informazioni relative ad
un singolo cliente possono essere viste come un
record i cui campi sono:
–
–
–
–
–
–
Un
Un
Un
Un
Un
Un
campo
campo
campo
campo
campo
campo
alfabetico per il nome
alfabetico per il cognome
alfanumerico per l’indirizzo
numerico per il numero del conto
numerico per la disponibilità sul conto
immagine per la foto
• Le informazioni riguardanti la banca possono essere
viste come un file costituito da un insieme di record,
uno per ogni cliente
File, record e campi
• Un aspetto importante riguarda la lungezza
dei record
• Vi sono due possibilità:
– file con record a lunghezza costante
– file con record a lunghezza variabile
Record a lunghezza costante
• Solo per comodità, possiamo rappresentare
graficamente un file con record a lunghezza costante
come una tabella
…
…
…
…
…
114561
513,89
Massimiliano
Rossi
Via Milano 151
271564
7000,14
Cristina
Bianchi
Corso Venezia 1
102574
13,67
Elena
Rossi
Via Milano 151
143256
1208,90
Ada
Bo
Via Po 1
…
…
…
…
…
• Per definire un file con record a lunghezza costante
occorre precisare il numero di byte destinati a ciascun
campo
Record a lunghezza costante
• La scelta di avere file con record a lunghezza
costante presenta due svantaggi:
– è difficile stimare a priori la dimensione di ciascun campo
– nella maggior parte dei casi, l’informazione che deve essere
memorizzata all’interno di un campo occupa meno spazio di
quello a disposizione
• L’alternativa alla stabilire a priori le dimensioni dei
campi è quella di avere campi a dimensione variabile
Record a lunghezza variabile
271564
Massimiliano Rossi Via Milano 151
7000,14 Cristina Bianchi Corso Venezia 1
102574
143256
Elena Rossi Via Milano 151
13,67
1208,90 Ada Bo Via Po 1
114561
513,89
• Nel caso di campi a dimensione variabile sorge
tuttavia il problema di separare le informazioni tra di
loro
Struttura fisica di un file
• Sebbene abbiamo usato una struttura a tabella per
discrevere logicamente le infoirmazioni contenute in
un file è importante notare che un file è una struttura
lineare
record1 record2 record 3 …
• Questo è anche il modo in cui un file viene
memorizzato fisicamente nella memoria di un
elaboratore
Struttura fisica di un file
• Nel caso di campi, e quindi di record con
dimensione variabili, è necessario introdurre
dei caratteri speciali per separare le varie
informazioni
– Per esempio, “&” per separare i record e “#” per
separare i campi
…&1146561#513,89#Massimiliano#Rossi#Via Milano
151&271564#7000,14#Cristina#Bianchi#Corso
Venezia 1&…
• I separatori “&” e “#” non sono necessari nel
caso di file con campi a dimensioni costanti
Struttura fisica di un file
• Un altro aspetto fondamentale riguarda il problema
del reperimento delle informazioni
• I dati che vengono memorizzati in un file devono
poter essere letti e modificati
• I principali metodi di accesso sono
– accesso sequenziale
– accesso diretto
– accesso con chiave
I file ad accesso sequenziale
• La ricerca dei record avviene sempre a partire
dall’inizio del file, leggendo tutti i record uno dopo
l’altro, fino a quando non si arriva a quello disiderato
• Esempio: supponiamo di voler leggere i dati sul
cliente “Bianchi”
– Dobbiamo leggere tutte le informazioni fino ad arrivare al
cognome cercato
…&1146561#513,89#Massimiliano#Rossi#Via Milano
151&271564#7000,14#Cristina#Bianchi#Corso Venezia 1&…
• Questo metodo di accesso non è efficiente perché
ogni volta la ricerca viene effettuata a partire
dall’inizio del file
I file ad accesso diretto
• L’ideale, dal punto di vista delle velocità di
accesso, sarebbe di poter accedere
direttamente ad un record senza dover
considerare tutti quelli precedenti
• Per fare questo è necessario conoscere
esattamente il punto del file (sequenza di
record) in cui inizia il record cui si è
interessati
I file ad accesso diretto
• Il punto di inizio di un record all’interno di un file prende il nome
di indirizzo di record
L’indirizzo di record n
…
Campo1 Campo 2 Campo 3
Record n-1
L’indirizzo di record n+1
Campo 4
Record n
Campo 5
…
Record n+1
• Un file è un sequenza di byte e l’indirizzo di un byte è il numero che
corrisponde alla posizione del byte nella sequenza
–Il primo byte ha indirizzo 0, il seconda ha indirizzo 1, ecc.
–L’indirizzo di un campo è quindi l’indirizzo del primo byte del campo
–L’indirizzo di un record è l’indirizzo del primo campo del record
I file ad accesso diretto
• Se l’indirizzo di un record è noto, è possibile
posizionarsi direttamente in quel punto ed
accedere all’informazione in modo diretto,
senza considerare le informazione precedenti
• In questo caso il tempo necessario per
accedere a un dato non depende dal punto in
cui esso è memorizzato nella sequenza
I file ad accesso diretto
• Nel caso di record a lunghezza costante:
– È possibile calcolare il punto di inizio di ciascun
record, anche senza conoscerne direttamente
l’indirizzo
– Esempio: supponiamo di avere un file con record
lunghi 50 byte
• I record inizieranno rispettivamente in posizione 0, 50,
100, 150,… nel file
– In generale, dato un file con record lunghi M byte,
per recuperare il record in n-esima posizione ci si
dovrà posizionare al byte che si trova in posizione
M*(n-1)
I file ad accesso diretto
• Nel caso di record a lunghezza costante:
– Per esempio: file con record a lunghi 10 byte (M=10)
– Per recuperare il record in secondo posizione ci si dovrà posizionare
al byte che si trova in posizione 10 (= M*(n-1) = 10*(2-1) )
– Per recuperare il record in quarto posizione ci si dovrà posizionare
al byte che si trova in posizione 30 (= M*(n-1) = 10*(4-1) )
0 1 2
9 10
…
10 byte
20
…
10 byte
30
…
10 byte
…
10 byte
I file ad accesso diretto
• Nel caso di record a lunghezza variabile:
– Non è possibile calcolare il punto di inizio di
un record
– Quindi non è possibile usare l’accesso
diretto