b'\n_START_ARTICLE_\nComputaci\xc3\xb3 algebraica\n_START_PARAGRAPH_\nEn matem\xc3\xa0tiques i ci\xc3\xa8ncies de la computaci\xc3\xb3, la computaci\xc3\xb3 algebraica, tamb\xc3\xa9 anomenada computaci\xc3\xb3 simb\xc3\xb2lica, \xc3\xa9s una disciplina cient\xc3\xadfica que es dedica a l\'estudi i desenvolupament d\'algorismes i programari per a la manipulaci\xc3\xb3 d\'expressions matem\xc3\xa0tiques i altres objectes matem\xc3\xa0tics. Encara que, parlant amb propietat, la computaci\xc3\xb3 algebraica hauria de ser una subdisciplina de la computaci\xc3\xb3 cient\xc3\xadfica, normalment se les considera disciplines diferents, perqu\xc3\xa8 la computaci\xc3\xb3 cient\xc3\xadfica es basa normalment en el c\xc3\xa0lcul num\xc3\xa8ric amb aritm\xc3\xa8tica en coma flotant pels nombres (que per definici\xc3\xb3 esdevenen aproximats), mentre que la computaci\xc3\xb3 algebraica posa especial \xc3\xa8mfasi en la computaci\xc3\xb3 exacta d\'expressions que contenen variables a les quals no se\'ls d\xc3\xb3na cap valor concret, sin\xc3\xb3 que es manipulen com a s\xc3\xadmbols (d\'aqu\xc3\xad el nom de computaci\xc3\xb3 simb\xc3\xb2lica)._NEWLINE_Els programaris que realitzen c\xc3\xa0lculs simb\xc3\xb2lics 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\xc3\xadnim s\xc3\xb3n: un m\xc3\xa8tode per representar dades matem\xc3\xa0tiques en un ordinador, un llenguatge de programaci\xc3\xb3 per l\'usuari (que normalment \xc3\xa9s diferent del llenguatge emprat per a la implementaci\xc3\xb3 del sistema), un gestor de mem\xc3\xb2ria dedicat, una interf\xc3\xadcie d\'usuari per a l\'entrada i la sortida d\'expressions matem\xc3\xa0tiques, un conjunt ampli de subrutines per realitzar les operacions usuals, com simplificaci\xc3\xb3 d\'expressions, derivades que usen la regla de la cadena, factoritzaci\xc3\xb3 de polinomis, integraci\xc3\xb3 indefinida, etc._NEWLINE_En els inicis de la computaci\xc3\xb3 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\xc3\xad a revisar l\'\xc3\xa0lgebra cl\xc3\xa0ssica per tal de fer-la m\xc3\xa9s efectiva i per descobrir algorismes eficients per tal d\'implementar aquesta efici\xc3\xa8ncia. Un exemple t\xc3\xadpic n\'\xc3\xa9s el c\xc3\xa0lcul del m\xc3\xa0xim com\xc3\xba divisor per polinomis, que \xc3\xa9s necessari per simplificar fraccions._NEWLINE_La computaci\xc3\xb3 algebraica s\'usa a bastament per dissenyar les f\xc3\xb3rmules utilitzades en programes num\xc3\xa8rics. Tamb\xc3\xa9 s\'usa en c\xc3\xa0lculs cient\xc3\xadfics complets, quan fallen els m\xc3\xa8todes purament num\xc3\xa8rics, com ara la criptografia de clau p\xc3\xbablica o alguns problemes no lineals.\n_START_SECTION_\nTerminologia\n_START_PARAGRAPH_\nAlguns autors distingeixen entre \xc3\xa0lgebra computacional i computaci\xc3\xb3 simb\xc3\xb2lica, i empren aquest darrer terme per referir-se a altres tipus de computaci\xc3\xb3 simb\xc3\xb2lica diferents de la computaci\xc3\xb3 amb f\xc3\xb3rmules matem\xc3\xa0tiques. Alguns autors empren computaci\xc3\xb3 simb\xc3\xb2lica per denominar la ci\xc3\xa8ncia de la computaci\xc3\xb3 referida a aquest tema, i "\xc3\xa0lgebra computacional" per l\'aspecte matem\xc3\xa0tic. En alguns idiomes, aquest terme no \xc3\xa9s una traducci\xc3\xb3 literal; per exemple, en franc\xc3\xa8s s\'anomena calcul formel, que significa "c\xc3\xa0lcul formal"._NEWLINE_En el passat, la computaci\xc3\xb3 simb\xc3\xb2lica s\'ha denominat com manipulaci\xc3\xb3 simb\xc3\xb2lica, manipulaci\xc3\xb3 algebraica, processament simb\xc3\xb2lic, matem\xc3\xa0tica simb\xc3\xb2lica o \xc3\xa0lgebra simb\xc3\xb2lica, per\xc3\xb2 aquests termes han caigut en des\xc3\xbas per referir-se a la computaci\xc3\xb3 simb\xc3\xb2lica, ja que denominen aspectes de manipulaci\xc3\xb3 no computacional.\n_START_SECTION_\nComunitat cient\xc3\xadfica\n_START_PARAGRAPH_\nNo hi ha cap societat cient\xc3\xadfica que es dediqui espec\xc3\xadficament a la computaci\xc3\xb3 algebraica, per\xc3\xb2 aquesta funci\xc3\xb3 est\xc3\xa0 assumida per l\'special interest group de l\'Association for Computing Machinery anomenat SIGSAM (Special Interest Group on Symbolic and Algebraic Manipulation; en angl\xc3\xa8s, Grup d\'Inter\xc3\xa8s Especial per la Manipulaci\xc3\xb3 Algebraica i Simb\xc3\xb2lica)._NEWLINE_Existeixen diverses confer\xc3\xa8ncies anuals sobre computaci\xc3\xb3 algebraica, la m\xc3\xa9s important d\'elles ISSAC (International Symposium on Symbolic and Algebraic Computation; en angl\xc3\xa8s, Simposi Internacional sobre Computaci\xc3\xb3 Simb\xc3\xb2lica i Algebraica), impulsada per SIGSAM._NEWLINE_Tamb\xc3\xa9 existeixen diverses publicacions especialitzades en computaci\xc3\xb3 algebraica, la m\xc3\xa9s important el Journal of Symbolic Computation fundada el 1985 per Bruno Buchberger. Altres publicacions publiquen de forma regular articles sobre computaci\xc3\xb3 algebraica.\n_START_SECTION_\nRepresentaci\xc3\xb3 de dades\n_START_PARAGRAPH_\nCom que els programaris de c\xc3\xa0lcul num\xc3\xa8ric s\xc3\xb3n altament eficients per realitzar c\xc3\xa0lculs aproximats, \xc3\xa9s for\xc3\xa7a com\xc3\xba, en computaci\xc3\xb3 algebraica, posar \xc3\xa8mfasi en realitzar c\xc3\xa0lculs exactes amb dades representades de forma exacta. Aquesta representaci\xc3\xb3 tan exacta implica que, encara que la grand\xc3\xa0ria de la sortida sigui petita, les dades interm\xc3\xa8dies generades durant un c\xc3\xa0lcul poden cr\xc3\xa9ixer d\'una forma impredictible. Aquest comportament s\'anomena inflor de l\'expressi\xc3\xb3 (en angl\xc3\xa8s, expression swell). Per subsanar aquest problema, hom usa diversos m\xc3\xa8todes en la representaci\xc3\xb3 de les dades, aix\xc3\xad com en els algorismes que les manipulen.\n_START_SECTION_\nNombres\n_START_PARAGRAPH_\nEls sistemes num\xc3\xa8rics habituals emprats en an\xc3\xa0lisi num\xc3\xa8rica s\xc3\xb3n o b\xc3\xa9 la representaci\xc3\xb3 de nombres en coma flotant o els enters d\'una grand\xc3\xa0ria m\xc3\xa0xima fixada, que s\'anomenen de forma impr\xc3\xb2pia enters per la majoria de llenguatges de programaci\xc3\xb3. Cap d\'ells \xc3\xa9s convenient per la computaci\xc3\xb3 algebraica, a causa de l\'efecte d\'inflor de l\'expressi\xc3\xb3._NEWLINE_En lloc d\'aix\xc3\xb2, els nombres b\xc3\xa0sics emprats en computaci\xc3\xb3 algebraica s\xc3\xb3n els enters matem\xc3\xa0tics, normalment representats com a una seq\xc3\xbc\xc3\xa8ncia de d\xc3\xadgits en alguna base de numeraci\xc3\xb3, normalment la major base permesa per la paraula de la m\xc3\xa0quina. Aquests enters permeten definir els nombres racionals, que s\xc3\xb3n fraccions irredu\xc3\xafbles de dos enters._NEWLINE_El proc\xc3\xa9s de programar una implementaci\xc3\xb3 eficient de les operacions aritm\xc3\xa8tiques \xc3\xa9s una tasca dif\xc3\xadcil. Per tant, la majoria de sistemes algebraics computacionals i alguns de comercials, com Maple, usen la llibreria GMP, que ha esdevingut un est\xc3\xa0ndard de facto.\n_START_SECTION_\nExpressions\n_START_PARAGRAPH_\nExcepte per nombres i variables, tota expressi\xc3\xb3 matem\xc3\xa0tica es pot veure com el s\xc3\xadmbol d\'un operador seguit d\'una seq\xc3\xbc\xc3\xa8ncia d\'operands. En programaris de computaci\xc3\xb3 algebraica, les expressions s\'acostumen a representar d\'aquesta manera. Aquesta representaci\xc3\xb3 \xc3\xa9s molt flexible, i molts termes que no semblen una expressi\xc3\xb3 matem\xc3\xa0tica a primer cop d\'ull, es poden representar i manipular com a tals. Per exemple, una equaci\xc3\xb3 \xc3\xa9s una expressi\xc3\xb3 on l\'operador \xc3\xa9s "=", una matriu es pot representar com una expressi\xc3\xb3 amb l\'operador "matriu" i on les files i les columnes en s\xc3\xb3n els operands. _NEWLINE_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\xc3\xa0metres i el cos, que \xc3\xa9s al seu torn una expressi\xc3\xb3 amb l\'operador "cos" i una seq\xc3\xbc\xc3\xa8ncia d\'instruccions com a operands. Rec\xc3\xadprocament, qualsevol expressi\xc3\xb3 matem\xc3\xa0tica es pot veure com a un programa. Per exemple, l\'expressi\xc3\xb3 a+b es pot veure com un programa per l\'addici\xc3\xb3, on a i b en s\xc3\xb3n els par\xc3\xa0metres. Executar aquest programa consisteix a avaluar l\'expressi\xc3\xb3 per valors donats de a i b; si no tenen cap valor (\xc3\xa9s a dir, s\xc3\xb3n indeterminats), el resultat de l\'avaluaci\xc3\xb3 \xc3\xa9s simplement l\'entrada. _NEWLINE_El proc\xc3\xa9s d\'avaluaci\xc3\xb3 diferida \xc3\xa9s fonamental en computaci\xc3\xb3 algebraica. Per exemple, l\'operador "=" de les equacions tamb\xc3\xa9 \xc3\xa9s, en la majoria de sistemes algebraics computacionals, el nom del programa per la prova d\'igualtat: normalment, l\'avaluaci\xc3\xb3 d\'una equaci\xc3\xb3 resulta en una equaci\xc3\xb3; per\xc3\xb2, quan es necessita una prova d\'igualtat, llavors l\'avaluaci\xc3\xb3 retorna un 0 o un 1 booleans. _NEWLINE_Com que la grand\xc3\xa0ria dels operands d\'una expressi\xc3\xb3 \xc3\xa9s impredictible i pot canviar durant una sessi\xc3\xb3 de treball, la seq\xc3\xbc\xc3\xa8ncia d\'operands se sol representar com una seq\xc3\xbc\xc3\xa8ncia de punters (com en Macsyma) o com a entrades d\'una taula hash (com en Maple).\n_START_SECTION_\nConsideracions matem\xc3\xa0tiques\n_START_PARAGRAPH_\nEn aquesta secci\xc3\xb3 considerem algunes q\xc3\xbcestions matem\xc3\xa0tiques fonamentals que sorgeixen tan bon punt es manipulen expressions mitjan\xc3\xa7ant un ordinador. Considerem principalment el cas de les fraccions algebraiques en diverses variables. De fet, aix\xc3\xb2 no \xc3\xa9s una restricci\xc3\xb3 perqu\xc3\xa8, a mesura que hom es troba amb funcions irracionals en el proc\xc3\xa9s de simplificaci\xc3\xb3 d\'una expressi\xc3\xb3, hom les considera com a noves inc\xc3\xb2gnites. Per exemple,  es pot veure com un polinomi en  i .\n_START_SECTION_\nIgualtat\n_START_PARAGRAPH_\nHi ha dues nocions d\'igualtat per les expressions matem\xc3\xa0tiques. La igualtat sint\xc3\xa0ctica \xc3\xa9s 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\xc3\xb2 \xc3\xa9s trivial, rarament t\xc3\xa9 import\xc3\xa0ncia matem\xc3\xa0tica, per\xc3\xb2 \xc3\xa9s l\'\xc3\xbanica igualtat que es pot comprovar f\xc3\xa0cilment amb un ordinador. La igualtat sem\xc3\xa0ntica es d\xc3\xb3na quan dues expressions diferents representen el mateix objecte matem\xc3\xa0tic, com per exemple _NEWLINE_\xc3\x89s conegut que pot no existir un algorisme que decideixi si dues expressions s\xc3\xb3n sem\xc3\xa0nticament iguals, si es permet l\'\xc3\xbas de logaritmes i exponencials. Per tant, la igualtat (sem\xc3\xa0ntica) nom\xc3\xa9s es pot verificar en algunes classes d\'expressions, com ara els polinomis o les fraccions racionals._NEWLINE_Per tal de verificar la igualtat de dues expressions, en comptes de dissenyar un algorisme espec\xc3\xadfic, normalment es transformen les expressions en alguna forma can\xc3\xb2nica, o b\xc3\xa9 es reescriu la seva difer\xc3\xa8ncia en una forma normal, i llavors es verifica la igualtat sint\xc3\xa0cica del resultat._NEWLINE_Contr\xc3\xa0riament al que succeeix en les matem\xc3\xa0tiques en general, "forma can\xc3\xb2nica" i "forma normal" no s\xc3\xb3n sin\xc3\xb2nims en computaci\xc3\xb3 algebraica. Dues formes can\xc3\xb3niques de dues expressions s\xc3\xb3n sem\xc3\xa0nticament iguals si i nom\xc3\xa9s si s\xc3\xb3n sint\xc3\xa0cticament iguals. D\'altra banda, una expressi\xc3\xb3 en forma normal \xc3\xa9s sem\xc3\xa0nticament zero nom\xc3\xa9s si \xc3\xa9s sint\xc3\xa0cticament zero. En altres paraules, el zero t\xc3\xa9 una \xc3\xbanica representaci\xc3\xb3 per expressions en forma normal._NEWLINE_Habitualment, hom prefereix les formes normals a les formes can\xc3\xb2niques en l\'\xc3\xa0mbit de la computaci\xc3\xb3 algebraica. D\'una banda, les formes can\xc3\xb2niques poden ser m\xc3\xa9s costoses de calcular que les formes normals. Per exemple, per reescriure un polinomi en forma can\xc3\xb2nica, s\'ha de expandir cada producte mitjan\xc3\xa7ant la distributivitat, mentre que aix\xc3\xb2 no \xc3\xa9s necessari per a calcular la forma normal. Addicionalment, pot ser (per exemple en expressions amb radicals) que una forma can\xc3\xb2nica, si existeix, depengui d\'algunes eleccions arbitr\xc3\xa0ries, i aquestes eleccions poden variar per dues expressions que han estat calculades de forma independent. Aquest \xc3\xa9s un motiu perqu\xc3\xa8 l\'\xc3\xbas d\'una forma can\xc3\xb2nica sigui impracticable.'