\[ \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