Calcul formel
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Consultez la liste des tâches à accomplir en page de discussion.
En mathématiques et en informatique, le calcul formel, aussi appelé calcul symbolique ou calcul algébrique, est un domaine scientifique qui concerne l'étude et le développement des algorithmes et des logiciels pour manipuler des expressions et des objets mathématiques. Bien que le calcul formel puisse être considéré comme une sous-discipline du calcul scientifique, ces deux domaines sont généralement distingués, car le calcul scientifique est basé sur le calcul numérique avec des nombres flottants 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 définie et sont manipulées comme des symboles.
Les logiciels de calcul formel incluent des méthodes pour représenter des données mathématiques dans un ordinateur, un langage de programmation (généralement différent de celui utilisé pour l'implémentation), un gestionnaire de mémoire dédié, une interface utilisateur pour l'entrée/sortie des expressions mathématiques et un ensemble de routines pour effectuer les opérations usuelles, telles que la simplification des expressions, la dérivation, la factorisation de polynômes, l'intégration indéfinie, etc.
Le calcul formel est largement utilisé pour expérimenter en mathématiques et pour concevoir des formules utilisées dans les programmes numériques. Il est également utilisé pour des calculs scientifiques, lorsque les méthodes purement numériques échouent, comme en cryptographie à clé publique ou pour certains problèmes non-linéaires.
Terminologie
[modifier | modifier le code]Certains auteurs distinguent le calcul formel du calcul symbolique, ce dernier terme désignant les types de calcul symbolique autres que ceux effectués avec des formules mathématiques. Certains auteurs utilisent le terme calcul symbolique pour l'aspect informatique du sujet et calcul formel pour l'aspect mathématique[1], ce nom reflète les liens que ce domaine a avec les méthodes formelles.
Le calcul symbolique a aussi été appelé, dans le passé, manipulation symbolique, manipulation algébrique, traitement symbolique, mathématiques symboliques ou algèbre symbolique, mais ces termes, qui se référaient aussi à des manipulations non computationnelles, ne sont plus utilisés en référence au calcul formel.
Communauté scientifique
[modifier | modifier le code]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 spécial de l'Association for Computing Machinery nommé SIGSAM (Special Interest Group on Symbolic and Algebraic Manipulation)[2].
Il existe plusieurs conférences annuelles sur le calcul formel, la principale étant ISSAC (International Symposium on Symbolic and Algebraic Computation), qui est régulièrement sponsorisée par SIGSAM[3].
Il existe plusieurs revues spécialisées dans le calcul formel, la principale étant le Journal of Symbolic Computation fondé en 1985 par Bruno Buchberger[4]. Il existe également plusieurs autres revues qui publient régulièrement des articles sur le calcul formel[5].
Aspects informatiques
[modifier | modifier le code]Représentation des données
[modifier | modifier le code]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. Cette représentation exacte implique que, même lorsque la taille de la sortie est petite, les données intermédiaires générées au cours d'un calcul peuvent croître de manière imprévisible. Ce comportement est appelé gonflement des expressions[6]. Pour atténuer ce problème, diverses méthodes sont utilisées dans la représentation des données, ainsi que dans les algorithmes qui les manipulent[7].
Histoire
[modifier | modifier le code]Calcul formel guidé par l'homme
[modifier | modifier le code]Les premiers systèmes de calcul formel, tels que l'ENIAC à l'Université de Pennsylvanie, dépendaient des calculatrices humaines ou des programmeurs pour le reprogrammer entre les calculs, manipuler ses nombreux modules physiques (ou panneaux) et alimenter son lecteur de cartes IBM[8].
Problèmes historiques
[modifier | modifier le code]Une grande partie du travail des chercheurs dans ce domaine a consisté à revisiter l'algèbre classique pour augmenter son efficacité tout en développant des algorithmes efficaces pour le calcul formel. Un exemple de ce type de travail est le calcul des plus grands communs diviseurs des polynômes, une tâche nécessaire pour simplifier les fractions et un composant essentiel du calcul formel. Les algorithmes classiques pour ce calcul, comme l'algorithme d'Euclide, se sont révélés inefficaces sur les corps infinis ; les algorithmes issus de algèbre linéaire ont rencontré des difficultés similaires[9].
Algorithmes utilisés en calcul formel
[modifier | modifier le code]
Quelques logiciels de calcul formels
[modifier | modifier le code]| Logiciel | Créateur | Date de sortie | Licence logicielle | Open source | Langage de programmation | Fonctionnalités, domaines |
|---|---|---|---|---|---|---|
| SageMath | William Stein et collaborateurs | 2005 | GPL |  Oui
|
Python, Cython | Généraliste |
| SymPy | Ondřej Čertík, Aaron Meurer et collaborateurs | 2007 | BSD | Oui
|
Python | Bibliothèque Python, généraliste |
| REDUCE (en) | Anthony C. Hearn et collaborateurs | 1968 | BSD modifiée | Oui
|
RLISP | Applications en physique |
| PARI/GP | Henri Cohen, Karim Belabas et collaborateurs | 1985 | GPL | Oui
|
C | Théorie des nombres |
| GAP | GAP Group | 1986 | GPL | Oui
|
Langage GAP | Théorie des groupes, combinatoire, automates |
| Singular | Wolfram Decker, Gert-Martin Greuel, Gerhard Pfister et Hans Schönemann | 1986 | GPL | Oui
|
C++ | Algèbre commutative, théorie des anneaux, géométrie algébrique |
| CoCoA (en) | John Abbott, Anna Maria Bigatti et Lorenzo Robbiano | 1988 | GPL | Oui
|
C++ | Algèbre commutative, polynômes, base de Gröbner |
| Xcas | Bernard Parisse | 2000 | GPL | Oui
|
C++ | Représentations graphiques, géométrie dynamique, tableur, éducationnel |
| Wolfram | Stephen Wolfram, Wolfram Research | 1988 | Propriétaire |  Non
|
Wolfram Language, C/C++ | Généraliste |
| Maple | Université de Waterloo, Maplesoft | 1982 | Propriétaire | Non
|
Langage Maple, C | Généraliste |
Voir aussi
[modifier | modifier le code]- Démonstration automatique de théorèmes
- Preuve assistée par ordinateur
- Géométrie algébrique computationnelle (en)
- Système de calcul formel
- Analyseur différentiel
- Assistant de preuve
- Vérification de modèles
- Calcul symbolique-numérique (en)
- Simulation symbolique (en)
- Intelligence artificielle symbolique
Références
[modifier | modifier le code]- ↑ (en) Stephen M. Watt, « Making Computer Algebra More Symbolic (Invited) », (ISBN 9788468983813, OCLC 496720771), p. 43–49
- ↑ Site officiel de SIGSAM
- ↑ « Liste des conférences SIGSAM » [archive du ] (consulté le )
- ↑ Joel S. Cohen, Computer Algebra and Symbolic Computation: Mathematical Methods, AK Peters, (ISBN 978-1-56881-159-8, lire en ligne), 14
- ↑ Liste des revues SIGSAM
- ↑ « Lecture 12: Rational Functions and Conversions — Introduction to Symbolic Computation 1.7.6 documentation », sur homepages.math.uic.edu (consulté le )
- ↑ Sylvain Neut, Michel Petitot et Raouf Dridi, « La vision géométrique d'Élie Cartan ou comment éviter le gonflement des expressions », Journal of Symbolic Computation, polynomial System Solving in honor of Daniel Lazard, vol. 44, no 3, , p. 261–270 (ISSN 0747-7171, DOI 10.1016/j.jsc.2007.04.006, lire en ligne)
- ↑ "ENIAC in Action: What it Was and How it Worked". ENIAC: Celebrating Penn Engineering History. University of Pennsylvania. Consulté le 3 décembre 2023.
- ↑ E. Kaltofen, « Factorisation des polynômes », Computing Supplementa, Vienne, Springer Vienne, (ISBN 978-3-211-81776-6, DOI 10.1007/978-3-7091-7551-4_8, consulté le ), p. 95–113
Liens externes
[modifier | modifier le code]- Pour une définition détaillée du sujet
- Bruno Buchberger, « Calcul symbolique (éditorial) », Journal of Symbolic Computation, vol. 1, no 1, , p. 1–6 (DOI 10.1016/S0747-7171(85)80025-0, lire en ligne)
- Pour les manuels consacrés au sujet
- James H. Davenport, Yvon Siret et Èvelyne Tournier (Traduit du français par A. Davenport et J. H. Davenport), Calcul formel: Systèmes et algorithmes de calcul algébrique, Academic Press, (ISBN 978-0-12-204230-0)
- Joachim von zur Gathen et Jürgen Gerhard, Modern computer algebra, Cambridge University Press, (ISBN 0-521-82646-2)
- K. O. Geddes, S. R. Czapor et G. Labahn, Algorithms for Computer Algebra, (ISBN 978-0-7923-9259-0, DOI 10.1007/b102438, Bibcode 1992afca.book.....G, lire en ligne
) - Computer Algebra: Symbolic and Algebraic Computation, vol. 4, (ISBN 978-3-211-81776-6, DOI 10.1007/978-3-7091-7551-4, S2CID 5221892, lire en ligne )
- Notice dans un dictionnaire ou une encyclopédie généraliste :
