En matemàtiques i ciències de la computació, la computació algebraica, també anomenada computació simbòlica, és una disciplina científica que es dedica a l'estudi i desenvolupament d'algorismes i programari per a la manipulació d'expressions matemàtiques i altres objectes matemàtics. Encara que, parlant amb propietat, la computació algebraica hauria de ser una subdisciplina de la computació científica, normalment se les considera disciplines diferents, perquè la computació científica es basa normalment en el càlcul numèric amb aritmètica en coma flotant pels nombres (que per definició esdevenen aproximats), mentre que la computació algebraica posa especial èmfasi en la computació exacta d'expressions que contenen variables a les quals no se'ls dona cap valor concret, sinó que es manipulen com a símbols (d'aquí el nom de computació simbòlica).
Els programaris que realitzen càlculs simbòlics s'anomenen sistemes algebraics computacionals, on el terme sistema es refereix a la complexitat de les aplicacions que el formen, i que com a mínim són: un mètode per representar dades matemàtiques en un ordinador, un llenguatge de programació per l'usuari (que normalment és diferent del llenguatge emprat per a la implementació del sistema), un gestor de memòria dedicat, una interfície d'usuari per a l'entrada i la sortida d'expressions matemàtiques, un conjunt ampli de subrutines per realitzar les operacions usuals, com simplificació d'expressions, derivades que usen la regla de la cadena, factorització de polinomis, integració indefinida, etc.
En els inicis de la computació algebraica, vers 1970, quan es van aplicar els algorismes coneguts als ordinadors, es va veure que eren altament ineficients. Per tant, una gran part de la feina dels investigadors consistí a revisar l'àlgebra clàssica per tal de fer-la més efectiva i per descobrir algorismes eficients per tal d'implementar aquesta eficiència. Un exemple típic n'és el càlcul del màxim comú divisor per polinomis, que és necessari per simplificar fraccions.
La computació algebraica s'usa a bastament per dissenyar les fórmules utilitzades en programes numèrics. També s'usa en càlculs científics complets, quan fallen els mètodes purament numèrics, com ara la criptografia de clau pública o alguns problemes no lineals.
Terminologia Alguns autors distingeixen entre àlgebra computacional i computació simbòlica, i empren aquest darrer terme per referir-se a altres tipus de computació simbòlica diferents de la computació amb fórmules matemàtiques. Alguns autors empren computació simbòlica per denominar la ciència de la computació referida a aquest tema, i "àlgebra computacional" per l'aspecte matemàtic.Making Computer Algebra More Symbolic (Invited) , Stephen M. Watt, p. 43-49, Proc. Transgressive Computing 2006: A conference in honor or Jean Della Dora, (TC 2006), 24–26 abril 2006, Granada, Espanya En alguns idiomes, aquest terme no és una traducció literal; per exemple, en francès s'anomena calcul formel, que significa "càlcul formal".
En el passat, la computació simbòlica s'ha denominat com manipulació simbòlica, manipulació algebraica, processament simbòlic, matemàtica simbòlica o àlgebra simbòlica, però aquests termes han caigut en desús per referir-se a la computació simbòlica, ja que denominen aspectes de manipulació no computacional.
Comunitat científica No hi ha cap societat científica que es dediqui específicament a la computació algebraica, però aquesta funció està assumida per lspecial interest group de l'Association for Computing Machinery anomenat SIGSAM (Special Interest Group on Symbolic and Algebraic Manipulation; en anglès, Grup d'Interès Especial per la Manipulació Algebraica i Simbòlica).
Existeixen diverses conferències anuals sobre computació algebraica, la més important d'elles ISSAC (International Symposium on Symbolic and Algebraic Computation; en anglès, Simposi Internacional sobre Computació Simbòlica i Algebraica), impulsada per SIGSAM.Llista de conferències de SIGSAM
També existeixen diverses publicacions especialitzades en computació algebraica, la més important el Journal of Symbolic Computation fundada el 1985 per Bruno Buchberger. Altres publicacions publiquen de forma regular articles sobre computació algebraica.Llista de publicacions de SIGSAM
Aspectes en ciències de la computació Representació de dades Com que els programaris de càlcul numèric són altament eficients per realitzar càlculs aproximats, és força comú, en computació algebraica, posar èmfasi en realitzar càlculs exactes amb dades representades de forma exacta. Aquesta representació tan exacta implica que, encara que la grandària de la sortida sigui petita, les dades intermèdies generades durant un càlcul poden créixer d'una forma impredictible. Aquest comportament s'anomena inflor de l'expressió (en anglès, expression swell). Per esmenar aquest problema, hom usa diversos mètodes en la representació de les dades, així com en els algorismes que les manipulen.
Nombres Els sistemes numèrics habituals emprats en anàlisi numèrica són o bé la representació de nombres en coma flotant o els enters d'una grandària màxima fixada, que s'anomenen de forma impròpia enters per la majoria de llenguatges de programació. Cap d'ells és convenient per la computació algebraica, a causa de l'efecte d'inflor de l'expressió.
En lloc d'això, els nombres bàsics emprats en computació algebraica són els enters matemàtics, normalment representats com una seqüència de dígits en alguna base de numeració, normalment la major base permesa per la paraula de la màquina. Aquests enters permeten definir els nombres racionals, que són fraccions irreduïbles de dos enters.
El procés de programar una implementació eficient de les operacions aritmètiques és una tasca difícil. Per tant, la majoria de sistemes algebraics computacionals i alguns de comercials, com Maple, usen la llibreria GMP, que ha esdevingut un estàndard de facto.
Expressions Excepte per nombres i variables, tota expressió matemàtica es pot veure com el símbol d'un operador seguit d'una seqüència d'operands. En programaris de computació algebraica, les expressions s'acostumen a representar d'aquesta manera. Aquesta representació és molt flexible, i molts termes que no semblen una expressió matemàtica a primer cop d'ull, es poden representar i manipular com a tals. Per exemple, una equació és una expressió on l'operador és "=", una matriu es pot representar com una expressió amb l'operador "matriu" i on les files i les columnes en són els operands.
Fins i tot els programes es poden considerar i representar com a expressions, amb l'operador "procediment" i, almenys, dos operands, la llista de paràmetres i el cos, que és al seu torn una expressió amb l'operador "cos" i una seqüència d'instruccions com a operands. Recíprocament, qualsevol expressió matemàtica es pot veure com un programa. Per exemple, l'expressió es pot veure com un programa per l'addició, on a i b en són els paràmetres. Executar aquest programa consisteix a avaluar l'expressió per valors donats de a i b; si no tenen cap valor (és a dir, són indeterminats), el resultat de l'avaluació és simplement l'entrada.
El procés d'avaluació diferida és fonamental en computació algebraica. Per exemple, l'operador "=" de les equacions també és, en la majoria de sistemes algebraics computacionals, el nom del programa per la prova d'igualtat: normalment, l'avaluació d'una equació resulta en una equació; però, quan es necessita una prova d'igualtat, llavors l'avaluació retorna un 0 o un 1 booleans.
Com que la grandària dels operands d'una expressió és impredictible i pot canviar durant una sessió de treball, la seqüència d'operands se sol representar com una seqüència de punters (com en Macsyma) o com a entrades d'una taula hash (com en Maple).
Simplificació Una expressió com
és farragosa i difícil de manipular. Per tal de simplificar-la a és necessari proveir-se de regles de simplificació per a aquesta i d'altres expressions.
Aquesta simplificació es du a terme normalment mitjançant regles de reescriptura. Existeixen diferents tipus de regles de reescriptura; n'és un exemple la intenció de reduir la grandària de l'expressió, com ara . Aquestes regles s'apliquen de forma sistemàtica en els sistemes algebraics computacionals.
La primera dificultat apareix amb les operacions associatives com l'addició i la multiplicació. La forma habitual de tractar l'associativitat és considerar que la suma i la multiplicació tenen un nombre arbitrari d'operands, és a dir, es representa com . Quant a la subtracció i la divisió, la forma més senzilla és reescriure -E, E-F, E/F com a (-1)·E, E + (-1)·F, E·F−1, respectivament. En altres paraules, en la representació interna de les expressions, no hi ha cap substracció ni divisió ni oposat per la suma, llevat de la representació dels nombres.
Apareix una segona dificultat amb la commutativitat de l'addició i de la multiplicació. El problema rau en reconèixer ràpidament els termes semblants per tal de combinar-los o cancel·lar-los. De fet, el mètode per trobar els termes semblants, consistent en provar cada parell de termes, és massa costós per fer-lo practicable amb sumes o productes molt llargs. Per resoldre aquest problema, Macsyma ordena els operands de sumes i productes mitjançant una funció de comparació que situa els termes semblants en posicions consecutives, i així es poden detectar fàcilment. En Maple, la funció de hash està dissenyada per generar col·lisions quan es troben termes semblants, i això permet combinar-los a mesura que s'introdueixen. Aquest disseny de la funció de hash també permet reconèixer de forma immediata les expressions de subexpressions que apareixen diversos cops en un càlcul, i emmagatzemar-los una sola vegada. Això comporta no només un estalvi d'espai, sinó també una acceleració dels càlculs, perquè així s'evita repetir el mateix càlcul en diverses expressions idèntiques.
Algunes regles de reescriptura de vegades incrementen i de vegades disminueixen la grandària de les expressions a les quals s'apliquen. Aquest és el cas de la distributivitat o les identitats trigonomètriques. Per exemple, la propietat distributiva permet reescriure i Com que, en general, no es pot predir si una regla de reescriptura portarà a una expressió més senzilla o més complicada, normalment s'apliquen aquestes regles només quan l'usuari ho demana explícitament. En el cas de la distributivitat, la funció que aplica aquesta regla s'acostuma a anomenar "expansió". La regla de reescriptura inversa, anomenada "factorització", requereix un algorisme no trivial i, per tant, esdevé una funció clau en els sistemes algebraics computacionals (vegeu Factorització dels polinomis).
Consideracions matemàtiques En aquesta secció considerem algunes qüestions matemàtiques fonamentals que sorgeixen tan bon punt es manipulen expressions mitjançant un ordinador. Considerem principalment el cas de les fraccions algebraiques en diverses variables. De fet, això no és una restricció perquè, a mesura que hom es troba amb funcions irracionals en el procés de simplificació d'una expressió, hom les considera com a noves incògnites. Per exemple, es pot veure com un polinomi en i .
Igualtat Hi ha dues nocions d'igualtat per les expressions matemàtiques. La igualtat sintàctica és la igualtat de les expressions en si, la qual cosa vol dir que s'escriuen (o es representen en un ordinador) de la mateixa manera. Com que verificar això és trivial, rarament té importància matemàtica, però és l'única igualtat que es pot comprovar fàcilment amb un ordinador. La igualtat semàntica es dona quan dues expressions diferents representen el mateix objecte matemàtic, com per exemple