Calcul formel

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 mathématiques et d'autres 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.

Intégration symbolique d'une fonction algébrique en utilisant le système de calcul formel Axiom

Les logiciels qui effectuent des calculs symboliques sont appelés système de calcul formel, le terme système faisant référence à la complexité des principales applications qui incluent, au minimum, une méthode pour représenter des données mathématiques dans un ordinateur, un langage de programmation utilisateur (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 large ensemble de routines pour effectuer les opérations usuelles, telles que la simplification des expressions, la dérivation en utilisant la règle de la chaîne, la factorisation des 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 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 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]. Dans certaines langues, le nom du domaine n'est pas une traduction directe de son nom anglais. Typiquement, il est appelé calcul formel en français, ce qui signifie « calcul formel ». 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

Voir aussi

• Démonstrateur de théorèmes automatisé
• Preuve assistée par ordinateur
• Géométrie algébrique computationnelle
• Système de calcul formel
• Analyseur différentiel
• Vérificateur de preuves
• Vérificateur de modèles
• Calcul symbolique-numérique
• Simulation symbolique
• Intelligence artificielle symbolique