Álgebra computacional - Computer algebra

Integração simbólica da função algébrica f ( x ) = x/√ x 4 + 10 x 2 - 96 x - 71usando o sistema de álgebra computacional Axiom

Em matemática e ciência da computação , álgebra computacional , também chamada de computação simbólica ou computação algébrica , é uma área científica que se refere ao estudo e desenvolvimento de algoritmos e software para manipular expressões matemáticas e outros objetos matemáticos . Embora a álgebra de computador possa ser considerada um subcampo da computação científica , eles são geralmente considerados como campos distintos porque a computação científica é geralmente baseada em computação numérica com números de ponto flutuante aproximados , enquanto a computação simbólica enfatiza a computação exata com expressões contendo variáveis que não têm valor dado e são manipulados como símbolos.

Os aplicativos de software que realizam cálculos simbólicos são chamados de sistemas de álgebra computacional , com o termo sistema aludindo à complexidade das principais aplicações que incluem, pelo menos, um método para representar dados matemáticos em um computador, uma linguagem de programação do usuário (geralmente diferente da linguagem usado para a implementação), um gerenciador de memória dedicado, uma interface de usuário para a entrada / saída de expressões matemáticas, um grande conjunto de rotinas para realizar operações usuais, como simplificação de expressões, diferenciação usando regra de cadeia , fatoração polinomial , integração indefinida , etc. .

A álgebra computacional é amplamente usada para fazer experiências em matemática e para projetar as fórmulas que são usadas em programas numéricos. Também é usado para cálculos científicos completos, quando métodos puramente numéricos falham, como na criptografia de chave pública , ou para alguns problemas não lineares .

Terminologia

Alguns autores distinguem a álgebra computacional da computação simbólica, usando o último nome para se referir a tipos de computação simbólica que não sejam a computação com fórmulas matemáticas . Alguns autores usam computação simbólica para o aspecto de ciência da computação do assunto e "álgebra de computador" para o aspecto matemático. Em alguns idiomas, o nome do campo não é uma tradução direta de seu nome em inglês. Normalmente, é chamado de calcul formel em francês, que significa "cálculo formal". Este nome reflete os laços que este campo tem com métodos formais .

A computação simbólica também foi referida, no passado, como manipulação simbólica , manipulação algébrica , processamento simbólico , matemática simbólica ou álgebra simbólica , mas esses termos, que também se referem à manipulação não computacional, não são mais usados ​​em referência ao computador álgebra.

Comunidade científica

Não existe sociedade erudita específica para álgebra computacional, mas essa função é assumida pelo grupo de interesse especial da Association for Computing Machinery denominado SIGSAM (Grupo de Interesse Especial em Manipulação Simbólica e Algébrica).

Existem várias conferências anuais sobre álgebra computacional, sendo a primeira o ISSAC (Simpósio Internacional de Computação Simbólica e Algébrica), que é regularmente patrocinado pelo SIGSAM.

Existem vários periódicos especializados em álgebra computacional, sendo o principal o Journal of Symbolic Computation, fundado em 1985 por Bruno Buchberger . Existem também vários outros periódicos que publicam regularmente artigos em álgebra da computação.

Aspectos da ciência da computação

Representação de dados

Como o software numérico é altamente eficiente para computação numérica aproximada , é comum, em álgebra computacional, enfatizar a computação exata com dados representados exatamente. Essa representação exata implica que, mesmo quando o tamanho da saída é pequeno, os dados intermediários gerados durante um cálculo podem crescer de forma imprevisível. Este comportamento é denominado aumento de expressão . Para contornar este problema, vários métodos são utilizados na representação dos dados, bem como nos algoritmos que os manipulam.

Números

Os sistemas de números usuais usados ​​em computação numérica são números de ponto flutuante e inteiros de um tamanho limitado limitado. Nada disso é conveniente para álgebra computacional, devido ao aumento da expressão.

Portanto, os números básicos usados ​​na álgebra computacional são os inteiros dos matemáticos, comumente representados por uma sequência ilimitada de dígitos com sinal em alguma base de numeração , geralmente a maior base permitida pela palavra de máquina . Esses inteiros permitem definir os números racionais , que são frações irredutíveis de dois inteiros.

Programar uma implementação eficiente das operações aritméticas é uma tarefa difícil. Portanto, a maioria dos sistemas de álgebra de computador gratuitos e alguns comerciais, como Mathematica e Maple (software) , usam a biblioteca GMP , que é, portanto, um padrão de fato .

Expressões

Representação da expressão (8-6) * (3 + 1) como árvore Lisp , de Dissertação de Mestrado de 1985.

Exceto para números e variáveis , cada expressão matemática pode ser vista como o símbolo de um operador seguido por uma seqüência de operandos. Em softwares de álgebra de computador, as expressões geralmente são representadas dessa maneira. Esta representação é muito flexível e muitas coisas que parecem não ser expressões matemáticas à primeira vista, podem ser representadas e manipuladas como tais. Por exemplo, uma equação é uma expressão com “=” como um operador, uma matriz pode ser representada como uma expressão com “matriz” como um operador e suas linhas como operandos.

Mesmo programas podem ser considerados e representados como expressões com operador “procedimento” e, pelo menos, dois operandos, a lista de parâmetros e o corpo, que é uma expressão com “corpo” como operador e uma sequência de instruções como operandos. Por outro lado, qualquer expressão matemática pode ser vista como um programa. Por exemplo, a expressão a + b pode ser vista como um programa de adição, com a e b como parâmetros. A execução deste programa consiste em avaliar a expressão para determinados valores de a e b ; se não tiverem nenhum valor - ou seja, são indeterminados -, o resultado da avaliação é simplesmente sua entrada.

Este processo de avaliação tardia é fundamental em álgebra computacional. Por exemplo, o operador “=” das equações é também, na maioria dos sistemas de álgebra computacional, o nome do programa do teste de igualdade: normalmente, a avaliação de uma equação resulta em uma equação, mas, quando um teste de igualdade é necessário , - quer explicitamente solicitado pelo usuário através de um comando “avaliação para um booleano”, ou automaticamente iniciado pelo sistema no caso de um teste dentro de um programa - então a avaliação para um booleano 0 ou 1 é executada.

Como o tamanho dos operandos de uma expressão é imprevisível e pode mudar durante uma sessão de trabalho, a sequência dos operandos é geralmente representada como uma sequência de ponteiros (como no Macsyma ) ou entradas em uma tabela hash (como no Maple ).

Simplificação

A aplicação bruta das regras básicas de diferenciação em relação ax na expressão dá o resultado

Uma expressão tão complicada claramente não é aceitável, e um procedimento de simplificação é necessário assim que se trabalha com expressões gerais.

Essa simplificação normalmente é feita por meio de regras de reescrita . Existem várias classes de regras de reescrita que devem ser consideradas. O mais simples consiste nas regras de reescrita que sempre reduzem o tamanho da expressão, como E - E → 0 ou sin (0) → 0 . Eles são aplicados sistematicamente em sistemas de álgebra computacional.

A primeira dificuldade ocorre com operações associativas como adição e multiplicação. A maneira padrão de lidar com a associatividade é considerar que a adição e a multiplicação têm um número arbitrário de operandos, ou seja, a + b + c é representado como "+" ( a , b , c ) . Assim, a + ( b + c ) e ( a + b ) + c são simplificados para "+" ( a , b , c ) , que é mostrado a + b + c . Que tal a - b + c ? Para lidar com este problema, a maneira mais simples é reescrever sistematicamente - E , E - F , E / F como, respectivamente, (−1) ⋅ E , E + (−1) ⋅ F , E ⋅ F −1 . Ou seja, na representação interna das expressões, não há subtração, nem divisão, nem menos unário, fora da representação dos números.

Uma segunda dificuldade ocorre com a comutatividade de adição e multiplicação. O problema é reconhecer rapidamente os termos semelhantes para combiná-los ou cancelá-los. Na verdade, o método para encontrar termos semelhantes, consistindo em testar cada par de termos, é muito caro para ser praticável com somas e produtos muito longos. Para resolver este problema, Macsyma ordena os operandos de somas e produtos com uma função de comparação que é projetada para que termos semelhantes fiquem em lugares consecutivos e, portanto, sejam facilmente detectados. No Maple , a função hash é projetada para gerar colisões quando termos semelhantes são inseridos, permitindo combiná-los assim que forem introduzidos. Este design da função hash permite também reconhecer imediatamente as expressões ou subexpressões que aparecem várias vezes em um cálculo e armazená-las apenas uma vez. Isso permite não apenas economizar espaço na memória, mas também acelerar o cálculo, evitando a repetição das mesmas operações em várias expressões idênticas.

Algumas regras de reescrita às vezes aumentam e às vezes diminuem o tamanho das expressões às quais são aplicadas. É o caso da distributividade ou identidades trigonométricas . Por exemplo, a lei da distributividade permite a reescrita e Como não há como fazer uma boa escolha geral de aplicar ou não essa regra de reescrita, tais reescritas são feitas apenas quando explicitamente solicitadas pelo usuário. Para a distributividade, a função do computador que aplica essa regra de reescrita é geralmente chamada de "expandir". A regra de reescrita reversa, chamada "fator", requer um algoritmo não trivial, que é, portanto, uma função chave em sistemas de álgebra de computador (veja Fatoração polinomial ).

Aspectos matemáticos

Nesta seção, consideramos algumas questões matemáticas fundamentais que surgem assim que se deseja manipular expressões matemáticas em um computador. Consideramos principalmente o caso das frações racionais multivariadas . Essa não é uma restrição real, pois, assim que as funções irracionais que aparecem em uma expressão são simplificadas, costumam ser consideradas como novas indeterminadas. Por exemplo,

é visto como um polinômio em e

Igualdade

Existem duas noções de igualdade para expressões matemáticas . A igualdade sintática é a igualdade das expressões, o que significa que são escritas (ou representadas em um computador) da mesma forma. Por ser trivial, a igualdade sintática raramente é considerada pelos matemáticos, embora seja a única igualdade fácil de testar com um programa. A igualdade semântica é quando duas expressões representam o mesmo objeto matemático, como em

Sabe-se do teorema de Richardson que pode não existir um algoritmo que decida se duas expressões representando números são semanticamente iguais, se exponenciais e logaritmos são permitidos nas expressões. Portanto, a igualdade (semântica) pode ser testada apenas em algumas classes de expressões, como os polinômios e as frações racionais .

Para testar a igualdade de duas expressões, em vez de projetar algoritmos específicos, é comum colocar as expressões em alguma forma canônica ou colocar sua diferença em uma forma normal e testar a igualdade sintática do resultado.

Ao contrário da matemática usual, "forma canônica" e "forma normal" não são sinônimos em álgebra computacional. Uma forma canônica é tal que duas expressões na forma canônica são semanticamente iguais se e somente se elas forem sintaticamente iguais, enquanto uma forma normal é tal que uma expressão na forma normal é semanticamente zero apenas se for sintaticamente zero. Em outras palavras, zero tem uma representação única por expressões na forma normal.

As formas normais são geralmente preferidas em álgebra computacional por várias razões. Em primeiro lugar, os formulários canônicos podem ser mais caros de calcular do que os formulários normais. Por exemplo, para colocar um polinômio na forma canônica, é necessário expandir por distributividade todos os produtos, embora não seja necessário com a forma normal (veja abaixo). Em segundo lugar, pode ser o caso, como para expressões envolvendo radicais, que uma forma canônica, se existe, depende de algumas escolhas arbitrárias e que essas escolhas podem ser diferentes para duas expressões que foram calculadas independentemente. Isso pode inviabilizar o uso de uma forma canônica.

História

No início da álgebra computacional, por volta de 1970, quando os algoritmos há muito conhecidos foram colocados em computadores pela primeira vez, eles se mostraram altamente ineficientes. Portanto, grande parte do trabalho dos pesquisadores da área consistiu em revisitar a álgebra clássica a fim de torná-la eficaz e descobrir algoritmos eficientes para implementar essa eficácia. Um exemplo típico desse tipo de trabalho é o cálculo dos maiores divisores comuns polinomiais , que é necessário para simplificar as frações. Surpreendentemente, o algoritmo clássico de Euclides revelou-se ineficiente para polinômios em campos infinitos e, portanto, novos algoritmos precisaram ser desenvolvidos. O mesmo também era verdade para os algoritmos clássicos da álgebra linear .

Veja também

Referências

Leitura adicional

Para uma definição detalhada do assunto:

Para livros didáticos dedicados ao assunto: