Aritmetica algebrei computaţionale

Aritmetica este, în general, un domeniu al matematicii care studiază cele mai simple tipuri de numere (naturale, întregi, raţionale) precum şi cele mai simple operaţii definite asupra lor (adunare, scădere, înmulţire şi împărţire). Denumirea provine din greacă de la ριθμός – număr. Preistoria aritmeticii se limitează la un număr mic de vestigii în care se observă clar operaţiile de adunare şi scădere a unor numere foarte mici. Cele mai devreme vestigii sunt din Africa Centrală şi se referă la anii 20000 – 18000 î.H. Şi egiptenii, şi babilonienii foloseau toate operaţiile (2000 î.H.). Grecii antici studiau matematica şi în context filosofic. Exemplu poate servi „Introducerea în Aritmetică” a lui Nicomahos (60 – 120), în care se totalizează perspectiva lui Pitagora asupra numerelor. Trecerea la sistemul zecimal de numeraţie (graţie tratatului „Liber Abbaci” scris de Fibonacci în 1202) şi dezvoltarea algebrei au simplificat esenţiale algoritmii de efectuare a calculelor. Actualmente aritmetica este tratată ca cel mai simplu domeniu matematic.

Aritmetica Algebrei Computaţionale nu se limitează doar la numere, ci studiază şi expresiile algebrice. În plus, pe lângă operaţiile de adunare, scădere, înmulţire şi împărţire, studiază şi alte operaţii, cum este, spre exemplu, exponenţierea.

Algebra Computaţională se defineşte pe domenii, care pot fi divizate în două clase.

Domenii numerice:

  • {Z,+,-,×}numerele întregi cu operaţiile de adunare, scădere şi înmulţire;
  • {Zm,+m,-mm}numerele întregi în cadrul aritmeticii modulare (modulus m), unde m este un număr pozitiv întreg;
  • {Q,+,-,×,/}numerele raţionale cu operaţiile de adunare, scădere, înmulţire şi împărţire;
  • {{x=a+ib, a,b in Z},+,-,×}numerele întregi de tip Gauss, adică numerele complexe cu părţile reală şi imaginară întregi;
  • {Q(a),+,-,×,/}, p(a)=0, – câmpul algebric extins, numărul algebric a este definit prin polinomul p cu coeficienţi de tip întreg ce pot fi reprezentaţi exact; numărul algebric a este rădăcina polinomului p, adică rădăcina pătratică din 7 este reprezentată de a2-7 şi numărul algebric b ar putea fi reprezentat prin polinomul b2-5b+1;
  • {Rnf,+,-, ×,/} numere cu virgulă flotantă (mobilă) de exactitatea n cifre zecimale, unde n este un număr întreg pozitiv arbitrar;

Domenii de expresii algebrice:

  • inelul polinoamelor O[x1,x2,…,xn] de n variabile cu operaţiile de adunare, scădere, înmulţire şi exponenţiere cu un număr întreg nenegativ;
  • serii de puteri, precum şi alte serii
  • funcţii raţionale K(x1,x2,…,xn) – extensiune a inelului polinoamelor cu operaţia de împărţire, adică în acest domeniu sunt definite operaţiile de adunare, scădere, înmulţire, împărţire şi exponenţiere cu un număr întreg;
  • extensiunea funcţiilor raţionale cu radicali (exponente raţionale), cu operaţiile de adunare, scădere, înmulţire, împărţire şi exponenţiere cu un număr raţional;
  • funcţii algebrice {yi, pi(X,y1,…,ym)=0, i=1,…,m} definite implicit prin sisteme de ecuaţii polinomiale cu coeficienţi întregi care depind de funcţii algebrice şi de variabile din mulţimea X={x1,…,xn};
  • extensiunea funcţiilor raţionale cu funcţiile elementare transcendentale exp şi ln;
  • funcţiile transcendentale, adică funcţiile care nu pot fi reprezentate printr-o succesiune finită de operaţii de adunare , înmulţire şi extragere a rădăcinii (funcţii care nu pot fi reprezentate în cadru algebric);
  • extensiunea funcţiilor raţionale cu funcţii transcendentale;
  • inelele matriceale;
  • câmpurile diferenţiale (K,`);
  • grupele finite;
  • în general, utilizatorul unui sistem de algebră computaţională poate utiliza expresii algebrice din oricare domeniu – sistemul va depista singur cărui domeniu aparţine şi va folosi algoritmii corespunzători.

Calculele numerice şi cele simbolice au specificul corespunzător, care se evidenţiază prin contrapunere:

Calcule numerice <–> Calcule simbolice
Inexacte, de regulă <–> Exacte
Variate răspunsuri <–> Adesea nu se poate produce rezultatul
Calcule nevoluminoase <–> Calcule voluminoase
Zerourile nu au un tratament special, cu excepţia singularităţilor <–> Zerourile pot simplifica foarte mult calculele
Zerouri? – când numerele sunt mici <–> Zerouri? – expresii echivalente cu zero
Maximizarea dimensiunii pivoturilor pentru stabilitate <–> Minimizarea dimensiunii pivoturilor pentru a împiedica creşterea expresiilor

Referindu-ne aparte la algoritmii de efectuare a operaţiilor cu numere întregi, vom menţiona că pentru adunare, scădere şi înmulţire se folosesc aceiaşi algoritmi binecunoscuţi de fiecare, doar că se efectuează în baza 2n. Totuşi pentru înmulţire există algoritmi mai eficienţi, iar cei pentru împărţire cer o estimare iniţială a rezultatului.

Reamintim că la reprezentarea în calculator a structurilor algebrice, un rol special revine reprezentărilor numerice şi celor sub formă de listă prefix. Reprezentarea expresiilor sub formă de liste permite efectuarea operaţiilor aritmetice conform unor algoritmi transparenţi. Spre exemplu, adunarea a două polinoame de gradul n necesită un volum de calcule de ordinul O(n).

De fapt, majoritatea operaţiilor în algebra computaţională sunt simplificări de expresii. Şi în acest context există o întrebare sacramentală: care dintre formele expresiei este mai simplă? Despre indeciziile care pot apărea în acest context ne putem da seama şi în următorul caz: (a+b)2 <–> a2+2ab+b2. Expresiile sunt echivalente, dar care dintre ele e mai simplă depinde şi de context.

Complexitatea unei expresii poate fi tratată din câteva perspective. Pentru a le elucida este util de referit şi la operatorul canonic de simplificare. Un operator S este operator canonic de simplificare dacă şi numai dacă:

  • pentru orice t, S(t)~t,
  • pentru orice t1, t2, din t1~ t2 rezultă S(t1)~S(t2).

Operatorul canonic de simplificare oferă un singur reprezentant pentru expresii echivalente. În algebra computaţională se folosesc mai des operatori de simplificare necanonici, combinaţii de simplificări canonice şi de confruntări cu originalul.

Complexitatea unui număr raţional se notează prin R şi se consideră ca sumă a valorilor absolute ale numărătorului şi numitorului.

Complexitatea unui număr în virgulă mobilă se notează prin F şi este egală cu modulul lui (se notează prin B pentru numere mari bigfloats).

Complexitate unei expresii se notează prin E şi este egală cu dimensiunea expresiei – numărul de operatori şi operanzi.

În lumina acestor noţiuni, noţiunea de simplificare devine mai clară.

Într-un viitor apropiat urmează să ne oprim şi asupra algoritmilor de efectuare a operaţiilor, atât numerice, cât şi de simplificare.

Anunțuri

Un comentariu la “Aritmetica algebrei computaţionale

  1. Pingback: Aritmetica algebrei computaţionale - Ziarul toateBlogurile.ro

Lasă un răspuns

Completează mai jos detaliile tale sau dă clic pe un icon pentru a te autentifica:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare / Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare / Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare / Schimbă )

Fotografie Google+

Comentezi folosind contul tău Google+. Dezautentificare / Schimbă )

Conectare la %s