Nessun titolo diapositiva - Dipartimento di Ingegneria dell

Fondamenti di Informatica
Monica Bianchini
Dipartimento di Ingegneria dell’Informazione
ENIAC (1946 ca.)
E-mail: [email protected]
1
Anno accademico 2010-2011
Sommario
• Introduzione
il calcolo automatico dalla preistoria ai giorni
nostri
• L’algebra di Boole
da Analisi Matematica della Logica (1847) al
progetto degli elaboratori digitali
• Sistemi di numerazione
UNIVAC (1951)
da additivi a posizionali, da decimale a binario,
a esadecimale: l’alfabeto dell’elaboratore
• La rappresentazione dei dati e l’aritmetica
degli elaboratori
dai bit ai numeri, ai testi, alle immagini, alla
musica, ai video in digitale
2
Anno accademico 2010-2011
Introduzione
3
Anno accademico 2010-2011
Cenni storici  1
Wilhelm Schickard (1592-1635)
• La presenza “invasiva” dell’informatica nella vita di tutti i giorni è
un fenomeno relativamente recente; non recente è invece la
necessità di avere a disposizione strumenti e metodi per contare
rapidamente, elaborare dati, “calcolare”

Le prime testimonianze di strumenti per contare risalgono a 30.000
anni fa

I primi esempi di algoritmi  procedure di calcolo “automatico” 
sono stati scoperti in Mesopotamia su tavolette babilonesi risalenti al
18001600 a.C.
• Il sogno di costruire macchine capaci di effettuare
calcoli automatici affonda le radici nel pensiero
filosofico del ‘600:

Macchina moltiplicatrice (1624)
Wilhelm Schickard introdusse la prima macchina
moltiplicatrice dotata di accumulatori cilindrici
4
Anno accademico 2010-2011
Cenni storici  2
Blaise Pascal (1623-1662)
Gottfried Leibnitz (1646-1716)
• Pascal e Leibnitz non solo affrontarono il problema, già studiato da
Cartesio, di automatizzare il ragionamento logicomatematico, ma
si cimentarono anche nella realizzazione di semplici macchine per
calcolare (capaci di effettuare somme e sottrazioni)
Macchina addizionatrice  la Pascalina (B. Pascal)
Macchina computazionale (G. Leibnitz)
5
Anno accademico 2010-2011
Cenni storici  3
Charles Babbage (1791-1871)
• La macchina alle differenze, concepita da
Babbage nel 1833, rappresenta il primo
esempio di macchina programmabile di
utilità generale
• In seguito, lo stesso Babbage progetta la
macchina analitica (mai realizzata, troppo
complessa e critica la sua costruzione per le
tecnologie meccaniche dell’epoca)

La prima programmatrice nella storia
dell’informatica è Ada Augusta Byron,
contessa di Lovelace
Macchina
alle
differenze:
modello
ricostruito presso il Museo della Scienza
di Londra seguendo il progetto del 1849
6
Anno accademico 2010-2011
Cenni storici  4
Herman Hollerith (1860-1929)
• Fu Herman Hollerith, nel 1890, a sviluppare
la macchina a schede perforate, per
compiere le statistiche del censimento
decennale degli Stati Uniti

I dati venivano immessi su schede di
cartone opportunamente perforate, le stesse
schede che sono state usate fino a due
decenni or sono

Le schede venivano successivamente
“contate” da una sorta di pantografo che
permetteva diversi tipi di elaborazioni
(totali, medie, statistiche, etc.)

Si impiegarono due anni e mezzo ad
analizzare i dati (contro i sette anni del
censimento
del
1880),
nonostante
l’incremento di popolazione da 50 a 63
milioni
Anno accademico 2010-2011
Census Tabulator (1890)
7
Cenni storici  5
• Successivamente la macchina a schede
perforate venne utilizzata con successo
per i censimenti in Austria, Norvegia e
Russia, tanto che Hollerith decise di
fondare una società: la Computing
Tabulating Recording Company che, nel
1923, divenne l’International Business
Machine, o IBM
• Nel 1932, il tedesco Konrad Zuse realizza
una macchina elettromeccanica in grado
di eseguire calcoli con controllo
programmato, ed introduce il sistema di
numerazione binario (la cui algebra era
stata definita da Leibnitz e da Boole)
Anno accademico 2010-2011
Konrad Zuse (1910-1995)
Il calcolatore Z1 (1939)
8
Cenni storici  6
Alan Turing (1912-1954)
• Durante la seconda guerra mondiale, fioriscono i progetti di
elaboratori da utilizzarsi per scopi bellici
 Enigma,
realizzata dai tedeschi (A.
Scherbius) per codificare le comunicazioni
militari
 Red Purple, di costruzione giapponese
 Computer Colossus, costruito dagli inglesi
per la decifrazione dei messaggi tedeschi,
alla cui progettazione e realizzazione
collaborò Alan Turing, permise la vittoria
angloamericana sull’Atlantico
La macchina Enigma
9
Anno accademico 2010-2011
Cenni storici  7
• Con l’invenzione del tubo a vuoto (1904), del transistor (1947) e,
infine, dei circuiti integrati (1969), l’evoluzione dei computer
divenne inarrestabile
• Finora la potenza di calcolo degli elaboratori si è decuplicata ogni
56 anni (…ma non può durare, almeno con le tecnologie in uso)
10
Anno accademico 2010-2011
Cenni storici  8
John Von Neumann (1903-1957)
• La costruzione dei primi calcolatori risale all’inizio degli anni ‘40,
grazie alla tecnologia elettronica; i primi esemplari venivano
programmati mediante connessioni elettriche e commutatori
(ENIAC, Mark I)
• Il nome di Von Neumann è legato invece ai primi calcolatori a
programma memorizzato realizzati alla fine degli anni ‘40 (EDSAC,
Whirlwind, IAS, UNIVAC)

Per la prima volta, vige il principio di unitarietà di rappresentazione di
dati e istruzioni, che vengono codificati, all’interno dell’elaboratore, in
maniera indistinguibile
• La diffusione dei calcolatori a livello mondiale è avvenuta nei
decenni ‘60 e ‘70
11
Anno accademico 2010-2011
Cenni storici  9
ENIAC (1946)
Whirlwind (1949)
Mark I (1948)
IAS (1952)
EDSAC (1949)
UNIVAC (1952)
12
Anno accademico 2010-2011
Cenni storici  10
• Tuttavia, l’esplosione dell’informatica come fenomeno di massa è
datata 1981, anno in cui l’IBM introdusse un tipo particolare di
elaboratore: il Personal Computer (PC)
• La particolarità dei PC consisteva nell’essere “assemblati” con
componenti facilmente reperibili sul mercato (e quindi a basso
costo)

Possibilità per qualsiasi casa produttrice di costruire “cloni”
• Attualmente i PC, o meglio il loro componente fondamentale  il
microprocessore  è utilizzato in tutti i settori applicativi (non
solo per elaborare dati):





Telefoni cellulari, ricevitori satellitari digitali, GPS
Bancomat e carte di credito
Lavatrici e forni a microonde
Computer di bordo e ABS
...
Anno accademico 2010-2011
13
Cenni storici  11
• L’esigenza di realizzare sistemi di elaborazione dotati di più
processori operanti in parallelo è stata sentita fin dalla preistoria
dell’informatica

In una relazione dello scienziato, generale e uomo politico italiano
Luigi Menabrea, datata 1842, sulla macchina analitica di Babbage, si fa
riferimento alla possibilità di usare più macchine dello stesso tipo in
parallelo, per accelerare calcoli lunghi e ripetitivi
• Solo la riduzione dei costi dell’hardware ha consentito, verso la fine
degli anni ‘60, l’effettiva costruzione dei primi supercalcolatori,
come le macchine CDC6600 e Illiac e, successivamente, il Cray e le
macchine vettoriali
• A partire dagli anni ‘90, gli ulteriori sviluppi della microelettronica
hanno permesso la realizzazione di calcolatori a parallelismo
massiccio e a “grana fine”, caratterizzati dall’interconnessione di
decine di migliaia di unità di elaborazione elementari: le reti
neurali, capaci di “simulare” il comportamento del cervello umano,
sulla base degli studi di McCulloch e Pitts (1943)
Anno accademico 2010-2011
14
Cenni storici  12
Cray 1 (1976)
Illiac (1955)
Cray XE6 (2010)
CDC 6600 (1963)
Portatile e Palmare (oggi)
PC IBM (1981)
15
Anno accademico 2010-2011
Frasi celebri ed altro…
•
•
•
•
•
•
•
•
“Penso che ci sia mercato nel mondo per non più di cinque computer.” (Thomas Watson,
Presidente di IBM, 1943)
“Ho girato in lungo e in largo questo paese e ho parlato con le migliori menti e posso
assicurarvi che questa moda dell’elaborazione automatica è un capriccio che non vedrà la
fine dell’anno.” (Editor di libri scientifici di Prentice Hall, 1947)
“Una unità di calcolo sull’ENIAC è dotata di 18.000 tubi elettronici a vuoto e pesa 30
tonnellate, ma è possibile che in futuro i computer abbiano soltanto 1000 tubi e pesino
soltanto una tonnellata e mezzo.” (Popular Mechanics, 1949)
“Abbiamo un computer qui a Cambridge, ce n’è uno a Manchester e uno al laboratorio
nazionale di fisica. Immagino che sarebbe giusto averne uno anche in Scozia, ma non di
più.” (Douglas Hartree, fisico inglese, 1951)
“Ma... a che serve?” (Un ingegnere della Advanced Computing Systems, Divisione dell’IBM,
commentando il microchip, 1965).
Nel 1976, il New York Times pubblicò un libro dal titolo La scienza nel ventesimo secolo,
nel quale il calcolatore veniva menzionato una sola volta e indirettamente, in relazione al
calcolo delle orbite dei pianeti
“Non c’è ragione perché qualcuno possa volere un computer a casa sua.” (Ken Olson,
fondatore di Digital, 1977)
“640 Kbytes should be enough for anybody.” (Bill Gates, 1981)
Anno accademico 2010-2011
16
Che cos’è l’informatica  1
• Informatica  fusione delle parole informazione e
automatica  l’insieme delle discipline che studiano gli
strumenti per l’elaborazione automatica dell’informazione e i
metodi per un loro uso corretto ed efficace
• L’informatica
è la scienza della
dell’elaborazione dell’informazione
rappresentazione
e
 L’accento sull’ “informazione” fornisce una spiegazione del
perché l’informatica sia ormai parte integrante di molte attività
umane: laddove deve essere gestita dell’informazione,
l’informatica è un valido strumento di supporto
 Il termine “scienza” sottolinea il fatto che, nell’informatica,
l’elaborazione dell’informazione avviene in maniera sistematica
e rigorosa, e pertanto può essere automatizzata
Anno accademico 2010-2011
17
Che cos’è l’informatica  2
• L’informatica non è la scienza dei calcolatori elettronici: il
calcolatore è lo strumento che la rende “operativa”
• L’elaboratore (computer, calcolatore) è un’apparecchiatura
digitale, elettronica ed automatica capace di effettuare
trasformazioni sui dati:
 Digitale: i dati sono rappresentati mediante un alfabeto finito,
costituito da cifre, digit, che ne permette il trattamento
mediante regole matematiche
 Elettronica: realizzazione tramite tecnologie di tipo elettronico
 Automatica:
capacità di eseguire
operazioni senza interventi esterni
una
successione
di
• “La disumanità del computer sta nel fatto che, una volta
programmato e messo in funzione, si comporta in maniera
perfettamente onesta.” (Isaac Asimov)
Anno accademico 2010-2011
18
L’architettura di Von Neumann
• La capacità dell’elaboratore di eseguire successioni di
operazioni in modo automatico è determinata dalla presenza
di un dispositivo di memoria
 Nella memoria sono registrati i dati e...
 ...le operazioni da eseguire su di essi (nell’ordine secondo cui
devono essere eseguite): il programma, la “ricetta” usata
dall’elaboratore per svolgere il proprio compito
• Il programma viene interpretato dall’unità di controllo

Modello di Von Neumann
19
Anno accademico 2010-2011
La macchina universale
• Programma: sequenza di operazioni atte a predisporre
l’elaboratore alla soluzione di una determinata classe di
problemi
 Il programma è la descrizione di un algoritmo in una forma
comprensibile all’elaboratore
• Algoritmo: sequenza finita di istruzioni attraverso le quali
un operatore umano è capace di risolvere ogni problema di
una data classe; non è direttamente eseguibile
dall’elaboratore
• L’elaboratore è una macchina universale: cambiando il
programma residente in memoria, è in grado di risolvere
problemi di natura diversa (una classe di problemi per ogni
programma)
20
Anno accademico 2010-2011
Ancora sull’informatica…
• L’informatica è lo studio sistematico degli algoritmi che
descrivono e trasformano l’informazione: la loro teoria,
analisi, progetto, efficienza, realizzazione (ACM, Association
for Computing Machinery)
• Nota
È possibile svolgere concettualmente un’attività di tipo
informatico senza l’ausilio del calcolatore, per esempio nel
progettare ed applicare regole precise per svolgere
operazioni aritmetiche con carta e penna; l’elaboratore,
tuttavia, è uno strumento di calcolo potente, che permette
la gestione di quantità di informazione altrimenti intrattabili
21
Anno accademico 2010-2011
L’algebra di Boole
22
Anno accademico 2010-2011
L’algebra di Boole  1
George Boole (1810-1864)
• Contempla due costanti 0 e 1 (falso e vero)
• Corrispondono a due stati che si escludono a vicenda
• Possono descrivere lo stato di apertura o chiusura di un
generico contatto o di un circuito a più contatti
0
• Sui valori booleani
AND, OR, NOT
1
si
definiscono
le
operazioni
23
Anno accademico 2010-2011
L’algebra di Boole  2
• Le operazioni AND e OR sono operazioni binarie, l’operazione NOT
è unaria
• Nella valutazione delle espressioni booleane esiste una relazione di
precedenza fra gli operatori NOT, AND e OR, nell’ordine in cui
sono stati elencati
• Gli operatori dell’algebra booleana possono essere rappresentati in
vari modi

Spesso sono descritti semplicemente come AND, OR e NOT

Nella descrizione dei circuiti appaiono sotto forma di porte logiche

In matematica si usano  per OR e  per AND, mentre si rappresenta
il NOT con una barra posta sopra l’espressione che viene negata
24
Anno accademico 2010-2011
L’operazione di OR
• Si definisce l’operazione di somma logica (OR):
il valore della somma logica è il simbolo 1 se il valore
di almeno uno degli operandi è il simbolo 1
00
01
10
11




0
1
1
1
0
0
0
1
0+0
0+1
1
1
0
1
1+0
1+1
25
Anno accademico 2010-2011
L’operazione di AND
• Si definisce l’operazione di prodotto logico (AND):
il valore del prodotto logico è il simbolo 1 se il valore di
tutti gli operandi è il simbolo 1
00
01
10
11




0
0
0
1
0
0
0
00
01
0
1
10
1
1
1
11
26
Anno accademico 2010-2011
La negazione NOT
• Si definisce l’operatore di negazione (NOT):
l’operatore inverte il valore della costante su cui opera
0  1
1  0
• Dalla definizione…
0  0
1  1
27
Anno accademico 2010-2011
Variabili binarie
• Una variabile binaria indipendente può assumere uno
dei due valori 0 e 1
0
x
1
• Date n variabili binarie indipendenti, la loro somma
logica (OR) è
1 se almeno una xi vale 1
x 1 + x 2 + …+ x n =
0 se x1= x2= …= xn = 0
28
Anno accademico 2010-2011
AND e NOT con variabili binarie
• Date n variabili binarie indipendenti, il loro prodotto
logico (AND) è
0 se almeno una xi vale 0
x1  x2  … xn =
1 se x1= x2= …= xn = 1
• La negazione di una variabile x è
x=0
x=1
se
se
x=1
x=0
• L’elemento x  NOT(x) viene detto complemento di x;
il complemento è unico
Anno accademico 2010-2011
29
Alcune identità
• Si verificano le seguenti identità:
x + 1  1
x + 0  x
x + x  x
x1x
x00
xxx
Legge dell’idempotenza
 0 è l’elemento neutro per l’operazione di OR; 1 è l’elemento
neutro per l’AND
 Gli elementi neutri sono unici
x1  x
• Ad esempio…
x 1
x 0
01  0
Anno accademico 2010-2011
11  1
OK!
30
Altre proprietà
• Per gli operatori AND e OR valgono le seguenti
proprietà:
commutativa x1+x2  x2+x1
x1x2  x2 x1
associativa
x1+x2+x3  x1+(x2+x3)
x1x2 x3  x1(x2x3)
distributiva del prodotto rispetto alla somma x1 x2 + x1x3  x1(x2+x3)
• Per l’operatore NOT si provano le seguenti identità:
x + x  1
x x  0
x  x
31
Anno accademico 2010-2011
Configurazione delle variabili
• Date n variabili binarie indipendenti x1, x2,…, xn, queste
possono assumere 2n configurazioni distinte
Ad esempio per n=3 si hanno 8 configurazioni
000 001 010 011
100 101 110 111
x1x2x3
• Una configurazione specifica è individuata univocamente
da un AND (a valore 1) di tutte le variabili, dove quelle
corrispondenti ai valori 0 compaiono negate
010
x1x2x3
32
Anno accademico 2010-2011
Funzioni logiche
• Una variabile y è una funzione delle n variabili
indipendenti x1, x2,…, xn, se esiste un criterio che fa
corrispondere in modo univoco ad ognuna delle 2n
configurazioni delle xi un valore di y
y = F(x1,x2,…,xn)
• Una rappresentazione esplicita di una funzione è la
tabella di verità, in cui si elencano tutte le possibili
combinazioni di x1, x2, …, xn, con associato il valore di y
x1
y = x1+x2
Anno accademico 2010-2011
0
0
1
1
x2
0
1
0
1
y
0
1
1
1
33
Una tabella di verità
• Date tre variabili booleane (A,B,C), si scriva la funzione F
che vale 1 quando solo due di esse hanno valore 1
A
B C
F
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
0
0
1
0
1
1
0
0
1
0
1
0
1
0
1
Si può scrivere la funzione come
somma logica delle configurazioni
corrispondenti agli 1
F(A,B,C)  ABC  ABC  ABC
Forma canonica: somma di prodotti (OR di AND)
tutte le funzioni logiche si possono scrivere in questa forma
Anno accademico 2010-2011
34
Un esempio: lo XOR  1
• La funzione XOR verifica la disuguaglianza di due
variabili
x1
0
0
1
1
x2 XOR
0
1
0
1
0
1
1
0
• L’espressione come somma di prodotti è quindi...
XOR = x1x2 + x1x2
35
Anno accademico 2010-2011
Un esempio: lo XOR  2
Porta logica per XOR
36
Anno accademico 2010-2011
Esempi
• Legge dell’assorbimento x1 x1x2  x1
• Leggi di De Morgan
(x1x2)  x1x2
(x1x2)  x1x2
• Dalle leggi di De Morgan si evince che la scelta delle funzioni
OR, AND e NOT, come funzioni primitive, è ridondante
 L’operazione logica AND può essere espressa in funzione delle
operazioni OR e NOT; in modo analogo, l’operazione OR può
essere espressa tramite AND e NOT
• Le relazioni stabilite sono generalmente applicate nelle
trasformazioni di funzioni booleane in altre equivalenti, ma di
più facile realizzazione circuitale
37
Anno accademico 2010-2011
Un esempio di circuito logico
y1 = F(B,C,D) = (BC)D
38
Anno accademico 2010-2011
Un circuito con due interruttori
• I due interruttori corrispondono a due variabili (A,B) a
valori booleani  le variabili assumono i due valori 0 e 1
che corrispondono alle due posizioni dell’interruttore
A
A
0
0
1
1
B
L
A
A
B
A=0 B=0
A
A
0
0
1
1
B
B
A=1 B=0
Anno accademico 2010-2011
L
A
A
0
0
1
1
B
L
B
A
B
L
A=0 B=1
0
0
1
1
0
1
0
1
1
0
0
1
0
0
1
1
B
B
A=1 B=1
L
L  ABAB
39
Un esercizio
• Progettare un circuito per accendere e spegnere una
lampada da uno qualsiasi di tre interruttori indipendenti
L = 0
Cambia lo
stato di un
interruttore
qualsiasi
Anno accademico 2010-2011
0
0
0
1
1
1
A
0
B
0
C
0
L = 1
0
0
0
1
1
1
A
0
B
1
C
0
40
Analisi delle combinazioni
• Si considera cosa accade a partire dalla configurazione di partenza,
cambiando lo stato di un interruttore per volta
L = 0
L = 1
L = 0
A
B
C
A
B
C
0
0
1
0
1
1
L = 1
L = 0
A
B
C
A
B
C
A
B
C
0
0
0
0
1
0
1
0
1
A
B
C
1
1
1
L = 0
L = 1
Anno accademico 2010-2011
L = 1
A
B
C
A
B
C
1
0
0
1
1
0
41
Scrittura della funzione logica
• Dalle otto combinazioni si ottiene la tabella di verità della
funzione logica
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
L
0
1
1
0
1
0
0
1
• Si può scrivere la funzione L come somma logica di
prodotti logici
L  ABC  ABC  ABC  ABC
Anno accademico 2010-2011
42
Come collegare gli interruttori
• Si può manipolare l’espressione di L usando la proprietà
distributiva dell’AND rispetto all’OR
L = ABC  ABC  ABC  ABC
L = A (BC  BC)  A (BC  BC)
B
C
A
B
C
A
B
C
B
C
1 0 0
Anno accademico 2010-2011
B
C
A
B
C
A
B
C
B
C
1 0 1
43
Esercizi
•
Esercizio 1
Siano a2, a1, b2, b1 i bit che rappresentano due numeri interi
positivi (Aa2a1 e Bb2b1). Sia r una variabile booleana che vale 1
se e solo A è maggioreuguale a B (AB). Ad esempio, quando
A11 e B10, allora a21, a11, b21, b10 e r1. Si scriva la
forma canonica che definisce r come funzione di a2, a1, b2, b1.
•
Esercizio 2
I signori A, B, C e D fanno parte di un consiglio di
amministrazione. Sapendo che hanno a disposizione le seguenti
quote di possesso azionario A40%, B25%, C20%, D15%,
formalizzare tramite tabella di verità (con successiva estrazione
della forma canonica) la funzione booleana che decide quando il
consiglio di amministrazione è in grado di approvare una mozione.
44
Anno accademico 2010-2011
Esercizi (continua)
•
Esercizio 3
Il direttore di una squadra di calcio vuol comprare 4 giocatori dal
costo di 2, 5, 6 e 8 milioni di euro, ma ha a disposizione solo 8
milioni. Siano a2, a5, a6, a8 variabili booleane che valgono 1 se e
solo se si acquistano, rispettivamente, i giocatori da 2, 5, 6, 8
milioni. Sia r una variabile che è vera se e solo se l’insieme di
giocatori che si decide di comprare non supera la cifra disponibile.
Ad esempio, se a21, a51, a60, a80, allora r1. Si scriva la
forma canonica che definisce r come funzione delle variabili a2, a5,
a 6 , a8 .
45
Anno accademico 2010-2011
Sistemi di numerazione
46
Anno accademico 2010-2011
Ancora un po’ di preistoria…  1
• I primi esempi di utilizzo di sistemi di numerazione
risalgono al neolitico, ovvero a circa 50.000 anni fa
• In epoca preistorica, le più utilizzate furono le basi 2, 5,
10, 20, 12, e 60
 Mentre le basi 2, 5, 10 e 20 sono suggerite dalla fisiologia
umana, 12 e 60 sembrano suggerite da scopi utilitaristici:
12 è divisibile per 1, 2, 3, 4, 6 e 12 mentre 60 per 1, 2, 3,
4, 5, 6, 10, 12, 15, 20, 30 e 60
 La base 12 è ancora utilizzata in alcune misure di tempo,
60 nella misurazione di angoli e tempo
47
Anno accademico 2010-2011
Ancora un po’ di preistoria…  2
• Da notare che il 7 non compare mai nelle basi di
numerazione e, in effetti, ebbe significati particolari,
anche religiosi, presso i popoli antichi
 Il 7 esprime infatti la globalità, l’universalità, l’equilibrio
perfetto
 Era legato al compiersi del ciclo lunare
 Presso i Babilonesi erano ritenuti festivi, e consacrati al
culto, i giorni di ogni mese multipli di 7
48
Anno accademico 2010-2011
E di storia…  1
• Tra le prime testimonianze certe dell’utilizzo di concetti
aritmetici avanzati vi sono le tavole numeriche
babilonesi, elenchi di numeri utilizzati per calcoli
astronomici e di agrimensura, risalenti al X secolo a.C.
• Tuttavia, nelle culture dell’antica Mesopotamia,
esistevano tabelle per le addizioni e le sottrazioni già
durante il regno di Sargon I, intorno al 2350 a.C.
49
Anno accademico 2010-2011
E di storia…  2
• Il documento più significativo dell’antico Egitto è il
papiro di Ahmes o Ahmose, dal nome dello scriba che lo
compose nel 1650 a.C.
• Lo stesso Ahmes sostiene inoltre che il suo materiale è
tratto da un documento anteriore, e fa risalire l’originale
ad Imhotep, medico e architetto del faraone Djoser
della III dinastia, e quindi al 2650 a.C. circa
 Imhotep è ritenuto l’architetto della grande piramide a
gradoni di Saqqara, la cui enorme base quadrata ha lati
perfetti al centimetro!
50
Anno accademico 2010-2011
I numeri in Mesopotamia  1
• Un antichissimo strumento utilizzato un po’ ovunque per
aiutarsi nei conteggi è costituito da semplici sassolini
• Non a caso la parola “calcolo” deriva dal latino calculus,
che significa appunto sassolino
• Appartengono alla civiltà dei Sumeri varie tavolette che
contengono i più antichi segni numerali usati dall’uomo
e risalgono al 35003000 a.C.
• Inizialmente, però, i Sumeri avevano semplicemente
perfezionato il metodo dei sassolini, costruendone di
particolari, in terracotta, di forme e dimensioni diverse,
ciascuno con un proprio valore
51
Anno accademico 2010-2011
I numeri in Mesopotamia  2
• I simboli fondamentali usati nella numerazione sumera
corrispondono ai numeri 1, 10, 60, 600, 3600, 36000
• I valori dei sassolini sono crescenti secondo una scala che
procede per 10 e per 6 alternativamente
1
10
60
600
3600
36000
52
Anno accademico 2010-2011
I numeri in Mesopotamia  3
• Il sistema di rappresentazione dei valori attraverso i
“calculi” è un sistema additivo
• Come in ogni sistema di rappresentazione additivo,
l’operazione di addizione risulta particolarmente
semplice
• Per addizionare due o più valori basterà infatti mettere
insieme i simboli uguali di ciascuno degli addendi:
l’addizione è compiuta nel gesto stesso dell’unione dei
sassolini
• L’insieme dei sassolini indicherà complessivamente il
valore risultato dell’addizione
53
Anno accademico 2010-2011
I numeri in Mesopotamia  4
• Successivamente i Sumeri, per motivi di praticità,
realizzarono gli stessi simboli su tavolette di argilla,
utilizzando bastoncini di diverse dimensioni…
• …cominciarono cioè a “scrivere” i numeri


54
Anno accademico 2010-2011
I numeri in Mesopotamia  5
Tavoletta pittografica con un conto di 33 misure d’olio (Godin Tepe, Iran, 3100 a.C.) 55
Anno accademico 2010-2011
I numeri in Mesopotamia  6
• Un ruolo speciale nell’aritmetica sumera spetta dunque
ai numeri 10 e 60: caratteristica ereditata poi dal
sistema babilonese
• Vari secoli dopo, attorno al XIX secolo a.C., a partire
dall’antica numerazione sumera, gli scienziati Babilonesi
crearono infatti un sistema di scrittura basato sui soli
due simboli:

cuneo verticale  1

parentesi uncinata  10
56
Anno accademico 2010-2011
I numeri in Mesopotamia  7
• Si rappresentavano i numeri da 1 a 59
• Per i numeri successivi, si ha la prima testimonianza
dell’uso di una notazione posizionale
 Non
si introducevano infatti altri simboli, ma si
affiancavano gruppi di cunei per indicare le successive
potenze del 60
 Si tratta dunque di un sistema di numerazione posizionale
(come il nostro, ma) in base 60
57
Anno accademico 2010-2011
I numeri in Mesopotamia  8
58
Anno accademico 2010-2011
I numeri in Mesopotamia  9
Tavoletta di argilla (19001600 a.C.) contenente un elenco di terne pitagoriche
(misure dei lati di un triangolo rettangolo)
Anno accademico 2010-2011
59
I numeri in Mesopotamia  10
• Ad esempio:
 7322
• Il sistema di spaziatura consentiva di risolvere le
ambiguità di interpretazione dei raggruppamenti
• Ai tempi di Alessandro Magno era però invalso anche
l’uso di un simbolo (due cunei obliqui) per indicare un
posto vuoto; questo simbolo svolgeva alcune funzioni
del nostro zero, ma non tutte: veniva usato fra colonne
e mai per indicare colonne vuote alla fine della sequenza
60
Anno accademico 2010-2011
I numeri nell’antico Egitto  1
• La civiltà degli Egizi ci ha lasciato alcune fra le più
antiche tracce di matematica scritta
• I primi numeri scritti si individuano infatti su monumenti e stele databili all’inizio del III millennio a.C.
• Si tratta di iscrizioni che impiegano il sistema geroglifico,
la scrittura pittografica egizia
61
Anno accademico 2010-2011
I numeri nell’antico Egitto  2
• Nel sistema geroglifico vengono riservati ai numeri sette
simboli diversi per rappresentare le potenze del 10, da 1 a 106
• I geroglifici utilizzati erano:
Pastoia per bestiame o giogo
Rotolo di fune
Bastoncino
Ninfea o fiore di loto
Uomo a braccia levate,
simbolo del dio Heh
62
Dito
Anno accademico 2010-2011
Girino o rana
I numeri nell’antico Egitto  3
• I numeri venivano formati raggruppando i simboli,
generalmente posti in ordine dal più piccolo al più
grande, da sinistra a destra (o viceversa)
• Il sistema di numerazione non è, tuttavia, posizionale
 L’ordine dei simboli che definiscono le potenze del 10 può
venire alterato senza cambiare il valore del numero
rappresentato
 L’ordine è una sorta di convenzione linguistica, senza
significato matematico
63
Anno accademico 2010-2011
I numeri nell’antico Egitto  4
131.200
64
Anno accademico 2010-2011
I numeri nell’antico Egitto  5
• Esempi di operazioni
 Addizione: si effettua sommando i simboli uguali e, qualora
si superi il valore 10, sostituendo i dieci simboli con il
simbolo opportuno (quello subito “superiore” nella gerarchia)
 Moltiplicazione: utilizza un sistema che sottintende la base 2
 si
scompone il moltiplicatore in potenze di 2, poi si raddoppia il
moltiplicando tante volte quante necessario, e infine si esegue
la somma
65
Anno accademico 2010-2011
I numeri nell’antico Egitto  6
• Esempio: 713
13
91
66
Anno accademico 2010-2011
I numeri nell’antica Grecia  1
• Nella civiltà greca classica sono noti due principali
sistemi di numerazione
 Il primo, più antico, è noto come
attico ed è per molti
aspetti simile a quello in uso presso i Romani; utilizzava
infatti accanto ai simboli fondamentali per l’1 e le potenze
di 10 fino a 10000, un simbolo speciale per il 5, che
combinato con i precedenti, dava altri simboli anche per
50, 500, 5000, 50000
 Compaiono testimonianze di questo sistema dal V al I
secolo a.C. ma, a partire dal III secolo, si diffonde anche il
sistema detto ionico o alfabetico
67
Anno accademico 2010-2011
I numeri nell’antica Grecia  2
• Il sistema ionico si serve di ventisette simboli alfabetici
(alcuni dei quali arcaici e non più usati nella Grecia
classica) per indicare le unità da 1 a 9, le decine da 10 a
90, le centinaia da 100 a 900
• Si usavano poi nuovamente le prime nove lettere
precedute da un apice in basso per indicare i multipli di
1000, e per esprimere numeri ancora più grandi si
ricorreva al simbolo M (iniziale di miriade) che indicava
la moltiplicazione per 10000 del numero che seguiva
 Sistema di numerazione decimale additivo
68
Anno accademico 2010-2011
I numeri nell’antica Grecia  3
• Ad esempio:
 67.766.776
69
Anno accademico 2010-2011
I numeri nell’antica Roma  1
• Nel sistema di numerazione romano, a base decimale, ci
si serviva, come è noto, anche di simboli speciali per
indicare 5, 50, 500
• Alcune antiche epigrafi inducono a ritenere che i segni
usati fossero inizialmente segni speciali, forse di origine
etrusca, che solo successivamente furono identificati con
le lettere I, V, X, L, C, D, M
I V X
1
L
5 10 50
C
D
M
100
500
1000
70
Anno accademico 2010-2011
I numeri nell’antica Roma  2
• La scrittura dei numeri
additivamente i segni
avveniva
combinando
• Per agevolare scrittura e lettura si diffuse più tardi un
sistema sottrattivo già utilizzato, ad esempio, dagli Assiri
(che ha traccia anche nelle forme verbali come ad
esempio “undeviginti”, stessa cosa di “decem et
novem”)
 Un simbolo posto alla sinistra di un simbolo di quantità
maggiore viene sottratto, così IX e VIIII indicano entrambi
il numero 9
• Ancora in epoca tarda, un segno che prese l’aspetto di
una linea orizzontale posta sopra le lettere serviva per
indicarne la moltiplicazione per 1000
Anno accademico 2010-2011
71
La storia continua…
• Per molte centinaia di anni ancora (con l’unica eccezione dei Babilonesi) gli uomini hanno continuato ad
utilizzare sistemi di numerazione additivi
 Più semplici da usare dato che la somma “si fa da sé”
 Poco
adatti a rappresentare numeri grandi (che
presuppongono l’uso di tanti simboli posti gli uni accanto
agli altri)
72
Anno accademico 2010-2011
Dall’India… il sistema decimale  1
• La civiltà indiana, più antica delle civiltà classiche, è già
documentata dal 3000 a.C.
• Sebbene l’uso della matematica dovesse essere ben
sviluppato già in epoca arcaica, i primi testi che ci sono
giunti risalgono al V secolo d.C.
• Non è però ancora chiaro dove e quando si sia
sviluppato il sistema di notazione decimale posizionale
che, in seguito, attraverso gli Arabi, si è diffuso in
Europa
73
Anno accademico 2010-2011
Dall’India… il sistema decimale  2
• Tale sistema viene utilizzato nell’opera del matematico
indiano vissuto attorno al 500 d.C. Aryabhata, la più
antica che ci è pervenuta (se si eccettuano frammenti
sparsi di matematici anteriori), dove però manca ancora
l’uso di un simbolo zero
• Testimonianze di scritture in forma posizionale si
registrano anche prima del manuale di Aryabhata,
mentre per avere datazioni sicure di forme complete in
cui compare anche il simbolo zero occorre arrivare al IX
secolo d.C.
74
Anno accademico 2010-2011
Dall’India… il sistema decimale  3
• L’idea di usare un numero limitato di simboli a cui dare
valore diverso a seconda della posizione occupata può
essere stata, secondo alcuni studiosi, sviluppata dagli
Indiani per conoscenza diretta  o ereditata dai Greci
 del sistema sessagesimale babilonese
• Gli Indiani avrebbero allora iniziato ad utilizzare
solamente i primi 9 simboli del loro sistema decimale in
caratteri Brahmi, in uso dal III secolo a.C.
75
Anno accademico 2010-2011
Dall’India… il sistema decimale  4
• I simboli assumono forme diverse a seconda delle zone
e dei periodi, ma sono comunque quelli che gli Arabi più
tardi utilizzarono e che, dalla forma araba, sono passati
in Europa, fino alla forma definitiva resa uniforme dalla
stampa nel XV secolo
76
Anno accademico 2010-2011
Sistemi di numerazione posizionali
• Sistemi di numerazione posizionali:
La base del sistema di numerazione
Le cifre del sistema di numerazione
Il numero è scritto specificando le cifre in ordine ed il
suo valore dipende dalla posizione relativa delle cifre
Esempio: Il sistema decimale (Base 10)
Cifre : 0 1 2 3 4 5 6 7 8 9
5641 = 5·103 + 6·102 + 4·101 + 1·100
Posizione: 3 2 1 0
77
Anno accademico 2010-2011
Sistemi in base B
• La base definisce il numero di cifre diverse nel sistema
di numerazione
• La cifra di minor valore è sempre lo 0; le altre sono,
nell’ordine, 1,2,…,B1; se B>10 occorre introdurre
B10 simboli in aggiunta alle cifre decimali
Un numero intero N si rappresenta con la scrittura (cncn1…c2c1c0)B
N = cnBn+cn1Bn1+...+c2B2+c1B1+c0B0
cn è la cifra più significativa, c0 la meno significativa
Un numero frazionario N’ si rappresenta come (0,c1c2…cn)B
N’ = c1B1+c2B2+...+cnBn
78
Anno accademico 2010-2011
Numeri interi senza segno
• Con n cifre in base B si rappresentano tutti i numeri
interi positivi da 0 a Bn1 (Bn numeri distinti)
Esempio: base 10
2 cifre: da 0 a 1021 = 99
Esempio: base 2
2 cifre: da 0 a 221 = 3
00
01
02
….
98
99
102 = 100 valori
00
01
10
11
22 = 4 valori
79
Anno accademico 2010-2011
Il sistema binario (B2)
• La base 2 è la più piccola per un sistema di numerazione
Cifre: 0 1  bit (binary digit)
Esempi:
Forma
polinomia
(101101)2 = 125 + 024 + 123 + 122 + 021 + 120 =
32 + 0 + 8 + 4 + 0 + 1 = (45)10
(0,0101)2 = 021 + 122 + 023 + 124 =
0 + 0,25 + 0 + 0,0625 = (0,3125)10
(11,101)2 = 121 + 120 + 121 + 022 + 123 =
2 + 1 + 0,5 + 0 + 0,125 = (3,625)10
80
Anno accademico 2010-2011
Dal bit al byte
• Un byte è un insieme di 8 bit (un numero binario ad 8 cifre)
b7b6b5b4b3b2b1b0
• Con un byte si rappresentano i numeri interi fra 0 e 281  255
00000000
00000001
00000010
00000011
…………….
11111110
11111111
28 = 256 valori distinti
• È l’elemento base con cui si rappresentano i dati nei calcolatori
• Si utilizzano sempre dimensioni multiple (di potenze del 2) del
byte: 2 byte (16 bit), 4 byte (32 bit), 8 byte (64 bit)…
81
Anno accademico 2010-2011
Dal byte al kilobyte
• Potenze del 2
24 = 16
28 = 256
216 = 65536
210 = 1024
(K=Kilo)
220 = 1048576
(M=Mega)
230 = 1073741824 (G=Giga)
• Cosa sono KB (Kilobyte), MB (Megabyte), GB (Gigabyte)?
1
1
1
1
1
KB = 210 byte = 1024 byte
MB = 220 byte = 1048576 byte
GB = 230 byte = 1073741824 byte
TB = 240 byte = 1099511627776 byte (Terabyte)
PB = 250 byte = 1125899906842624 byte (Petabyte)
Anno accademico 2010-2011
82
Da decimale a binario
Numeri interi
• Si divide ripetutamente il numero intero decimale per 2 fino
ad ottenere un quoziente nullo; le cifre del numero binario
sono i resti delle divisioni; la cifra più significativa è l’ultimo
resto
Esempio: convertire in binario (43)10
43 : 2 = 21
21 : 2 = 10
10 : 2 = 5
5:2= 2
2:2= 1
1:2= 0
+1
+1
+0
+1
+0
+1
resti
bit più significativo
(43)10 = (101011)2
83
Anno accademico 2010-2011
Da decimale a binario
Numeri razionali
• Si moltiplica ripetutamente il numero frazionario decimale per 2,
fino ad ottenere una parte decimale nulla o, dato che la
condizione potrebbe non verificarsi mai, per un numero prefissato
di volte; le cifre del numero binario sono le parti intere dei
prodotti successivi; la cifra più significativa è il risultato della
prima moltiplicazione
Esempio: convertire in binario (0,21875)10 e (0,45)10
0,21875
0,4375
0,875
0,75
0,5
 2 = 0 ,4375
 2 = 0,875
 2 = 1,75
 2 = 1,5
 2 = 1,0
(0,21875)10 = (0,00111)2
Anno accademico 2010-2011
0,45
0,90
0,80
0,60
0,20





2
2
2
2
2
=
=
=
=
=
0,9
1,8
1,6
1,2
0,4 etc.
(0,45)10  (0,01110)2
84
Da binario a decimale
• Oltre all’espansione esplicita in potenze del 2  forma polinomia…
(101011)2 = 125 + 024 + 123 + 022 + 121 + 120 = (43)10
• …si può operare nel modo seguente: si raddoppia il bit più
significativo e si aggiunge al secondo bit; si raddoppia la somma e
si aggiunge al terzo bit… si continua fino al bit meno significativo
Esempio: convertire in decimale (101011)2
bit più significativo
1x2=
2x2=
5x2=
10 x 2 =
21 x 2 =
2 + 0
4 + 1
10 + 0
20 + 1
42 + 1 = 43
(101011)2 = (43)10
Anno accademico 2010-2011
85
Esercizi
• Si verifichino le seguenti corrispondenze:
 (110010)2(50)10
 (1110101)2(102)10
 (1111)2(17)10
 (11011)2(27)10
 (100001)2(39)10
86
Anno accademico 2010-2011
Sistema esadecimale
• La base 16 è molto usata in campo informatico
Cifre: 0 1 2 3 4 5 6 7 8 9 A B C D E F
La corrispondenza in decimale delle cifre oltre il 9 è
Esempio:
A = (10)10
B = (11)10
C = (12)10
D = (13)10
E = (14)10
F = (15)10
(3A2F)16 = 3163 + 10162 + 2161 + 15160 =
34096 + 10256 + 216 + 15
= (14895)10
87
Anno accademico 2010-2011
Da binario a esadecimale
• Una cifra esadecimale corrisponde a 4 bit
0 corrisponde a 4 bit a 0 0000 0
0001
0010
0011
0100
0101
0110
0111
1
2
3
4
5
6
7
1000
1001
1010
1011
1100
1101
1110
1111
8
9
A
B
C
D
E
F F corrisponde a 4 bit a 1
• Si possono rappresentare numeri binari lunghi con poche cifre (1/4)
• La conversione da binario ad esadecimale è immediata,
raggruppando le cifre binarie in gruppi di 4 (da destra) e
sostituendole con le cifre esadecimali secondo la tabella precedente
88
Anno accademico 2010-2011
Dal bit all’hex
• Un numero binario di 4n bit corrisponde a un numero
esadecimale di n cifre
Esempio: 32 bit corrispondono a 8 cifre esadecimali
1101 1001 0001 1011 0100 0011 0111 1111
D
9
1
B
4
3
7
F
(D91B437F)16
Esempio: 16 bit corrispondono a 4 cifre esadecimali
0000 0000 1111 1111
0
0
F
F
(00FF)16
89
Anno accademico 2010-2011
Da esadecimale a binario
• La conversione da esadecimale a binario si ottiene
espandendo ciascuna cifra con i 4 bit corrispondenti
Esempio: convertire in binario il numero esadecimale 0x0c8f
Notazione usata in molti linguaggi di
programmazione (es. C e Java) per
rappresentare numeri esadecimali
0
c
8
f
0000 1100 1000 1111
Il numero binario ha 4  4=16 bit
90
Anno accademico 2010-2011
Esempi  1
• In qualsiasi base, l’essere il sistema di numerazione posizionale
impone che combinazioni diverse di cifre uguali rappresentino
numeri diversi; ad esempio:
• (319)10  (193)10
• (152)6  (512)6, infatti...
(152)6=162+561+260=36+30+2=(68)10
(512)6=562+161+260=180+6+2=(188)10
• Numeri che hanno identica rappresentazione, in basi diverse,
hanno valori diversi:

(234)10  (234)8 , infatti...
(234)8 = 282 + 381 + 480 = 264 + 38 + 4 = 128+24+4 = (156)10
Osservazione: più piccola è la base, minore è il valore del numero
rappresentato dalla stessa sequenza di cifre
91
Anno accademico 2010-2011
Esempi  2
• La notazione posizionale si applica anche per il calcolo del valore
dei numeri frazionari, infatti...

(0,872)10 = 8101 + 7102 + 2103
= 8/10 + 7/100 + 2/1000 = 0,8 + 0,07 + 0,002
• Quante cifre occorreranno per rappresentare il numero decimale
36 in base 2? Sappiamo che con n cifre si rappresentano i numeri
da 0 a 2n1, quindi...

per n=1 (con una cifra) si rappresentano 0...211  0,1

per n=2: 0...221  0...3

per n=3: 0...231  0...7
Effettivamente possiamo verificare che
(100100)2=(36)10, infatti...

per n=4: 0...241  0...15
100100=125+024+023+122+021+020

per n=5: 0...251  0...31

per n=6: 0...261  0...63
Anno accademico 2010-2011
= 32 + 4 = 36
con 6 cifre necessarie per la codifica
del numero in base 2
92
Esempi  3
• Quesito: Per quale base B risulterà vera l’uguaglianza
17 + 41 + 22 = 102 ?
Se i numeri sono rappresentati in base B, sappiamo che:
(17)B = 1B1+7B0 = B+7
(41)B = 4B1+1B0 = 4B+1
(22)B = 2B1+2B0 = 2B+2
(102)B = 1B2+0B1+2B0 = B2+2
da cui... B+7+4B+1+2B+2 = 7B+10 = B2+2
 Si ottiene un’equazione di 2° grado: B2  7B  8 = 0
Risolvendo:  = 49+32 = 81
(7+9)/2 = 8
È la soluzione!
(79)/2 = 1
Non può essere
una base
B = (7   )/2 =
Anno accademico 2010-2011
93
La rappresentazione dei dati e
l’aritmetica degli elaboratori
94
Anno accademico 2010-2011
Numeri interi positivi
• I numeri interi positivi sono rappresentati all’interno
dell’elaboratore utilizzando un multiplo del byte
(generalmente 8 byte)
• Se l’intero si rappresenta con un numero di cifre
minore, vengono aggiunti zeri nelle cifre più
significative
Esempio: 12 viene rappresentato in un byte come…
00001100
95
Anno accademico 2010-2011
Numeri con segno
• Per rappresentare numeri con segno, occorre utilizzare
un bit per definire il segno del numero
• Si possono usare tre tecniche di codifica



Modulo e segno
Complemento a 2
Complemento a 1
96
Anno accademico 2010-2011
Modulo e segno
• Il bit più significativo rappresenta il segno: 0 per i numeri
positivi, 1 per quelli negativi
• Esiste uno zero positivo (00…0) e uno zero negativo (10…0)
• Se si utilizzano n bit si rappresentano tutti i numeri compresi
fra (2n11) e 2n11
Esempio: con 4 bit si rappresentano i numeri fra 7 ((231)) e 7 (231)
0000
0001
0010
0011
positivi
0100
0101
0110
0111
Anno accademico 2010-2011
0
1
2
3
4
5
6
7
1000
1001
1010
1011
1100
1101
1110
1111
0
1
2
3
negativi
4
5
6
7
97
Complemento a 2
• Il complemento a 2 di un numero binario (N)2 a n cifre è il numero
{
2n(N)2 = 10……0(N)2
• Il complemento a 2 si calcola…
n zeri

Effettuando il complemento a 1 del numero di partenza (negazione di
ogni cifra): si trasforma ogni 0 in 1 e ogni 1 in 0

Aggiungendo 1 al numero ottenuto
• Oppure: a partire da destra, lasciando invariate tutte le cifre fino al
primo 1 compreso, quindi invertendo il valore delle rimanenti
01010111
10101000
10101001
Anno accademico 2010-2011
complemento a 1
1
100000000
011111111
01010111
10101000
10101001
28
281
N
281N
281N1
98
Interi in complemento a 2
• I numeri positivi sono rappresentati (come) in modulo e segno
• I numeri negativi sono rappresentati in complemento a 2  la cifra
più significativa ha sempre valore 1
• Lo zero è rappresentato come numero positivo (con una sequenza
di n zeri)
• Il campo dei numeri rappresentabili varia da 2n1 a 2n11
Esempio: numeri a 4 cifre
Anno accademico 2010-2011
0000
0001
0010
0011
0100
0101
0110
0111
0
1
2
3
4
5
6
7
1000
1001
1010
1011
1100
1101
1110
1111
8
7
6
5
4
3
2
1
Nota: 0111 7
1000 8
99
Interi a 16 bit
• Numeri interi rappresentati su 16 bit in complemento a 2:
Il numero intero positivo più grande è 2151=(32767)10
0111 1111 1111 1111
0x 7
F
F
F
Il numero intero negativo più piccolo è 215=(32768)10
1000 0000 0000 0000
0x 8
0
0
0
0111 1111 1111 1111 +
1
1000 0000 0000 0000
Il numero intero –1 è rappresentato come
1111 1111 1111 1111
0x F
F
F
F
0000 0000 0000 0000 +
1
0000 0000 0000 0001
100
Anno accademico 2010-2011
Addizione binaria
• Le regole per l’addizione di due bit sono
0
0
1
1
+
+
+
+
0
1
0
1
=
=
=
=
0
1
1
0 con riporto di 1
• L’ultima regola è… (1)2(1)2  (10)2 … (112)10 !!
Esempio
riporti
1 11 1
01011011+
01011010 
10110101
91+
90 
181
101
Anno accademico 2010-2011
Sottrazione binaria  1
• Le regole per la sottrazione di due bit sono
00
10
11
10  1
Esempio
=0
=1
=0
= 1 con prestito di 1 dalla cifra precedente a sinistra
0 10
11001
101
10100
25 
5
20
• La sottrazione può divenire complicata: quando si ha
una richiesta sulla cifra precedente a sinistra, che è
uno 0, l’operazione si propaga a sinistra fino alla prima
cifra ad 1 del sottraendo
102
Anno accademico 2010-2011
Sottrazione binaria  2
• Utilizzando la rappresentazione in complemento a 2,
addizione e sottrazione sono trattate come un’unica
operazione
{
N1N2 = N1(2nN2)2n
si trascura il bit n 1
complemento a 2 di N2: rappresentazione di (N2)
 Si calcola il complemento a 2 di N2
 Si somma N1 con il complemento a 2 di N2
 Si trascura il bit più significativo del risultato
Esempio: (010001)2(000101)2 = (17)10(5)10
010001 
111011
1001100
Anno accademico 2010-2011
(12)10
103
Rappresentazioni in complemento
• Sono utili perché l’operazione di somma algebrica può
essere realizzata non curandosi del bit di segno
• In complemento a 1 (più semplice da calcolare)…
 Zero ha due rappresentazioni: 00000000 e 10000000
 La somma bit a bit funziona “quasi sempre”
00110 
10101 =
11011
(6)
(10)
(4)
11001 
11010 =
10011
(6)
(5)
(12)
• In complemento a 2…
 Zero ha una sola rappresentazione
 La somma bit a bit funziona sempre
Anno accademico 2010-2011
104
Overflow
• L’overflow si ha quando il risultato di un’operazione
non è rappresentabile correttamente con n bit
Esempio: 5 bit  [16,15]
14 
10 
24
01110 
01010 
11000
8
8 
10 
18
11000 
10110 
101110 14
• Per evitare l’overflow occorre aumentare il numero di
bit utilizzati per rappresentare gli operandi
• C’è overflow se c’è riporto al di fuori del bit di segno e
non sul bit di segno, o se c’è riporto sul bit di segno,
ma non al di fuori
105
Anno accademico 2010-2011
Moltiplicazione binaria
• Le regole per la moltiplicazione di due bit sono
0
0
1
1
Esempio
0
1
0
1
=
=
=
=
0
0
0
1
1100111  101
1100111
0000000
1100111
1000000011
2n corrisponde ad
• Moltiplicare per
coda al moltiplicando
51
Anno accademico 2010-2011




aggiungere n zeri in
110011  10000 = 1100110000
 16 = 24
816
106
Divisione binaria
• La divisione binaria di A per B viene calcolata in modo
analogo alla divisione decimale, così da ottenere un
quoziente Q ed un resto R, tali che A  BQ  R
(
• La divisione binaria si compone di una serie di sottrazioni
110^
1^
1^
0
101
101
111
1010
54 = 510 + 4
1 01
1 00
per 2n equivale
• Dividere
a scorrere il numero a destra di
n posizioni; le cifre scartate costituiscono il resto
110011  10000 = 11 con resto 11
Anno accademico 2010-2011
51:16 = 3 con resto 3
107
Esempio
• Quesito: Data una base B, si consideri il numero
x(C5C4C3C2C1C0)B, dove le singole cifre valgono:
C5  B1, C4  B1, C3  B1, C2  0, C1  0, C0  0
Qual è la rappresentazione in base B del risultato
dell’espressione (x/B3)1?
 Dividere per B3, che per qualsiasi base si rappresenta
come 1000, equivale a “shiftare” il numero di tre cifre a
sinistra
 Rimangono quindi le tre cifre più significative, tutte
uguali a B1
 Sommando 1, a causa dei riporti, si ottiene quindi come
risultato dell’espressione 1000B3, qualsiasi sia il valore
della base B
Anno accademico 2010-2011
108
Esercizi
•
Esercizio 1
Assumendo che un elaboratore rappresenti i numeri interi con
segno su quattro bit in complemento a 2, si calcolino entrambi i
membri della seguente identità:
(AC)B  (AB)C,
con A7, B5, C7. Si ottiene lo stesso risultato dal calcolo dei due
membri? Discutere le motivazioni della risposta.
•
Esercizio 2
Si determini, se esiste, la base b di un sistema di numerazione tale
che (842)b  (1202)10
Si determini, se esiste, la base b  16 di un sistema di
numerazione tale che (725)b  (626)b  (224)10
109
Anno accademico 2010-2011
Numeri in virgola mobile
• La rappresentazione dei numeri in virgola mobile è in
relazione con la notazione scientifica (es. 1.2102120)
• La IEEE ha previsto uno
rappresentazione in virgola mobile
standard
per
la
 singola precisione
(32 bit = 4 byte)
 doppia precisione
(64 bit = 8 byte)
 quadrupla precisione (128 bit = 16 byte)
Singola precisione
31
23 22
0
8 bit
Segno
Il valore è
Esponente
(o Caratteristica)
23 bit
Mantissa
Eccesso: vale 2t11, se t è il numero di cifre
(1)S 1.M2E127 se E0
(1)S 0.M2126 se E=0
Anno accademico 2010-2011
riservate alla caratteristica  rappresentazione
“interna” dell’esponente sempre positiva
110
Singola precisione
• Il numero più grande rappresentabile è 2128(2223)21296.811038
0 11111111 11111111111111111111111
2255127
1.111111111111111111111111
• Il più piccolo numero positivo è 212622321491.41045
0 00000000 00000000000000000000001
2126
0.00000000000000000000001
0.25
0.5
32 numeri
• In totale si0 01111101
rappresentano
2
distinti, metà positivi, metà
00000000000000000000000
0 01111110 00000000000000000000000
negativi
• Circa metà dei numeri sono compresi fra 1 e 1 (E127<0)
223 valori 223 valori
0 0.25 0.5
Anno accademico 2010-2011
1
223 valori
223 valori
2
4
111
L’aritmetica floatingpoint:
Addizione
•
Metodo per il calcolo dell’addizione
1.
Se le caratteristiche dei numeri sono diverse, si considera il
numero con caratteristica minore e…
1.1
Si trasla la mantissa di un posto a destra
Si incrementa la caratteristica di 1, fino a quando le due
caratteristiche sono uguali, e corrispondono alla
caratteristica del risultato
La mantissa del risultato è ottenuta dalla somma delle due
mantisse
1.2
2.
3.
Se l’addizione comporta un riporto oltre la cifra più
significativa, si trasla la mantissa del risultato a destra di un
posto, il riporto nel bit più significativo, e si incrementa la
caratteristica di 1
Anno accademico 2010-2011
112
Un esempio di addizione
• Supponiamo che per la rappresentazione floating–point vengano utilizzati
otto bit, di cui uno per il segno, tre per la caratteristica e quattro per la
mantissa
3.25
0 1 1 0 1 1 0 1
s
E4
N = (1) 0.M2
1.125
1 0 0 1
0 1 0 1
• La caratteristica del secondo operando è più piccola di una unità, quindi la
mantissa deve scorrere di una posizione a destra
1001  0100
• La caratteristica del risultato è 110 e la mantissa è 1101+ 0100 = 10001;
la caratteristica deve essere aumentata di 1 e portata a 111, e la mantissa
del risultato traslata a destra di una posizione:
0
1
1
Anno accademico 2010-2011
1
1
0
0
0
Codifica il numero 4 (dato che la
caratteristica si rappresenta in eccesso
a 4), ma il risultato corretto è 4.375:
errore di troncamento
113
L’aritmetica floatingpoint:
Moltiplicazione
•
Metodo per il calcolo della moltiplicazione
1.
Si moltiplicano le due mantisse
2.
Si addizionano le due caratteristiche
3.
Si trasla a sinistra il prodotto delle due mantisse fino ad
ottenere un 1 come cifra più significativa; si diminuisce la
caratteristica di 1 per ogni traslazione eseguita
4.
Si tronca la mantissa al numero di bit utilizzati nella
rappresentazione; la mantissa del prodotto è il risultato del
troncamento
5.
Si sottrae l’eccesso alla somma delle
ottenendo la caratteristica del prodotto
caratteristiche,
114
Anno accademico 2010-2011
Un esempio di moltiplicazione
• Supponiamo che per la rappresentazione floating–point vengano utilizzati
otto bit, di cui uno per il segno, tre per la caratteristica e quattro per la
mantissa
N = (1)s0.M2E4
0
0
1
0
1
1
0
1
0
1
0
1
1
0
0
1
0.203125
1.125
• Moltiplicando le mantisse e sommando le caratteristiche si ottiene:
M=01110101
E=111
• La mantissa del risultato deve essere traslata di un posto a sinistra, e la
somma delle caratteristiche deve essere decrementata di 1; infine la
mantissa deve essere troncata alle 4 cifre significative e l’eccesso (100)
sottratto alla caratteristica:
0
0
1
Anno accademico 2010-2011
0
1
1
1
0
Codifica il numero 0.21875, ma il
risultato corretto è 0.228515625:
errore di troncamento
115
L’aritmetica degli elaboratori  1
• L’aritmetica “interna” degli elaboratori
notevolmente dall’aritmetica classica
differisce
• Sebbene le stesse operazioni possano essere realizzate
secondo modalità diverse su elaboratori diversi, si
riscontrano alcune caratteristiche comuni:
 Rappresentazione binaria dei numeri
 Rango finito dei numeri rappresentabili
 Precisione finita dei numeri
 Operazioni espresse in termini di operazioni più semplici
116
Anno accademico 2010-2011
L’aritmetica degli elaboratori  2
• Rango finito dei numeri rappresentabili
 Qualunque sia la codifica utilizzata, esistono sempre il
più grande ed il più piccolo numero rappresentabile
 I
limiti inferiore e superiore del rango di
rappresentazione dipendono sia dal tipo di codifica, sia
dal numero di bit utilizzati
 Se il risultato di un’operazione non appartiene al rango
dei numeri rappresentabili, si dice che si è verificato un
overflow (un underflow, più precisamente, se il risultato
è più piccolo del più piccolo numero rappresentabile)
117
Anno accademico 2010-2011
L’aritmetica degli elaboratori  3
• Precisione finita dei numeri
 La precisione della rappresentazione di un numero
frazionario è una misura di quanto essa corrisponda al
numero che deve essere rappresentato
 Negli elaboratori, i numeri frazionari sono rappresentati
in virgola mobile (floating–point), utilizzando un numero
finito di bit
 È plausibile che un numero reale non ammetta una
rappresentazione finita, quindi dovrà essere codificato in
maniera approssimata
 Negli
elaboratori si rappresentano soltanto numeri
razionali (fino ad una data precisione)
Anno accademico 2010-2011
118
L’aritmetica degli elaboratori  4
• Operazioni espresse in termini di operazioni più semplici
 La maggior parte degli elaboratori non possiede circuiti in
grado di eseguire direttamente tutte le operazioni:
 La sottrazione si realizza per mezzo di una complementazione e
di un’addizione
 La moltiplicazione si realizza per mezzo di una successione di
addizioni e di shift (traslazioni)
 La divisione si realizza per mezzo di una successione di shift e
sottrazioni
 Le operazioni più semplici sono eseguite direttamente da
appositi circuiti (in hardware); le operazioni più complesse
sono realizzate mediante l’esecuzione di successioni di
operazioni più semplici, sotto il controllo di programmi
appositamente realizzati, e generalmente memorizzati
permanentemente (in firmware)
Anno accademico 2010-2011
119
Codifica dei caratteri alfabetici  1
• Oltre ai numeri, molte applicazioni
elaborano caratteri (simboli)
informatiche
• Gli elaboratori elettronici trattano numeri

Si codificano i caratteri e i simboli per mezzo di numeri
• Per poter scambiare dati (testi) in modo corretto,
occorre definire uno standard di codifica
A
01000001
3
00110011
$
00100100
120
Anno accademico 2010-2011
Codifica dei caratteri alfabetici  2
• Ovvero… quando si scambiano dati, deve essere noto il
tipo di codifica utilizzato
• La codifica deve prevedere le lettere dell’alfabeto, le
cifre numeriche, i simboli, la punteggiatura, i caratteri
speciali per certe lingue (æ, ã, ë, è,…)
• Lo standard di codifica più diffuso è il codice ASCII, per
American Standard Code for Information Interchange
121
Anno accademico 2010-2011
Codifica ASCII
• Definisce una tabella di corrispondenza fra ciascun carattere e un
codice a 7 bit (128 caratteri)
• I caratteri, in genere, sono rappresentati con 1 byte (8 bit); i
caratteri con il bit più significativo a 1 (quelli con codice dal 128 al
255) rappresentano un’estensione della codifica
• La tabella comprende sia caratteri di controllo (codici da 0 a 31)
che caratteri stampabili
• I caratteri alfabetici/numerici hanno codici ordinati secondo
l’ordine alfabetico/numerico
Anno accademico 2010-2011
0 48
1 49
…….
8 56
9 57
A 65
B 66
…….
Y 89
Z 90
a 97
b 98
…….
y 121
z 122
cifre
maiuscole
minuscole
122
Caratteri di controllo ASCII
• I caratteri di controllo (codice da 0 a 31) hanno funzioni speciali
• Si ottengono o con tasti specifici o con una sequenza Ctrlcarattere
Ctrl
^@
^A
Dec
0
1
Hex
0
1
Code
NULL
SOH
^G
^H
^I
^J
^K
^L
^M
……
^Z
^[
……
^_
7
8
9
10
11
12
13
…
26
27
…
31
7
8
9
A
B
C
D
…
1A
1B
…
1F
BEL
BS
HT
LF
VT
FF
CR
……
EOF
ESC
……
US
……
…
…
……
Nota
carattere nullo
partenza blocco
…………………
beep
backspace
tabulazione orizzontale
line feed (cambio linea)
tabulazione verticale
form feed (alim. carta)
carriage return (a capo)
……………………
fine file
escape
………
separatore di unità
123
Anno accademico 2010-2011
Caratteri stampabili
Dec Hx Chr Dec Hx Chr Dec Hx Chr Dec Hx Chr Dec Hx Chr Dec Hx Chr
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
20
21
22
23
24
25
26
27
28
29
2A
2B
2C
2D
2E
2F
SPACE
!
”
#
$
%
&
’
(
)
*
+
,
.
/
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
30
31
32
33
34
35
36
37
38
39
3A
3B
3C
3D
3E
3F
0
1
2
3
4
5
6
7
8
9
:
;
<
=
>
?
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
40
41
42
43
44
45
46
47
48
49
4A
4B
4C
4D
4E
4F
@
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
50
51
52
53
54
55
56
57
58
59
5A
5B
5C
5D
5E
5F
P
Q
R
S
T
U
V
W
X
Y
Z
[
\
]
^
_
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
60
61
62
63
64
65
66
67
68
69
6A
6B
6C
6D
6E
6F
`
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
70
71
72
73
74
75
76
77
78
79
7A
7B
7C
7D
7E
7F
p
q
r
s
t
u
v
w
x
y
z
{
|
}
~
DEL
Nota: il valore numerico di una cifra può essere calcolato come differenza del
suo codice ASCII rispetto al codice ASCII della cifra 0 (es. ‘5’‘0’ = 5348 = 5)
Anno accademico 2010-2011
124
Tabella ASCII estesa
• I codici oltre il 127 non sono compresi nello standard
originario
125
Anno accademico 2010-2011
La codifica delle immagini  1
• Le immagini vengono anch’esse codificate come una
sequenza di bit: il processo di “traduzione” da un’immagine
ad una sequenza binaria prende il nome di digitalizzazione
 L’immagine è suddivisa in punti o pixel (per
picture element ) e
ciascun punto viene codificato con un numero, che corrisponde
ad un colore o ad un particolare tono di grigio
 Si utilizzano un numero di colori o di sfumature che sia una
potenza del 2, in modo da codificare l’informazione legata a
ciascun pixel con un opportuno numero di bit
126
Anno accademico 2010-2011
La codifica delle immagini  2
• Le immagini vengono memorizzate come lunghe sequenze di
bit: per interpretarle è necessario conoscere...
 ...le dimensioni dell’immagine (base ed altezza in numero di
pixel), detta anche risoluzione
 ...il numero di colori (o toni di grigio) disponibili per ogni pixel
• Se un immagine viene codificata ad una data risoluzione,
potrà comunque essere presentata su un dispositivo a più
bassa risoluzione, a patto di “ignorare” parte dell’informazione
127
Anno accademico 2010-2011
La codifica delle immagini  3
• Come è avvenuto per i caratteri, anche per le immagini sono
stati definiti standard di codifica, che assicurano la
compatibilità fra sistemi diversi, per quanto concerne la
trasmissione e la visualizzazione delle immagini
 TIFF 
Tagged Image File Format
 JPEG
 PNG 
Portable Network Graphics
• Per ridurre lo spazio necessario per memorizzare le immagini
si utilizzano tecniche di compressione (utili anche per la
trasmissione su rete Internet)
128
Anno accademico 2010-2011
La codifica delle immagini  4
• Le tecniche di compressione si dividono in…
 Tecniche lossless: non provocano perdita di informazione, sono
adatte a codificare immagini in cui sono presenti ampie aree
monocromatiche  si codificano in maniera compatta insiemi di
pixel aventi le stesse caratteristiche
 Tecniche lossly: provocano perdita di informazione, facendo
decadere la qualità dell’immagine
• Normalmente ai formati JPEG e PNG, molto diffusi per lo
scambio di immagini su Internet, si applicano metodi di
compressione lossly
129
Anno accademico 2010-2011