Calcul formel

Informations

Langue d'enseignement : Français
Crédits ECTS: 6

Programme

  • Heures d'enseignement dispensées à l'étudiant : 50 heures
  • Temps de travail personnel : 100 heures

Objectifs et compétences

Objectifs :
Apprendre à représenter et manipuler les structures algébriques avec comme objectif le calcul.

(1) Représentation et manipulation de structures algébriques.

(a) Complexité des opérations élémentaires dans Z et R[X] (division euclidienne et pgcd), algorithmes naïfs et sous-quadratiques.

(b) Applications : représentation de corps de fractions, de quotients, en particulier nombres algébriques et corps finis), de complétions (R, séries formelles), sommes directes.

(2) Algorithmes algébriques fondamentaux.

(a) Euclide étendu et applications : inverse modulaire, lemme chinois effectif (calcul modulaire), évaluation/interpolation (d'Hermite).

(b) Exponentiation binaire.

(c) Symbole de Legendre / Jacobi (racines carrées dans Z/pZ et Z/p^nZ).

(d) Tests de non-primalité (Solovay-Strassen, Rabin-Miller).

(e) Générateurs d'un groupe cyclique et preuve de primalité.

(f) Le crible d'Eratosthène.

(g) Factorisation dans Z et K[X].

(3) Systèmes polynomiaux.

(a) Systèmes linéaires sur Z ou K[X], systèmes de congruences.

(b) Idéaux de K[x1,...,xn], division euclidienne, bases de Gröbner.

Compétences :
  • Connaître le ou les champs professionnel(s) associé(s) à la discipline.

  • Maitriser les concepts fondamentaux en mathématiques et en probabilité

  • Être capable de mettre en oeuvre des algorithmes de base de calcul scientifique
  • Utiliser des logiciels de calcul formel et scientifique
  • Connaitre les propriétés des différentes structures algébriques.

  • Utiliser des outils mathématiques (y compris le calcul numérique et matriciel) et statistiques.

Organisation pédagogique

le mode de fonctionnement de l'UE est présenté au début des enseignements

Contrôle des connaissances

1ère session :

Contrôle continu - coef. 0,4

Examen écrit terminal (3h)- coef. 0,6

Note 1ère session = 0,4*Contrôle continu + 0,6*Examen écrit terminal

2ème session :

Examen écrit terminal (3h)- coef. 0,6

Note 2nde session = 0,6*Examen écrit terminal session 2 + 0,4*note max(contrôle continu de session 1; examen écrit terminal session 2)

Lectures recommandées

l'ensemble des références bibliographiques est communiqué au début des enseignements

Responsable de l'unité d'enseignement

Gilles Zemor

Enseignants

la composition de l'ensemble de l'équipe pédagogique est communiquée au début des enseignements