\[ \def\CC{\bf C} \def\QQ{\bf Q} \def\RR{\bf R} \def\ZZ{\bf Z} \def\NN{\bf N} \]

Calcul Formel: Qu’est-ce?

Premiers calculs avec Sage

1 + 1
( 1 + 2 * (3 + 5) ) * 2
2^3
2**3

Calcul exact (par opposition à calcul numérique):

20/6
2^10
2^100
2^1000
20.0 / 14
numerical_approx(20/14)
numerical_approx(2^1000)
numerical_approx(20/14, digits=60)

Premier exemple d’instabilité numérique:

(1 + 10^50) - 10^50
(1.0 + 10^50) - 10^50

En exigeant suffisamment de précision:

a = numerical_approx(1, digits=49)
(a+10^50)-10^50
a = numerical_approx(1, digits=48)
(a+10^50)-10^50

Quelques exemples supplémentaires:

factorial(100)
factor(2^(2^5)+1)

Calcul formel avec des fonctions et constantes usuelles:

arccos(sin(pi/3))
sqrt(2)
exp(I*pi/6)
simplify(arccos(sin(pi/3)))
simplify(exp(i*pi/6))
numerical_approx( 6*arccos( sin(pi/3)), digits=60 )
numerical_approx( sqrt(2), digits=60 )

Calcul algébrique (Computer Algebra):

Résidus modulo, corps finis

Calcul modulo \(4\) :

m = 7 % 4; m
3 * m + 1

Et si l’on veut faire tout les calculs suivants modulo \(4\) :

Z4 = IntegerModRing(4); Z4
m = Z4(7); m

Par la suite, tous les calculs faisant intervenir m sont fait modulo \(4\). Ainsi, dans l’exemple suivants, \(3\) et \(1\) sont automatiquement convertis dans \(\ZZ/n\ZZ\) :

3 * m + 1

Corps finis:

Z3 = GF(3); Z3

Matrices

a = matrix(QQ, [[1,2,3],[2,4,8],[3,9,27]])
(a^2 + 1) * a^(-1)

Polynômes, fractions rationnelles

P = QQ['x']; P
F = P.fraction_field(); F
p = P(x+1) * P(x); p
p + 1/p
parent(p + 1/p)

Nombres algébriques

k.<a> = NumberField(x^3 + x + 1)
a^3
a^4+3*a

Calcul symbolique

Digression: variables de programmation vs variables symboliques

demo-symbolics

Résumé

Calcul formel =

  • Arithmétique (nombres, …)

  • Calcul algébrique (matrices, polynômes, séries, groupes)

  • Calcul symbolique (intégration, …)

Calcul mathématique (computational mathematics) =

  • Calcul formel

  • Combinatoire, graphes

  • Calcul numérique

  • Recherche opérationnelle

L’option Algèbre et Calcul Formel

Grands thèmes

  • Arithmétique

  • Algèbre linéaire

  • Factorisation

  • Polynômes et systèmes polynomiaux

  • Groupes, combinatoire, …

  • En filigrane: algorithmique et complexité

Applications

  • Cryptographie

  • Codage

  • Solveurs exacts (linéaire, …) pour les sciences de l’ingénieur

  • Robotique

Idées centrales

  • Diviser pour mieux régner

  • Élimination (Gauß, Euclide, Gröbner, SGS)

  • Évaluation (Fourier)

  • Changements de représentation