Algèbre Algorithmique 4MA023

M1 Mathématiques & Applications, Semestre 2, 6 ECTS

Équipe pédagogique

Pierre-Vincent Koseleff, Pierre Charollois

Planning

Objectifs

Ce cours, qui aborde certains aspects de l'algorithmique algébrique, est une introduction aux problématiques du Calcul Formel. Des notions de complexité seront abordées, cependant le but n'est pas une programmation pointue des algorithmes. Ce cours constitue une bonne introduction à l'option "Algèbre Effective et Calcul Formel" de l'agrégation de Mathématiques. Il permet également d'envisager un Master en Mathématiques fondamentales. Il constitue une passerelle possible pour les étudiants de Mathématiques vers des cours de M2 en Informatique (par exemple, la filière SFPN à SU) ou en Mathématiques-Informatique.

Prérequis

Connaissances générales en algèbre de niveau L3.

Thèmes abordés

Algorithme d'Euclide
Cas de $\mathbf{Z}$ et $K[X]$. Calculs du pgcd, des coefficients de Bézout. Aspects effectifs (contrôle de la taille des coefficients, nombre d'opérations élémentaires). Théorème chinois. Facteurs invariants, forme normale de Smith, forme normale d'Hermite. Classification des groupes abéliens de type fini. Invariants de similitude.
Résultants
Définition et premières propriétés. Applications (élimination, courbes rationnelles; Géométrie, théorème des zéros de Hilbert; calculs effectifs dans les extensions algébriques).
Calculs dans les corps finis
Propriétés. Factorisation dans ${\mathbf F}_q[X]$, algorithme de Berlekamp. Applications.
Calcul modulaire
Remontée de Hensel (Factorisation dans $\mathbf{Z}[X]$). Méthode de Newton (Décomposition de Dunford). Borne d'Hadamard, calculs de déterminants entiers.
Réseaux
Recherche de vecteurs courts dans un réseau de ${\mathbf R}^n.$ Algorithme de Gauss (dimension 2), algorithme LLL. Applications à la détermination de relations linéaires entre nombres complexes, et à la factorisation dans ${\mathbf Q}[X].$

Nous prévoyons de faire quelques séances de TP en Sage (en plus ou à la place des TD).