Noţiuni elementare de matematică pentru programatori (1) - Tipuri numerice

Nu de puţine ori, în spatele unor programe extrem de cunoscute stau algoritmi matematici de o complexitate descurajantă; să ne gândim, de exemplu, la algoritmii folosiţi de motoarele de căutare, dar nu numai. Evident, e greu de crezut că un novice într-ale programării se va apuca să scrie un program care să poată concura serios cele mai populare motoare de căutare, sau alte asemenea programe, dar unele noţiuni de matematică sunt necesare. Mai cu seamă că, pentru un informatician, unele noţiuni matematice pot avea un sens uşor diferit ca pentru un matematician „pur”.

Orice program de calculator face, în esenţă, trei lucruri:

• Colectează informaţii externe, în principal de la utilizator(date de intrare),
•  Prelucrează aceste informaţii, şi,
• Comunică aceste rezultate în exterior (date de ieşire).

În principal, datele de intrare, ca şi cele de ieşire sunt furnizate/recepţionate de un utilizator utilizator uman, şi, prin urmare, trebuie să aibă o formă „umană”.

Pentru a putea fi uşor prelucrată, informaţia trebuie structurată specific; acest lucru este valabil deopotrivă şi pentru calculatoare, şi pentru oameni. Aceasta presupune existenţa unor „compartimente”, sau „sertăraşe” diferite pentru diversele tipuri de informaţii. 

Cele mai cunoscute şi utilizate (de către mai toate limbajele de programare) de astfel de „sertăraşe” – ele se numesc, de fapt, tipuri – sunt: întreg, real, logic, caracter, şir (tablou) (uni-, bi- sau multidimensional), şir de caractere, structură/uniune, mulţime etc. 

 

Pentru a avea acces la un astfel de obiect, el trebuie să aibă un nume. Trebuie să facem distincţie între numele obiectului/datei şi conţinutul său. 

Calculatoarele nu ştiu să manipuleze altceva decât date binare, pentru un calculator „totul este bit” (sau o succesiune de biţi). Calculatorul depozitează datele cu care lucrează în memorie – deocamdată nu vom face nicio distincţie între diferitele tipuri de memorie. Putem să ne imaginăm această memorie ca fiind un şir lung de căsuţe în care sunt înscrise informaţii binare. Pentru a regăsi şi manipula o dată, calculatorul trebuie să cunoască trei lucruri, şi anume: adresa de început, lungimea, şi respectiv tipul datei. Aceste informaţii pot fi uneori redundante, alteori nu. De exemplu, pentru o dată de tip numeric sau logic este suficient să cunoaştem adresa de început, fiindcă o astfel de dată are, întotdeauna o lungime fixă precizată, pe când o dată de tip şir de caractere are o  variabilă.

Toate aceste informaţii se regăsesc, la un moment dat, în numele datei respective şi, de regulă, pot fi aflate prin anumite tehnici specifice.

În alte cuvinte, ori de câte ori o anumită locaţie de memorie trebuie tratată într-un anumit fel, deoarece în ea este înscrisă o dată de un anumit tip, avem de-a face cu o variabilă. Pe parcursul execuţiei unui program, o variabilă poate să-şi schimbe conţinutul (informaţia propriu-zisă, pe care o conţine), adresa, poate fi distrusă sau clonată (copiată) etc. O variabilă care îşi păstrează conţinutul pe toată durata execuţiei unui program se numeşte constantă.

Tipul întreg

Cu numerele întregi suntem familiarizaţi de la orele de matematică din şcoala elementară. Despre numerele întregi ştim următoarele

• Mulţimea numerelor întregi este infinită, ceea ce înseamnă că nu putem reprezenta în memoria unui calculator orice element al ei, ci numai o submulţime oarecare bine definită şi, de obicei, suficient de bogată pentru majoritatea aplicaţiilor. Încercarea de a atribui unei variabile întregi o valoare care iese din acest spectru conduce la eroarea numită depăşire de tip, şi la tratarea (de regulă) a variabilei respective, tot ca o variabilă întreagă (sau reală), dar cu o valoare diferită celei la care ne-am fi aşteptat.
• Pe mulţimea numerelor întregi sunt definite cele patru operaţii aritmetice obişnuite: adunare, scădere, înmulţire şi împărţire, care sunt implementate în orice limbaj de programare. Rezultatul adunării, scăderii şi al înmulţirii este întotdeauna un număr întreg şi, din acest punct de vedere, nu e nicio problemă. În schimb, în legătură cu împărţirea se ivesc două probleme, şi anume:  

  Împărţirea prin zero nu este definită, din punct de vedere matematic, şi, din acest punct de vedere, orice tentativă de efectuare a unei astfel de operaţii este sancţionată de calculator. În unele situaţii, aceasta poate fi o greşeală fatală (conduce la oprirea necondiţionată a programului), dar de regulă, acesta continuă (putând, însă, duce la obţinerea unor rezultate imprevizibile sau/şi nedorite). 

  Câtul a două numere întregi nu este, de regulă, întreg, iar această problemă este rezolvată diferit de diferite limbaje de programare. Frecvent, există doi operatori de împărţire, unul pentru împărţirea întreagă (câteodată, unul şi pentru obţinerea restului), şi unul pentru împărţirea propriu-zisă. Dacă notăm cu % operatorul de împărţire întreagă, cu mod pe cel pentru obţinerea restului, şi cu : pe cel de împărţire obişnuită, atunci rezultatul evaluării expresiilor 13 % 5, 13 mod 5 şi, respectiv, 13 : 5 este 2, 3, şi, respectiv, 2,6.

• Există, de asemenea, şi operaţia de ridicare la putere, definită ca o înmulţire repetată; această operaţie este, de regulă definită, in diverse limbaje, printr-o funcţie specifică.
• Oricărui număr întreg îi putem asocia un opus şi respectiv, un alt număr întreg, care reprezintă valoarea sa absolută (sau modulul). Opusul unui număr întreg se obţine înmulţindu-l cu -1 (ceea ce, din punct de vedere tehnic, atât în matematica obişnuită, cât şi în cele mai multe limbaje, se realizează prin prefixarea cu semnul -), iar modulul, printr-o funcţie matematică specifică.
• Adunarea şi înmulţirea au proprietăţile aritmetice binecunoscute: 

a)      Comutativitate: a+b = b +a, respectiv a*b = b*a; 
b)      Asociativitate: (a+b)+c = a+(b+c), respectiv (a*b)*c = a*(b*c);
c)       Există elementul neutru (0 pentru adunare, 1 pentru înmulţire): a+0 = 0+a = a, respectiv a*1 = 1*a = a;
d)      Înmulţirea este distributivă faţă de adunare: a*(b+c) = a*b + a*c;

• Avem următoarea regulă a semnelor: (-a)*b = a*(-b) = -(a*b); (-a)*(-b) = a*b;

7.       Atenţie la semnul înmulţirii, acesta este întotdeauna obligatoriu în informatică (i.e. a*b e cu totul altceva decât ab).

În matematică, sunt utilizate frecvent numere întregi de forma a*10^n. Astfel de numere sunt tratate, de regulă, ca reale, de limbajele de programare!

Cu privire la împărţirea întreagă menţionată mai sus, menţionăm următoarea teoremă binecunoscută din matematica elementară:

TEOREMA ÎMPĂRŢIRII ÎNTREGI: Oricare ar fi două numere întregi d (numit şi deîmpărţit), şi î (împărţitor), cu î nenul (diferit de zero), există şi sunt unice două numere întregi c (cât) şi r (rest), astfel încât:

•  d = î*c + r, şi, în plus,
•  0 ≤ r < mod(c).

În plus, operaţia prin care se obţin cele două numere întregi, cât şi rest, poartă numele de împărţire întreagă.

În cazul in care restul unei împărţiri (întregi) este zero, spunem că avem o împărţire exactă (fără rest). 

Fiind dat un număr întreg a, dacă există două numere întregi b şi c, astfel încât a = b*c, spunem că a se divide prin b (şi c), sau că este un multiplu al acestor numere, sau că b (sau c) este un divizor întreg al numărului a. De exemplu, numărul 6 are următorii divizori: -6, -3, -2, -1, 1, 2, 3 şi 6. De multe ori, prin „divizor” înţelegem, de fapt, doar divizorii naturali (întregi nenegativi) ai unui număr natural. 

În aceste condiţii, e uşor de arătat că orice număr natural cel putin egal cu 2 are (cel puţin) doi divizori: pe 1 şi pe el însuşi. Pentru orice număr natural, aceşti divizori (1 şi el însuşi) se numesc improprii, alţi eventuali divizori numindu-se, evident, divizori proprii.

Un număr care nu are alţi divizori decât cei improprii se numeşte număr prim, altfel se numeşte neprim (compus). Numărul 1 nu e nici prim, nici compus.

E binecunoscut următorul rezultat:

TEOREMA FUNDAMENTALĂ A ARITMETICII: Orice număr natural cel puţin egal cu doi se scrie, în mod unic, dacă facem abstrcţie de ordinea factorilor, ca produs de numere prime.

De exemplu, 6 = 2*3 (ceea ce e totuna cu 6 = 3*2 – ordinea factorilor nu contează).

Acest rezultat este crucial, deopotrivă în matematică şi în informatică. De exemplu, în informatică, aproape toţi algoritmii de criptare folosiţi în informatică, adică acei algoritmi care permit transmiterea în siguranţă a unor date critice într-o reţea de calculatoare, se bazează pe această proprietate simplă a numerelor naturale; ca să fim, totuşi, cinstiţi, precizăm că, de fapt, aceşti algoritmi se bazează pe faptul că, din punct de vedere practic, este foarte uşor să înmulţim anumiţi factori primi pentru a obţine un număr compus, în timp ce invers, a determina dacă un anumit număr întreg este sau nu prim şi, in caz afirmativ, de a-i determina factorii primi, poate fi extrem de dificil (chiar pentru un calculator deosebit de performant).

Tot în legătură cu acest rezultat fundamental al aritmeticii este şi algoritmul lui Euclid, care, în mod tradiţional, este prezentat, în mediile şcolare, ca un prim exemplu de algoritm, aşa după cum programul „Hello, world” este prezentat, în mod tradiţional, ca un prim exemplu, ori de cate ori se începe studiul unui nou limbaj de programare.

Algoritmul lui Euclid apare în celebra sa lucrare „Elementele” (cca. 300 î.e.n.) şi se referă la determinarea celui mai mare divizor comun a două numere naturale (mai mari sau egale cu doi).

Din cele spuse mai sus, rezultă că două numere naturale, mai mari sau egale cu doi, au cel puţin un divizor comun, şi anume pe 1 – dacă nu mai au alţi divizori comuni, ele numindu-se prime între ele. Algoritmul lui Euclid se referă, deci, la determinarea celui mai mare dintre aceşti divizori, şi se poate prezenta astfel:

1.  Fie cele două numere a şi b. Presupunem că a ≥ b, dacă nu e aşa, schimbă-le numele (numeşte numărul mai mare a, şi pe cel mai mic b);
2. Împarte pe a la b, obţinând câtul c şi restul r.
3. Dacă r este zero (împărţirea de la pasul precedent a fost exactă), atunci numărul căutat (cel mai mar divizor comun) este c, altfel, continuă algoritmul cu pasul 1, cu c pe post de a şi r pe post de b.

Fireşte, acest algoritm s-ar cuveni temeinic analizat, din punct de vedere al teoriei algoritmilor – şi, poate voi face vreodată acest lucru – dar, acum este mai important să vorbim de tipul real. 

Tipul real

De regulă, matematicienii fac o distincţie clară între numerele raţionale, definite ca mulţimea tuturor numerelor care sunt (sau pot fi) scrise ca fracţii ordinare care au atât numitorul, cât şi numărătorul numere întregi, respectiv, numerele iraţionale, care nu pot fi scrise astfel.

Apoi, din punctul de vedere al reprezentării zecimale, numerele raţionale pot fi numere zecimale finite, cele la care partea zecimală este compusă dintr-un număr finit de cifre nenule, şi numere zecimale infinite (sau periodice), cele care nu îndeplinesc această condiţie, respectiv la care partea zecimală conţine un număr infinit de cifre nenule. Numerele zecimale periodice pot fi, de asemenea, numere zecimale periodice simple, cele la care perioada începe imediat după virgulă, şi respectiv, numere zecimale periodice mixte, cele la care perioada începe la câteva cifre după virgulă.

Numerele iraţionale pot fi, la rândul lor, algebrice, cele care pot fi soluţii ale unei ecuaţii polinomiale cu coeficienţi întregi (şi aici întră, de exemplu, toţi radicalii), respectiv transcendente, cele care nu pot fi (şi, ca exemplu de numere transcendente, cităm celebrele π – a cărui iraţionalitate fusese intuită de mai-vechea noastră cunoştinţă Muhammad ibn Mūsā al-Khwārizmī,şi a cărui transcendenţă a fost demonstrată de Lindemann, respectiv e (baza logaritmilor naturali), lucru stabilit de Hermite – deşi teorema respectivă poartă numele lui Lindemann si Weierstrass). 

Mulţimea numerelor raţionale este infinită, cardinalul ei fiind acelaşi cu al mulţimii numerelor numerelor întregi respectiv  „alef zero”, în timp ce mulţimea numerelor iraţionale este tot infinită, dar „mult mai bogată” în elemente, cardinalul ei fiind „alef c”. 

Pentru un calculator, astfel de lucruri, la nivelul comun, incomprehensibile, deoarece spaţiul de memorie în care îşi poate reprezenta astfel de numere este limitat.

Prin urmare, pentru un calculator, un „număr real” (tipul float, double etc.) reprezintă, de fapt, numere zecimale finite, cu un număr oarecare maxim, fixat, de zecimale – ceea ce echivalează, de fapt, cu o anumită precizie.

Acest lucru poate crea o serie de probleme programatorilor obişnuiţi să gândească în sens absolut matematic. De exemplu, in matematica „obişnuită”, înmulţirea şi împărţirea (cu un număr nenul) sunt operatii inverse una alteia, a împărţi un număr cu o anumită valoare şi apoi a-l înmulţi cu exact acea valoare nemodificând valoarea iniţială (adică: din punct de vedere matematic, a:b*b = a, indiferent de valorile lui a şi b). Acest lucru nu este, neapărat adevărat, în informatică, de exemplu, pentru calculator, 1:3 nu este 0,(3), ci 0,3333 ... – un număr de zecimale care depinde de precizia respectivă, iar apoi, 1:3*3 este 0,3333 ... * 3 = 0,9999 ..., ceea ce nu e întotdeauna interpretat ca fiind egal cu 1. Din acest motiv, sunt total nerecomandate comparaţiile exacte ale valorilor de tip real, care pot conduce la rezultate eronate.

Faţă de ceea ce am spus despre tipul întreg, în cazul tipului real apare, în plus, problema conversiei (a cast-ului) la un întreg.

Această problemă este rezolvată în mod diferit de diferitele limbaje de programare. În unele din ele există funcţii, cum ar fi floor, ceiling, round, şi aşa mai departe, care realizează o conversie explicită, cu pierdere de precizie, evident, in alte situaţii se poate face o conversie implicită etc.

Sisteme de numeraţie

Poate unul din cele mai importante progrese în domeniul matematicii a fost descoperirea sistemului de numeraţie poziţional, care a permis realizarea facilă de calcule aritmetice. Cu toţii cunoaştem sistemul de numeraţie roman, şi ... nu mai e nimic de spus în legătură cu acesta.

Ideea de bază a oricărui sistem de numeraţie este aceasta: cu ajutorul unui sistem de n simboluri desemnăm toate valorile numerice întregi (naturale) de la 0 la n-1. Apoi, n unităţi formează o unitate superioară (o  „zece” a bazei respective), şi aşa mai departe.

De exemplu, numărul 1234 s-ar putea „traduce” după cum urmează: numărul care reprezintă suma tuturor obiectelor care se află într-o grămadă compusă din 4 obiecte singulare, 3 „snopuri” de câte 10 obiecte, 2 „snopuri” de „snopuri” de câte 10 obiecte, şi un „snop” de „snopuri” de „snopuri” de câte 10 obiecte.

Baza 10, cea pe care o folosim în mod curent, nu are nimic „natural” în ea. De fapt, singurul lucru care ne îndreptăţeşte să folosim această bază de numeraţie şi nu alta, este faptul că, in prima copilărie, învăţăm să numărăm pe degete – de unde şi termenii digit, digital etc. – şi, în mod „natural”, avem 10 degete (la cele două mâini). 

Pentru un calculator, această opţiune nu este decât o „ciudăţenie” a omului, reprezentarea internă a datelor, a tuturor tipurilor de date făcându-se în sistemul binar (baza 2), care operează cu doare două simboluri, respectiv 0 şi 1. Pe drept cuvânt, se poate spune că, pentru un calculator, lumea e o înşiruire de 0 şi 1, totul, dar absolut totul, reducându-se, până la urmă, la o secvenţă de 0 şi 1. 

Există doi algoritmi simpli de transformare a unui număr din baza 2 în baza 10, şi reciproc.

În baza 10 – de fapt în orice sistem de numeraţie poziţional – orice număr este o sumă de puteri ale bazei. De exemplu: 2.670.458 = 2*1.000.000 + 6*100.000 + 7*10.000 + 0*1.000 + 4*100 + 5*10 + 8*1 = 2*10^6 +6*10^5 + 7*10^4 + 0*10^3 +4*10^2 + 5*10^1 + 8*10^0. Similar, numărul 1.111.010.111, din baza 2, reprezintă 1*2^9 + 1*2^8 + 1*2^7 +1*2^6 +0*2^5 + 1*2^4 + 0*2^3 + 1*2^2 +1*2^1 + 1*2^0 = 1*512 + 1*256 + 1*128 + 1*64 +0*32 + 1*16 + 0*8 + 1*4 + 1*2 + 1*1 =  983 (în baza 10).

Învers, împărţim succesiv numărul respectiv la 2 (sau la baza respectivă), reţinând de fiecare dată restul, (până când obţinem câtul 0). De exemplu:

983 : 2 = 491 r 1

491 : 2 = 245 r 1

245 : 2 = 122 r 1

122 : 2 = 61 r 0

61 : 2 = 30 r 1

30 : 3 = 15 r 0

15 : 2 = 7 r 1

7 : 2 = 3 r 1

3 : 2 = 1 r 1

1 : 2 = 0 r 1

Acum, „citind” (sau „ordonând”) resturile respective de la „coadă la cap” (sau, „de jos în sus”), obţinem numărul căutat: 1.111.010.111 (în baza 2).

În informatică, se folosesc, de asemenea, baza 8 şi baza 16. Motivul pentru care se utilizează aceste baze este acela că o cifră octală (în baza opt) reprezintă (este echivalentă cu) trei cifre binare, în timp ce o cifră hevazecimală, patru cifre binare.

Atât, deocamdată.