En matemáticas e informática , [1] álgebra informática , también llamada computación simbólica o computación algebraica , es un área científica que se refiere al estudio y desarrollo de algoritmos y software para manipular expresiones matemáticas y otros objetos matemáticos . Aunque el álgebra informática podría considerarse un subcampo de la informática científica , generalmente se consideran campos distintos porque la informática científica suele basarse en cálculos numéricos con números aproximados de coma flotante , mientras que el cálculo simbólico enfatiza el cálculo exacto con expresiones que contienen variables que no tienen un valor determinado y son manipulados como símbolos.
Las aplicaciones de software que realizan cálculos simbólicos se denominan sistemas de álgebra informática , aludiendo el término sistema a la complejidad de las principales aplicaciones que incluyen, al menos, un método para representar datos matemáticos en una computadora, un lenguaje de programación de usuario (generalmente diferente del lenguaje utilizado para la implementación), un administrador de memoria dedicado, una interfaz de usuario para la entrada/salida de expresiones matemáticas, un gran conjunto de rutinas para realizar operaciones habituales, como simplificación de expresiones, diferenciación usando la regla de la cadena , factorización polinomial , integración indefinida , etc.
El álgebra informática se utiliza ampliamente para experimentar en matemáticas y diseñar las fórmulas que se utilizan en programas numéricos. También se utiliza para cálculos científicos completos, cuando fallan los métodos puramente numéricos, como en la criptografía de clave pública , o para algunos problemas no lineales .
Algunos autores distinguen el álgebra informática del cálculo simbólico utilizando este último nombre para referirse a tipos de cálculo simbólico distintos del cálculo con fórmulas matemáticas . Algunos autores utilizan la computación simbólica para el aspecto informático de la materia y el "álgebra informática" para el aspecto matemático. [2] En algunos idiomas, el nombre del campo no es una traducción directa de su nombre en inglés. Normalmente, en francés se llama calcul formel , que significa "cálculo formal". Este nombre refleja los vínculos que tiene este campo con los métodos formales .
En el pasado, también se ha hecho referencia a la computación simbólica como manipulación simbólica , manipulación algebraica , procesamiento simbólico , matemáticas simbólicas o álgebra simbólica , pero estos términos, que también se refieren a la manipulación no computacional, ya no se utilizan en referencia a la informática. álgebra.
No existe una sociedad científica específica del álgebra informática, pero esta función la asume el grupo de interés especial de la Asociación de Maquinaria de Computación denominado SIGSAM (Grupo de Interés Especial en Manipulación Simbólica y Algebraica). [3]
Hay varias conferencias anuales sobre álgebra informática, siendo la principal el ISSAC (Simposio Internacional sobre Computación Simbólica y Algebraica), que es patrocinado regularmente por SIGSAM. [4]
Hay varias revistas especializadas en álgebra informática, siendo la principal la Journal of Symbolic Computation, fundada en 1985 por Bruno Buchberger . [5] También hay varias otras revistas que publican regularmente artículos sobre álgebra informática. [6]
Como el software numérico es muy eficiente para el cálculo numérico aproximado , es común, en álgebra informática, enfatizar el cálculo exacto con datos exactamente representados. Una representación tan exacta implica que, incluso cuando el tamaño de la salida es pequeño, los datos intermedios generados durante un cálculo pueden crecer de forma impredecible. Este comportamiento se llama expresión hinchada . [7] Para obviar este problema, se utilizan diversos métodos en la representación de los datos, así como en los algoritmos que los manipulan. [8]
Los sistemas numéricos habituales utilizados en el cálculo numérico son los números de coma flotante y los números enteros de un tamaño acotado fijo. Ninguno de estos es conveniente para el álgebra informática, debido al aumento de expresión. [9]
Por lo tanto, los números básicos utilizados en álgebra informática son los números enteros de los matemáticos, comúnmente representados por una secuencia ilimitada de dígitos con signo en alguna base de numeración , generalmente la base más grande permitida por la palabra de máquina . Estos números enteros permiten definir los números racionales , que son fracciones irreducibles de dos números enteros.
Programar una implementación eficiente de las operaciones aritméticas es una tarea difícil. Por lo tanto, la mayoría de los sistemas informáticos de álgebra gratuitos y algunos comerciales como Mathematica y Maple , [10] [11] utilizan la biblioteca GMP , que es, por tanto, un estándar de facto .
Excepto los números y las variables , cada expresión matemática puede verse como el símbolo de un operador seguido de una secuencia de operandos. En el software de álgebra informática, las expresiones suelen representarse de esta manera. Esta representación es muy flexible y muchas cosas que a primera vista no parecen expresiones matemáticas, pueden representarse y manipularse como tales. Por ejemplo, una ecuación es una expresión con "=" como operador, una matriz se puede representar como una expresión con "matriz" como operador y sus filas como operandos.
Incluso los programas pueden considerarse y representarse como expresiones con el operador "procedimiento" y, al menos, dos operandos, la lista de parámetros y el cuerpo, que es a su vez una expresión con "cuerpo" como operador y una secuencia de instrucciones como operandos. Por el contrario, cualquier expresión matemática puede verse como un programa. Por ejemplo, la expresión a + b puede verse como un programa para la suma, con a y b como parámetros. La ejecución de este programa consiste en evaluar la expresión para valores dados de a y b ; si no se les da ningún valor, el resultado de la evaluación es simplemente su entrada.
Este proceso de evaluación retrasada es fundamental en el álgebra informática. Por ejemplo, el operador "=" de las ecuaciones es también, en la mayoría de los sistemas de álgebra informática, el nombre del programa de la prueba de igualdad: normalmente, la evaluación de una ecuación da como resultado una ecuación, pero, cuando se necesita una prueba de igualdad , ya sea solicitado explícitamente por el usuario a través de un comando de "evaluación a un resultado booleano", o iniciado automáticamente por el sistema en el caso de una prueba dentro de un programa, luego se ejecuta la evaluación a un resultado booleano.
Como el tamaño de los operandos de una expresión es impredecible y puede cambiar durante una sesión de trabajo, la secuencia de los operandos generalmente se representa como una secuencia de punteros (como en Macsyma ) [13] o entradas en una tabla hash (como en Arce ).
La aplicación cruda de las reglas básicas de diferenciación con respecto a x en la expresión da el resultado
Generalmente se desea una expresión más simple que esta y se necesita simplificación cuando se trabaja con expresiones generales.
Esta simplificación normalmente se realiza mediante la reescritura de reglas . [14] Hay varias clases de reglas de reescritura que deben considerarse. Las más simples son reglas que siempre reducen el tamaño de la expresión, como E − E → 0 o sin(0) → 0 . Se aplican sistemáticamente en sistemas de álgebra informática.
Se produce una dificultad con operaciones asociativas como la suma y la multiplicación. La forma estándar de lidiar con la asociatividad es considerar que la suma y la multiplicación tienen un número arbitrario de operandos, es decir, que a + b + c se representa como "+"( a , b , c ) . Por lo tanto, a + ( b + c ) y ( a + b ) + c se simplifican a "+"( a , b , c ) , que se muestra a + b + c . En el caso de expresiones como a − b + c , la forma más sencilla es reescribir sistemáticamente − E , E − F , E / F como, respectivamente, (−1)⋅ E , E + (−1)⋅ F , mi ⋅ F −1 . Es decir, en la representación interna de las expresiones, no hay resta ni división ni menos unario, fuera de la representación de los números.
Otra dificultad surge con la conmutatividad de la suma y la multiplicación. El problema es reconocer rápidamente los términos similares para poder combinarlos o cancelarlos. Probar cada par de términos es costoso con sumas y productos muy largos. Para solucionar este problema, Macsyma clasifica los operandos de sumas y productos en un orden que coloca los términos similares en lugares consecutivos, lo que permite una fácil detección. En Maple , una función hash está diseñada para generar colisiones cuando se ingresan términos similares, lo que permite combinarlos tan pronto como se introducen. Esto permite que las subexpresiones que aparecen varias veces en un cálculo se reconozcan inmediatamente y se almacenen solo una vez. Esto ahorra memoria y acelera el cálculo al evitar la repetición de las mismas operaciones en expresiones idénticas.
Algunas reglas de reescritura a veces aumentan y otras veces reducen el tamaño de las expresiones a las que se aplican. Este es el caso de la distributividad o identidades trigonométricas . Por ejemplo, la ley de distributividad permite la reescritura y, como no hay forma de hacer una buena elección general sobre si aplicar o no dicha regla de reescritura, dicha reescritura se realiza sólo cuando el usuario la invoca explícitamente. Para la distributividad, la función informática que aplica esta regla de reescritura suele denominarse "expandir". La regla de reescritura inversa, llamada "factor", requiere un algoritmo no trivial, que por tanto es una función clave en los sistemas de álgebra informática (consulte Factorización polinomial ).
Algunas preguntas matemáticas fundamentales surgen cuando uno quiere manipular expresiones matemáticas en una computadora. Consideramos principalmente el caso de las fracciones racionales multivariadas . Esto no es una restricción real, porque, tan pronto como se simplifican las funciones irracionales que aparecen en una expresión, normalmente se consideran nuevas indeterminadas. Por ejemplo,
se ve como un polinomio en y
Hay dos nociones de igualdad para expresiones matemáticas . La igualdad sintáctica es la igualdad de su representación en una computadora. Esto es fácil de probar en un programa. La igualdad semántica es cuando dos expresiones representan el mismo objeto matemático, como en
Se sabe por el teorema de Richardson que puede no existir un algoritmo que decida si dos expresiones que representan números son semánticamente iguales si se permiten exponenciales y logaritmos en las expresiones. En consecuencia, la igualdad (semántica) puede comprobarse sólo en algunas clases de expresiones como los polinomios y las fracciones racionales .
Para probar la igualdad de dos expresiones, en lugar de diseñar algoritmos específicos, se suele poner las expresiones en alguna forma canónica o poner su diferencia en una forma normal , y probar la igualdad sintáctica del resultado.
En álgebra informática, "forma canónica" y "forma normal" no son sinónimos. [15] Una forma canónica es tal que dos expresiones en forma canónica son semánticamente iguales si y sólo si son sintácticamente iguales, mientras que una forma normal es tal que una expresión en forma normal es semánticamente cero sólo si es sintácticamente cero. En otras palabras, el cero tiene una representación única como expresión en forma normal.
Las formas normales suelen preferirse en álgebra informática por varias razones. En primer lugar, las formas canónicas pueden ser más costosas de calcular que las formas normales. Por ejemplo, para poner un polinomio en forma canónica, hay que expandir cada producto mediante distributividad , mientras que no es necesario con una forma normal (ver más abajo). En segundo lugar, puede darse el caso, como ocurre con las expresiones que involucran radicales, que una forma canónica, si existe, dependa de algunas elecciones arbitrarias y que estas elecciones puedan ser diferentes para dos expresiones que se han calculado de forma independiente. Esto puede hacer impracticable el uso de una forma canónica.
Los primeros sistemas de álgebra informática, como el ENIAC de la Universidad de Pensilvania , dependían de computadoras humanas o programadores para reprogramarlo entre cálculos, manipular sus numerosos módulos físicos (o paneles) y alimentar su lector de tarjetas IBM. [16] Las matemáticas se encargaron de la mayor parte de la programación de cálculos guiados por humanos de ENIAC: Jean Jennings , Marlyn Wescoff , Ruth Lichterman , Betty Snyder , Frances Bilas y Kay McNulty lideraron dichos esfuerzos. [17]
En 1960, John McCarthy exploró una extensión de funciones recursivas primitivas para calcular expresiones simbólicas a través del lenguaje de programación Lisp mientras estaba en el Instituto de Tecnología de Massachusetts . [18] Aunque su serie sobre "Funciones recursivas de expresiones simbólicas y su cálculo por máquina" quedó incompleta, [19] McCarthy y sus contribuciones a la programación de inteligencia artificial y al álgebra informática a través de Lisp ayudaron a establecer el Proyecto MAC en el Instituto de Tecnología de Massachusetts y el organización que más tarde se convirtió en el Laboratorio de IA de Stanford (SAIL) en la Universidad de Stanford , cuya competencia facilitó un desarrollo significativo en álgebra informática a lo largo de finales del siglo XX.
Los primeros esfuerzos en computación simbólica, en las décadas de 1960 y 1970, enfrentaron desafíos relacionados con la ineficiencia de algoritmos conocidos desde hace mucho tiempo cuando se transfirieron a sistemas de álgebra informática. [20] Los predecesores del Proyecto MAC, como ALTRAN , buscaron superar las limitaciones algorítmicas a través de avances en hardware e intérpretes, mientras que los esfuerzos posteriores se dirigieron hacia la optimización del software. [21]
Gran parte del trabajo de los investigadores en este campo consistió en revisar el álgebra clásica para aumentar su eficacia y al mismo tiempo desarrollar algoritmos eficientes para su uso en álgebra informática. Un ejemplo de este tipo de trabajo es el cálculo del máximo común divisor polinómico , una tarea necesaria para simplificar fracciones y un componente esencial del álgebra informática. Los algoritmos clásicos para este cálculo, como el algoritmo de Euclides , resultaron ineficientes en campos infinitos; Los algoritmos del álgebra lineal enfrentaron luchas similares. [22] Por lo tanto, los investigadores se dedicaron a descubrir métodos para reducir polinomios (como los de un anillo de números enteros o un dominio de factorización único ) a una variante computable eficientemente mediante un algoritmo euclidiano.
Para una definición detallada del tema:
Para libros de texto dedicados al tema:
