Calcul Formel: Qu’est-ce?
Contenu
Calcul Formel: Qu’est-ce?¶
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)
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