Álgebra computacional

La sección de introducción de este artículo contiene información que no está incluida en ninguna otra parte del artículo . Si la información es apropiada para la introducción del artículo, esta información también debe incluirse en el cuerpo del artículo. ( Mayo de 2020 ) ( Aprenda cómo y cuándo eliminar este mensaje )

En matemáticas e informática , ^[1] el álgebra computacional , 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 computacional podría considerarse un subcampo de la computación científica , generalmente se consideran como campos distintos porque la computación científica generalmente se basa en el cálculo numérico con números de punto flotante aproximados , mientras que la computación simbólica enfatiza el cálculo exacto con expresiones que contienen variables que no tienen un valor dado y se manipulan como símbolos.

Las aplicaciones de software que realizan cálculos simbólicos se denominan sistemas de álgebra computacional , haciendo alusión con 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 (normalmente diferente del lenguaje utilizado para la implementación), un gestor 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 mediante la regla de la cadena , factorización de polinomios , integración indefinida , etc.

El álgebra computacional se utiliza ampliamente para experimentar en matemáticas y diseñar las fórmulas que se utilizan en los programas numéricos. También se utiliza para cálculos científicos completos, cuando los métodos puramente numéricos fallan, como en la criptografía de clave pública , o para algunos problemas no lineales .

Algunos autores distinguen el álgebra computacional 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 el cálculo simbólico para el aspecto informático de la materia y "álgebra computacional" 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, se le llama calcul formel en francés, que significa "cálculo formal". Este nombre refleja los vínculos que este campo tiene con los métodos formales .

En el pasado, también se hacía referencia al cálculo simbólico 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 al álgebra computacional.

No existe una sociedad científica específica para el álgebra computacional, sino que esta función la asume el grupo de interés especial de la Association for Computing Machinery llamado SIGSAM (Special Interest Group on Symbolic and Algebraic Manipulation). ^[3]

Existen varias conferencias anuales sobre álgebra computacional, siendo la más importante el ISSAC (Simposio Internacional sobre Computación Simbólica y Algebraica), que es patrocinado regularmente por SIGSAM. ^[4]

Existen varias revistas especializadas en álgebra computacional, siendo la más importante Journal of Symbolic Computation, fundada en 1985 por Bruno Buchberger . ^[5] También existen otras revistas que publican regularmente artículos sobre álgebra computacional. ^[6]

Como el software numérico es altamente eficiente para el cálculo numérico aproximado , es común, en álgebra computacional, enfatizar el cálculo exacto con datos representados exactamente. Tal representación 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 una manera impredecible. Este comportamiento se llama oleaje de expresión . ^[7] Para obviar este problema, se utilizan varios métodos en la representación de los datos, así como en los algoritmos que los manipulan. ^[8]

Los sistemas de numeración que se utilizan habitualmente en los cálculos numéricos son los números de punto flotante y los números enteros de tamaño fijo y acotado. Ninguno de ellos resulta conveniente para el álgebra computacional, debido a la expansión de las expresiones. ^[9]

Por tanto, los números básicos utilizados en el álgebra computacional 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 , normalmente la base más grande permitida por la palabra 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 ello, la mayoría de los sistemas de álgebra computacional gratuitos y algunos comerciales como Mathematica y Maple ^[10] [ ^11] utilizan la biblioteca GMP , que es por tanto un estándar de facto .

A excepción de los números y las variables , toda expresión matemática puede ser vista como el símbolo de un operador seguido de una secuencia de operandos. En el software de álgebra computacional, las expresiones se representan generalmente 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 puede representarse 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 en sí mismo una expresión con "cuerpo" como operador y una secuencia de instrucciones como operandos. A la inversa, cualquier expresión matemática puede considerarse como un programa. Por ejemplo, la expresión a + b puede considerarse 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 diferida es fundamental en el álgebra computacional. Por ejemplo, el operador "=" de las ecuaciones es también, en la mayoría de los sistemas de álgebra computacional, el nombre del programa del test de igualdad: normalmente, la evaluación de una ecuación da como resultado una ecuación, pero, cuando se necesita un test de igualdad, ya sea solicitado explícitamente por el usuario mediante un comando de "evaluación a un booleano", o iniciado automáticamente por el sistema en el caso de un test dentro de un programa, entonces 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 Maple ).

La aplicación cruda de las reglas básicas de diferenciación con respecto a x en la expresión da el resultado $Estilo de visualización a^{x}}$

${\displaystyle x\cdot a^{x-1}\cdot 0+a^{x}\cdot \left(1\cdot \log a+x\cdot {\frac {0}{a}}\right).}$

Generalmente se desea una expresión más simple que ésta y se necesita simplificación cuando se trabaja con expresiones generales.

Esta simplificación se realiza normalmente mediante reglas de reescritura . ^[14] Hay varias clases de reglas de reescritura a tener en cuenta. Las más simples son las 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 computacional.

Una dificultad ocurre con operaciones asociativas como la suma y la multiplicación. La forma estándar de tratar 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 como 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 , E ⋅ F ⁻¹ . En otras palabras, en la representación interna de las expresiones, no hay resta ni división ni resta unaria, fuera de la representación de los números.

Otra dificultad se presenta con la conmutatividad de la suma y la multiplicación. El problema es reconocer rápidamente los términos iguales para combinarlos o cancelarlos. Probar cada par de términos es costoso con sumas y productos muy largos. Para solucionar esto, Macsyma ordena los operandos de sumas y productos en un orden que coloca los términos iguales en lugares consecutivos, lo que permite una fácil detección. En Maple , se diseña una función hash para generar colisiones cuando se ingresan términos iguales, 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 a veces disminuyen el tamaño de las expresiones a las que se aplican. Este es el caso de la distributividad o las identidades trigonométricas . Por ejemplo, la ley de distributividad permite reescribir y Como no hay forma de hacer una buena elección general de aplicar o no tal regla de reescritura, dicha reescritura se realiza solo cuando es invocada explícitamente por el usuario. Para la distributividad, la función de computadora que aplica esta regla de reescritura se llama típicamente "expandir". La regla de reescritura inversa, llamada "factorizar", requiere un algoritmo no trivial, que es por lo tanto una función clave en los sistemas de álgebra computacional (ver Factorización de polinomios ).${\displaystyle (x+1)^{4}\rightarrow x^{4}+4x^{3}+6x^{2}+4x+1}$${\displaystyle (x-1)(x^{4}+x^{3}+x^{2}+x+1)\rightarrow x^{5}-1.}$

Cuando se quieren manipular expresiones matemáticas en un ordenador surgen algunas cuestiones matemáticas fundamentales. Consideraremos 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, suelen considerarse como nuevas indeterminadas. Por ejemplo,

${\displaystyle (\sin(x+y)^{2}+\log(z^{2}-5))^{3}}$

se considera un polinomio en y${\displaystyle \sin(x+y)}$${\displaystyle \log(z^{2}-5)}$

Existen 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

${\displaystyle (x+y)^{2}=x^{2}+2xy+y^{2}.}$

Se sabe, a partir del teorema de Richardson , que no puede 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 solo 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, es habitual 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 computacional, "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 solo si son sintácticamente iguales, mientras que una forma normal es tal que una expresión en forma normal es semánticamente cero solo si es sintácticamente cero. En otras palabras, cero tiene una representación única como expresión en forma normal.

Las formas normales suelen preferirse en álgebra computacional 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, uno tiene que desarrollar cada producto a través de la distributividad , mientras que no es necesario con una forma normal (ver más abajo). En segundo lugar, puede darse el caso, como en el caso de expresiones que involucran radicales, de 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 computacional, 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 femeninas manejaron la mayoría de los cálculos guiados por humanos de la programación 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 Tecnológico de Massachusetts . ^[18] Aunque su serie sobre "Funciones recursivas de expresiones simbólicas y su cálculo por máquina" permaneció incompleta, ^[19] McCarthy y sus contribuciones a la programación de inteligencia artificial y al álgebra computacional a través de Lisp ayudaron a establecer el Proyecto MAC en el Instituto Tecnológico de Massachusetts y la organización que luego se convirtió en el Laboratorio de IA de Stanford (SAIL) en la Universidad de Stanford , cuya competencia facilitó un desarrollo significativo en álgebra computacional a lo largo de fines 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 hacía mucho tiempo cuando se los trasladaba a sistemas de álgebra computacional. ^[20] Los predecesores del Proyecto MAC, como ALTRAN , buscaron superar las limitaciones algorítmicas mediante avances en hardware e intérpretes, mientras que los esfuerzos posteriores se orientaron hacia la optimización del software. ^[21]

Una gran parte del trabajo de los investigadores en el campo consistió en revisar el álgebra clásica para aumentar su efectividad mientras se desarrollaban algoritmos eficientes para su uso en álgebra computacional. Un ejemplo de este tipo de trabajo es el cálculo del máximo común divisor de polinomios , una tarea necesaria para simplificar fracciones y un componente esencial del álgebra computacional. Los algoritmos clásicos para este cálculo, como el algoritmo de Euclides , demostraron ser ineficientes sobre cuerpos infinitos; los algoritmos del álgebra lineal enfrentaron dificultades similares. ^[22] Por lo tanto, los investigadores recurrieron al descubrimiento de métodos para reducir polinomios (como aquellos sobre un anillo de números enteros o un dominio de factorización único ) a una variante eficientemente computable a través de un algoritmo euclidiano.

• Demostrador automático de teoremas
• Prueba asistida por computadora
• Geometría algebraica computacional
• Sistema de álgebra computacional
• Analizador diferencial
• Comprobador de pruebas
• Comprobador de modelos
• Cálculo simbólico-numérico
• Simulación simbólica
• Inteligencia artificial simbólica

Para una definición detallada del tema:

• Buchberger, Bruno (1985). "Computación simbólica (Un editorial)" (PDF) . Revista de computación simbólica . 1 (1): 1–6. doi :10.1016/S0747-7171(85)80025-0.

Para los libros de texto dedicados al tema:

• Davenport, James H. ; Siret, Yvon; Tournier, Èvelyne (1988). Álgebra informática: sistemas y algoritmos para computación algebraica . Traducido del francés por A. Davenport y JH Davenport. Academic Press. ISBN 978-0-12-204230-0.
• von zur Gathen, Joachim; Gerhard, Jürgen (2003). Álgebra informática moderna (2ª ed.). Prensa de la Universidad de Cambridge. ISBN 0-521-82646-2.
• Geddes, KO; Czapor, SR; Labahn, G. (1992). Algoritmos para álgebra computacional . Bibcode :1992afca.book.....G. doi :10.1007/b102438. ISBN 978-0-7923-9259-0.
• Buchberger, Bruno; Collins, George Edwin; Loos, Rüdiger; Albrecht, Rudolf, eds. (1983). Álgebra informática: computación simbólica y algebraica . Suplemento de informática. vol. 4. doi :10.1007/978-3-7091-7551-4. ISBN 978-3-211-81776-6. Número de identificación del sujeto  5221892.