Algèbre informatique

Apprendre encore plus La section principale de cet article contient des informations qui ne sont pas incluses ailleurs dans l’article . ( mai 2020 )Si l’information est appropriée pour le titre de l’article, cette information doit également être incluse dans le corps de l’article. (Découvrez comment et quand supprimer ce modèle de message)

En mathématiques et en informatique , ^[1] le calcul formel , également appelé calcul symbolique ou calcul algébrique , est un domaine scientifique qui fait référence à l’étude et au développement d’ algorithmes et de logiciels permettant de manipuler des expressions mathématiques et d’autres objets mathématiques . Bien que l’algèbre informatique puisse être considérée comme un sous-domaine du Calcul scientifique , ils sont généralement considérés comme des domaines distincts car le Calcul scientifique est généralement basé sur le Calcul numérique avec des nombres à virgule flottante approximatifs ., tandis que le calcul symbolique met l’accent sur le calcul exact avec des expressions contenant des variables qui n’ont pas de valeur donnée et sont manipulées comme des symboles.

Intégration symbolique de la fonction algébrique f ( x ) =X/√ x ⁴ + 10 x ² – 96 x – 71en utilisant le système de calcul formel Axiom

Les applications logicielles qui effectuent des calculs symboliques sont appelées systèmes de calcul formel , le terme système faisant allusion à la complexité des principales applications qui incluent, au moins, une méthode pour représenter des données mathématiques dans un ordinateur, un langage de programmation utilisateur (généralement différent du langage utilisé pour l’implémentation), un gestionnaire de mémoire dédié, une interface utilisateur pour l’entrée/sortie d’expressions mathématiques, un large ensemble de routines pour effectuer des opérations habituelles, comme la simplification d’expressions, la différenciation à l’aide d’ une règle de chaîne , la Factorisation polynomiale , l’Intégration indéfinie , etc. .

Le calcul formel est largement utilisé pour expérimenter en mathématiques et pour concevoir les formules utilisées dans les programmes numériques. Il est également utilisé pour des calculs scientifiques complets, lorsque les méthodes purement numériques échouent, comme dans la Cryptographie à clé publique , ou pour certains problèmes non linéaires .

Terminologie

Certains auteurs distinguent l’algèbre informatique du calcul symbolique en utilisant ce dernier nom pour désigner des types de calcul symbolique autres que le calcul avec des formules mathématiques . Certains auteurs utilisent le calcul symbolique pour l’aspect informatique du sujet et le “calcul formel” pour l’aspect Mathématique. ^[2] Dans certaines langues, le nom du champ n’est pas une traduction directe de son nom anglais. Typiquement, on l’appelle calcul formel en français, ce qui signifie « calcul formel ». Ce nom reflète les liens de ce domaine avec les méthodes formelles .

Le calcul symbolique a également été appelé, dans le passé, manipulation symbolique , manipulation algébrique , traitement symbolique , mathématiques symboliques ou algèbre symbolique , mais ces termes, qui font également référence à la manipulation non computationnelle, ne sont plus utilisés en référence à l’informatique. algèbre.

Communauté scientifique

Il n’existe pas de société savante spécifique au calcul formel, mais cette fonction est assumée par le groupe d’intérêt de l’ Association for Computing Machinery nommé SIGSAM (Special Interest Group on Symbolic and Algebraic Manipulation). ^[3]

Il existe plusieurs conférences annuelles sur l’algèbre informatique, la première étant l’ ISSAC (Symposium international sur le calcul symbolique et algébrique), qui est régulièrement parrainé par le SIGSAM. ^[4]

Il existe plusieurs revues spécialisées en calcul formel, la principale étant Journal of Symbolic Computation fondée en 1985 par Bruno Buchberger . ^[5] Il existe également plusieurs autres revues qui publient régulièrement des articles en calcul formel. ^[6]

Aspect informatique

Apprendre encore plus Cette section ne cite aucune source . ( novembre 2012 )Veuillez aider à améliorer cette section en ajoutant des citations à des sources fiables . Le matériel non sourcé peut être contesté et supprimé . (Découvrez comment et quand supprimer ce modèle de message)

Représentation des données

Comme les logiciels numériques sont très efficaces pour le Calcul numérique approximatif , il est courant, en calcul formel, de mettre l’accent sur le calcul exact avec des données exactement représentées. Une telle représentation exacte implique que, même lorsque la taille de la sortie est petite, les données intermédiaires générées lors d’un calcul peuvent croître de manière imprévisible. Ce comportement est appelé expression swell . Pour obvier à ce problème, diverses méthodes sont utilisées dans la représentation des données, ainsi que dans les algorithmes qui les manipulent.

Nombres

Les systèmes de nombres usuels utilisés en Calcul numérique sont les nombres à virgule flottante et les nombres Entiers de taille bornée fixe. Aucun de ceux-ci n’est pratique pour l’algèbre informatique, en raison de la houle d’expression. ^{[ citation nécessaire ]}

Par conséquent, les nombres de base utilisés en calcul formel sont les nombres Entiers des mathématiciens, généralement représentés par une séquence de chiffres signée illimitée dans une base de numération , généralement la plus grande base autorisée par le Mot machine . Ces Entiers permettent de définir les nombres rationnels , qui sont des fractions irréductibles de deux Entiers.

Programmer une implémentation efficace des opérations arithmétiques est une tâche difficile. Par conséquent, la plupart des systèmes de calcul formel gratuits et certains systèmes commerciaux tels que Mathematica et Maple (logiciel) , utilisent la bibliothèque GMP , qui est donc une norme de facto .

Expressions Représentation de l’expression (8-6)*(3+1) sous la forme d’un arbre Lisp , d’après un mémoire de maîtrise de 1985. ^[7]

À l’exception des nombres et des variables , chaque expression Mathématique peut être considérée comme le symbole d’un opérateur suivi d’une séquence d’opérandes. Dans les logiciels de calcul formel, les expressions sont généralement représentées de cette manière. Cette représentation est très flexible, et de nombreuses choses qui ne semblent pas être des expressions mathématiques à première vue peuvent être représentées et manipulées comme telles. Par exemple, une équation est une expression avec “=” comme opérateur, une matrice peut être représentée comme une expression avec “matrice” comme opérateur et ses lignes comme opérandes.

Même les programmes peuvent être considérés et représentés comme des expressions avec l’opérateur “procédure” et, au moins, deux opérandes, la liste des paramètres et le corps, qui est lui-même une expression avec “corps” comme opérateur et une séquence d’instructions comme opérandes. Inversement, toute expression Mathématique peut être considérée comme un programme. Par exemple, l’expression a + b peut être vue comme un programme pour l’addition, avec a et b comme paramètres. L’exécution de ce programme consiste à évaluer l’expression pour des valeurs données de a et b ; s’ils n’ont aucune valeur — c’est-à-dire qu’ils sont indéterminés —, le résultat de l’évaluation est simplement son entrée.

Ce processus d’évaluation différée est fondamental en calcul formel. Par exemple, l’opérateur “=” des équations est aussi, dans la plupart des systèmes de calcul formel, le nom du programme du test d’égalité : normalement, l’évaluation d’une équation aboutit à une équation, mais, lorsqu’un test d’égalité est nécessaire , – soit explicitement demandé par l’utilisateur via une commande « évaluation vers un booléen », soit lancé automatiquement par le système dans le cas d’un test à l’intérieur d’un programme – alors l’évaluation vers un booléen 0 ou 1 est exécutée.

Comme la taille des opérandes d’une expression est imprévisible et peut changer au cours d’une session de travail, la séquence des opérandes est généralement représentée comme une séquence de pointeurs (comme dans Macsyma ) ou d’entrées dans une table de hachage (comme dans Maple ).

Simplification

L’application brute des règles de base de différenciation par rapport à x sur l’expression un X {displaystyle a^{x}} $a^{x}$ $a^{x}$ donne le résultat

X ⋅ un X − 1 ⋅ 0 + a x ⋅ ( 1 ⋅ log ⁡ a + x ⋅ 0 a ) . {displaystyle xcdot a^{x-1}cdot 0+a^{x}cdot left(1cdot log a+xcdot {frac {0}{a}}right) .} $xcdot a^{x-1}cdot 0+a^{x}cdot left(1cdot log a+xcdot {frac {0}{a}}right).$ $xcdot a^{x-1}cdot 0+a^{x}cdot left(1cdot log a+xcdot {frac {0}{a}}right).$

Learn more.

Calcul lambda

Jul 14, 2022

Calcul

Jun 26, 2022

Une expression aussi compliquée n’est évidemment pas acceptable, et une procédure de simplification s’impose dès que l’on travaille avec des expressions générales.

Cette simplification se fait normalement par des règles de réécriture . ^[8] Il existe plusieurs classes de règles de réécriture qui doivent être prises en compte. La plus simple consiste dans les règles de réécriture qui réduisent toujours la taille de l’expression, comme E − E → 0 ou sin(0) → 0 . Ils sont systématiquement appliqués dans les systèmes de calcul formel.

La première difficulté survient avec les opérations associatives comme l’addition et la multiplication. La manière standard de traiter l’associativité est de considérer que l’addition et la multiplication ont un nombre arbitraire d’opérandes, c’est-à-dire que a + b + c est représenté par “+”( a , b , c ) . Ainsi a + ( b + c ) et ( a + b ) + c sont tous deux simplifiés en “+” ( a , b , c ), qui est affiché a + b + c . Qu’en est-il de a − b + c ? Pour traiter ce problème, le plus simple est de réécrire systématiquement − E , E − F , E / F comme, respectivement, (−1)⋅ E , E + (−1)⋅ F , E ⋅ F ⁻¹ . Autrement dit, dans la représentation interne des expressions, il n’y a ni soustraction ni division ni moins unaire, en dehors de la représentation des nombres.

Une deuxième difficulté survient avec la Commutativité de l’addition et de la multiplication. Le problème est de reconnaître rapidement les termes semblables afin de les combiner ou de les annuler. En effet, la méthode de recherche de termes semblables, consistant à tester chaque couple de termes, est trop coûteuse pour être praticable avec des sommes et des produits très longs. Pour résoudre ce problème, Macsyma trie les opérandes des sommes et des produits avec une fonction de comparaison qui est conçue pour que les mêmes termes soient à des endroits consécutifs, et donc facilement détectés. Dans Maple , la fonction de hachageest conçu pour générer des collisions lorsque des termes similaires sont saisis, permettant de les combiner dès qu’ils sont introduits. Cette conception de la fonction de hachage permet aussi de reconnaître immédiatement les expressions ou sous-expressions qui apparaissent plusieurs fois dans un calcul et de ne les stocker qu’une seule fois. Cela permet non seulement de gagner de la place mémoire mais aussi d’accélérer les calculs, en évitant la répétition des mêmes opérations sur plusieurs expressions identiques.

Certaines règles de réécriture augmentent parfois et parfois diminuent la taille des expressions auxquelles elles s’appliquent. C’est le cas de la Distributivité ou des identités trigonométriques . Par exemple, la loi de Distributivité permet de réécrire ( x + 1 ) 4 → x 4 + 4 x 3 + 6 x 2 + 4 x + 1 {displaystyle (x+1)^{4}rightarrow x^{4}+4x^{3}+6x^{2}+4x+1} $(x+1)^{4}rightarrow x^{4}+4x^{3}+6x^{2}+4x+1$ $(x+1)^{4}rightarrow x^{4}+4x^{3}+6x^{2}+4x+1$ et ( x − 1 ) ( x 4 + x 3 + x 2 + x + 1 ) → x 5 − 1. {displaystyle (x-1)(x^{4}+x^{3}+x^{2}+x+1)rightarrow x^{5}-1.} $(x-1)(x^{4}+x^{3}+x^{2}+x+1)rightarrow x^{5}-1.$ $(x-1)(x^{4}+x^{3}+x^{2}+x+1)rightarrow x^{5}-1.$ Comme il n’existe aucun moyen de faire un bon choix général d’application ou non d’une telle règle de réécriture, de telles réécritures ne sont effectuées que lorsqu’elles sont explicitement demandées par l’utilisateur. Pour la Distributivité, la fonction informatique qui applique cette règle de réécriture est généralement appelée “expand”. La règle de réécriture inverse, appelée “facteur”, nécessite un algorithme non trivial, qui est donc une fonction clé dans les systèmes de calcul formel (voir Factorisation polynomiale ).

Aspects mathématiques

Dans cette section, nous considérons quelques questions mathématiques fondamentales qui se posent dès que l’on veut manipuler des expressions mathématiques dans un ordinateur. Nous considérons principalement le cas des fractions rationnelles multivariées . Ce n’est pas une réelle restriction, car, dès que les fonctions irrationnelles apparaissant dans une expression sont simplifiées, elles sont généralement considérées comme de nouvelles indéterminées. Par example,

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

est considéré comme un polynôme en sin ⁡ ( x + y ) {displaystyle sin(x+y)} et log ⁡ ( z 2 − 5 ) {displaystyle log(z^{2}-5)} $log(z^{2}-5)$ $log(z^{2}-5)$

Égalité

Il existe deux notions d’égalité pour les expressions mathématiques . L’ égalité syntaxique est l’égalité des expressions ce qui signifie qu’elles sont écrites (ou représentées dans un ordinateur) de la même manière. Étant triviale, l’égalité syntaxique est rarement considérée par les mathématiciens, bien que ce soit la seule égalité facile à tester avec un programme. L’ égalité sémantique se produit lorsque deux expressions représentent le même objet Mathématique, comme dans

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

On sait d’après le théorème de Richardson qu’il peut ne pas exister d’algorithme qui décide si deux expressions représentant des nombres sont sémantiquement égales, si les exponentielles et les logarithmes sont autorisés dans les expressions. Par conséquent, l’égalité (sémantique) ne peut être testée que sur certaines classes d’expressions telles que les polynômes et les fractions rationnelles .

Pour tester l’égalité de deux expressions, au lieu de concevoir des algorithmes spécifiques, il est courant de mettre les expressions sous une forme canonique ou de mettre leur différence sous une forme normale , et de tester l’égalité syntaxique du résultat.

Contrairement aux mathématiques habituelles, “forme canonique” et “forme normale” ne sont pas synonymes en calcul formel. ^[9] Une forme canonique est telle que deux expressions sous forme canonique sont sémantiquement égales si et seulement si elles sont syntaxiquement égales, tandis qu’une forme normale est telle qu’une expression sous forme normale n’est sémantiquement nulle que si elle est syntaxiquement nulle. En d’autres termes, zéro a une représentation unique par des expressions sous forme normale.

Les formes normales sont généralement préférées en calcul formel pour plusieurs raisons. Premièrement, les formes canoniques peuvent être plus coûteuses à calculer que les formes normales. Par exemple, pour mettre un polynôme sous forme canonique, il faut développer par Distributivité chaque produit, alors que ce n’est pas nécessaire avec une forme normale (voir ci-dessous). Deuxièmement, il se peut, comme pour les expressions comportant des radicaux, qu’une forme canonique, si elle existe, dépende de choix arbitraires et que ces choix puissent être différents pour deux expressions calculées indépendamment. Cela peut rendre impraticable l’utilisation d’une forme canonique.

Histoire

Au début de l’algèbre informatique, vers 1970, lorsque les algorithmes connus de longue date ont été mis pour la première fois sur des ordinateurs, ils se sont avérés très inefficaces. ^[10] Ainsi, une grande partie du travail des chercheurs du domaine a consisté à revisiter l’ algèbre classique afin de la rendre efficace et de découvrir des algorithmes efficaces pour mettre en œuvre cette efficacité. Un exemple typique de ce type de travail est le calcul des plus grands diviseurs communs polynomiaux , qui est nécessaire pour simplifier les fractions. Étonnamment, l’algorithme classique d’Euclides’est avéré inefficace pour les polynômes sur des corps infinis, et donc de nouveaux algorithmes ont dû être développés. Il en était de même pour les algorithmes classiques de l’algèbre linéaire .

Voir également

Démonstrateur de théorème automatisé
Preuve assistée par ordinateur
Géométrie algébrique computationnelle
Système d’algèbre informatique
Vérificateur de preuve
Vérificateur de modèle
Calcul symbolique-numérique
Simulation symbolique
Intelligence artificielle symbolique

Références

^ “Association ACM en algèbre informatique” .
^ Watt, Stephen M. (2006). Rendre l’algèbre informatique plus symbolique (invité) (PDF) . Proc. Transgressive Computing 2006 : Une conférence en l’honneur de Jean Della Dora, (TC 2006). p. 43–49.
^ Site officiel SIGSAM
^ “Liste SIGSAM des conférences” . Archivé de l’original le 2013-08-08 . Récupéré le 15/11/2012 .
^ Cohen, Joel S. (2003). Algèbre informatique et calcul symbolique : méthodes mathématiques . AK Peters, Ltd. p. 14 . ISBN 978-1-56881-159-8.
^ Liste SIGSAM des revues
^ Kevin G. Cassidy (décembre 1985). La faisabilité de la récupération automatique du stockage avec l’exécution simultanée de programmes dans un environnement LISP (PDF) (mémoire de maîtrise). École supérieure navale, Monterey / CA. Ici : p.15
^ Buchberger, Bruno et Rudiger Loos. « Simplification algébrique ». Algèbre informatique. Springer, Vienne, 1982. 11-43.
^ Davenport, JH, Siret, Y., & Tournier, É. (1988). Algèbre informatique. Londres : Académique.
^ Kaltofen, Erich (1982), “Factorisation des polynômes”, dans Buchberger, B.; Loos, R.; Collins, G. (eds.), Computer Algebra , Springer Verlag, pp. 95–113, CiteSeerX 10.1.1.39.7916

Lectures complémentaires

Pour une définition détaillée du sujet :

Calcul symbolique (un éditorial) , Bruno Buchberger , Journal of Symbolic Computation (1985) 1, pp. 1–6.

Pour les manuels consacrés au sujet :

Davenport, James H. ; Siret, Yvon; Tournier, Evelyne (1988). Calcul formel : systèmes et algorithmes pour le calcul algébrique . Traduit du français par A. Davenport et JH Davenport. Presse académique. ISBN 978-0-12-204230-0.
von zur Gathen, Joachim ; Gerhard, Jürgen (2003). Algèbre informatique moderne (deuxième éd.). La presse de l’Universite de Cambridge. ISBN 0-521-82646-2.
Geddes, KO ; Czapor, SR; En ligneLabahn, G. (1992). Algorithmes pour l’algèbre informatique . Bibcode : 1992afca.book…..G . doi : 10.1007/b102438 . ISBN 978-0-7923-9259-0.
Buchberger, Bruno; Collins, George Edwin; Loos, Rudiger ; Albrecht, Rudolf, éd. (1983). Algèbre informatique . Suppléments informatiques. Vol. 4. doi : 10.1007/978-3-7091-7551-4 . ISBN 978-3-211-81776-6. S2CID 5221892 .