Fondamenti ciuto et alt., McGraw-Hill di informatica€¦ · A.Gori - Fondamenti di informatica 6...

HTML 1

Fondamenti di informatica

A.Gori - Fondamenti di informatica 1

di informatica

Alessandro [email protected]

informottica.webnode.it

Bibliografia”Introduzione ai Sistemi Informatici” IV edizione, Sciuto et alt., McGraw-Hill


[email protected]

Argomenti

Rappresentazione e trattamento di


dati / informazioni

La codifica dei dati



Per formalizzare dati (es. numeri e caratteri alfabetici) si utilizzano successioni di simboli, scelti da un insieme finito detto ALFABETO.


Ad ogni alfabeto è associato un insieme di REGOLE di COMPOSIZIONE che definiscono le successioni “ben formate”

Es.:1234,45 OK 1,23,45 no OKOcchio a 123,456 (in Italia o in Inghilterra)Problemi di ambiguità semantica ………………


Nel caso di successioni tutte della solita lunghezza, il numero di simboli dell’alfabeto e la lunghezza della successione determinano il numero delle possibili successioni diverse ossia il numero di “oggetti


successioni diverse ossia il numero di “oggetti rappresentabili”

Con 10 simboli (ad es. le cifre decimali) quante diverse successioni di lunghezza k posso ottenere?

10k

HTML 2

Alfabeto Binario• Per rappresentare l’informazione all’interno di un calcolatore

(alfabeto interno) si usa l’alfabeto binario poiché le sue componenti possono trovarsi in due soli stati (0/1);

I motivi per i quali i calcolatori sono stati costruiti con tali• I motivi per i quali i calcolatori sono stati costruiti con tali componenti sono i seguenti:

1. Alta tolleranza dei circuiti al rumore: garanzia di un alto grado di tolleranza agli errori;

2. Circuiti più semplici, tali da poter essere costruiti a basso costo.

Sistema Binario

Motivazioni

Nei sistemi di elaborazione si adottail SISTEMA BINARIO


“Bistabilità” dei dispositivi usati nei computer:Es. presenza o assenza di tensione elettrica in un dispositivoAlfabeto Binario (due soli simboli: 0 e 1)

BIT (binary digit) unità elementare di informazione

Bit, Byte, Word

• Bit = Binary digit (cifra binaria (1/0))

• Byte = 8 bit (raggruppamento più comune nelle memorie e nei dispositivi I/O)memorie e nei dispositivi I/O)

• Parola (Word) = raggruppamento più grande del byte si misura in n° di byte

Utilizzando un alfabeto costituito da 2 simboli (0,1) quante successioni diverse ossia quante rappresentazioni diverse si possono ottenere di lunghezza k?

Sistema Binario

Domanda


Si ottengono 2k diverse rappresentazioni

Esempio: se k=3 ?

Se k=3: 000 001 010 011 100 101 110 111 8 diverse combinazioni

Ad una successione di 8 bit si dà il nome di BYTE e di questo si considerano i multipli:

– Kilobyte Kb 2^10 = 1024– Megabyte Mb 2^20 = 1048576

Sistema Binario


Megabyte Mb 2 20 = 1048576– Gigabyte Gb 2^30 ordine di miliardi– Terabyte Tb 2^40 ordine di milioni di milioni

Sistema Binario


HTML 3

Sistema Binario


Sistema Binario


Sistema Binario

?

DOMANDA


Sistema Binario

?

DOMANDA


RISPOSTA

Sistema Binario

?

DOMANDA

Quanti bit mi occorrono per codificare i giorni della settimana


RISPOSTA

Occorrono 3 bit !!!

Sistema Binario


HTML 4

Sistema Binario


Sistema Binario


Sistema Binario


Sistema Binario


Quanti simboli binari occorrono per codificarli?

Sistema Binario


Codifica ASCII

ASCII = American Standard Code for Information Interchange

A.Gori - Fondamenti di informatica 2416 bit

HTML 5

Codifica di caratteri e testo

La codifica dei caratteri attualmente utilizzata e` detta ASCII ; utilizza 8 bit per codificare un carattere.

I primi 128 numeri (0xxxxxxx) vengono


I primi 128 numeri (0xxxxxxx) vengono utilizzati per la codifica dei caratteri Standard, (lettere maiuscole, minuscole, numeri 0-9, segni di punteggiatura ecc.) mentre gli altri 128 numeri (1xxxxxxx) codificano la tabella con le estensioni per gli altri simboli.

Codifica ASCII

• Ogni carattere è rappresentato su 8 bit;

• L’ASCII originario era di 7 bit, forzato a 8 bit con il bit più significativo = 0;


più significativo 0;

• Quindi si utilizzano solo metà delle 256 codifiche, ovvero si rappresentano:27 = 128 caratteri:

01234567

0

Codici ASCII


Sistemi di NumerazioneParte Formale


Parte Formale

Numeri Interi


Esempi Numeri Interi

Posizionale


Non Posizionale

HTML 6

SistemiSistemi didiNumerazioneNumerazione PosizionaliPosizionali (1)(1)

• Criterio per la rappresentazione di un insieme infinito di numeri mediante un insieme limitato di simboli.Un sistema di n mera ione posi ionale è costit ito


• Un sistema di numerazione posizionale è costituito da:

1) Una base b;2) Un insieme ordinato di cifre;3) Un codice di interpretazione (interpretazione posizionale);4) Un insieme di algoritmi per le 4 operazioni aritmetiche

fondamentali.

SistemiSistemi didiNumerazioneNumerazione in Base “b” (1)in Base “b” (1)

• Il codice di interpretazione specifica che ad ogni posizione è associato un peso;

• Ogni cifra associata ad una posizione indica il


numero delle volte che deve essere considerato il peso corrispondente a quella posizione;

• Sistema di numerazione posizionale in base “b”:sistema di numerazione posizionale in cui i pesi sono espressi come potenze della base “b”.

SistemiSistemi didiNumerazioneNumerazione in Base “b” (2)in Base “b” (2)

• Numero in base “b”:Numero rappresentato utilizzando il sistema di numerazione in base “b” ed una sequenza di cifre


del tipo: (cn-1cn-2 ··· c0 .c-1 ··· c-m)b ;

Il simbolo “.” (punto di separazione) separa la parte intera

da quella frazionaria:• c0 ha peso b0

c1 ′′ b1

c-1 ′′ b-1.

Forma Forma PolinomiaPolinomia

• Vale la relazione (conseguenza della definizione di numero in base “b”):

(c c ··· c c ··· c ) =


(cn-1cn-2 ··· c0 .c-1 ··· c-m)b =

cn-1 bn-1+cn-2bn-2 +··· +c0b0 .+ c-1 b-1 ··· c-m b-m

• Tale somma di prodotti è dettaForma Polinomia

Sistema di Numerazionein Base 10

• Base 10 (b = 10):

Cif {0 1 9}


– Cifre ci = {0,1, …, 9}

– Esempio:

(127.3)10 = 1·102 + 2·101 + 7·100 .+ 3 ·10-1

Sistema di Numerazionein Base 2

• Base 2 (b = 2):– Cifre ci = {0,1}– Esempio:


(101.01)2 = 1·22 + 0·21 + 1·20 .+ 0·2-1 + 1·2-2 = (5.25)10

Conseguenza:– La forma polinomia rappresenta l’algoritmo di conversione

binario – decimale;• In generale:

Forma Polinomia

sistema in base b ⇒ sistema decimale

HTML 7

Algoritmi di ConversioneDecimale - Binario

• Si distinguono due casi:– Numeri interi (Algoritmo delle Divisioni Successive);– Numeri frazionari (Algoritmo delle Moltiplicazioni Successive);


• In caso di numeri reali con parte intera e frazionaria i due algoritmi vengono applicati separatamente e combinati i risultati.

Metodo delleDivisioni Successive (1)

• (N)10 ∈ N• N = cn-1 2n-1+cn-22n-2 +··· +c020

• Dividendo per 2 entrambi i membri:Essendo N = 2Q+R ⇒ N/2 = Q+R/2 ( con R=0 o 1)


Essendo N = 2Q+R ⇒ N/2 = Q+R/2 ( con R=0 o 1)• Si ha:

N/2 = Q + R/2 = cn-1 2n-2+cn-22n-3 +··· +c120 + c02-1

Q R/2

• Quindi R = c0ovvero c0 è il resto della divisione di (N)10 per 2.


• Q = cn-1 2n-2+cn-22n-3 +··· +c120

• Dividendo per 2 entrambi i membri:Essendo Q = 2Q’+R ⇒ Q/2 = Q’+R’/2 (R’=0 o 1)

Si h


• Si ha:Q/2 = Q’ + R’/2 = cn-1 2n-3+cn-22n-4 +··· +c220 + c12-1

Q’ R’/2

• Quindi R’ = c1ovvero c1 è il resto della divisione di (Q)10 per 2.


• I coefficienti forma polinomia in base 2 di (N)10 intero sono rappresentati dai resti delle divisioni successive di (N)10 , e dei quozienti


ottenuti, per 2

• L’algoritmo termina quando si ottiene un quoziente uguale a zero

Metodo delleDivisioni Successive (es.)

• (N)10 = 13• N/2 = 13/2 ⇒ Q = 6 R=1 ⇒ c0 = 1• Q/2 = 6/2 ⇒ Q = 3 R=0 ⇒ c1 = 0• Q/2 = 3/2 ⇒ Q = 1 R=1 ⇒ c = 1


• Q/2 = 3/2 ⇒ Q = 1 R=1 ⇒ c2 = 1• Q/2 = 1/2 ⇒ Q = 0 R=1 ⇒ c3 = 1

(N)10 = 13 ⇒ (N)2 = (1101)2

(N)2 = (1101)2 ⇒ (N)10 = (1·23 + 1·22 + 0·21 + 1·20) = (13)10

Esempio – Base 2

Convertire in binario con l’algoritmo delleDi i i i i il 98


(98)10 = (1100010)2

Divisioni successive il numero 98

HTML 8

Esempio – Base 2


(98)10 = (1100010)2

Esempio – Base 2

Scrivere l’algoritmo formale che risolve la conversione di un numero naturale


(98)10 = (1100010)2

la conversione di un numero naturaleda base 10 a base 2

Esempio Inizio

Leggi A

Attuale AST “”

A<0 ?

Quoz [ Attuale/2 ]Resto Attuale – Quoz*2

ST “RESTO“ ST

Vero

Falso

Attuale=0 ?

“Il risultato è=“ ST

Fine

Falso Vero

ST “RESTO“ + STAttuale Quoz

ERRORE

Esempio – Base 2

Scrivere l’algoritmo formale che risolve la conversione di un numero da base 10


(98)10 = (1100010)2

la conversione di un numero da base 10 ad una base naturale qualsiasi diversa da zero

Esempio – Base 8

3


(799)10 = (1437)8

Esempio – Base 16


(1479)10 = (5C7)16

HTML 9

Binario - Esadecimale


Binario - Esadecimale


Numeri interi negativiIl modo più semplice per rappresentare i numeri interi con segno è dato dalla rappresentazione in modulo e segno

Se si utilizzano k bit, il primo si usa per indicare il segno del numero (1=negativo


indicare il segno del numero (1=negativo, 0=positivo); i restanti k-1 servono per rappresentare il modulo del numero.

Qual è l’intervallo di numeri rappresentabili?

[-2k-1 +1 , 2k-1 –1]

Sistema Binario


Domande: •Con 4 bit quali numeri si possono rappresentare?•E con 8?•Come si rappresenta il numero 010 ?

Sistema Binario


Sistema Binario


HTML 10

Numeri interi negativiPer evitare la doppia codifica dello 0, si preferisce utilizzare la cosiddetta rappresentazione in complemento a base(in questo caso, in complemento a 2)


Se si utilizzano successioni di n bit, per rappresentare il numero x, si utilizza il valore binario corrispondente a 2n+x

Sistema Binario


Domande:• Qual è l’intervallo di numeri rappresentabili con k bit?• Come si rappresenta lo 010 ?

Sia k=4:

Sistema Binario


Sistema Binario


Sistema Binario


Sistema Binario


HTML 11

Operazioni aritmetiche


Operazioni aritmetiche


Mediante rappresentazioni posizionali si possono trattare anche i numeri reali.

Solo alcuni numeri reali possono essere

Numeri Reali


Solo alcuni numeri reali possono essere rappresentati con un numero finito di cifre della parte frazionaria: tali numeri sono un sottoinsieme dei numeri razionali.

Siamo abituati a considerare che tutti i razionali siano rappresentabili in modo finito, utilizzando l'artificio della definizione del periodo: questo artificio

Numeri Reali


definizione del periodo: questo artificio richiede una particolare simbologia e non rientra nella notazione posizionale "pura".

Dovendo considerare solo rappresentazioni finite, con un numero di cifre limitato a priori, saremo in

Numeri Reali


p ,grado di rappresentare solo un sottoinsieme dei razionali; in pratica, saremo in grado di rappresentare solo approssimazioni dei numeri reali.

Numeri Reali


HTML 12

Si usa una approssimazione del numero su p+f cifre (p per la parte intera ed f per quella frazionaria).

Es

Virgola fissa


Es. Sia p=5 e f=3 e si consideri il numero binario 00101011

Qual è il valore decimale corrispondente?

R=1*22+1+1*2-2+1*2-3 = 4+1+1/4+1/8=5+3/8=5.375

Virgola fissa

Viceversa si può ottenere la stringa binaria che rappresenta il numero 5.375 con l'algoritmo seguente che fornisce le cifre della rappresentazione


fornisce le cifre della rappresentazione a partire dalla più significativa.

Si tiene conto che 4< 5.375 <8 e quindi servono almeno 3 cifre per la parte intera, mentre poniamo f=3

p=3f=3

Virgola fissa


Numeri Reali


Numeri Reali


Virgola mobileLa codifica binaria piu` diffusa dei numeri razionali e` denominata IEEE754 e prevede l’utilizzo della notazione scientifica normalizzata in base 2 su 32

Numeri Reali


bit (singola precisione) o 64 bit (doppia precisione) cosi` suddivisi:

HTML 13

Tipi di dati primitivi numerici

La differenza tra i diversi tipi per dati numerici consiste nello spazio di memoria che viene utilizzata per la rappresentazione

E quindi nell’intervallo di valori che possono rappresentare

Memoria


Tipo

byteshortintlong

floatdouble

in byte

1248

48

Valore min

-128-32,768-2,147,483,648< -9 x 1018

+/- 3.4 x 1038 con 7 cifre significative+/- 1.7 x 10308 con 15 cifre significative

Valore max

12732,7672,147,483,647> 9 x 1018

Aritmetica degli Elaboratori

• Proprietà:1. Rappresentazione binaria dei numeri;2. Rango finito;3. Alcune operazioni sono espresse in funzione di altre

più semplici;


4. Precisione finita (precisione di macchina):la rappresentazione in precisione finita determina un errore di troncamento;

5. Operazioni per mezzo di altre:– Sottrazione per mezzo di una complementazione e una

addizione– Moltiplicazione con successione di somme e shift.

Errore di Troncamento

• Teorema

ato;rappresent valore - vero valore assoluto Errore =

verovaloreatorappresent valore - vero valore relativo Errore =


Teorema– Hp) Rappresentazione binaria di un numero frazionario X

alla p-esima cifra dopo il punto;– Ts) Errore assoluto di troncamento ≤ 2-p

Dim:=+−+= ∑ ∑∑ ∑

=

+

=

−−

=

+∞

=

−− )( assoluto Err.

atorappresent valorevero valore444 3444 21444 3444 21

m

i

p

i

ii

ii

m

i i

ii

ii cccc

0 10 1

2222

ppp

i

i

i

i

pi pi

i

c

ii

i

c −−

+−

−

+

=

−+∞

=

−+∞

+=

+∞

+=

−

=

−− =

−−

−−

=−=≤= ∑∑∑ ∑ 221

2121

122221

1

1001 1

1

)(

se

Rappresentazione dei numeri

• La precisione e` la distanza tra 2 numeri adiacenti rappresentabili.

• La precisione e` data da N elevato alla -M dove N e` la base del numero ed M e` il


dove N e la base del numero ed M e il numero di cifre utilizzate dopo la virgola.

• Se ad esempio in base 10 rappresentiamo i numeri con 1 cifra dopo la virgola, la precisione e` 10 alla -1 ovvero 0,1

Rappresentazione binaria dei numeri reali

I NUMERI RAZIONALI E REALI

I numeri reali non possono essere rappresentati con una sequenza di bit


rappresentati con una sequenza di bit poiche` il numero di possibili codifiche e` finito; dobbiamo quindi approssimare i numeri reali con numeri razionali, cioe` con un intervallo di variazione finito e con una precisione finita.

I numeri razionali possono essere rappresentati componendo la parte intera e la parte frazionaria (come siamo abituati a fare con i numeri decimali).L 2 i d ll i l

Rappresentazione binaria dei numeri reali


Le 2 parti sono separate dalla virgola (esempio decimale 234,567 ).La sequenza di bit e` suddivisa in 2 campi, una per la parte intera e uno per la parte frazionaria.

Parte intera Parte decimale

HTML 14


Esistono 2 modi per rappresentare i numeri razionali: a virgola fissa e a virgola mobile.

Virgola fissa


gLa notazione a virgola fissa prevede una separazione (non modificabile) della sequenza di bit in 2 parti: una per la parte intera e una per la parte frazionaria.

Rappresentazione dei numeriVirgola mobile• In questa modalità il numero e` espresso in

notazione scientifica n = +/- C,M x BEXP

• Dove C e` la parte intera (numero naturale


p (diverso da 0), M e` la mantissa (numero naturale), B e` la base ed EXP e` l’esponente (numero relativo, maggiore o minore di zero).

• Ad esempio 234,567 = 234,567 x 10 elevato a 0 = 2345,67 x 10 elevato a -1 = ecc .


Virgola mobile

Un numero espresso in forma esponenziale si dice Normalizzato se a sinistra della virgola vi e` una sola cifra.


La notazione scientifica normalizzata dell’esempio precedente e`:

2,34567 x 102

Rappresentazione dei numeriVirgola mobile

La codifica binaria piu` diffusa dei numeri razionali e` denominata IEEE754 e prevede l’utilizzo della notazione scientifica normalizzata in base 2 su 32


bit (singola precisione) o 64 bit (doppia precisione) cosi` suddivisi:

Rappresentazione dei numeriVirgola mobile

Il numero reale n si rappresenta cosi` :

n = -/+( 1 o 0) e=ESPONENTE DELLA BASE 2 1, m

Esempio : 0 24 687 (numero positivo dalla base e elevato alla 24 moltiplicato per 1,687)

Nella singola precisione e e` composto da 8 bit e quindi


Nella singola precisione e e composto da 8 bit, e quindi l’esponente massimo esprimibile è 256 ( 2 elevato alla 8) suddiviso tra numeri negativi e positivi (può` variare tra +128 e –127). Il numero e` rappresentato in forma normalizzata, quindi prima della virgola abbiamo sempre un 1.

La mantissa m e` la sequenza di bit dopo la virgola.

S è il bit di segno: se s vale 1 allora il segno è negativo, altrimenti è positivo.

Esempio di numero in virgola mobile

(singola precisione)1 10 0101Traduzione : il primo 1 ci dice che il numero è negativo;10 ci dice che l’esponente vale 10 cioè 2 in binario


10 ci dice che l esponente vale 10 cioè 2 in binario0101 è il numero dopo la virgola preceduta sempre da un 1:quindi - 1,0101x 2 = - 101,01 = -5,25 Infatti si ha:

-(1+ 2 + 2 ) x 2 = - (1 + ¼ + 1/16) x 4 = - 5,25

2

-4-2 2

Fondamenti ciuto et alt., McGraw-Hill di informatica€¦ · A.Gori - Fondamenti di informatica 6...

Documents

Transcript of Fondamenti ciuto et alt., McGraw-Hill di informatica€¦ · A.Gori - Fondamenti di informatica 6...