Calcul Formel: Qu’est-ce?#
\( \def\CC{\bf C} \def\QQ{\bf Q} \def\RR{\bf R} \def\ZZ{\bf Z} \def\NN{\bf N} \)
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#
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