Algebra informatica - Computer algebra

Integrazione simbolica della funzione algebrica f ( x ) = X/√ x ⁴ + 10 x ² - 96 x - 71utilizzando il sistema di computer algebra Axiom

In matematica e informatica , l'algebra informatica , chiamata anche calcolo simbolico o calcolo algebrico , è un'area scientifica che si riferisce allo studio e allo sviluppo di algoritmi e software per la manipolazione di espressioni matematiche e altri oggetti matematici . Sebbene l'algebra informatica possa essere considerata un sottocampo del calcolo scientifico , sono generalmente considerati campi distinti perché il calcolo scientifico è solitamente basato su calcoli numerici con numeri approssimativi in virgola mobile , mentre il calcolo simbolico enfatizza il calcolo esatto con espressioni contenenti variabili che non hanno un valore dato e vengono manipolati come simboli.

Le applicazioni software che eseguono calcoli simbolici sono chiamate sistemi di computer algebra , con il termine sistema alludendo alla complessità delle principali applicazioni che comprendono, almeno, un metodo per rappresentare dati matematici in un computer, un linguaggio di programmazione utente (solitamente diverso dal linguaggio utilizzato per l'implementazione), un gestore di memoria dedicato, un'interfaccia utente per l'input/output di espressioni matematiche, un ampio insieme di routine per eseguire operazioni usuali, come semplificazione di espressioni, differenziazione mediante regola della catena , fattorizzazione polinomiale , integrazione indefinita , ecc. .

L'algebra informatica è ampiamente utilizzata per sperimentare in matematica e per progettare le formule utilizzate nei programmi numerici. Viene utilizzato anche per calcoli scientifici completi, quando i metodi puramente numerici falliscono, come nella crittografia a chiave pubblica , o per alcuni problemi non lineari .

Terminologia

Alcuni autori distinguono l'algebra del computer dal calcolo simbolico usando quest'ultimo nome per riferirsi a tipi di calcolo simbolico diversi dal calcolo con formule matematiche . Alcuni autori usano il calcolo simbolico per l'aspetto informatico della materia e "computer algebra" per l'aspetto matematico. In alcune lingue il nome del campo non è una traduzione diretta del suo nome inglese. Tipicamente, si chiama calcul formel in francese, che significa "calcolo formale". Questo nome riflette i legami che questo campo ha con i metodi formali .

Il calcolo simbolico è stato anche chiamato, in passato, manipolazione simbolica , manipolazione algebrica , elaborazione simbolica , matematica simbolica o algebra simbolica , ma questi termini, che si riferiscono anche alla manipolazione non computazionale, non sono più usati in riferimento al computer algebra.

Comunità scientifica

Non esiste una società scientifica specifica per l'algebra informatica, ma questa funzione è assunta dal gruppo di interesse speciale dell'Associazione per le macchine informatiche denominato SIGSAM (Gruppo di interesse speciale sulla manipolazione simbolica e algebrica).

Ci sono diverse conferenze annuali sull'algebra informatica, la prima delle quali è ISSAC (International Symposium on Symbolic and Algebraic Computation), che è regolarmente sponsorizzata da SIGSAM.

Ci sono diverse riviste specializzate in computer algebra, la principale è Journal of Symbolic Computation fondata nel 1985 da Bruno Buchberger . Ci sono anche molte altre riviste che pubblicano regolarmente articoli di computer algebra.

Aspetti di informatica

Rappresentazione dei dati

Poiché il software numerico è altamente efficiente per il calcolo numerico approssimativo , è comune, nell'algebra dei computer, enfatizzare il calcolo esatto con dati rappresentati esattamente. Una rappresentazione così esatta implica che, anche quando la dimensione dell'output è piccola, i dati intermedi generati durante un calcolo possono crescere in modo imprevedibile. Questo comportamento è chiamato swell di espressione . Per ovviare a questo problema, vengono utilizzati vari metodi nella rappresentazione dei dati, nonché negli algoritmi che li manipolano.

Numeri

I soliti sistemi numerici utilizzati nel calcolo numerico sono numeri in virgola mobile e interi di dimensione limitata fissa. Nessuno di questi è conveniente per l'algebra del computer, a causa del rigonfiamento dell'espressione.

Pertanto, i numeri di base utilizzati nell'algebra dei computer sono gli interi dei matematici, comunemente rappresentati da una sequenza di cifre illimitata con segno in qualche base di numerazione , solitamente la base più grande consentita dalla parola macchina . Questi interi permettono di definire i numeri razionali , che sono frazioni irriducibili di due interi.

Programmare un'implementazione efficiente delle operazioni aritmetiche è un compito difficile. Pertanto, la maggior parte dei sistemi di computer algebra gratuiti e alcuni commerciali come Mathematica e Maple (software) utilizzano la libreria GMP , che è quindi uno standard de facto .

espressioni

Rappresentazione dell'espressione (8-6)*(3+1) come albero di Lisp , da una tesi di laurea del 1985.

Ad eccezione dei numeri e delle variabili , ogni espressione matematica può essere vista come il simbolo di un operatore seguito da una sequenza di operandi. Nel software di computer algebra, le espressioni sono solitamente rappresentate in questo modo. Questa rappresentazione è molto flessibile e molte cose che a prima vista non sembrano espressioni matematiche, possono essere rappresentate e manipolate come tali. Ad esempio, un'equazione è un'espressione con "=" come operatore, una matrice può essere rappresentata come un'espressione con "matrice" come operatore e le sue righe come operandi.

Anche i programmi possono essere considerati e rappresentati come espressioni con l'operatore “procedura” e, almeno, due operandi, la lista dei parametri e il corpo, che è esso stesso un'espressione con “corpo” come operatore e una sequenza di istruzioni come operandi. Al contrario, qualsiasi espressione matematica può essere vista come un programma. Ad esempio, l'espressione un + b può essere visto come un programma per l'aggiunta, con un e b come parametri. L'esecuzione di questo programma consiste nel valutare l'espressione per dati valori di un e b ; se non hanno alcun valore, cioè sono indeterminati, il risultato della valutazione è semplicemente il suo input.

Questo processo di valutazione ritardata è fondamentale nell'algebra informatica. Ad esempio, l'operatore “=” delle equazioni è anche, nella maggior parte dei sistemi di computer algebra, il nome del programma del test di uguaglianza: normalmente, la valutazione di un'equazione risulta in un'equazione, ma, quando è necessario un test di uguaglianza ,—o richiesto esplicitamente dall'utente tramite un comando "valutazione su booleano", o avviato automaticamente dal sistema nel caso di un test all'interno di un programma—quindi viene eseguita la valutazione su un valore booleano 0 o 1.

Poiché la dimensione degli operandi di un'espressione è imprevedibile e può cambiare durante una sessione di lavoro, la sequenza degli operandi è solitamente rappresentata come una sequenza di puntatori (come in Macsyma ) o voci in una tabella hash (come in Maple ).

Semplificazione

L'applicazione grezza delle regole base di differenziazione rispetto a x sull'espressione dà il risultato ${\displaystyle a^{x}}$

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

Chiaramente un'espressione così complicata non è accettabile, ed è necessaria una procedura di semplificazione non appena si lavora con espressioni generali.

Questa semplificazione viene normalmente effettuata mediante regole di riscrittura . Ci sono diverse classi di regole di riscrittura che devono essere considerate. La più semplice consiste nelle regole di riscrittura che riducono sempre la dimensione dell'espressione, come E − E → 0 o sin(0) → 0 . Sono applicati sistematicamente nei sistemi di computer algebra.

La prima difficoltà si verifica con operazioni associative come addizione e moltiplicazione. Il modo standard per trattare l'associatività è considerare che l'addizione e la moltiplicazione hanno un numero arbitrario di operandi, cioè che a + b + c è rappresentato come "+" ( a , b , c ) . Quindi a + ( b + c ) e ( a + b ) + c sono entrambi semplificati in "+" ( a , b , c ) , che viene visualizzato a + b + c . Che ne dici di a − b + c ? Per affrontare questo problema, il modo più semplice è riscrivere sistematicamente − E , E − F , E / F come, rispettivamente, (−1)⋅ E , E + (−1)⋅ F , E ⋅ F ⁻¹ . In altre parole, nella rappresentazione interna delle espressioni, non c'è sottrazione né divisione né meno unario, al di fuori della rappresentazione dei numeri.

Una seconda difficoltà si verifica con la commutatività dell'addizione e della moltiplicazione. Il problema è riconoscere rapidamente i termini simili per combinarli o cancellarli. Infatti il ​​metodo per trovare termini simili, consistente nel testare ogni coppia di termini, è troppo costoso per essere praticabile con somme e prodotti molto lunghi. Per risolvere questo problema, Macsyma ordina gli operandi di somme e prodotti con una funzione di confronto progettata in modo che termini simili siano in posizioni consecutive e quindi facilmente individuabili. In Maple , la funzione hash è progettata per generare collisioni quando vengono immessi termini simili, consentendo di combinarli non appena vengono introdotti. Questo design della funzione hash permette anche di riconoscere immediatamente le espressioni o sottoespressioni che compaiono più volte in un calcolo e di memorizzarle solo una volta. Ciò consente non solo di risparmiare spazio di memoria ma anche di velocizzare il calcolo, evitando la ripetizione delle stesse operazioni su più espressioni identiche.

Alcune regole di riscrittura a volte aumentano e talvolta diminuiscono la dimensione delle espressioni a cui vengono applicate. È il caso della distributività o delle identità trigonometriche . Ad esempio, la legge di distributività consente la riscrittura e poiché non esiste un modo per fare una buona scelta generale di applicare o meno tale regola di riscrittura, tali riscritture vengono eseguite solo quando esplicitamente richieste dall'utente. Per la distributività, la funzione del computer che applica questa regola di riscrittura è generalmente chiamata "espandi". La regola di riscrittura inversa, chiamata "fattore", richiede un algoritmo non banale, che è quindi una funzione chiave nei sistemi di computer algebra (vedi Fattorizzazione polinomiale ). ${\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.}$

Aspetti matematici

In questa sezione consideriamo alcune domande matematiche fondamentali che sorgono non appena si vogliono manipolare espressioni matematiche in un computer. Consideriamo principalmente il caso delle frazioni razionali multivariate . Questa non è una vera restrizione, perché, non appena le funzioni irrazionali che compaiono in un'espressione vengono semplificate, vengono solitamente considerate come nuove indeterminate. Per esempio,

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

è visto come un polinomio in e${\displaystyle \sin(x+y)}$${\displaystyle \log(z^{2}-5)}$

Uguaglianza

Ci sono due nozioni di uguaglianza per le espressioni matematiche . L' uguaglianza sintattica è l'uguaglianza delle espressioni che significa che sono scritte (o rappresentate in un computer) allo stesso modo. Essendo banale, l'uguaglianza sintattica è raramente considerata dai matematici, sebbene sia l'unica uguaglianza facilmente verificabile con un programma. L' uguaglianza semantica è quando due espressioni rappresentano lo stesso oggetto matematico, come in

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

È noto dal teorema di Richardson che potrebbe non esistere un algoritmo che decida se due espressioni che rappresentano numeri sono semanticamente uguali, se esponenziali e logaritmi sono ammessi nelle espressioni. Pertanto, l'uguaglianza (semantica) può essere verificata solo su alcune classi di espressioni come i polinomi e le frazioni razionali .

Per testare l'uguaglianza di due espressioni, invece di progettare algoritmi specifici, è normale mettere le espressioni in qualche forma canonica o mettere la loro differenza in una forma normale e testare l'uguaglianza sintattica del risultato.

A differenza della matematica normale, "forma canonica" e "forma normale" non sono sinonimi nell'algebra dei computer. Una forma canonica è tale che due espressioni in forma canonica sono semanticamente uguali se e solo se sono sintatticamente uguali, mentre una forma normale è tale che un'espressione in forma normale è semanticamente zero solo se è sintatticamente zero. In altre parole, zero ha una rappresentazione univoca mediante espressioni in forma normale.

Le forme normali sono generalmente preferite nell'algebra informatica per diversi motivi. In primo luogo, le forme canoniche possono essere più costose da calcolare rispetto alle forme normali. Ad esempio, per mettere un polinomio in forma canonica, si deve espandere per distributività ogni prodotto, mentre non è necessario con una forma normale (vedi sotto). In secondo luogo, può accadere, come per le espressioni che coinvolgono i radicali, che una forma canonica, se esiste, dipenda da alcune scelte arbitrarie e che queste scelte possano essere diverse per due espressioni che sono state calcolate indipendentemente. Ciò può rendere impraticabile l'uso di una forma canonica.

Storia

All'inizio dell'algebra dei computer, intorno al 1970, quando gli algoritmi noti da tempo furono installati per la prima volta sui computer, si rivelarono altamente inefficienti. Pertanto, gran parte del lavoro dei ricercatori nel campo consisteva nel rivisitare l' algebra classica per renderla efficace e scoprire algoritmi efficienti per implementare questa efficacia. Un tipico esempio di questo tipo di lavoro è il calcolo dei massimi comun divisori polinomiali , necessario per semplificare le frazioni. Sorprendentemente, il classico algoritmo di Euclide si è rivelato inefficiente per i polinomi su campi infiniti, e quindi è stato necessario sviluppare nuovi algoritmi. Lo stesso valeva anche per gli algoritmi classici dell'algebra lineare .

Guarda anche

• Dimostrazione di teoremi automatizzati
• Prova assistita da computer
• Geometria algebrica computazionale
• Sistema di computer algebra
• Controllo delle prove
• Controllo del modello
• Calcolo simbolico-numerico
• Simulazione simbolica
• Intelligenza artificiale simbolica

Riferimenti

Ulteriori letture

Per una definizione dettagliata del soggetto:

• Calcolo simbolico (un editoriale) , Bruno Buchberger , Journal of Symbolic Computation (1985) 1, pp. 1-6.

Per i libri di testo dedicati all'argomento:

• Davenport, James H. ; Siret, Yvon; Tournier, Evelyne (1988). Computer algebra: sistemi e algoritmi per il calcolo algebrico . Tradotto dal francese da A. Davenport e JH Davenport. stampa accademica. ISBN 978-0-12-204230-0.
• von zur Gathen, Gioacchino; Gerhard, Jürgen (2003). Computer algebra moderna (seconda ed.). Cambridge University Press. ISBN 0-521-82646-2.
• Geddes, KO; Czapor, SR; Labahn, G. (1992). "Algoritmi per Computer Algebra" . doi : 10.1007/b102438 . ISBN 978-0-7923-9259-0. Citare il diario richiede |journal=( aiuto )
• Buchberger, Bruno; Collins, George Edwin; Loos, Rüdiger; Albrecht, Rudolf, ed. (1983). "Computer Algebra" . Supplementi di informatica. 4 . doi : 10.1007/978-3-7091-7551-4 . ISBN 978-3-211-81776-6. Citare il diario richiede |journal=( aiuto )