Algebra computaţională

Am ezitat mult timp să abordez pe blog subiecte matematice. Succesul blogurilor matematice celebre, despre care am scris anterior (au circa 35-40 de mii de vizitatori zilnic) mi-au dat curajul să încerc… Statistica legată de articolele cu subiecte matematice publicate, mi-a ilustrat că sunt citite de mulţi vizitatori. Aşa că mai revin cu asemenea subiecte.

Algebra computaţională este un domeniu care ţine atât de matematică, cât şi de informatică. Pentru a înţelege specificul domeniului, va trebui să clarificăm succint care este deosebirea dintre algebra tradiţională (abstractă) şi cea computaţională.

Cuvântul algebra este derivat de la cuvântul arab Al-Jabr. Este una din cele două operaţii folosite la rezolvarea ecuaţiilor pătratice în tratatul „Al-Kitāb al-mukhtaṣar fī hīsāb al-ğabr wa’l-muqābala” scris în 820 de către Abū Abdallāh Muḥammad ibn Mūsā al-Khwārizmī (780-850), binecunoscut ca al-Horezmi. Apropo, de la numele lui provine cuvântul algoritm. All-Horezmi, împreună cu Diofant din Alexandria (Διόφαντος ὁ Ἀλεξανδρεύς, născut 200-214  – decedat 284-298), sunt consideraţi părinţii algebrei. Tratatul lui al-Horezmi a fost primul în care s-au abordat sistematic problemele de soluţionare a ecuaţiilor liniare şi pătratice. Este tradus în latină în secolul XII.

Al-Khwarizmi

Istoria algebrei desigur nu începe cu acest tratat Problema rezolvării ecuaţiei pătratice este abordată încă de babilonieni în 1800 î.H. De-a lungul secolelor un şir de iluştri matematicieni au contribuit la dezvoltarea acestui domeniu al matematicii, algebra clasică (elementară) fiind, în general, legată de rezolvarea ecuaţiilor polinomiale, a sistemelor de ecuaţii liniare şi a ecuaţiilor diofantine.

Algebra abstractă (modernă) ia naştere la sfârşitul secolului XIX începutul secolului XX.

Algebra abstractă studiază structuri algebrice:
grupuri, inele, corpuri, module, latice, spații vectoriale, algebre,
dar şi aplicaţiile între asemenea structuri.

Structura algebrică (numită şi sistem algebric) constă din una sau mai multe mulţimi (suport), închise în raport cu una sau mai multe operaţii, care satisfac anumite axiome.

Prin generalizare, am putea cere ca un sistem de algebră computaţională să înglobeze caracteristicile specifice diverselor structuri algebrice, cu precizarea că mulţimile suport şi operaţiile să fie definite cu ajutorul calculatorului, care să asigure şi posibilitatea realizării diverselor tipuri de calcule şi manipulări asupra componentelor structurilor algebrice.

Actualmente, prin sistem de algebră computaţională se înţelege un program sau un sistem de programe care facilitează efectuarea calculelor simbolice/algebrice. Formal vorbind, SAC modern corespund mai mult algebrei clasice.

Să evidenţiem deosebirile dintre calculele numerice şi cele simbolice prin comparaţie:

Calcule numerice Calcule simbolice
4/12 → 0.333333 4/12 → 1/3
3+4 → 7 3x + 4x → 7x
cos(3.13159) → -0.999999 cos(π) → -1
sin(2x) → 2 sin(x) cos(x)
(cos(x))’→ -sin(x)
rezultat numeric rezultat algebric
evaluare simplificare

Calculul simbolic include:

  • calcule cu exactitate arbitrară, fără rotunjire;
  • calcule cu simboluri şi variabile;
  • calcule cu funcţii;
  • manipularea formulelor;
  • operaţii simbolice (diferenţiere, integrare, factorizare etc.)

Algebra computaţională (calculul algebric, manipularea simbolică) este un domeniu al calculului ştiinţific care dezvoltă, analizează, implementează şi utilizează algoritmi pentru rezolvarea problemelor matematice.

Importanţa calculelor simbolice/algebrice este evidentă. Uneori calculele şi rezultatele numerice nu sunt relevante, cele simbolice fiind mult mai simple şi mai clare.

Aşadar, caracteristicile de bază ale structurilor algebrice ale sistemelor de algebră computaţională sunt:

  1. reprezentarea exactă a structurilor algebrice,
  2. aritmetica exactă a structurilor algebrice,
  3. aplicarea altor operaţii analitice asupra structurilor algebrice.

Să clarificăm care sunt mulţimile suport de bază, dar şi structurile de date care permit reprezentarea exactă a structurilor algebrice:

1. Numerele întregi

  • reprezentarea prin cuvinte de n biţi (<2n-1);
  • reprezentarea prin masive unidimensionale A, fiecare element fiind un cuvânt de n biţi (numerele întregi sunt reprezentate în sistem de numeraţie cu baza 2n-1);
  • deoarece memoria este finită, numerele reprezentate vor fi şi ele limitate la un anumit număr de cifre.

2. Polinoamele

  • Forma prefix – polinoamele sunt reprezentat prin liste, folosind 4 operatori (PLUS pentru adunare, DIFFERENCE pentru scădere (sau operatorul unar MINUS), TIMES pentru înmulţire şi EXPT pentru exponenţiere; astfel x3+2x2+1 se va reprezenta ca (PLUS (EXPT X 3) (TIMES 2 (EXPT 2)) (1) ), primul operator PLUS fiind operator prefix; reprezentarea poată fi aplicată asupra oricărei expresii; algoritmii care folosesc această reprezentare nu sunt cei mai rapizi;
  • Reprezentarea densă, în care pentru un polinom de gradul n vor fi salvaţi n+1 coeficienţi; dacă în polinom majoritatea coeficienţilor sunt nuli, atunci o asemenea reprezentare nu este de loc bună nici din punctul de vedere al memoriei folosite, nici din cel al timpului;
  • Reprezentarea rarefiată, în care se specifică prin perechi exponentul şi coeficientul respectiv (i, ci);  de regulă se alege o ordine de scriere, sau crescătoare sau descrescătoare;
  • Reprezentarea recursivă este una rarefiată cu ordonare a exponentului, reprezentare folosită pentru polinoame cu mai multe variabile; în primul rând se selectează ordonarea variabilelor (de regulă alfabetică); prima variabilă din ordonare este de bază; coeficienţii pe lângă puterile ei vor fi polinoame în alte variabile; în rest se foloseşte reprezentarea rarefiată de câte ori este nevoie.

3. Expresiile

  • Se foloseşte forma cu prefix, adică ca listă.

Să reţinem că listele sunt structuri de date extrem de importante în algebra computaţională.

P.S. Articolul a fost publicat pe blog pentru prima oară pe 9 septembrie 2010, ora 16:30.

Anunțuri

3 comentarii la “Algebra computaţională

  1. Pingback: Algebra computaţională - Ziarul toateBlogurile.ro

  2. Scrii mai sus că „Problema rezolvării ecuaţiei pătratice este abordată încă de babilonieni în 1800 î.H.” Dumnezeule milostiv, ce le lumina atât de mult minţile de maimuţoi? De unde proveneau ştiinţa lor, curiozitatea lor, abilităţile lor în acele vremuri? Eu, unul, sunt consternat…

  3. Civilizaţia sumero-babiloniană a fost una din cele mai impresionante dintre cele pe care le cunoaştem până acum! Când se creează condiţiile necesare, omul îşi poate evidenţia natura lui divină, dacă stăm pe poziţii creaţioniste. Dacă privim din perspectiva atesită, atunci putem conchide că evoluţia poate demonstra posibilităţi miraculoase, ce a şi făcute cu mii de ani în urmă…

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