SISTEME DE NUMERATIE

II. SISTEME DE NUMERAŢIE

II.1. Generalitati

Din cele mai vechi timpuri, s-a pus problema gasirii unor procedee de scriere a numerelor naturale care sa permita o scriere rapida a ordinului lor de marime si elaborarea unor reguli eficiente de efectuare a operatiilor cu acestea. Adoptarea sistemului de numeratie zecimal s-a încheiat abia în secolele 16-17 si reprezinta o etapa importanta în dezvoltarea matematicii.

Un sistem de numeratie este privit ca "un ansamblu de reguli prin care valorile numerice pot fi scrise prin intermediul simbolurilor, denumite numere".

Se numeste sistem de numeratie totalitatea regulilor de reprezentare a numerelor folosind un anumit set de simboluri distincte, numit alfabet; simbolurile sunt numite cifre.

Prin definitie, totalitatea simbolurilor grafice utilizate pentru scrierea numerelor reprezinta alfabetul sistemului de numeratie.

De exemplu, sistemul de numeratie în baza 2 are alfabetul ; sistemul de numeratie în baza 16 are alfabetul .

În decursul timpului, în diferite zone ale globului au fost folosite sisteme de numeratie cu o varietate destul de mare de baze de numeratie: 3, 4, 5, 6, 10, 12, 20, 60. Dar cea mai des folosita a fost baza 10, probabil ca urmare a socotitului pe degete.

Semnele folosite pentru notarea cifrelor sunt destul de variate. Modul lor de grupare pentru reprezentarea unui numar califica un sistem de numeratie ca nepozitional (aditiv, multiplicativ) sau pozitional.

II.2. Sisteme de numeratie nepozitionale

În aceste sisteme exista semne distincte (cifre) pentru fiecare grup de obiecte folosit în procesul numararii. Sistemul de numeratie egiptean este un astfel de sistem. Valoarea unui numar se obtine prin adunarea cifrelor dupa anumite reguli. De exemplu:

Sistemele aditive

Sistemul de numeratie roman este un sistem aditiv-substractiv. Valoarea unui numar se obtine prin adunarea sau scaderea cifrelor dupa anumite reguli. De exemplu, XI = 11, MMCIII = 2103; IV = 4, IX = 9.

Sistemele multiplicative

Un sistem multiplicativ este acela în care pentru aflarea valorii unui numar este necesar sa se înmulteasca anumite perechi de simboluri într-o maniera asemanatoare sistemului aditiv (sistemul de numeratie chinez).

II.3. Sistemele de numeratie pozitionale

În sistemele de numeratie pozitionale, un simbol din alcatuirea unui numar (cifra) are valoare intrinseca dar si o valoare prin pozitia pe care o ocupa în numar. Aceasta implica existenta unui simbol cu valoare intrinseca nula (zero). În unele sisteme pozitionale în care regulile o permit, este posibil sa se renunte la acest simbol. Regulile folosite în aceste sisteme sunt mai complexe decât în cele aditive.

Cel mai raspândit sistem de numeratie este cel cu baza 10, numit sistemul zecimal. Sistemul de numeratie cu baza 2 se numeste binar. Este limbajul circuitelor electronice. Sistemul de numeratie cu baza 16 este numit hexazecimal si este folosit în programarea calculatoarelor. Are avantajul ca este relativ apropiat de sistemul zecimal si ca numerele scrise în baza 16 pot fi foarte usor convertite în baza de numeratie 2.

Iata cum se scrie un numar în sistemul zecimal pozitional:

40.323 = 4·10⁴ + 0·10³ + 3·10² + 2·10¹ + 3·10⁰ (1)

Trebuie remarcat ca cifra 3 apare de doua ori în scrierea numarului. Când se afla pe ultimul loc, reprezinta trei obiecte; când se afla pe antepenultimul loc, reprezinta trei sute de obiecte.

Sistemele de numeratie pozitionale folosesc acelasi sistem de reguli de reprezentare a numerelor; ele difera doar prin alfabetul pe care îl utilizeaza si, implicit, prin baza.

Baza unui sistem de numeratie pozitional este data de numarul de elemente care formeaza alfabetul sistemului de numeratie.

Un sistem de numeratie pozitional în baza "r" are urmatoarele caracteristici:

·  939v216j   939v216j   939v216j   939v216j utilizeaza un alfabet cu r simboluri diferite între ele numite cifre, cu valori consecutive; aceeasi cifra asezata în pozitii diferite ale unei secvente, poate avea valori diferite;

·  939v216j   939v216j   939v216j   939v216j cifra 0 are cea mai mica valoare când este asezata singura;

·  939v216j   939v216j   939v216j   939v216j cifra cu valoarea cea mai mare când este asezata singura, adica valoarea cu o unitate mai mica decât baza sistemului, deci în cazul de fata r - 1;

·  939v216j   939v216j   939v216j   939v216j în functie de pozitia lor în numar, cifrele se înmultesc cu puteri crescatoare ale bazei r obtinându-se dezvoltarea numarului dupa puterile bazei:

N_r = a_na_n-1.a₂a₁a₀ = a_n .rⁿ +a_n-1 .r^n-1 + .+ a₂ .r² + a₁ .r¹ +a₀ . r⁰ (2)

  939v216j

II.3.1. Sistemul de numeratie zecimal

Alfabetul sistemului zecimal, cel mai cunoscut si utilizat în prezent este format din zece cifre : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

Aceste cifre sunt prin definitie numere consecutive, astfel 7 = 6 + 1.

Un numar în baza 10 conform relatiei (1) poate fi scris ca o suma de puteri ale lui 10:

1998 = 1 . 10³ + 9 . 10² + 9 . 10¹ + 8 (3)

Propozitia 1: fie a si b doua numere naturale scrise în baza u: a = a_m a_m-1 ... a₁ a₀ si b= b_nb_n-1 ... b₁b₀. Atunci a < b daca si numai daca m < n sau m = n si a_t < b_t, unde t este cel mai mare indice i pentru care a_i č b_i.

Demonstratie: daca m < n, atunci rezulta ca a < u^m+1 uⁿ b, deci a < b. Presupunem ca m = n si a_t < b_t, unde t = max. Avem a_t  939v216j +  939v216j 1  939v216j   939v216j b, deci a_t· u^t + u^t b_tu^t. Rezulta ca:

(4)

deci a < b.

Reciproc, daca a < b, atunci din prima parte a demonstratiei deducem ca m < n sau  939v216j m= n si a_t < b_t, unde t = max.

Exemple:

Daca a = 122311₍₁₀₎, b = 92197₍₁₀₎, deoarece m > n, a > b.

Daca a = 1011000₍₂₎, b = 1010111₍₂₎, deoarece m = n si pentru t = 3, a_t > b_t, rezulta ca a > b.

  939v216j

Propozitia 2: numarul maxim care poate fi reprezentat în baza u cu m cifre este u^m- 1.

Demonstratie: fie a = c_m-1c_m-2 ... c₀ cel mai mare numar cu m cifre, reprezentat în baza u.

Atunci:

c_i = u - 1 pentru i = 0, ..., m - 1;

a + 1 = 10 ... 0_(u) , unde numarul are m + 1 cifre; (5)

a + 1 = 1· u^m,

Conform definitiei a = u^m - 1.

Exemplu: numarul maxim care se poate reprezenta cu 4 cifre, în baza 10, este 9999, adica 10⁴ - 1.

II.3.2. Sistemul de numeratie binar

Sistemul de numeratie binar, cel mai simplu posibil inventat acum 500 de ani în China si cel mai utilizat în reprezentarea codificata a numerelor în calculatoare, are urmatoarele caracteristici:

·  939v216j   939v216j   939v216j   939v216j baza de numeratie a sistemului este 2 si contine numai doua simboluri, cifrele: 0 si 1;

·  939v216j   939v216j   939v216j   939v216j cifra cu valoarea cea mai mare este 1.

Un numar scris în baza 2, poate fi dezvoltat dupa puterile bazei astfel:

N₂ = a_na_n-1.a₂a₁a₀ = a_n .2ⁿ +a_n-1 .2^n-1 + .+ a₂ .2² + a₁ .2¹ +a₀ . 2⁰ (6)

În continuare sunt prezentate câteva numere scrise în baza 2:

_, 101010₂ , 11100010_.2 .

Ultimul numar poate fi dezvoltat dupa puterile lui 2 astfel:

11100010₂ = 1 . 2⁷ + 1 . 2⁶ + 1 . 2⁵ + 1 . 2¹ (7)

II.3.3. Sistemul de numeratie octal

Utilizat în reprezentarea codificata a numerelor în calculatoare este si sistemul de numeratie octal, întrucât îl include pe cel binar.

Are urmatoarele caracteristici:

·  939v216j   939v216j   939v216j   939v216j baza de numeratie a sistemului este 8 si contine opt cifre: de la 0 la 7;

·  939v216j   939v216j   939v216j   939v216j cifra cu valoarea ce mai mare este 7.

Un numar scris în baza 8, poate fi dezvoltat dupa puterile bazei astfel:

N₈ = a_na_n-1.a₂a₁a₀ = a_n .8ⁿ +a_n-1 .8^n-1 + .+ a₂ .8² + a₁ .8¹ +a₀ . 8⁰ (8)

  939v216j

În continuare sunt prezentate câteva numere scrise în baza 8:

1067_8, 705043₈ , 65703021₈

Ultimul numar poate fi dezvoltat dupa puterile lui 8 astfel:

65703021₈ = 6 . 8⁷ + 5 . 8⁶ + 7 . 8⁵ + 3 . 8³ + 2 . 8¹ + 1 (9)

  939v216j

II.3.4. Sistemul de numeratie hexazecimal

  939v216j

Utilizat cel mai mult în ultima vreme în reprezentarea codificata a numerelor în calculatoare este sistemul de numeratie hexazecimal, întrucât le include pe cele binar si octal.

Are urmatoarele caracteristici:

·  939v216j   939v216j   939v216j   939v216j baza de numeratie a sistemului este 16 si contine 16 cifre: de la 0 la 9 si în plus literele consecutive A, B , C, D, E si F;

·  939v216j   939v216j   939v216j   939v216j simbolul cu valoarea cea mai mare este F si are valoarea 15.

Un numar scris în baza 16, poate fi dezvoltat dupa puterile bazei astfel:

N₁₆ = a_na_n-1.a₂a₁a₀ = a_n .16ⁿ +a_n-1 .16^n-1 + .+ a₂ .16² + a₁ .16¹ +a₀ . 16⁰ (10)

În continuare sunt prezentate câteva numere scrise în baza 16:

1A6F_16, B05093₁₆ , 6CD03089₁₆

Ultimul numar poate fi dezvoltat dupa puterile lui 16 astfel:

6CD03089₁₆ = 6 . 16⁷ + C . 16⁶ + D . 16⁵ + 3 . 16³ + 8 . 16¹ + 9 (11)

Exista algoritmi de transformare a numerelor dintr-un sistem de numeratie în altul.

În tabelul 2.1 sunt prezentate conversiile câtorva numere în sistemele zecimal, binar, octal si hexazecimal.

  939v216j Tabelul 2.1. Reprezentarea numerelor în diferite sisteme de numeratie

II.4. Conversia dintr-o baza de numeratie oarecare în

baza 10

Se considera sistemul de numeratie cu baza u. Un numar rational pozitiv a reprezentat în baza u prin sirul a_{(u)  939v216j} =  939v216j a_n-1u^n-2 ... u₀, u_-1 ... u_-m are, prin definitie, valoarea în baza 10:

Exemple

Poate fi scris si sub forma:

11021434₍₅₎ = 5·(5·(5·(5·(5·(5·(5·1 +2) + 0) + 2) + 1) + 4) + 3) + 4 =

= 5·(5·(5·(5·(5·(5·7 + 0) + 2) + 1) + 4) + 3) + 4 =

= 5·(5·(5·(5·(5·35 + 2) + 1) + 4) + 3) + 4 =

= 5·(5·(5·(5·177 + 1) + 4) + 3) + 4 =

= 5·(5·(5·886 + 4) + 3) + 4 =

= 5·(5·4434 + 3) + 4 =

= 5·22173 + 4 =

= 110869

De aici se poate desprinde usor un algoritm de conversie:

Se înmulteste baza cu numarul din dreapta, se aduna rezultatul cu numarul din dreapta-sus si se scrie rezultatul pe rândul de jos:

(

40A₍₁₆₎ = 4·16² 0·16¹ + A·16⁰ + = 1024 + 10 = 1034

II.5. Conversia din baza 10 într-o baza de numeratie

oarecare B

Pentru a trece un numar din baza 10 într-o alta baza de numeratie uÎ, u > 1 se aplica urmatorul algoritm:

Pasul 1. Se converteste partea întreaga a numarului, conform procedurii de la pasul 2 si partea fractionara a numarului conform procedurii de la pasul 3.

Pasul 2. Se fac împartiri întregi, succesive la baza u, pornind de la numarul întreg care se converteste:

·  939v216j   939v216j   939v216j   939v216j în urma fiecarei împartiri se obtine un cât si un rest;

·  939v216j   939v216j   939v216j   939v216j noul cât este deîmpartitul urmatoarei împartiri întregi;

·  939v216j   939v216j   939v216j   939v216j algoritmul se încheie când se obtine câtul 0;

·  939v216j   939v216j   939v216j   939v216j resturile obtinute, începând cu ultimul si pâna la primul, reprezinta cifrele numarului, de la cea mai semnificativa la cea mai putin semnificativa.

Pasul 3. Se fac înmultiri succesive, cu baza u, începând cu partea fractionara a numarului care se converteste:

·  939v216j   939v216j   939v216j   939v216j partea fractionara a fiecarui produs constituie deînmultitul pentru produsul urmator;

·  939v216j   939v216j   939v216j   939v216j partea fractionara a numarului convertit în baza u este reprezentata de succesiunea obtinuta din partile întregi ale tuturor produselor obtinute, începând cu primul produs, care furnizeaza cifra cea mai semnificativa a rezultatului;

·  939v216j   939v216j   939v216j   939v216j algoritmul se încheie cu un rezultat exact atunci când:

1. se obtine ca produs partial un întreg;

2. se obtine aproximarea dorita a numarului fractionar dupa un anumit numar de pasi.

Demonstratie: Pasul 2 - fie a numarul întreg în baza 10 care se converteste în baza u, conform algoritmului de la pasul 2 si fie reprezentarea în baza u obtinuta prin conversie, de forma c_n-1c_n-2 ... c₀. Algoritmul este corect daca se termina într-un numar finit de pasi si daca:

Daca se noteaza cu a₁ câtul obtinut dupa prima împartire întreaga si cu c₀ restul acestei împartiri; au loc relatiile:

c = a₀ - a₁·u, a₁ < a₀ (14)

Analog, pentru orice i = 1, ..., n au loc relatiile:

c_i-1 = a_i--1 - a_i·u, a_i < a_i-1 (15)

Din sirul de inegalitati a_i < a_i-1 (i = 1, ..., n) rezulta finitudinea algoritmului.

Fie ultimul rest, c_n-1 = a_n-1 - a_n·u, unde a_n = 0. Rezulta:

a = c₀ + a₁·u = c₀ + c₁·u + a₂·u² = ... = c₀·u⁰ + c₁·u¹ + c₂·u² + ... + a_n-1·u^n-1 =  939v216j c₀·u⁰ + c₁·u¹ + ...  939v216j + a_n-1·u^n-1 + a_n·uⁿ  (16)

În pasul 3: fie a numarul subunitar în baza 10 care se converteste în baza u conform algoritmului de la pasul 3 si fie reprezentarea în baza u, obtinuta prin conversie, de forma 0,c_-1c_-2 ... c_-m. Algoritmul este corect daca:

Se noteaza cu a₁ partea fractionara a primului produs si cu c_-1 partea întreaga a acestuia. Au loc relatiile:

a ·u = c_-1 +  939v216j a₁  a₁ = c_-1·u^-1 +  939v216j a₁·u^-1  (18)

Analog, pentru orice i =1, ..., m au loc relatiile:

a_i-1·u = c_-i +  939v216j a_i  a_i-1 = c_-i·u^-i +  939v216j a_i·u^-i  (19)

Din sirul de egalitati a_i-1 = c_-i·u^-i +  939v216j a_i·u^-i (i =1, ..., m), rezulta:

a = c_-1·u^-1 + c_-2·u^-2 + a₂·u^-2 = c_-1·u^-1 + c_-2·u^-2 + ... + a_m-1·u^-(m-1) = ... = c_-1·u^-1 + c_-2·u^-2 + ... + c_m-1·u^-(m-1) + c_-m·u^-m 

  939v216j

Cazul 1: daca exista un m astfel încât a_m = 0, atunci algoritmul este finit si rezultatul conversiei este exact.

Cazul 2: este posibil ca numarului rational a₀, reprezentat în baza 10 sa îi corespunda un numar rational 0,c_-1c_-2 ... c_-m reprezentat in baza u printr-o fractie periodica; în acest caz, algoritmul se încheie atunci când se determina perioada.

Exemple

Pasul 2. Conversia numarului 95.244 în baza 5 se obtine astfel:

Rezultatul obtinut este 95.244 = 11021434₍₅₎.

Pasul 3. Conversia numarului 0,7109375 în baza 2 se obtine astfel:

Rezultatul conversiei este 0,1011011₍₂₎.