Calcul formel
domaine des mathématiques et de l’informatique qui s’intéresse aux algorithmes opérant sur des objets de nature mathématique par le biais de représentations finies et exactes
From Wikipedia, the free encyclopedia
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.
Cet article est une ébauche concernant les mathématiques.
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
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
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
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. 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
Calcul formel guidé par l'homme
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
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
Quelques logiciels de calcul formels
| 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
- 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
