Sistemi di numerazione - ludovico.net · • Nel sistema binario si usano le cifre 0 e 1. La base 2...

Sistemi di numerazione

Presentazione 4.1

Informatica Generale (Prof. Luca A. Ludovico)

Introduzione

• Un sistema di numerazione è un sistema utilizzato per esprimere i numeri e possibilmente alcune operazioni che si possono effettuare su di essi.

• Storicamente i sistemi di numerazione si sono riferiti alla successione dei cosiddetti numeri naturali, ossia:

– numeri interi positivi (1, 2, 3, 4, ...); simbolo N– numeri interi non negativi (0, 1, 2, 3, 4, ...); simbolo N0

• I più antichi sistemi di numerazione hanno base 10, con riferimento all'atto di contare sulle dita delle mani.

Informatica Generale (Prof. Luca A. Ludovico)Presentazione 4.1

Sistema di numerazione additivo

• Idea primordiale: ad ogni simbolo è associato un valore e il numero rappresentato è dato dalla somma dei valori dei simboli.

• Ad esempio, ciascun dito o sassolino rappresenta un’unità. Il totale è dato dalla somma delle singole unità.

• Caso reale: il sistema di numerazione romano originario (I, II, III, IIII, V, VI, VII, VIII, VIIII, X, …), che nel medioevo diventa anche sottrattivo (I, II, III, IV, V, VI, VII, VIII, IX, X, …).


Sistema di numerazione posizionale

• Un numero è rappresentato da una sequenza di cifre.

• Es.: 333 è un numero, il singolo 3 è una cifra.

• In un sistema posizionale, il valore di ogni cifra dipende dalla sua posizione all'interno della sequenza. La cifra all'estrema destra ha il valore minore (cifra meno significativa), quella all'estrema sinistra il valore maggiore (cifra più significativa).


Definizione di “base”

• E' possibile scegliere il numero di cifre (o simboli) differenti utilizzabili in una notazione posizionale. Tale numero prende il nome di base.

• Nel sistema decimale si usano le cifre 0,1,2,3,4,5,6,7,8,9.

• Nel sistema binario si usano le cifre 0 e 1. La base 2 è la più piccola possibile per un sistema di numerazione. Il valore posizionale è legato alle potenze di 2.

• Nel sistema ottale si usano 0,1,2,3,4,5,6,7. Il valore posizionale è legato alle potenze di 8.

• Nel sistema esadecimale si usano 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F. Il valore posizionale è legato alle potenze di 16.


Confronto tra base 2, 10 e 16

Base 2 Base 10 Base 16

0000 00 0

0001 01 1

0010 02 2

0011 03 3

0100 04 4

0101 05 5

0110 06 6

0111 07 7

1000 08 8

1001 09 9

1010 10 A

1011 11 B

1100 12 C

1101 13 D

1110 14 E

1111 15 F

… … …


Come si rappresentano numeri >= base

• Esempio in base 16

– 0 1 2 3 4 5 6 7 8 9 A B C D E F sono sufficienti per i numeri 0..15; ma poi?

– 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F è la rappresentazione su due cifre dei numeri sopra

– La cifra più significativa ora diventa il secondo simbolo dell’alfabeto: 10 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E 1F

– Esaurita la sequenza, la cifra più significativa diventa il terzo simbolo dell’alfabeto: 20 21 ...

– Quando si esauriscono i simboli dell’alfabeto, si aggiunge un’ulteriore cifra.


Alcune osservazioni sulle basi

• La rappresentazione dei numeri in una data base piuttosto che in un’altra ne cambia la scrittura (ad es. 1510 = 11112 = F16), ma non il significato semantico. Pertanto anche le operazioni matematiche danno lo stesso risultato e godono delle stesse proprietà in ogni base.

• Si osservi che in una generica base n, i simboli utilizzati ricadono convenzionalmente nell’intervallo [0..n-1].– Ad esempio, i simboli usati come cifre in base 10 sono [0..9]– Ne consegue che ad es. il numero 1041 non possa esistere in

alcuna base n≤4.


Alcune osservazioni sulle basi

• Data una base n e un numero composto da m cifre, quante differenti combinazioni si possono ottenere?

nm

• Questo perché ogni cifra rappresenta una casella che è possibile valorizzare con un simbolo scelto tra gli nsimboli della base n. Con 2 caselle, si hanno n x ncombinazioni di simboli, e via dicendo…

– Esempio: con 2 cifre in base 10, si ottengono 102 diverse combinazioni: [00..99]

– Esempio: con 4 cifre in base 2, si ottengono 24 diverse combinazioni: [0000..1111]


Conversione da base n a base 10

• Per una numerazione in base n, con n numero naturale > 1, la base supporta n cifre distinte.

Sia A un numero rappresentato come una sequenza di k+1 cifre ak…a0.Esso si può esprimere in base 10 secondo la formula

ove b è la rappresentazione in base 10 di n.

• Ad esempio, se n = 2 il numeroa = 1012 = 1 • 22 + 0 • 21 + 1 • 20 = 4 + 1 = 510

∑=

•k

j

jj ba

0][


Conversione da base 10 a base n (num. interi)

• Metodo delle divisioni successive: consiste nel prendere il numero da convertire e dividerlo per la base considerata; prenderne il quoziente e dividerlo ancora per la base, e così via, fino a che non si ottiene come risultato un quoziente zero.

• In questa sequenza di divisioni occorre ricordare i resti che man mano si ottengono, perché sono questi che, letti in senso inverso dall'ultimo al primo, costituiscono proprio la conversione cercata.


Algoritmo

Sia a il numero da convertire.

1. Si divide a per la nuova base n; sia q il quoziente ed ril resto.

2. Si converte r nella corrispondente cifra della nuova base n.

3. Si aggiunge la cifra così ottenuta a sinistra delle cifre ottenute in precedenza.

4. Se q = 0, fine; altrimenti poni a = q e torna al passo 1.


Esempio: da base 10 a base 2

a = 3510 2

17 1

8 1

4 0

2 0

1 0

0 1

a = 3510 = 1000112

a = 3210 2

16 0

8 0

4 0

2 0

1 0

0 1

a = 3210 = 1000002


Esempio: da base 10 a base 5 e viceversa

a = 3210 5

6 2

1 1

0 1

a = 3210 = 1125

a = 1125 = 1 • 52 + 1 • 51 + 2 • 50 = 25 + 5 + 2 = 3210

Osservazione: questo tipo di verifica può sempre essere fatto per controllare la correttezza del risultato


Come fare esercizio di conversione tra basi

• Tramite i metodi illustrati, è possibile convertire i numeri da base 10 a una qualsiasi base n (metodo delle divisioni successive) e da una qualsiasi base n a base 10 (somma di prodotti).

• Ad esempio, la Calcolatrice di Windows in modalità scientifica (Visualizza > Scientifica) presenta una scelta di rappresentazione dei numeri che contempla le basi Bin (2), Oct (8), Dec (10) e Hex (16).


Conversione da base n a base 10 (frazionari)

• Per i numeri frazionari si usa lo stesso principio sopra illustrato, ma dopo la virgola le potenze di n per cui vanno moltiplicate le cifre diventano negative.

• Esempio a = 101,112 =

= 1 • 22 + 1 • 20 + 1 • 2-1 + 1 • 2-2 == 1 • 4 + 1 • 1 + 1 • 1/2 + 1 • 1/4 == 5,7510


Conversione da base 10 a base n (frazionari)

• Per i numeri frazionari si usa per la parte a sinistra della virgola (parte intera) il metodo delle divisioni successive, e per la parte a destra della virgola (parte frazionaria) il metodo delle moltiplicazioni successive.

• Si moltiplica per n la parte frazionaria, ottenendo un nuovo numero con parte intera e parte frazionaria. Si procede fino a quando la parte frazionaria è diventata nulla o si sia trovato un numero sufficiente di cifre.

• La lettura delle cifre-risultato (ossia la colonna delle parti intere) procede dall’alto verso il basso.


Esempio: da base 10 a base 2 (num. frazionari)

a = 0,62510 2

1 0,25

0 0,5

1 0

a = 0,62510 = 0,1012

I passaggio0,625 • 2 = 1,25 spezzato in 1 + 0,25

II passaggio0,25 • 2 = 0,5 spezzato in 0 + 0,5

III passaggio0,5 • 2 = 1 spezzato in 1 + 0

L’algoritmo si ferma in quanto la colonna di destra contiene uno 0.

Si sarebbe potuto continuare, però…


Esempio: da base 10 a base 2 (num. frazionari)

a = 0,310 2

0 0,6

1 0,2

0 0,4

0 0,8

1 0,6

1 0,2

0 0,4

0 0,8

… …

a = 0,310 = 0,01001100…2

I passaggio0,3 • 2 = 0,6 spezzato in 0 + 0,6

II passaggio0,6 • 2 = 1,2 spezzato in 1 + 0,2

III passaggio0,2 • 2 = 0,4 spezzato in 0 + 0,4

…

L’algoritmo si ferma in quanto la colonna di destra contiene uno 0. Ma in questo caso non avverrà mai. Allora quando ci si ferma?


Osservazioni sull’approssimazione dei risultati

• Alcuni numeri frazionari, la cui rappresentazione in base 10 è banale (ad es. 0,3 o 0,7) non hanno una rappresentazione finita in base 2.

• Motivo: la parte frazionaria in generale non può essere scomposta in somme di potenze (negative) di 2.

• Ogni cifra diversa da 0 che riusciamo a calcolare dopo la virgola aggiunge precisione e quindi approssima meglio il risultato. Però costa spazio!


Osservazioni sull’approssimazione dei risultati

• Esempio: calcoliamo differenti approssimazioni di 0,3 nella conversione da base 10 a base 2.

1 cifra: 0,310 ≈ 0,02 = 010 Errore: 0,3102 cifre: 0,310 ≈ 0,012 = 0,2510 Errore: 0,05103 cifre: 0,310 ≈ 0,0102 = 0,2510 Errore: 0,05104 cifre: 0,310 ≈ 0,01002 = 0,2510 Errore: 0,05105 cifre: 0,310 ≈ 0,010012 = 0,2812510 Errore: 0,01875106 cifre: 0,310 ≈ 0,0100112 = 0,29687510 Errore: 0,00312510

… …


Conversione tra basi generiche

• E’ sempre possibile convertire un numero da una base m a una base n con m ed n generici.

• Un metodo consiste nell’utilizzare la base 10 come passaggio intermedio. – Il numero x viene prima convertito da base m a base 10, per

poi essere nuovamente convertito da base 10 a base n.

• In alcuni casi si può procedere a una conversione diretta.


Conversione diretta tra basi

• Se le basi di origine m e di destinazione n sono l’una potenza dell’altra, è applicabile un metodo di conversione diretta. Questa può essere svolta per sostituzione di gruppi di cifre invece che con algoritmi di divisione.

• Se n = mk, allora k cifre del numero nella base originaria mvengono sostituite con singole cifre nella nuova base n. – E’ il caso di m = 2 ed n = 16, ad esempio.

• Viceversa, se m = nk, allora ogni singola cifra del numero nella base originaria m viene espansa in k cifre nella nuova base n. – E’ il caso di m = 9 ed n = 3, ad esempio.


Sistemi di numerazione - ludovico.net · • Nel sistema binario si usano le cifre 0 e 1. La base 2...

Documents

Transcript of Sistemi di numerazione - ludovico.net · • Nel sistema binario si usano le cifre 0 e 1. La base 2...