Pot Pourri autour de l'algorithme d'Euclide

 - Calcul de PGCD (oeuf corse)

   Exercice: calculer le pgcd de 42 et 51

 - Simplification de fractions rationnelles
   => Forme normales dans K(X), extensions transcendantales

 - Décomposition sans carrés d'un polynôme

   Démo: Trouver la décomposition sans carrés du polynôme suivant,
   puis le factoriser:

                         5    4      3      2
                        x  + x  - 2 x  - 2 x  + x + 1

   Le faire à la machine sur un polynome plus gros

 - Euclide étendu, Bezout effectif

   Écrire l'invariant pour les s et t, et en déduire les équations de
   mise à jour.

   Exemple: calcul du PGCD des deux polynômes pour l'exercice 5.19
   qui resservira pour l'interpolation de Cauchy.

   Exercice: compléter les colonnes s et t du pgcd de 51 et 42

 - Équations linéaires diophantiennes

   Exercice:
   Résoudre l'équation diophantienne linéaire 51 a + 42 b = 27

   Résolution d'équation diophantiennes linéaires, forme de Hermite,
   Algèbre linéaire sur les PID, structure des Z-modules, ...
   Classification des groupes commutatifs

 - Calcul d'inverse modulo n / p
   Inverse de 11 modulo 13?
   => corps effectifs: Z/pZ, extensions algébriques

 - Algorithme des restes chinois
   Exercice: Trouver f<100 tel que f = 2 mod 11 et f = 7 mod 13
    - Calcul du pgcd étendu sur machine
    - Illustration de l'interpolant de Lagrange
   Exemple avec 3 entiers: f = 2 mod 11, f = -1 mod 13, f = 10 mod 17
    - construction des interpolants
    - description de l'ensemble des solutions
    - lien avec l'algèbre linéaire
   Cadre général (p. 102)
    - Description précise
    - Théorème 5.2, "Interpolant de Lagrange", ...
   Cas particuliers:
    - Entiers (fait)
    - Interpolation de Lagrange
      (trouver un polynôme ayant certaines valeurs en certains points)
      Exercice 5.4 p. 131 (peut-être à traiter en exemple à la machine)
      Applications:
       - Calcul rapide de produits
       - codage, partage de secret
    - Exemple trivial Taylor
      (trouver un polynôme ayant un certain développement de Taylor en
      un point donné)
    - Interpolation de Hermite (mix de Taylor et Lagrange)
    - Exemple: Cubic spline ex. 5.35
      Trouver une fonction de R dans R polynomiale cubique par
      morceaux qui interpole les valeurs et dérivées premières et
      secondes données en les bornes des intervalles.

      Bézier? Ex 5.46 p. 136 (sujet de TP?)
      Courbe de Bézier: courbe paramétrique cubique dans le plan
      passant par des points donnés, avec des dérivées à gauche (B_i)
      et à droite (C_i) fixées.

   Applications:
   => Calcul de déterminant sur Z
      Comment obtenir une borne?
      Inégalité d'Hadamard: |det A| <= n^(n/2) B^n, where B^n is the maximal
      absolute value of an entry of A. Ou la calculer explicitement
      sur la matrice
   => Calcul de déterminant sur K[X]
      Exemple sur machine: 5.32 p. 134, en laissant les
      étudiants choisir la méthode et les points d'interpolation
   => Calcul du polynôme caractéristique

 - Algorithme des restes chinois rationnels

   - Interpolation de Cauchy
     Exemple 5.19

     Applications:
      - Calcul de déterminant dans K(X)
      - Calcul de solutions A x = y avec A à coeffs dans Q
        Cf. Ex 5.33 p.134 (ou alors en TP)

   - Approximant de Padé (en TP)
     TODO: Lien avec le dévelopement en fractions continues

   - Décomposition partielle des fractions rationnelles
      - Cas f sans carrés
      - Cas f puissance; décomposition p-adique

   - Suites récurentes, Berlekamp-Masse
     Reprendre l'exemple de l'article, dans Z/2Z,
     s = 1 0 1 0 0

TP: c'était pas convaincant pour les méthodes modulaires pour les
tailles de matrices accessibles, et vu les arithmétiques modulaires de
Maple/MuPAD. Faire les benchmarks avant, et éventuellement prévoir une
démo pendant le cours sur un autre système. Faire le TP sur les
polynômes où c'est beaucoup plus convaincant:

K := Dom::UnivariatePolynomial(z, Dom::Rational):
M := Dom::Matrix(K):
n := 8:
d := 5: // Random sur K renvoie des polynômes de degré <= 5
m := M::random(n,n):
time((det1 := linalg::det(m)));     // 51 secondes
//mexpr := Dom::Matrix(Dom::ExpressionField(normal))(m):
//time(linalg::det(mexpr)); // Là, on est mort: 137 secondes

detMultiModulaire :=
proc(m)
begin
    borne := d * n ; // le degré du déterminant est inférieur à cette borne
    result := K::zero:
    for i from 0 to d*n do
        lagrange := _mult( K(z-j)/(i-j) $ j in {$0..i-1, $i+1..borne} );
        me := matrix(mapcoeffs(m, evalp, z=i)):
        result := result + lagrange * linalg::det(me);
    end_for:
    result;
end_proc:
time((det2 := detMultiModulaire(m)))