Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: [email protected]...

112
damenti di Informatica I damenti di Informatica I a.a. 2008-09 a.a. 2008-09 1 Fondamenti di Fondamenti di Informatica I Informatica I E-mail: E-mail: [email protected] [email protected] Monica Bianchini Monica Bianchini Dipartimento di Ingegneria Dipartimento di Ingegneria dell’Informazione dell’Informazione ENIAC (1946 ca.) ENIAC (1946 ca.)

Transcript of Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: [email protected]...

Page 1: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 1

Fondamenti di Informatica IFondamenti di Informatica I

E-mail: E-mail: [email protected]@dii.unisi.it

Monica BianchiniMonica BianchiniDipartimento di Ingegneria dell’InformazioneDipartimento di Ingegneria dell’Informazione

ENIAC (1946 ca.)ENIAC (1946 ca.)

Valued Acer Customer
ENIACIl primo calcolatore elettronico, l’ENIAC - Electronical Numerical Integrator And Calculator - nacque per esigenze belliche (per il calcolo di tavole balistiche). Venne commissionato dal Dipartimento della Guerra degli Stati Uniti all’Università della Pennsylvania, ed il suo prototipo fu realizzato alla fine della seconda guerra mondiale, nel 1946.L’ENIAC, per la cui costruzione furono usate 18000 valvole termoioniche, occupava una stanza lunga più di 30 metri e dissipava una quantità enorme di energia elettrica. L’impiego di componenti elettroniche, tuttavia, lo rendeva capace di eseguire 300 moltiplicazioni al secondo, molte più dei precedenti calcolatori elettromeccanici.
Page 2: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 2

IntroduzioneIntroduzioneil calcolo automatico dalla preistoria ai giorni nostri

L’algebra di BooleL’algebra di Booleda Analisi Matematica della Logica (1847) al progetto degli elaboratori digitali

Sistemi di numerazioneSistemi di numerazioneda additivo a posizionale, da decimale a binario, a esadecimale: l’alfabeto dell’elaboratore

La rappresentazione dei datiLa rappresentazione dei dati e l’aritmetica degli e l’aritmetica degli elaboratorielaboratoridai bit ai numeri, ai testi, alle immagini, alla musica, ai video in digitale

SommarioSommario

UNIVAC (1951)UNIVAC (1951)

Valued Acer Customer
UNIVACIl primo calcolatore concepito ed impostato come prodotto commerciale, fu realizzato da Eckert e Mauchly (gli stessi costruttori dell’ENIAC) per l’Ufficio Centrale di Statistica degli Stati Uniti.L’algebra di BooleFu teorizzata dal matematico inglese George Boole (1810-1864) nel lavoro “Analisi Matematica della Logica”, pubblicato nel 1847. Include un insieme di operazioni su variabili logiche (o variabili booleane), che possono assumere i due soli valori true e false, indicati da 1 e 0. Le tecniche sviluppate nell’algebra booleana possono essere applicate all’analisi ed alla progettazione dei circuiti elettronici, poiché essi sono realizzati con dispositivi che possono assumere solo due stati.Su insiemi di costanti e variabili logiche possono essere definite funzioni che hanno esse stesse la caratteristica di assumere due soli valori. La definizione di una funzione booleana può essere effettuata per mezzo di una tabella di verità, che indica il valore della funzione in corrispondenza di ogni possibile configurazione dei valori degli argomenti. Le funzioni booleane possono essere scritte e manipolate anche con metodi algebrici, dato un insieme di funzioni (o operazioni) elementari tramite le quali poter esprimere ogni altra funzione.
Page 3: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 3

IntroduzioneIntroduzione

Page 4: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 4

Cenni storici Cenni storici 1 1

Anche se la presenza “invasiva” dell’informatica nella vita di tutti i giorni è un fenomeno relativamente recente, non recente è 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 faI primi esempi di algoritmi procedure di calcolo “automatico” sono stati ritrovati in Mesopotamia su tavolette babilonesi risalenti al 18001600 a.C.

Il sogno di costruire macchine capaci di effettuare calcoli automatici affonda le radici nel pensiero filosofico del ‘600:

Pascal e Leibniz non solo affrontarono il problema, già studiato da Cartesio, di automatizzare il ragionamento logico matematico, ma si cimentarono nella realizzazione di semplici macchine per calcolare (capaci di effettuare somme e sottrazioni)

Page 5: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 5

Cenni storici Cenni storici 2 2

La macchina alle differenzemacchina alle differenze, concepita da Babbage nel 1833, rappresenta il primo esempio di macchina programmabile di utilità generale

La prima programmatrice nella storia dell’informatica è Ada Augusta Byron, contessa di Lovelace

In seguito, lo stesso Babbage progetta la macchina macchina analiticaanalitica (mai realizzata, troppo complessa e critica la sua costruzione per le tecnologie meccaniche dell’epoca)

Page 6: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 6

Cenni storici Cenni storici 3 3

Fu Herman Hollerith, nel 1890, a sviluppare la macchina a schede perforatemacchina 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 sonoLe 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

Page 7: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 7

Cenni storici Cenni storici 4 4

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 Computing Tabulating Recording CompanyRecording Company che, nel 1923, divenne l’International Business MachineInternational Business Machine, o IBMIBM

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 Leibniz e da Boole)

Page 8: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 8

Cenni storici Cenni storici 5 5

EnigmaEnigma, realizzata dai tedeschi per codificare le comunicazioni militari

Red PurpleRed Purple, di costruzione giapponese

Computer ColossusComputer Colossus, costruito dagli inglesi per la decifrazione dei messaggi tedeschi, alla cui progettazione e realizzazione collaborò Alan TuringAlan Turing, permise la vittoria angloamericana sull’Atlantico

Durante la seconda guerra mondiale, fioriscono i progetti di elaboratori da utilizzarsi per scopi bellici

La macchina EnigmaLa macchina Enigma

Page 9: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 9

Cenni storici Cenni storici 6 6

Con l’invenzione del tubo a vuototubo a vuoto (1904), del transistortransistor (1947) e, infine, dei circuiti integraticircuiti integrati (1969), l’evoluzione dei computer divenne inarrestabile

Attualmente la potenza di calcolo degli elaboratori decuplica ogni 56 anni (…ma non può durare, almeno con le tecnologie in uso)

Page 10: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 10

Cenni storici Cenni storici 7 7

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 (ENIACENIAC, Mark I Mark I)Il nome di Von Neumann è legato invece ai primi calcolatori a programma memorizzato realizzati alla fine degli anni ‘40 (EDSACEDSAC, WhirlwindWhirlwind, IASIAS, UNIVACUNIVAC)

Per la prima volta, vige il principio di unitarietà di unitarietà di rappresentazione di dati e istruzionirappresentazione 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

Page 11: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 11

Cenni storici Cenni storici 8 8

EDSAC (1949)EDSAC (1949)ENIAC (1946)ENIAC (1946) Mark I (1948)Mark I (1948)

UNIVAC (1952)UNIVAC (1952)Whirlwind Whirlwind (1949)(1949)

IAS (1952)IAS (1952)

Page 12: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 12

Cenni storici Cenni storici 9 9

Tuttavia, l’esplosione dell’informatica come fenomeno di massa è datata 1981, anno in cui l’IBM introdusse un tipo particolare di elaboratore: il Personal ComputerPersonal 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 microprocessoremicroprocessore è utilizzato in tutti i settori applicativi (non solo per elaborare dati):

Telefoni cellulariRicevitori satellitari digitaliBancomat e carte di creditoLavatrici e forni a microondeComputer di bordo e ABS...

Page 13: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 13

Cenni storici Cenni storici 10 10

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 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 CDC6600CDC6600 e IlliacIlliac e, successivamente, il CrayCray e le macchine vettorialiA 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 estremamente elementari: le reti reti neuralineurali, capaci di “simulare” il comportamento del cervello umano, sulla base degli studi di McCulloch e Pitts (1943)

Page 14: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 14

Cenni storici Cenni storici 11 11

CDC 6600 CDC 6600 (1963)(1963)

Illiac (1955)Illiac (1955)

PC IBM (1981)PC IBM (1981) Portatile e Palmare (oggi)Portatile e Palmare (oggi)

Cray 1 (1976)Cray 1 (1976)Cray X1 (2002)Cray X1 (2002)

Page 15: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 15

Frasi celebri ed altro…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 avanti e indietro questa nazione (USA) e ho parlato con la gente. Vi assicuro che questa moda dell’elaborazione automatica non vedrà l’anno prossimo.” (Editor di libri scientifici di Prentice Hall, 1947) “Nel futuro i computer verranno a pesare non più di una tonnellata e mezzo.” (Popular Mechanichs, 1949)Nel 1976, il New York TimesNew York Times pubblicò un libro dal titolo La La scienza nel ventesimo secoloscienza 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)

Page 16: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 16

Che cos’è l’informatica Che cos’è l’informatica 1 1

InformaticaInformatica fusione delle parole informazioneinformazione e automaticaautomatica l’insieme delle discipline che studiano gli strumenti per l’elaborazione automatica dell’informazione e i metodi per un loro uso corretto ed efficaceL’informatica è la scienza della rappresentazione e L’informatica è la scienza della rappresentazione e dell’elaborazione dell’informazionedell’elaborazione dell’informazione

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 supportoIl termine “scienza” sottolinea il fatto che, nell’informatica, l’elaborazione dell’informazione avviene in maniera sistematica e rigorosa, e pertanto può essere automatizzata

Page 17: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 17

Che cos’è l’informatica Che cos’è l’informatica 2 2

L’informatica non è, quindi, la scienza e la tecnologia dei calcolatori elettronici: il calcolatore è lo strumento che la rende “operativa”L’elaboratoreelaboratore (computer, calcolatore) è un’apparecchiatura digitaledigitale, elettronicaelettronica ed automaticaautomatica capace di effettuare trasformazioni sui dati:

DigitaleDigitale: i dati sono rappresentati mediante un alfabeto finito, costituito da cifre (digitdigit), che ne permette il trattamento mediante regole matematicheElettronicaElettronica: realizzazione tramite tecnologie di tipo elettronicoAutomaticaAutomatica: capacità di eseguire una successione di operazioni senza interventi esterni

“La disumanità del computer sta nel fatto che, una volta programmato e messo in funzione, si comporta in maniera perfettamente onesta.” (Isaac Asimov)

Page 18: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 18

L’architettura di Von NeumannL’architettura di Von Neumann

La capacità dell’elaboratore di eseguire successioni di operazioni in modo automatico è determinata dalla presenza di un dispositivo di memoriamemoria

Nella memoria sono registrati i datidati e...

...la descrizione delle operazioni da eseguire su di essi (nell’ordine secondo cui devono essere eseguite): il programmaprogramma, la “ricetta” usata dall’elaboratore per svolgere il suo compito

Il programma viene interpretato dall’unità di controllounità di controllo

Modello diModello di Von NeumannVon Neumann

Page 19: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 19

La macchina universaleLa macchina universale

ProgrammaProgramma: sequenza di operazioni atte a predisporre l’elaboratore alla soluzione di una determinata classe di problemi

Il programma è la descrizione di un algoritmoalgoritmo in una forma comprensibile all’elaboratore

AlgoritmoAlgoritmo: 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 universalemacchina universale: cambiando il programma residente in memoria, è in grado di risolvere problemi di natura diversa (una classe di problemi per ogni programma)

Page 20: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 20

Ancora sull’informatica... Ancora sull’informatica...

L’informatica è lo studio sistematico degli algoritmi L’informatica è lo studio sistematico degli algoritmi che descrivono e trasformano l’informazione: la loro che descrivono e trasformano l’informazione: la loro teoria, analisi, progetto, efficienza, realizzazione (ACM teoria, analisi, progetto, efficienza, realizzazione (ACM Association for Computing Machinery) Association for Computing Machinery)

NotaNota: È possibile svolgere un’attività concettualmente 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 informazioni altrimenti intrattabili

Page 21: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 21

L’algebra di BooleL’algebra di Boole

Page 22: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 22

Algebra BooleanaAlgebra Booleana

Contempla due costanti 00 e 11 (falsofalso e verovero)Corrispondono a due stati che si escludono a vicendaPossono descrivere lo stato di apertura o chiusura di un generico contatto o di un circuito a più contatti

Si definiscono delle operazioni fra i valori booleani:ANDAND, OROR, NOTNOT sono gli operatori fondamentali

0 1

Valued Acer Customer
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; le parentesi vengono utilizzate nel modo consueto.
Page 23: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 23

L’operazione di ORL’operazione di OR

Si definisce l’operazione di somma logicasomma 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

0+0 0+1

00 001 110 111 1

1

1

1

0

1+0 1+1

Page 24: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 24

L’operazione di ANDL’operazione di AND

Si definisce l’operazione di prodotto logicoprodotto logico (AND):il valore del prodotto logico è il simbolo 1 se il valore di tutti gli operandi è il simbolo 1

00 001 010 011 1

11

11

01

10

10

01

00

00

Page 25: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 25

La negazione NOTLa negazione NOT

Si definisce l’operatore di negazionenegazione (NOT):l’operatore inverte il valore della costante su cui opera

Dalla definizione…

0 11 0

0 01 1

Page 26: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 26

Variabili binarieVariabili binarie

Una variabile binaria indipendente può assumere uno dei due valori 0 e 1

Date N variabili binarie indipendenti, la loro somma logica (OR) è

A0

1

A+B+C+D+….N =

1 se almeno una Ni vale 1

0 se A= B= …= N = 0

Page 27: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 27

AND e NOT con variabili binarieAND e NOT con variabili binarie

A B … N =

0 se almeno una Ni vale 0

1 se A= B= …= N = 1

A = 0 se A = 1A = 1 se A = 0

Valued Acer Customer
L’elemento x’ = NOT(x) viene detto complemento di x. Il complemento è unico.
Page 28: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 28

Alcune identitàAlcune identità

A + 1 1A + 0 A A + A A

A 1 AA 0 0 A A A

A 1 A

1 1 101 0

A 0 A 1

OK!OK!

Valued Acer Customer
0 è l’elemento neutro per l’operazione di OR; 1 è l’elemento neutro per l’AND. Gli elementi neutri sono unici. La legge x + x = x·x = x è detta legge dell’idempotenza.
Page 29: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 29

Per gli operatori AND e OR valgono le seguenti proprietà:

Per l’operatore NOT si provano le seguenti identità:

Altre proprietàAltre proprietà

commutativacommutativa A+B B+A AB BA

associativaassociativa A+B+CA+(B+C) ABCA (BC)

distributiva deldistributiva del prodotto rispetto alla sommaprodotto rispetto alla somma AB+AC

A(B+C)

A + A 1A A 0 A A

Page 30: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09

Proprietà dell’Algebra di Boole

30

Page 31: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09

Teoremi 1 dell’Algebra di Boole

31

Page 32: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09

Teoremi 1 dell’Algebra di Boole

32

Page 33: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 33

Date N variabili binarie indipendenti A, B,…, Ni, queste possono assumere 2n configurazioni distinte

Una configurazione specifica è individuata univocamente da un AND (a valore 1) di tutte le variabili, dove quelle corrispondenti ai valori 0 compaiono negate

Configurazioni delle variabiliConfigurazioni delle variabili

Ad esempio per N3 si hanno 8 configurazioni

A B C 000 001 010 011100 101 110 111

A B C010

Page 34: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 34

Una variabile y è una funzione delle N variabili indipendenti A, B,…, Ni, se esiste un criterio che fa corrispondere in modo univoco ad ognuna delle 2n configurazioni delle xi un valore di y

Una rappresentazione esplicita di una funzione è la tabella di veritàtabella di verità, in cui si elencano tutte le possibili combinazioni di A, B, …, Ni, con

associato il valore di y

Funzioni logicheFunzioni logiche

y = F(A,B,…,Ni)

B A y0 0 00 1 11 0 11 1 1

y = A+B

Page 35: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 35

Una tabella di verità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 F0 0 0 00 0 1 00 1 0 00 1 1 11 0 0 01 0 1 11 1 0 11 1 1 0

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)Forma canonica: somma di prodotti (OR di AND) tutte le funzioni logiche si possono scrivere in questa forma

Page 36: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 36

Un esempio: lo XORUn esempio: lo XOR

A B XOR0 0 00 1 11 0 11 1 0

XOR = A B + AB

Valued Acer Customer
La legge dell’assorbimento x1+ x1· x2 = x1Le leggi di De Morgan (x1+ x2)’ = x1’· x2’ ( x1 · x2)’ = x1’+ x2’ ( ’ un modo alternativo per indicare la negazione).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.
Page 37: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 37

Un circuito con due interruttoriUn 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 B L

0 0 10 1 01 0 01 1 1

L = ABABA B

A B0

11

0

A=1 B=0

L

A B

A B0

11

0

A=1 B=1

L

A B

A B0

11

0

A=0 B=1

L

A B

A B0

11

0

A=0 B=0

L

Page 38: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 38

Un esercizioUn esercizio

Progettare un circuito per accendere e spegnere una lampada da uno qualsiasi di tre interruttori indipendenti

A B C

1 1 1

0 0 0

A B C

1 1

0

1

0 0

0 00

0 01

Cambia lostato di uninterruttorequalsiasi

L = 0

L = 1

Page 39: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 39

Analisi delle combinazioniAnalisi delle combinazioni

Si considera cosa accade a partire dalla configurazione di partenza, cambiando lo stato di un interruttore per volta

A B C

0 00

L = 0

L = 1A B C

0 10

A B C

0 01

L = 1

A B C

1 00

L = 1 L = 0A B C

1 01

A B C

1 11

L = 10 11

A B CL = 0

1 10

A B CL = 0

Page 40: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 40

Scrittura della funzione logicaScrittura della funzione logica

A B C L0 0 0 00 0 1 10 1 0 10 1 1 01 0 0 11 0 1 01 1 0 01 1 1 1

L ABC ABC ABC ABC

Page 41: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 41

Come collegare gli interruttoriCome collegare gli interruttori

Si può manipolare l’espressione di L usando la proprietà distributiva dell’AND rispetto all’OR

L A (BC BC) A (BC BC)

L ABC ABC ABC ABC

A

A

B

B

C

C

C

CB

B A

A

B

B

C

C

C

CB

B

1 0 0 1 0 1

Page 42: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 42

EserciziEsercizi

Esercizio 1Esercizio 1

Siano a2, a1, b2, b1 i bit che rappresentano due numeri interi positivi (Aa2a1 e Bb2b1). Sia r una variabile booleana che vale 1 se e solo A è maggiore di B (AB). Ad esempio, quando A11 e B10, allora a21, a11, b21, b10 e r1. Si scriva la forma canonica che definisce r come funzione di a2, a1, b2, b1.

Esercizio 2Esercizio 2I signori A, B, C e D fanno parte di un consiglio di amministrazione. Sapendo che hanno a disposizione le seguenti quote di possesso azionario A40%, B25%, C20%, D15%, 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.

Page 43: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 43

Esercizi (continua)Esercizi (continua)

Esercizio 3Esercizio 3Il 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 costa meno della cifra disponibile. Ad esempio, se a21, a51, a60, a80, allora r1. Si scriva la forma canonica che definisce r come funzione delle variabili a2, a5, a6, a8.

Page 44: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 44

Sistemi di numerazioneSistemi di numerazione

Page 45: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 45

Ancora un po’ di preistoria…Ancora un po’ di preistoria…

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, 12, 15, 20, 30 e 60Da notare che il 7 non compare mai nelle basi di numerazione e, in effetti, ebbe significati particolari, anche religiosi, presso i popoli antichi La base 12 è ancora utilizzata in certe misure di tempo, 60 nella misurazione di angoli e tempo

Page 46: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 46

……E di storiaE di storia

Tra le prime testimonianze certe dell’utilizzo di concetti numerici 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.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

Page 47: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 47

I numeri in Mesopotamia I numeri in Mesopotamia 1 1

Appartengono alla civiltà dei SumeriSumeri varie tavolette che contengono i più antichi segni numerali usati dall’uomo e risalgono al 35003000 a.C.I simboli fondamentali usati nella numerazione sumera corrispondono ai numeri 1, 10, 60, 600, 3600, 36000La numerazione è additiva, cioè i numeri si scrivono disponendo uno accanto all’altro i simboli fondamentali

Page 48: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 48

I numeri in Mesopotamia I numeri in Mesopotamia 2 2

Un ruolo speciale spetta ai numeri 10 e 60: caratteristica ereditata dal sistema babiloneseI BabilonesiBabilonesi usavano infatti la scrittura cuneiforme, con due simboli fondamentali, un cuneo verticale per le unità e una parentesi uncinata per le decine: si rappresentavano i numeri da 1 a 59Per 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 in base 60

Page 49: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 49

I numeri in Mesopotamia I numeri in Mesopotamia 3 3

Page 50: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 50

I numeri in Mesopotamia I numeri in Mesopotamia 4 4

Ad esempio:

Il sistema di spaziatura consentiva di risolvere le ambiguità di interpretazione dei raggruppamentiAi 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

= 7322

Page 51: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 51

I numeri nell’antico Egitto I numeri nell’antico Egitto 1 1

La matematica egizia utilizzava la base 10, ed impiegava simboli diversi per rappresentare le diverse potenze del 10, da 1 a 106 I geroglifici utilizzati erano:

Rotolo di fune

Uomo a braccia levate,simbolo del dio Heh

Bastoncino

Girino o ranaDito

Pastoia per bestiame o giogo

Ninfea o fiore di loto

Page 52: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 52

I numeri nell’antico Egitto I numeri nell’antico Egitto 2 2

I numeri venivano formati raggruppando i simboli, generalmente posti in ordine dal più piccolo al più grande, da sinistra a destra

Il sistema di numerazione non è, tuttavia, posizionale

L’ordine dei simboli che rappresentano le potenze del 10 può essere alterato senza cambiare il valore della quantità rappresentataL’ordine è una sorta di convenzione linguistica, senza significato matematico

Page 53: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 53

I numeri nell’antico Egitto I numeri nell’antico Egitto 3 3

=131.200

Page 54: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 54

I numeri nell’antico Egitto I numeri nell’antico Egitto 4 4

Esempi di operazioniEsempi di operazioniAddizioneAddizione: 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)

MoltiplicazioneMoltiplicazione: utilizza un sistema che sottintende la base due

si scompone il moltiplicatore in potenze di 2, poi si raddoppia il moltiplicando tante volte quante necessario, e infine si esegue la somma

Page 55: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 55

I numeri nell’antico Egitto I numeri nell’antico Egitto 5 5

EsempioEsempio: 713

13

=91

Page 56: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 56

I numeri nell’antica Grecia I numeri nell’antica Grecia 1 1

Nella civiltà greca classica sono noti due principali sistemi di numerazione

Il primo, più antico, è noto come atticoattico 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, 50000Compaiono testimonianze di questo sistema dal V al I secolo a.C. ma, a partire dal III secolo, si diffonde anche il sistema detto ionicoionico o alfabeticoalfabetico

Page 57: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 57

I numeri nell’antica Grecia I numeri nell’antica Grecia 2 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 additivoSistema di numerazione decimale additivo

Page 58: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 58

I numeri nell’antica Grecia I numeri nell’antica Grecia 3 3

Ad esempio:

= 67.766.776

Page 59: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 59

I numeri nell’antica Roma I numeri nell’antica Roma 1 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 L C D M1 5 10 50 100 500 1000

Page 60: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 60

I numeri nell’antica Roma I numeri nell’antica Roma 2 2

La scrittura dei numeri avveniva combinando additivamente i segni 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

Page 61: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 61

Dall’India… il sistema decimale Dall’India… il sistema decimale 11

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 ArabiArabi, si è diffuso in Europa

Page 62: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 62

Dall’India… il sistema decimale Dall’India… il sistema decimale 22

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.

Page 63: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 63

Dall’India… il sistema decimale Dall’India… il sistema decimale 33

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 IndianiIndiani 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 BrahmiBrahmi, in uso dal III secolo a.C.

Page 64: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 64

Dall’India… il sistema decimale Dall’India… il sistema decimale 44

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

Page 65: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 65

Sistemi di numerazione Sistemi di numerazione posizionaliposizionali

Sistemi di numerazione posizionaliposizionali:

La basebase del sistema di numerazioneLe cifrecifre del sistema di numerazione

Il numero è scritto specificando le cifre in ordine ed il suo valore dipende dalla posizione relativaposizione relativa delle cifreEsempioEsempio: 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

Page 66: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 66

Sistemi in base BSistemi in base B

La base definisce il numero di cifre diverse nel sistema di numerazioneLa cifra di minor valore è sempre lo 0; le altre sono, nell’ordine, 1,2,…,B1; se B>10 occorre introdurre B10 simboli in aggiunta alle cifre decimali

N = cnBn+cn1Bn1+...+c2B2+c1B1+c0B0

Un numero frazionariofrazionario N’ si rappresenta come (0,c1c2…cn)B

Un numero interointero N si rappresenta con la scrittura (cncn1…c2c1c0)B

N’ = c1B1+c2B2+...+cnBn

ccnn è la cifra più significativacifra più significativa, cc00 la meno significativameno significativa

Page 67: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 67

Numeri interi senza segnoNumeri interi senza segno

Con n cifre in base B si rappresentano tutti i numeri interi positivi da 0 a Bn1 (Bn numeri distinti)

EsempioEsempio: base 10

2 cifre: da 0 a 1021 = 99

000102….9899

EsempioEsempio: base 2

2 cifre: da 0 a 221 = 3

00011011

102 = 100 valori

22 = 4 valori

Page 68: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 68

Il sistema binario (B=2)Il sistema binario (B=2)

La base 2 è la più piccola per un sistema di numerazioneLa base 2 è la più piccola per un sistema di numerazione

Cifre: 0 1 bitbit (binary digitbinary digit)

EsempiEsempi:

(101101)2 = 125 + 024 + 123 + 122 + 021 + 120 = 32 + 0 + 8 + 4 + 0 + 1 = (45)10

(0,0101)2 = 021 + 122 + 023 + 124 = 0 + 0,25 + 0 + 0,0625 = (0,3125)10

(11,101)2 = 121 + 120 + 121 + 022 + 123 = 2 + 1 + 0,5 + 0 + 0,125 = (3,625)10

FormaFormapolinomipolinomiaa

Page 69: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 69

Un bytebyte è un insieme di 8 bit (un numero binario a 8 cifre)

Con un byte si rappresentano i numeri interi fra 0 e 281 255

È l’elemento base con cui si rappresentano i dati nei calcolatoriSi utilizzano sempre dimensioni multiple (di potenze del 2) del byte: 2 byte (16 bit), 4 byte (32 bit), 8 byte (64 bit)…

Dal bit al byteDal bit al byte

b7b6b5b4b3b2b1b0

00000000000000010000001000000011…………….1111111011111111

28 256 valori distinti

Page 70: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 70

Dal byte al kilobyteDal byte al kilobyte

24 = 1628 = 256216 = 65536

210 = 1024 (K=Kilo)220 = 1048576 (M=Mega)230 = 1073741824 (G=Giga)

1 KB = 210 byte = 1024 byte1 MB = 220 byte = 1048576 byte1 GB = 230 byte = 1073741824 byte1 TB = 240 byte = 1099511627776 byte (Terabyte)

Page 71: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 71

Da decimale a binarioDa decimale a binarioNumeri interiNumeri interi

Si divide ripetutamente il numero interointero 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

EsempioEsempio: convertire in binario (43)10

43 : 2 = 21 + 121 : 2 = 10 + 110 : 2 = 5 + 0 5 : 2 = 2 + 1 2 : 2 = 1 + 0 1 : 2 = 0 + 1

resti

bit più significativo

(43)10 = (101011)2

Page 72: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 72

Si moltiplica ripetutamente il numero frazionariofrazionario 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

Da decimale a binarioDa decimale a binarioNumeri razionaliNumeri razionali

EsempioEsempio: convertire in binario (0,21875)10 e (0,45)10 0,45 2 = 0,9

0,90 2 = 1,80,80 2 = 1,60,60 2 = 1,20,20 2 = 0,4 etc.

(0,45)10 (0,01110)2

0,21875 2 = 0 ,43750,4375 2 = 0,8750,875 2 = 1,750,75 2 = 1,50,5 2 = 1,0

(0,21875)10 = (0,00111)2

Page 73: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 73

Da binario a decimaleDa binario a decimale

Oltre all’espansione esplicita in potenze del 2 forma polinomiaforma polinomia…

…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

EsempioEsempio: convertire in decimale (101011)2

bit più significativo

(101011)2 = 125 + 024 + 123 + 022 + 121 + 120 = (43)10

1 x 2 = 2 + 0 2 x 2 = 4 + 1 5 x 2 = 10 + 0 10 x 2 = 20 + 1 21 x 2 = 42 + 1 = 43

(101011)2 = (43)10

Valued Acer Customer
EsercizioSi verifichino le seguenti corrispondenze:(110010)_2=(50)_10(1110101)_2=(102)_10(1111)_2=(17)_10(11011)_2=(27)_10(100001)_2=(39)_10(1110001110)_2=(237)_10
Page 74: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 74

Sistema esadecimaleSistema esadecimale

La base 16 è molto usata in campo informaticoLa base 16 è molto usata in campo informatico

Cifre: 0 1 2 3 4 5 6 7 8 9 A B C D E F

EsempioEsempio:

(3A2F)16 = 3163 + 10162 + 2161 + 15160 = 34096 + 10256 + 216 + 15 = (14895)10

La corrispondenza in decimale delle cifre oltre il 9 è

A = (10)10 D = (13)10

B = (11)10 E = (14)10

C = (12)10 F = (15)10

Page 75: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 75

Da binario a esadecimaleDa binario a esadecimale

0000 0 1000 80001 1 1001 90010 2 1010 A0011 3 1011 B0100 4 1100 C0101 5 1101 D0110 6 1110 E0111 7 1111 FF corrisponde a 4 bit a 1

0 corrisponde a 4 bit a 0

Page 76: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 76

Dai bit all’hexDai bit all’hex

Un numero binario di 4n bit corrisponde a un numero esadecimale di n cifre

EsempioEsempio: 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

EsempioEsempio: 16 bit corrispondono a 4 cifre esadecimali

0000 0000 1111 1111 0 0 F F

(00FF)16

Page 77: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 77

Da esadecimale a binarioDa esadecimale a binario

La conversione da esadecimale a binario si ottiene espandendo ciascuna cifra con i 4 bit corrispondenti

EsempioEsempio: convertire in binario il numero esadecimale 0x0x0c8f

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 x 4 16 bit

Page 78: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 78

Esempi Esempi 1 1

In qualsiasi base, l’essere il sistema di numerazione posizionaleposizionale impone che combinazioni diverse di cifre uguali rappresentino numeri diversi; ad esempio:

(319)10 (193)10

(152)6 (512)6, infatti... (152)6=162+561+260=36+30+2=(68)10

(512)6=562+161+260=180+6+2=(188)10

Numeri che hanno identica rappresentazione, in basi diverse, hanno valori diversi:

(234)10 (234)8 , infatti...(234)8 = 282 + 381 + 480 = 264 + 38 + 4 = 128+24+4 =

(156)10

OsservazioneOsservazione: più piccola è la base, minore è il valore del numero rappresentato dalla stessa sequenza di cifre

Page 79: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 79

Esempi Esempi 2 2

La notazione posizionale si applica anche per il calcolo del valore dei numeri frazionari, infatti...

(0,872)10 = 8101 + 7102 + 2103

= 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 2n1, quindi...

per n=1 (con una cifra) si rappresentano 0...211 0,1per n=2: 0...221 0...3per n=3: 0...231 0...7per n=4: 0...241 0...15per n=5: 0...251 0...31per n=6: 0...261 0...63

Effettivamente possiamo verificare che (100100)2=(36)10, infatti...

100100=125+024+023+122+021+020

= 32 + 4 = 36

con 66 cifre necessarie per la codifica del numero in base 2

Page 80: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 80

Esempi Esempi 3 3

QuesitoQuesito: Per quale base B risulterà vera l’uguaglianza17 + 41 + 22 = 102 ?

Se i numeri sono rappresentati in base B, sappiamo che:(17)B = 1B1+7B0 = B+7

(41)B = 4B1+1B0 = 4B+1

(22)B = 2B1+2B0 = 2B+2

(102)B = 1B2+0B1+2B0 = B2+2

da cui...B+7+4B+1+2B+2 = 7B+10 = B2+2

Si ottiene un’equazione di 2° grado: B2 7B 8 = 0Risolvendo: = 49+32 = 81

B = (7 )/2 =(79)/2 = 1

(7+9)/2 = 8 È la soluzione!È la soluzione!

Non può essere una base

Page 81: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 81

La rappresentazione dei datiLa rappresentazione dei dati e l’aritmetica degli elaboratorie l’aritmetica degli elaboratori

Page 82: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 82

Numeri interi positiviNumeri interi positivi

I numeri interi positivi sono rappresentati all’interno dell’elaboratore utilizzando un multiplo del byte (generalmente 4/8 byte)Se l’intero si rappresenta con un numero di cifre minore, vengono aggiunti zeri nelle cifre più significative

EsempioEsempio: 12 viene rappresentato in un byte come…

00001100

Page 83: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 83

Numeri con segnoNumeri 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

Page 84: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 84

Modulo e segnoModulo e segno

Il bit più significativo rappresenta il segno: 0 per i numeri positivi, 1 per quelli negativiEsiste uno zero positivo (00…0) e uno zero negativo (10…0)Se si utilizzano n bit si rappresentano tutti i numeri compresi fra (2n11) e 2n11

EsempioEsempio: con 4 bit si rappresentano i numeri fra 7 ((231)) e 7 (231)

0000 00001 10010 20011 30100 40101 50110 60111 7

1000 01001 11010 21011 31100 41101 51110 61111 7

positivi negativi

Page 85: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 85

Complemento a 2Complemento a 2

01010111

10101000

10101001

complemento a 1

1

100000000011111111 01010111 10101000

10101001

28

281N281N

281N1

2n(N)2 = 10……0(N)2

{n

Page 86: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 86

Interi in complemento a 2Interi in complemento a 2

I numeri positivinumeri positivi sono rappresentati (come) in modulo e segnoI numeri negativinumeri negativi sono rappresentati in complemento a 2 la cifra più significativa ha sempre valore 1Lo zero è rappresentato come numero positivo (con una sequenza di n zeri)Il campo dei numeri rappresentabili varia da 2n1 a 2n11EsempioEsempio: numeri a 4 cifre

0000 00001 10010 20011 30100 40101 50110 60111 7

1000 81001 71010 61011 51100 41101 31110 21111 1

Nota: 0111 7 1000 8

Page 87: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 87

Interi a 16 bitInteri a 16 bit

Numeri interi rappresentati su 16 bit in complemento a 2:

Il numero intero positivo più grande è 2151=(32767)10

0111 1111 1111 11110x 7 F F F

Il numero intero negativo più piccolo è 215=(32768)10

1000 0000 0000 00000x 8 0 0 0

0111 1111 1111 1111 + 1 1000 0000 0000 0000

Il numero intero –1 è rappresentato come

1111 1111 1111 11110x F F F F

0000 0000 0000 0000 + 1 0000 0000 0000 0001

Page 88: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 88

Addizione binariaAddizione binaria

0 + 0 00 + 1 11 + 0 11 + 1 0 con riporto di 1

EsempioEsempio1 11 101011011+0101101010110101

riporti

181

91+90

Page 89: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 89

Sottrazione binaria Sottrazione binaria 1 1

Le regole per la sottrazione di due bit sono

La sottrazione può divenire complicata: quando si ha una richiesta (di un prestito) sulla cifra precedente a sinistra, che è uno 0, l’operazione si propaga a sinistra fino alla prima cifra ad 1 del sottraendo

0 0 0 1 0 1 1 1 010 1 1 con prestito di 1 dalla cifra precedente a sinistra EsempioEsempio

0 10 1 1 0 0 1 1 0 11 0 1 0 0 20

25 5

Page 90: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 90

Sottrazione binaria – 2Sottrazione binaria – 2

Utilizzando la rappresentazione in complemento a 2, addizione e sottrazione sono trattate come un’unica operazione di somma algebricasomma algebrica

N1N2 = N1(2nN2)2n

complemento a 2 di N2: rappresentazione di (N2)

si trascura il bit n 1

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

EsempioEsempio: (010001)2(000101)2 = (17)10(5)10

010001 1110111001100 (12)10

{

Page 91: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 91

Sono utili perché l’operazione di somma algebrica può essere realizzata non curandosi del bit di segnoIn complemento a 1 (più semplice da calcolare)…

Zero ha due rappresentazioni: 00000000 e 11111111 La somma bit a bit funziona “quasi sempre”

In complemento a 2…Zero ha una sola rappresentazioneLa somma bit a bit funziona sempre

Rappresentazioni in Rappresentazioni in complementocomplemento

11001 (6)

11010 = (5)

1001110011 (12)

00110 (6)

10101 = (10)

11011 (4)

Page 92: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 92

OverflowOverflow

EsempioEsempio: 5 bit [16,15]

01110 0101011000

14 1024

11000 10110101110

8 10188 14

Punteggio nei vecchi videogame… sorpresa per i campioni!0111 1111 1111 1111 1 = 1000 0000 0000 0000 32767 1 = 32768

Page 93: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 93

Moltiplicazione binariaMoltiplicazione binaria

0 0 00 1 01 0 01 1 1

EsempioEsempio 1100111 x 101 1100111 0000000 11001111000000011

110011 x 10000 11001100000000 16 24

816

51

Page 94: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 94

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 BQ RLa divisione binaria si compone di una serie di sottrazioni

Dividere per 2n equivale a scorrere il numero a destra di n posizioni; le cifre scartate costituiscono il resto

Divisione binariaDivisione binaria

1 1 0 1 1 0 1 0 11 0 1 1 0 1 0 1 1 1

1 0 1 1 0 0

(

^^^

51:16 3 con resto 3

110011 10000 11 con resto 11

54 510 + 4

Page 95: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 95

EsempioEsempio

QuesitoQuesito: Data una base B, si consideri il numero x(C5C4C3C2C1C0)B, dove le singole cifre valgono:

C5 = B1, C4 = B1, C3 = B1, C2 = 0, C1 = 0, C0 = 0Qual è 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 sinistraRimangono quindi le tre cifre più significative,

tutte uguali a B1Sommando 1, a causa dei riporti, si ottiene

quindi come risultato dell’espressione 1000B3, qualsiasi sia il valore della base B

Page 96: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 96

EserciziEsercizi

Esercizio 1Esercizio 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(AC)C)B = (AB = (AB)B)CC,con A=7A=7, B=5B=5, C=7C=7. Si ottiene lo stesso risultato dal calcolo dei due membri? Discutere le motivazioni della risposta.

Esercizio 2Esercizio 2a) Si determini, se esiste, la base b di un sistema di

numerazione tale che

(842)(842)bb = (1202) = (1202)1010

b) Si determini, se esiste, la base b 16 di un sistema di numerazione tale che

(725)(725)bb (626) (626)bb = (224) = (224)1010

Page 97: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 97

Numeri in virgola mobileNumeri in virgola mobile

La rappresentazione dei numeri in virgola mobile è in relazione con la notazione scientificanotazione scientifica (es. 1.2102120)La IEEE ha previsto uno standard per la rappresentazione in virgola mobile singola precisionesingola precisione (32 bit 4 byte)

doppia precisionedoppia precisione (64 bit 8 byte) quadrupla precisionequadrupla precisione (128 bit 16 byte)

Singola precisione031 2223

23 bit8 bit

Mantissa(o Caratteristica)

Segno

Il valore è(1)S 1.M2E127 se E0(1)S 0.M2126 se E=0

Esponente

EccessoEccesso: vale 2t11, se t è il numero di cifre riservate alla caratteristica rappresentazione “interna” dell’esponente sempre positiva

Page 98: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 98

Singola precisioneSingola precisione

0 11111111 11111111111111111111111 2255127 1.111111111111111111111111

0 00000000 00000000000000000000001 2126 0.00000000000000000000001

0.50 1 2 4

223 valori223 valori 223 valori223 valori

Page 99: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 99

Metodo per il calcolo dell’addizione1. 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 1.2 Si incrementa la caratteristica di 1, fino a quando

le due

2. La mantissa del risultato è ottenuta dalla somma delle due mantisse

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

L’aritmetica floatingL’aritmetica floatingpoint: addizionepoint: addizione

caratteristiche sono uguali, e corrispondono alla caratteristica del risultato

Page 100: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 100

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

La caratteristica del secondo operando è più piccola di una unità, quindi la mantissa deve scorrere di una posizione a destra

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:

Un esempio di addizione Un esempio di addizione

0 1 001 11 0

1001 0100

Codifica il numero 4 (dato che la caratteristica si rappresenta in eccesso a 4), ma il risultato corretto è 4.375: errore di errore di troncamentotroncamento

1.125

3.25

01 100 01 1

0 0 111 11 0N = (1)s0.M2E4

Page 101: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 101

Metodo per il calcolo della moltiplicazione1. Si moltiplicano le due mantisse2. Si addizionano le due caratteristiche3. 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 caratteristiche, ottenendo la caratteristica del prodotto

L’aritmetica floatingL’aritmetica floatingpoint: point: moltiplicazionemoltiplicazione

Page 102: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 102

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

Moltiplicando le mantisse e sommando le caratteristiche si ottiene:

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:

Un esempio di moltiplicazione Un esempio di moltiplicazione

M=01110101 E=111

0 0 010 11 1Codifica il numero 0.21875, ma il risultato corretto è 0.228515625: errore di troncamentoerrore di troncamento

01 100 01 1 1.125

0.2031250 0 110 11 0N = (1)s0.M2E4

Page 103: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 103

L’aritmetica “interna” degli elaboratori differisce notevolmente dall’aritmetica classicaSebbene le stesse operazioni possano essere realizzate secondo modalità diverse su elaboratori diversi, si riscontrano alcune caratteristiche comuni:

Rappresentazione binaria dei numeriRappresentazione binaria dei numeri

Rango finito dei numeri rappresentabiliRango finito dei numeri rappresentabili

Precisione finita dei numeriPrecisione finita dei numeri

Operazioni espresse in termini di operazioni più Operazioni espresse in termini di operazioni più semplicisemplici

L’aritmetica degli elaboratori L’aritmetica degli elaboratori 1 1

Page 104: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 104

Rango finito dei numeri rappresentabiliRango finito dei numeri rappresentabili Qualunque sia la codifica utilizzata, esistono sempre il più grande ed il più piccolo numero rappresentabileI limiti inferiore e superiore del rango di rappresentazione dipendono sia dal tipo di codifica, sia dal numero di bit utilizzatiSe il risultato di un’operazione non appartiene al rango dei numeri rappresentabili, si dice che si è verificato un overflow (un underflowunderflow, più precisamente, se il risultato è più piccolo del più piccolo numero rappresentabile)

L’aritmetica degli elaboratori L’aritmetica degli elaboratori 2 2

Page 105: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 105

Precisione finita dei numeriPrecisione finita dei numeriLa precisioneprecisione della rappresentazione di un numero frazionario è una misura di quanto essa corrisponda al numero che deve essere rappresentatoNegli elaboratori, i numeri frazionari sono rappresentati in virgola mobile (floating–pointfloating–point), utilizzando un numero finito di bitÈ plausibile che un numero reale non ammetta una rappresentazione finita, quindi dovrà essere codificato in maniera approssimataNegli elaboratori si rappresentano soltanto numeri razionali (fino ad una data precisione)

L’aritmetica degli elaboratori L’aritmetica degli elaboratori 3 3

Page 106: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 106

Operazioni espresse in termini di operazioni più Operazioni espresse in termini di operazioni più semplicisemplici

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’addizioneLa moltiplicazione si realizza per mezzo di una successione di addizioni e di shift 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 hardwarehardware); 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 firmwarefirmware)

L’aritmetica degli elaboratori L’aritmetica degli elaboratori 4 4

Page 107: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 107

Codifica dei caratteri alfabetici – Codifica dei caratteri alfabetici – 11

Oltre ai numeri, molte applicazioni informatiche elaborano caratteri (simboli)Gli elaboratori elettronici trattano numeriSi codificano i caratteri e i simboli per mezzo di numeriPer poter scambiare dati (testi) in modo corretto, occorre definire uno standard di codifica

A 01000001

3 00110011

$ 00100100

Page 108: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 108

Codifica dei caratteri alfabetici – Codifica dei caratteri alfabetici – 22

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 codice ASCIIASCII, per American Standard Code for American Standard Code for Information InterchangeInformation Interchange

Page 109: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 109

Codifica ASCIICodifica ASCII

Definisce una tabella di corrispondenza fra ciascun carattere e un codice a 7 bit7 bit (128 caratteri)I caratteri, in genere, sono rappresentati con 1 byte1 byte (8 bit); i caratteri con il bit più significativo a 1 (quelli con codice dal 128 al 255) rappresentano un’estensione della codificaLa tabella comprende sia caratteri di controllocaratteri di controllo (codici da 0 a 31) che caratteri stampabilicaratteri stampabiliI caratteri alfabetici/numerici hanno codici ordinati secondo l’ordine alfabetico/numerico

A 65B 66…….Y 89Z 90

a 97b 98…….y 121z 122

0 481 49…….8 569 57

cifre maiuscole minuscole

Page 110: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 110

Caratteri di controllo ASCIICaratteri di controllo ASCII

I caratteri di controllo (codice da 0 a 31) hanno funzioni specialiSi ottengono o con tasti specifici o con una sequenza CtrlCtrlcaratterecarattere

Ctrl Dec Hex Code Nota^@ 0 0 NULL carattere nullo^A 1 1 SOH partenza blocco…… … … …… …………………^G 7 7 BEL beep^H 8 8 BS backspace^I 9 9 HT tabulazione orizzontale^J 10 A LF line feed (cambio linea)^K 11 B VT tabulazione verticale^L 12 C FF form feed (alim. carta)^M 13 D CR carriage return (a capo)…… … … …… ……………………^Z 26 1A EOF fine file^[ 27 1 B ESC escape…… … … …… ………^_ 31 1F US separatore di unità

Page 111: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 111

Caratteri ASCII stampabiliCaratteri ASCII stampabili

Dec Hx Chr Dec Hx Chr Dec Hx Chr Dec Hx Chr Dec Hx Chr Dec Hx Chr

32 20 SPACE 48 30 0 64 40 @ 80 50 P 96 60 ` 112 70 p33 21 ! 49 31 1 65 41 A 81 51 Q 97 61 a 113 71 q34 22 ” 50 32 2 66 42 B 82 52 R 98 62 b 114 72 r 35 23 # 51 33 3 67 43 C 83 53 S 99 63 c 115 73 s36 24 $ 52 34 4 68 44 D 84 54 T 100 64 d 116 74 t37 25 % 53 35 5 69 45 E 85 55 U 101 65 e 117 75 u38 26 & 54 36 6 70 46 F 86 56 V 102 66 f 118 76 v39 27 ’ 55 37 7 71 47 G 87 57 W 103 67 g 119 77 w40 28 ( 56 38 8 72 48 H 88 58 X 104 68 h 120 78 x 41 29 ) 57 39 9 73 49 I 89 59 Y 105 69 i 121 79 y42 2A * 58 3A : 74 4A J 90 5A Z 106 6A j 122 7A z43 2B + 59 3B ; 75 4B K 91 5B [ 107 6B k 123 7B {44 2C , 60 3C < 76 4C L 92 5C \ 108 6C l 124 7C |45 2D - 61 3D = 77 4D M 93 5D ] 109 6D m 125 7D }46 2E . 62 3E > 78 4E N 94 5E ^ 110 6E n 126 7E ~47 2F / 63 3F ? 79 4F O 95 5F _ 111 6F o 127 7F DEL

NotaNota: 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)

Page 112: Fondamenti di Informatica I a.a. 2008-09 1 Fondamenti di Informatica I E-mail: monica@dii.unisi.it Monica Bianchini Dipartimento di Ingegneria dellInformazione.

Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 112

Tabella ASCII estesaTabella ASCII estesa

I codici oltre il 127 non sono compresi nello standard originario