Programme de l’UE :

  • Pgcd et pgcd étendu : algorithmes d’Euclide et d’Euclide étendu (coût algébrique, coût arithmétique, propriétés, …), algorithme quasi-linéaire de Knuth et Schonhage.
  • Algorithmes sur les polynômes : évaluation, interpolation. Arbre des produits. Algorithmes quasi-linéaires pour l’évaluation multi-points et l’interpolation.
  • Algorithmique de l’algèbre lineaire : pivot de Gauss (sur un corps), applications (calcul d’image, de noyau, de déterminant, systèmes linéaires), méthodes multimodulaires et relèvement de Hensel sur Z ou K[X].
  • Résultant, élimination ; application au calcul de l’intersection de deux courbes algébriques planes.
  • Factorisation des polynômes sur Z/pZ : algorithme de Berlekamp, de Cantor-Zassenhaus, relèvement de Hensel d’une factorisation.
  • Application aux codes correcteurs d’erreurs : codes de Reed-Solomon. Algorithmes de décodage, de décodage en liste.

Nota: programme incomplet — à titre d’indication, voici le programme du cours de l’an dernier:

  1. Évaluation en un point : schéma de Horner, interprétation en termes de division euclidienne, optimalité dans le modèle de complexité non scalaire (pgms straight-line).
  2. Multiplication : racines (primitives) n-ièmes, transformée de Fourier discrète (DFT) et sa version rapide (FFT), DFT inverse, multiplication de polynômes par FFT, algorithme de Schonhage et Strassen, fonctionM(n).
  3. Division euclidienne : calcul rapide du reste à partir du quotient, polynômes réciproques, itération de Newton pour l’inversion modulo x^n en O(M(n)), équivalence de complexité entre division et multiplication.
  4. Évaluation multipoint et interpolation : algorithme de Lagrange, algorithme quadratique, arbre des sous-produits et algorithmes quasi-linéaires (somme de fractions, evaluation, interpolation), cas d’une progression géometrique (algorithme de Aho, Steiglitz, Ullman).
  5. Pgcd et pgcd étendu : algorithmes d’Euclide et d’Euclide étendu (analyse de coût, propriétés, …), algorithme quasi-linéaire de Knuth et Schonhage.
  6. Évaluation polynômiale en arithmétique flottante : standard IEEE 754, notations pour l’analyse des erreurs d’arrondi, stabilité (directe, inverse), conditionnement, error-free transforms et algorithmes TwoSum et TwoProd,technique de compensation appliquée au schéma de Horner.
  7. Algorithmique de l’algèbre lineaire : pivot de Gauss (sur un corps, sur Z ou K[X]), applications (calcul d’image, de noyau, de déterminant, systèmes linéaires) méthodes multimodulaires
  8. Résultant, élimination ; application au calcul de l’intersection de deux courbes algébriques planes ; sous-résultants et applications à l’analyse des variantes de l’algorithme d’Euclide étendu sur Z[X]
  9. Rappels sur les corps finis ; factorisation des polynômes sur les corps finis : algorithme de Berlekamp, de Cantor-Zassenhaus
  10. Relèvement de Hensel d’une factorisation ; bornes sur les facteurs d’un polynôme à coefficients entiers. Algorithme de Berlekamp-Zassenhaus pour la factorisation des polynômes à coefficients rationnels.

Intervenants

Cours: Guillaume Hanrot et Jean-Michel Muller

TDs: Silviu Filip