Calcul formel

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le calcul formel, ou parfois calcul symbolique, est le domaine de l'informatique et des mathématiques qui s'intéresse à l'étude et au développement d'algorithmes et de logiciels pour la manipulation symbolique d'expressions et d'autres objets mathématiques. Le calcul formel est en général considéré comme un domaine distinct du calcul scientifique, cette dernière appellation faisant référence au calcul numérique approché à l'aide de nombres en virgule flottante, là où le calcul formel met l'accent sur les calculs exacts sur des expressions pouvant contenir des variables.

Comme exemples d'opérations de calcul formel, on peut citer le calcul de dérivées ou de primitives, la simplification d'expressions, ou encore la décomposition en facteurs irréductibles de polynômes.

Historique[modifier | modifier le code]

Les premiers calculs symboliques sur ordinateur ont été réalisés dans les années 1950. Il s'agissait alors d'opérations spécifiques, comme le calcul de dérivées de fonctions. Les tout premiers systèmes étaient en général spécialisés et écrits par une ou deux personnes (Alpak par Brown en 1964, Formac par Bond et Tobey en 1964). Ces systèmes ont disparu depuis, faute de moyens humains et de développement. Sont apparus ensuite Reduce en 1968, Matlab en 1968 qui a donné Macsyma en 1970, et Scratchpad, développé par IBM dès le milieu des années soixante, qui est devenu Scratchpad II en 1975, pour n'être diffusé officiellement qu'en 1991 sous le nom d'Axiom. Ces trois systèmes (Reduce, Macsyma et Scratchpad) ont été écrits en Lisp. On a longtemps pensé que ce langage était préférable pour développer un système de calcul formel, jusqu'à l'apparition vers le milieu des années 1970 du langage C, dans lequel ont été écrits Maple (1980) et Mathematica (1988), successeur de SMP (1982).

Le calcul formel a acquis une notoriété considérable depuis 1988 avec l'arrivée de Mathematica, dont le concepteur, Stephen Wolfram, a mené une campagne de publicité partout dans le monde. Cette publicité a fait mieux connaître le calcul formel dans le milieu industriel.

Les systèmes de calcul formel les plus répandus actuellement sont Maple et Mathematica, et dans une moindre mesure Magma et Sage. Il s'agit de systèmes généraux, c'est-à-dire qu'ils savent manipuler des nombres en précision arbitraire, factoriser ou développer des polynômes et fractions à nombre quelconque de variables, dériver — et intégrer lorsque c'est possible — des expressions construites à l'aide de fonctions élémentaires, résoudre des équations, différentielles ou non, de façon exacte ou à défaut numérique, effectuer des développements limités à un ordre quelconque, manipuler des matrices à coefficients symboliques, tracer des graphiques en deux ou trois dimensions. Ces systèmes évoluent sans cesse, au rythme par exemple d'une nouvelle version tous les ans environ en ce qui concerne Maple.

Il existe aussi des logiciels spécialisés pour certains calculs symboliques. Ces logiciels ne fournissent pas tous les outils que propose un système général, mais ils disposent de fonctionnalités spécifiques à un domaine qu'ils sont souvent les seuls à offrir. En outre, dans leur domaine, ces logiciels sont souvent plus efficaces que les logiciels généraux. C'est le cas de PARI/GP et Kant en théorie des nombres, de Cayley (devenu Magma) et Gap en théorie des groupes, de Macaulay pour les manipulations d'idéaux, de FGb pour les calculs de bases de Gröbner.

Les objets du calcul formel[modifier | modifier le code]

Pour chaque type d'objet que le calcul formel appréhende, il faut définir une représentation, propre à être manipulée par un ordinateur, et ensuite concevoir des algorithmes travaillant sur ces représentations.

Les nombres[modifier | modifier le code]

Les entiers[modifier | modifier le code]

Les nombres entiers sont une des briques de base du calcul formel : ils servent à représenter d'autres objets plus complexes, et beaucoup de calcul se réduisent in fine à la manipulation d'entiers. La notion d'entier en informatique est significativement différente de la notion mathématique. En informatique, un entier est une valeur que peut prendre un mot machine ; cette valeur est bornée par 2B, où B est le nombre de bits d'un mot machine, selon l'ordinateur. Tant que cette limite n'est pas atteinte, un entier machine se comporte comme un entier idéal. En calcul formel, de grands entiers (bien plus grands que 264) apparaissent fréquemment, que ce soit dans des calculs intermédiaires ou dans un résultat final.

Un entier n est généralement représenté par la suite des chiffres de n dans une certaine base, 264 par exemple. Le processeur ne peut pas manipuler directement les entiers dépassant le mot machine ; il faut alors développer des algorithmes spécialisés. Pour l'addition et la soustraction les algorithmes naïfs (ceux qui sont enseignés à l'école, en base 10, pour les calculs à la main) sont bons. En revanche, la multiplication pose un problème de taille : l'algorithme naïf est terriblement lent. La découverte d'algorithmes rapides a été essentielle pour le développement du calcul formel.

La bibliothèque GNU MP, en langage C, est utilisée par la plupart des système de calcul formel pour gérer la manipulation des entiers.

Les rationnels[modifier | modifier le code]

Les nombres rationnels sont représentés par un couple numérateur-dénominateur, à l'instar de la construction formelle des rationnels. Les opérations sur les rationnels se réduisent à des opérations sur les entiers.

Les entiers modulaires[modifier | modifier le code]

Les entiers modulo p de l'arithmétique modulaire sont représentés par un élément de \{0,\dotsc,p-1\}. Les opérations de bases se réduisent aux opérations sur les entiers (addition, multiplication, division euclidienne, etc). Si p n'est pas trop grand, les entiers modulaires peuvent être représentés par un mot machine. Les opérations de bases sont alors particulièrement rapides. Les algorithmes efficaces du calcul formel essaient autant que possible de se ramener à la manipulation des entiers modulaires.

Les polynômes[modifier | modifier le code]

Les matrices[modifier | modifier le code]

Voir aussi[modifier | modifier le code]

Références[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • Alin Bostan, Frédéric Chyzak, Marc Giusti, Romain Lebreton, Bruno Salvy et Éric Schost, Algorithmes efficaces en calcul formel (support de cours, Master parisien de recherche en informatique) [lire en ligne]
  • James Davenport, Yvon Siret et Évelyne Tournier, Calcul formel : Systèmes et algorithmes de manipulation algébrique, Masson,‎ 1987 (ISBN 2225809909)
  • (en) Joachim von zur Gathen et Jürgen Gerhard, Modern computer algebra, Cambridge University Press,‎ 2003, 2e éd. (ISBN 0-521-82646-2)
  • (en) Keith O. Geddes, Stephen R. Czapor et George Labahn, Algorithms for Computer Algebra, Kluwer Academic Publishers,‎ 1992 (ISBN 0-7923-9259-0)