#!/usr/bin/env python
# coding: utf-8

# $$
# \def\QQ{\bf Q}
# \def\RR{\bf R}
# \def\ZZ{\bf Z}
# $$
# # Option Algèbre et Calcul Formel de l'Agrégation de Mathématiques: Introduction
# 
# ## Introduction
# 
# ### Objectifs de l'option
# 
# -   Savoir illustrer un enseignement:
#     -   Présentation d'exemples de tailles plus conséquentes
#     -   Évacuation des détails des calculs sans intérêt pédagogique
#     -   Interactivité, gestion du rythme, expérimentation avec la classe
#     -   Possibilité pour l'élève de refaire les calculs, et
#         d'expérimenter avec
# -   Comprendre le fonctionnement général des outils de calcul formel
# -   Aborder l'algèbre avec un autre point de vue, plus constructif
# -   Manipuler de la bibliographie
# 
# Moyens:
# 
# -   Expérimentation avec les outils de calcul formel
# -   Programmation d'algorithmes classiques pour bien les comprendre
# -   Étude de textes
# 
# ### Calcul Formel: Qu'est-ce?
# 
# Premiers calculs avec `Sage` :

# In[ ]:


1 + 1


# In[ ]:


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


# In[ ]:


2^3


# In[ ]:


2**3


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

# In[ ]:


20/6


# In[ ]:


2^10


# In[ ]:


2^100


# In[ ]:


2^1000


# In[ ]:


20.0 / 14


# In[ ]:


numerical_approx(20/14)


# In[ ]:


numerical_approx(2^1000)


# In[ ]:


numerical_approx(20/14, digits=60)


# Premier exemple d'instabilité numérique:

# In[ ]:


(1 + 10^50) - 10^50


# In[ ]:


(1.0 + 10^50) - 10^50


# Quelques exemples supplémentaires:

# In[ ]:


factorial(100)


# In[ ]:


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


# Calcul formel avec des fonctions et constantes usuelles:

# In[ ]:


arccos( sin(pi/3))


# In[ ]:


sqrt(2)


# In[ ]:


exp(I*pi/6)


# In[ ]:


simplify(arccos(sin(pi/3)))


# In[ ]:


simplify(exp(i*pi/6))


# In[ ]:


numerical_approx( 6*arccos( sin(pi/3)), digits=60 )


# In[ ]:


numerical_approx( sqrt(2), digits=60 )


# #### Calcul algébrique (Computer Algebra):
# 
# ##### Résidus modulo, corps finis
# 
# Calcul modulo $4$ :

# In[ ]:


m = 7 % 4; m


# In[ ]:


3 * m + 1


# Et si l'on veut faire tout les calculs suivants modulo $4$ :

# In[ ]:


Z4 = IntegerModRing(4); Z4


# In[ ]:


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$ :

# In[ ]:


3 * m + 1


# Corps finis:

# In[ ]:


Z3 = GF(3); Z3


# ##### Matrices

# In[ ]:


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


# In[ ]:


(a^2 + 1) * a^(-1)


# ##### Polynômes, fractions rationnelles

# In[ ]:


P = QQ['x']; P


# In[ ]:


F = P.fraction_field(); F


# In[ ]:


p = P(x+1) * P(x); p


# In[ ]:


p + 1/p


# In[ ]:


parent(p + 1/p)


# ##### Nombres algébriques

# In[ ]:


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


# In[ ]:


a^3


# In[ ]:


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 =
# 
# -   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 (Gauss, Euclide, Grobner, SGS)
# -   Évaluation (Fourrier)
# -   Changements de représentation
# 
# ## Systèmes de calculs et Sage
# 
# ### Les systèmes de calcul (formel)
# 
# #### Composants d'un Système de Calcul Formel (Computer Algebra System)
# 
# -   Arithmétique: entiers longs, corps finis, ...
# -   Polynômes, fractions rationnelles, matrices, ...
# -   Sommations, intégration, dérivation, limites symbolique
# -   Solveurs (linéaire, polynômiaux, équations différentielles, ...)
# -   Lien calcul numérique
# -   Bases de données (nombres premiers, groupes classiques, ...)
# -   Langage de programmation et structures de données Multiparadigme:
#     impératif / objet / fonctionnel Pourquoi programmer?
# -   Gestion de mémoire
# -   Interface avec d'autres systèmes
# -   Interface utilisateur
# 
# #### Quelques systèmes de calcul
# 
# Systèmes généralistes:
# 
# -   Mathematica
# -   Maple (<http://www.maplesoft.com/>)
# -   MuPAD (<http://www.mupad.org>, était pas trop cher)
# -   Axiom (<http://axiom-developer.org/>, libre)
# -   Sage (<http://www.sagemath.org>, libre)
# -   Matlab (calcul numérique)
# 
# Systèmes spécialisés:
# 
# -   Magma
# -   GAP (groupes)
# -   Linbox (algèbre linéaire exacte)
# -   Pari, NTL, ... (théorie des nombres)
# -   R (statistiques)
# -   Macsima (calcul symbolique, libre)
# 
# #### Caractéristiques communes
# 
# ##### Représentation arborescentes des objets, notion d'opérandes

# In[ ]:


var('a,b,c,d,e,f,g')


# In[ ]:


F = a + b * c + d * e * sin(f)^g


# In[ ]:


F.operands()


# ##### Gestion automatique de la mémoire
# 
# Que se passe-t'il lorsque l'on fait:

# In[ ]:


F = 0


# (comptage de références ou glaneur de cellule)
# 
# ##### Structures de données
# 
# Listes, ensembles et tables d'association
# 
# > sage: liste = \[sin(1+x), 3, sin(1+x)\]; liste
# >
# > sage: ensemble = { sin(1+x), 3, sin(1+x) }; ensemble
# >
# > sage: tableAssociative = { sin(1+x) : 1, 3 : 2 }
# >
# > sage: tableAssociative\[3\] 2
# >
# > sage: tableAssociative\[sin(1+x)\] 1
# 
# ##### Langage de programmation
# 
# Exécution conditionnelle, boucles, fonctions, ...
# 
# ## Modélisation mathématique
# 
# ### Le système Sage
# 
# <http://wiki.sagemath.org/GroupeUtilisateursParis?action=AttachFile&do=get&target=2012-02-16-SageParis.pdf>
# 
# ### `Sage` est orienté objet
# 
# `Python` et `Sage` utilisent fortement la programmation orientée objet.
# Même si cela reste relativement transparent pour une utilisation
# occasionnelle, il est utile d’en savoir un minimum, d’autant que ce fait
# est très naturel dans un contexte mathématique.
# 
# Le paradigme de la programmation orientée objet s’appuie sur un
# principe: «toute entité du monde physique ou mathématique que l’on
# souhaite manipuler avec l’ordinateur est modélisé par un *objet*»; de
# plus cette objet est une *instance* d’une *classe*. Ainsi, le nombre
# rationnel $o=12/35$ est modélisé par un objet qui est une instance de la
# classe `Rational` :

# In[ ]:


o = 12/35


# In[ ]:


type(o)


# Noter que cette classe est vraiment associée à l’objet $12/35$, et non
# seulement à la variable `o` qui le contient:

# In[ ]:


type(12/35)


# Précisons les définitions. Un *objet* est une portion de la mémoire de
# l’ordinateur qui contient l’information nécessaire pour représenter
# l’entité qu’il modélise. La *classe* quant à elle définit deux choses:
# 
# 1.  la *structure de données* d’un objet, c’est-à-dire comment
#     l’information est organisée dans le bloc mémoire. Par exemple, la
#     classe `Rational` stipule qu’un nombre rationel comme $12/35$ est
#     représenté, en gros, par deux nombres entiers: son numérateur et
#     son dénominateur.
# 2.  *son comportement*, et en particulier les *opérations* sur cet
#     objet: par exemple comment on extrait le numérateur d’un nombre
#     rationel, comment on calcule sa valeur absolue, comment on multiplie
#     ou additionne deux nombres rationels, etc. Chacune de ces opération
#     est implantée par une *méthode* (respectivement `numer`, `abs`,
#     {\_\_mult\_\_}, {\_\_add\_\_}, ...).
# 
# Pour factoriser un nombre entier $o$, on va donc appeller la méthode
# `factor` avec la syntaxe suivante:

# In[ ]:


o = 720


# In[ ]:


o.factor()


# que l’on peut lire comme: «prendre la valeur de `o` et lui appliquer la
# méthode `factor` sans autre argument». Sous le capot, effectue le calcul
# suivant:

# In[ ]:


type(o).factor(o)


# De gauche à droite: «demander à la classe de (la valeur de) `o`
# (`type(o)`) la méthode appropriée de factorisation (`type(o).factor`),
# et l’appliquer à `o`».
# 
# Notons au passage que l’on peut appliquer une opération à une valeur
# sans passer par une variable:

# In[ ]:


720.factor()


# et donc en particulier enchaîner les opérations, de la gauche vers la
# droite. Ici, on prend le numérateur d’un nombre rationnel, que l’on
# factorise ensuite:

# In[ ]:


o = 720 / 133


# In[ ]:


o.numerator().factor()


# #### Applications
# 
# ##### Polymorphisme
# 
# En quoi cela nous concerne-t-il? Tout d’abord, l’orientation objet
# permet le *polymorphisme*: quelque soit l’objet `o` que l’on veut
# factoriser, on peut toujours utiliser la notation `o.factor()` (ou son
# raccourci `factor(o)`). De même, calquant les notations mathématiques
# usuelles, le produit de deux objets `a` et `b` peut toujours être noté
# `a*b` même si l’algorithme utilisé dans chaque cas est différent (Pour
# une opération arithmétique binaire comme le produit, la procédure de
# sélection de la méthode appropriée est un peu plus compliquée que ce qui
# a été décrit précédemment. En effet elle doit gérer des opérations
# mixtes comme la somme $2 + 3/4$ d’un entier et d’un nombre rationnel. En
# l’occurence, $2$ sera converti en nombre rationnel $2/1$ avant
# l’addition. C’est le *modèle de coercion* de `Sage` qui est en charge de
# cela.). Voici un produit de deux nombres entiers:

# In[ ]:


3 * 7


# un produit de deux nombres rationnels, obtenu par produit des
# numérateurs et dénominateurs puis réduction:

# In[ ]:


(2/3) * (6/5)


# Un produit de deux nombres complexes, utilisant $I^2=-1$ :

# In[ ]:


(1 + I)  *  (1 - I)


# des produits commutatifs formels de deux expressions:

# In[ ]:


(x + 2) * (x + 1)


# In[ ]:


(x + 1) * (x + 2)


# Outre la simplicité de notation, cela permet d’écrire des programmes
# *génériques* comme:

# In[ ]:


def puissance_quatre(a):


# qui s’appliquent à tout objet admettant les opérations utilisées (ici la
# multiplication):

# In[ ]:


puissance_quatre(2)


# In[ ]:


puissance_quatre(3/2)


# In[ ]:


puissance_quatre(I)


# In[ ]:


puissance_quatre(x+1)


# In[ ]:


M = matrix([[0,-1],[1,0]]); M


# In[ ]:


puissance_quatre(M)


# ##### Introspection
# 
# Plus prosaïquement, l’orientation objet permet l’*introspection*: on
# peut ainsi accéder à l’aide en ligne spécifique à la factorisation des
# nombres entiers avec:

# In[ ]:


o = 720


# In[ ]:


x.factor


# voire à l’implantation de cette fonction, précédée de son aide en ligne:

# In[ ]:


o.factor


# En passant au dessus des détails techniques, on distingue bien que
# `Sage` délègue le calcul à d’autres logiciels (`Pari`, `Kash`, ...).
# 
# Enfin, on peut utiliser la complétion automatique pour demander
# interactivement à un objet `o` quelles sont toutes les opérations que
# l’on peut lui appliquer:

# In[ ]:


o.<tab>


# Ici, il y en a beaucoup; voici celles qui commencent par `n` :

# In[ ]:


o.n<tab>


# ### Éléments, parents, catégories
# 
# #### Éléments et parents
# 
# Dans la section précédente, nous avons vu la notion technique de
# *classe* d’un objet. Dans la pratique, il est suffisant de savoir que
# cette notion existe; on a rarement besoin de regarder explicitement le
# type d’un objet. En revanche `Sage` introduit une contrepartie plus
# conceptuelle de cette notion que nous allons aborder maintenant: celle
# du *parent* d’un objet.
# 
# Supposons par exemple que l’on veuille déterminer si un élément $a$ est
# *inversible*. La réponse ne va pas seulement dépendre de l’élément
# lui-même, mais de l’ensemble $A$ auquel il est considéré appartenir. Par
# exemple, le nombre $5$ n’est pas inversible dans l’ensemble $\ZZ$ des
# entiers, son inverse $1/5$ n’étant pas un entier:

# In[ ]:


a = 5; a


# In[ ]:


a.is_unit()


# En revanche, il est inversible dans l’ensemble des rationnels:

# In[ ]:


a = 5/1; a


# In[ ]:


a.is_unit()


# Comme nous l’avons vu dans la section précédente, `Sage` répond
# différemment à ces deux questions car les éléments $5$ et $5/1$ sont
# dans des classes différentes:

# In[ ]:


type(5)


# In[ ]:


type(5/1)


# Dans certains systèmes de calcul formel orientés objet, tels que `MuPAD`
# ou `Axiom` l’ensemble $X$ auquel $x$ est considéré appartenir (ici $\ZZ$
# ou $\QQ$) est simplement modélisé par la classe de $x$. `Sage` suit
# l’approche de `Magma`, et modélise $X$ par un objet supplémentaire
# associé à $x$, et appelé son *parent*:

# In[ ]:


parent(5)


# In[ ]:


parent(5/1)


# On peut retrouver ces deux ensembles avec les raccourcis:

# In[ ]:


ZZ


# In[ ]:


QQ


# et les utiliser pour *convertir* aisément un élément de l’un à l’autre
# lorsque cela a un sens:

# In[ ]:


QQ(5).parent()


# In[ ]:


ZZ(5/1).parent()


# In[ ]:


ZZ(1/5)


# Voici $1$ en tant qu’entier $1\in\ZZ$, nombre rationnel $1\in\QQ$, et
# approximations flottantes $1{,}0\in\RR$ et $1{,}0+0{,}0i \in\CC$ :

# In[ ]:


ZZ(1), QQ(1), RR(1), CC(1)


# #### Exemple: Combinatoire
# 
# Selon le même principe, lorsque l'on demande toutes les partitions de
# l'entier 5, le résultat est un objet qui modélise cet ensemble:

# In[ ]:


P = Partitions(5); P


# Pour obtenir la *liste* de ces objets, il faut le demander
# explicitement:

# In[ ]:


P.list()


# Cela permet de manipuler *formellement* des grands ensembles:

# In[ ]:


Partitions(100000).cardinality()


# Et de calculer paresseusement avec. Ici, on tire au hasard une main de
# cinq cartes à jouer:

# In[ ]:


Symboles = Set(["Coeur", "Carreau", "Pique", "Trefle"])


# In[ ]:


Valeurs  = Set([2, 3, 4, 5, 6, 7, 8, 9, 10, "Valet", "Dame", "Roi", "As"])


# In[ ]:


Cartes   = CartesianProduct(Valeurs, Symboles).map(tuple)


# In[ ]:


Mains    = Subsets(Cartes, 5)


# In[ ]:


Mains.cardinality()


# In[ ]:


Mains.random_element()                           # random


# et là on manipule un mot infini défini comme point fixe d'un morphisme:

# In[ ]:


m = WordMorphism('a->acabb,b->bcacacbb,c->baba')


# In[ ]:


m.fixed_point('a')


# #### Complément: Constructions
# 
# Les parents étant eux-même des objets, on peut leur appliquer des
# opérations. Ainsi, on peut construire le produit cartésien $\QQ^2$ :

# In[ ]:


cartesian_product([QQ, QQ])


# retrouver $\QQ$ comme corps des fractions de $\ZZ$ :

# In[ ]:


ZZ.fraction_field()


# construire l’anneau des polynômes en $x$ à coefficients dans $\ZZ$ :

# In[ ]:


ZZ['x']


# Par empilement successif, on peut construire des structure algébriques
# avancées comme l’espace des matrices $3\times 3$ à coefficients
# polynomiaux sur un corps fini:

# In[ ]:


Z5 = GF(5); Z5


# In[ ]:


P = Z5['x']; P


# In[ ]:


M = MatrixSpace(P, 3, 3); M


# dont voici un élément:

# In[ ]:


M.random_element()                           # random


# In[ ]:


M.det()


# #### Exemple: algèbre linéaire
# 
# Dans les exemples ci-dessous, nous ferons de l'algèbre linéaire sur le
# corps fini $\ZZ/7\ZZ$ :

# In[ ]:


K = GF(7); K


# In[ ]:


list(K)


# Nous avons choisi ce corps à titre d'illustration pour avoir des
# résultats *lisibles*. On aurait pu prendre des coefficients entiers,
# rationnels, ou numériques à plus ou moins haute précision. Les aspects
# numériques seront abordés plus en détail dans l'exposé suivant. Notons
# au passage que, même en calcul exact, il est possible de manipuler de
# relativement grosses matrices:

# In[ ]:


M = random_matrix(K, 10000, sparse=True, density=3/10000)


# In[ ]:


M.rank()                                                     # random


# Définissons donc une matrice à coefficients dans $\ZZ/7\ZZ$ :

# In[ ]:


A = matrix(K, 4, [5,5,4,3,0,3,3,4,0,1,5,4,6,0,6,3]); A


# Calculons le polynôme caractéristique de cette matrice:

# In[ ]:


P = A.characteristic_polynomial(); P


# On vérifie le théorème de Cayley-Hamilton sur cet exemple:

# In[ ]:


P(A)


# Notons que l'information sur le corps de base est préservée:

# In[ ]:


P.parent()


# ce qui influe directement sur la factorisation de ce polynôme:

# In[ ]:


factor(P)


# In[ ]:


factor(x^4 + 5*x^3 + 6*x + 2)


# Le calcul ci-dessus nous donne les valeurs propres: -3=4,-6=1 et -5=2.
# Quels sont les espaces propres?

# In[ ]:


A.eigenspaces_left()


# Récupérons ces espaces propres:

# In[ ]:


E = dict(A.eigenspaces_left())


# In[ ]:


E[2]


# `E[2]` n'est pas une *liste de vecteurs* ni une matrice, mais un *objet*
# qui modélise l'espace propre $E_2$, comme le sous-espace de
# $(\ZZ/7\ZZ)^4$ décrit par sa base échelon réduite. On peut donc lui
# poser des questions:

# In[ ]:


E[2].dimension()


# In[ ]:


E[2].basis()


# In[ ]:


V = E[2].ambient_vector_space(); V


# Voire faire des calculs avec:

# In[ ]:


E[2] + E[4]


# In[ ]:


v = V([1,2,0,3])


# In[ ]:


v in E[2]


# In[ ]:


E[2].echelon_coordinates(v)


# In[ ]:


E[2].is_subspace(E[4])


# In[ ]:


E[2].is_subspace(V)


# In[ ]:


Q = V/E[2]; Q


# In[ ]:


Q( V([0,0,0,1]) )


# On veut maintenant manipuler $A$ comme un morphisme sur $V$ :

# In[ ]:


phi = End(V)(A); phi


# In[ ]:


v = V.an_element()


# In[ ]:


v


# In[ ]:


phi(v)


# In[ ]:


(phi^-1)(v)


# In[ ]:


phi^4 + 5*phi^3 + 6*phi + 2


# In[ ]:


(phi - 1).image()


# In[ ]:


(phi - 1).kernel() == E[1]


# In[ ]:


phi.restrict(E[2])


# #### En résumé
# 
# -   *« Mathematics is the art of reducing any problem to linear algebra
#     »* William Stein
# -   Il serait en principe suffisant d'implanter l'algèbre linéaire sur
#     les matrices
# -   Le pari de Sage: *modéliser au plus près les mathématiques*, pour
#     que l'utilisateur ou le programmeur puisse s'exprimer dans le
#     langage adapté au problème considéré.
# 
# #### Complément: Catégories
# 
# Un parent n’a, en général, pas lui-même un parent, mais une *catégorie*
# qui indique ses propriétés:

# In[ ]:


QQ.category()


# De fait `Sage` sait que $\QQ$ est un corps:

# In[ ]:


QQ in Fields()


# et donc, par exemple, un groupe additif commutatif (voir
# Figure {fig:premierspas:catégories}):

# In[ ]:


QQ in CommutativeAdditiveGroups()


# Il en déduit que $\QQ[x]$ est un anneau euclidien:

# In[ ]:


QQ['x'].category()


# Toutes ces propriétés sont utilisées pour calculer rigoureusement et
# plus efficacement sur les éléments de ces ensembles.
# 
# ### Expressions versus domaines de calcul explicites
# 
# Dans cette section, nous donnons quelques exemples typiques pour lesquel
# il est important de contrôler le domaine de calcul. En première lecture,
# on peut passer rapidement sur les exemples plus avancés pour arriver
# directement à la synthèse de fin de section
# {premierpas:expressions\_versus\_domaines\_synthèse}.
# 
# #### Exemple: simplification d’expressions
# 
# Soit $c$ une expression un tout petit peu compliquée:

# In[ ]:


a = var('a')


# In[ ]:


c = (a+1)^2 - (a^2+2*a+1)


# et cherchons à résoudre l’équation en $x$ donnée par $cx=0$ :

# In[ ]:


eq =  c * x == 0


# L’utilisateur imprudent pourrait être tenté de simplifier cette équation
# par $c$ avant de la résoudre:

# In[ ]:


eq2 = eq / c; eq2


# In[ ]:


solve(eq2, x)


# Heureusement, `Sage` ne fait pas cette erreur:

# In[ ]:


solve(eq, x)


# Ici, `Sage` a pu résoudre correctement le système car le coefficient $c$
# est une expression polynomiale. Il est donc facile de tester si $c$ est
# nul; il suffit de le développer:

# In[ ]:


expand(c)


# Et d’utiliser le fait que deux polynômes sous forme développée
# identiques sont égaux. On dit que la forme développée d’un polynôme est
# une *forme normale*.
# 
# En revanche, sur un exemple à peine plus compliqué, `Sage` commet une
# erreur:

# In[ ]:


c = cos(a)^2 + sin(a)^2 - 1


# In[ ]:


eq = c*x == 0


# In[ ]:


solve(eq, x)


# alors même qu’il sait faire la simplification et même le test à zéro
# correctement:

# In[ ]:


c.simplify_trig()


# In[ ]:


c.is_zero()


# Cet exemple illustre l’importance du *test de nullité*, et plus
# généralement des *formes normales*, dans un domaine de calcul. Sans lui,
# tout calcul faisant intervenir une division devient hasardeux. Les
# algorithmes comme le pivot de Gauss en algèbre linéaire sont
# particulièrement sensibles à ces considérations.
# 
# #### Exemples: polynômes et formes normales
# 
# Construisons l’anneau $\QQ[x_1,x_2,x_3,x_4]$ des polynômes en $4$
# variables:

# In[ ]:


R = QQ['x1,x2,x3,x4']; R


# In[ ]:


x1, x2, x3, x4 = R.gens()


# Les éléments de $R$ sont automatiquement représentés sous forme
# développée:

# In[ ]:


x1 * (x2 - x3)


# qui comme nous l’avons vu est une forme normale. On dit alors que $R$
# est à *représentation normale*. En particulier le test à zéro y est
# immédiat:

# In[ ]:


(x1+x2)*(x1-x2) - (x1^2 -x2^2)


# Mais ce n’est pas toujours un avantage. Par exemple, si l’on construit
# le déterminant de Vandermonde $\prod_{1\leq i < j \leq n} (x_i-x_j)$ :

# In[ ]:


prod( (a-b) for (a,b) in Subsets([x1,x2,x3,x4],2) )


# on obtient $4!=24$ termes. Alors que la même construction avec une
# expression reste sous forme factorisée qui est ici beaucoup plus
# compacte et lisible:

# In[ ]:


x1, x2, x3, x4 = var('x1, x2, x3, x4')


# In[ ]:


prod( (a-b) for (a,b) in Subsets([x1,x2,x3,x4],2) )


# De même, une représentation factorisée ou partiellement factorisée
# permet des calculs de { pgcd} bien plus rapides. Réciproquement, il ne
# serait pas judicieux de mettre automatiquement tout polynôme sous forme
# factorisée, même s’il s’agit aussi d’une forme normale, car la
# factorisation est coûteuse et non compatible avec l’addition.
# 
# De manière générale, selon le type de calcul voulu, la représentation
# idéale d’un élément n’est pas toujours sa forme normale. Cela amène les
# systèmes de calcul formel à un compromis avec les expressions. Un
# certain nombre de simplifications basiques, comme la réduction des
# rationnels ou la multiplication par zéro, y sont effectuées
# automatiquement; les autres transformations sont laissées à l’initiative
# de l’utilisateur auquel des commandes spécialisées sont proposées.
# 
# #### Exemple: factorisation des polynômes
# 
# Considérons la factorisation de l’expression polynomiale suivante:

# In[ ]:


x = var('x')


# In[ ]:


p = 54*x^4+36*x^3-102*x^2-72*x-12


# In[ ]:


factor(p)


# Cette réponse est-elle satisfaisante? Il s’agit bien d’une factorisation
# de $p$, mais son optimalité dépend fortement du contexte! Pour le moment
# `Sage` considère `p` comme une expression symbolique, qui se trouve être
# polynomiale. Il ne peut pas savoir si l’on souhaite factoriser $p$ en
# tant que produit de polynômes à coefficients entiers ou à coefficients
# rationnels (par exemple). Pour prendre le contrôle, nous allons préciser
# dans quel ensemble (domaine de calcul?) nous souhaitons considérer $p$.
# Pour commencer, nous allons considérer $p$ comme un polynôme à
# coefficient entiers. Nous définissons donc l’anneau $R=\ZZ[x]$ de ces
# polynômes:

# In[ ]:


R = ZZ['x']; R


# Puis nous convertissons $p$ dans cet anneau:

# In[ ]:


q = R(p); q


# À l’affichage on ne voit pas de différence, mais $q$ sait qu’il est un
# élément de $R$ :

# In[ ]:


parent(q)


# Du coup, sa factorisation est sans ambiguïté:

# In[ ]:


factor(q)


# On procède de même sur le corps des rationels:

# In[ ]:


R = QQ['x']; R


# In[ ]:


q = R(p); q


# In[ ]:


factor(R(p))


# Dans ce nouveau contexte, la factorisation est encore non ambiguë; mais
# différente de précédemment. Notons au passage que `Sage` sait que $R$
# est un anneau euclidien:

# In[ ]:


R.category()


# et donc en particulier un anneau où la factorisation est unique (voir
# Figure {fig:premierspas:catégories}).
# 
# Cherchons maintenant une factorisation complète sur les nombres
# complexes. Une première option est de s’autoriser une approximation
# numérique des nombres complexes avec 16 bits de précision:

# In[ ]:


R = ComplexField(16)['x']; R


# In[ ]:


q = R(p); q


# In[ ]:


factor(R(p))


# Une autre est d’agrandir un peu le corps des rationnels; ici, on va
# rajouter $\sqrt{2}$.

# In[ ]:


R = QQ[sqrt(2)]['x']; R


# In[ ]:


q = R(p); q


# In[ ]:


factor(R(p))


# Enfin, peut-être souhaite-t’on que les coefficients soient considérés
# modulo $5$?

# In[ ]:


R = GF(5)['x']; R


# In[ ]:


q = R(p); q


# In[ ]:


factor(R(p))


# #### Synthèse
# 
# Dans les exemples précédents, nous avons illustré comment l’utilisateur
# peut contrôler le niveau de rigueur dans ses calculs. D’un côté il peut
# utiliser les expressions symboliques. Ces expressions vivent dans
# l’anneau des expressions symboliques:

# In[ ]:


parent(sin(x))


# que l’on peut aussi obtenir avec:

# In[ ]:


SR


# Les propriétés de cet anneau sont assez floues; il est commutatif:

# In[ ]:


SR.category()


# et les règles de calcul font en gros l’hypothèse que toutes les
# variables symboliques sont à valeur dans $\CC$. Le domaine de calcul
# (expressions polynomiale? rationnelles? trigonométriques?) n’étant pas
# spécifié explicitement, le résultat d’un calcul nécessite le plus
# souvent des transformations manuelles pour être mis sous la forme
# désirée (voir {sec:calculus:simplifications}), en utilisant par exemple
# `expand`, `combine`, `collect` et `simplify`. Pour bien utiliser ces
# fonctions, il faut savoir quel type de transformations elles effectuent
# et à quel domaine de calcul ces transformations s’appliquent. Ainsi,
# l’usage aveugle de la fonction `simplify` peut conduire à des résultats
# faux. Des variantes de `simplify` permettent alors de préciser la
# simplification à effectuer.
# 
# D’un autre côté, l’utilisateur peut *construire* un parent qui va
# spécifier explicitement le domaine de calcul. Cela est particulièrement
# intéressant lorsque ce parent est à *forme normale*: c’est-à-dire que
# deux objets éléments sont mathématiquement égaux si et seulement si ils
# ont la même représentation.
# 
# Pour résumer, la souplesse est l’avantage principal des expressions:
# 
# -   pas de déclaration explicite du domaine de calcul;
# -   ajout au vol de nouvelles variables ou fonctions symboliques;
# -   changement au vol du domaine de calcul (par exemple lorsque l’on
#     prend le sinus d’une expression polynomiale);
# -   utilisation de toute la gamme des outils d’analyse
#     (intégration, etc.).
# 
# Les avantages de la déclaration explicite du domaine de calcul sont:
# 
# -   vertus pégagogiques{:...};
# -   rigueur: les résultats obtenus sont garantis corrects (`Sage` n’est
#     pas un système de calcul *certifié*; il peut donc toujours y avoir
#     un bogue informatique; mais il n’y aura pas d’utilisation
#     d’hypothèse implicite).
# -   mise sous forme normale automatique (le plus souvent) — cela peut
#     aussi être un inconvénient ! — ;
# -   constructions avancées qui seraient délicates avec des expressions
#     (calculs sur un corps fini ou une extension algébrique de $\QQ$,
#     dans un anneau non commutatif...).
# 
# ### Exercices
# 
# -   Parcourir le premier chapitre de [Calcul Mathématique avec
#     Sage](http://sagebook.gforge.inria.fr/)
# -   Parcourir le tutorial-programming-python
# -   Parcourir le tutorial-comprehensions
# -   Faire le maximum de problèmes du [Projet
#     Euler](http://projecteuler.net)
# 
# ### Quelques liens
# 
# -   [Site principal sur Sage](http://www.sagemath.org/)
# -   [Site principal sur Sage en Français
#     (tutoriels, ...)](http://www.sagemath.org/fr/)
# -   [D'autres tutoriaux
#     Sage](http://combinat.sagemath.org/doc/thematic_tutorials/index.html)
# -   [Calcul Mathématique avec Sage](http://sagebook.gforge.inria.fr/)
# -   [Programmation Python pour les
#     mathématiques](http://www.dunod.com/sciences-techniques/sciences-fondamentales/mathematiques/programmation-en-python-pour-les-mathematiques)
# -   [Cours Python de Bob
#     Cordeau](http://www.iut-orsay.u-psud.fr/fr/departements/mesures_physiques/mphy_pedagogie.html)
# -   [Guide du calcul avec les logiciels
#     libres](http://www.dunod.com/sciences-techniques/sciences-fondamentales/mathematiques/master-et-doctorat-capes-agreg/guide-du-calcul-avec-les-logicie)
# -   [A First Course in Linear Algebra de Rob
#     Beezer](http://linear.ups.edu/)
# -   [Utilisation du système de calcul formel libre XCAS pour
#     l'agreg](http://www-fourier.ujf-grenoble.fr/~parisse/agreg.html)
# -   [A Computational Introduction to Number Theory and Algebra, by
#     Victor Shoup](http://shoup.net/ntb/)
# -   [Poly d'introduction à la programmation scientifique avec
#     MuPAD](http://www-lih.univ-lehavre.fr/~olivier/Enseignement/l1/cours/MuPAD/support/Programmation_scientifique_polyp.pdf)