L'unité d'enseignement « Arithmétique, algorithmes et applications » est une UE de niveau (300) spécialisation relevant de la licence d'informatique. Elle possède un volume de 6 ECTS et s'étend sur 12 semaines. Elle est placée sous la responsabilité de Aubry, philippe.

Description

L'unité d'enseignement a pour but de fournir la maîtrise d'algorithmes de calcul symbolique et de l'arithmétique sous-jacente aux codes correcteurs d'erreur et à la cryptographie.

Le cours commence par présenter le domaine du calcul formel et la représentation des données algébriques (en particulier entiers, rationnels, entiers modulaires et polynômes en une variable) et leur arithmétique. Implantation des opérations de base (addition, multiplication, exponentiation, évaluation ...) puis algorithmes rapides (Karatsuba, FFT). Algorithme d'Euclide et pgcd étendu. Applications du pgcd. Application des polynômes aux codes correcteurs: le CRC. Représentation et algorithmes de base en algèbre linéaire.

On étudiera en général la complexité des algorithmes présentés ci-dessus. Ceux-ci utilisent uniquement des connaissances de base en mathématiques : notions de division euclidienne et pgcd, nombres premiers, polynômes et racines d'un polynôme, matrices. Celles-ci sont fournies par exemple dans les UE de mathématiques LM110, 120, 115 et 125 proposées en L1.

Les notions vues en cours et TD seront illustrées par la représentation de données et des implantations en Caml. Il est préférable d'avoir des connaissances élémentaires dans ce langage pour suivre cette unité d'enseignement.

Préalables et buts pédagogiques

Bibliographie

• Cormen, Leiserson, Rivest: Introduction à l'algorithmique. Dunod, 1994

• J. Von Zur Gathen, J. Gerhardt: Modern Computer Algebra. Cambridge University Press, 1999

• D. E. Knuth: The Art of Computer Programming vol. 2 (seminumerical algorithms). Addison-Wesley, 1981

• P. Naudin, C. Quitté: Algorithmique algébrique. Masson, 1992

Contenu indicatif par semaine

1. Présentation. Modèles de complexité (listes, vecteurs).

2. Les grands entiers. Codage, opérations arithmétiques de base.

3. Optimisation des opérations.

4. Arithmétique des entiers relatifs, nombres rationnels et entiers modulaires (sans division).

5. Arithmétique des polynômes en une variable.

6. Division euclidienne, calcul du pgcd.

7. Bezout et l'algorithme de pgcd étendu.

8. Nombres premiers, Z/pZ, le corps à 2 éléments. Application du pgcd à la division dans Z/pZ.

9. Application des polynômes aux codes correcteurs: introduction au CRC (pas de présentation de théorie des codes).

10. Représentation des matrices. Matrices creuses. Arithmétique.

11. Multiplication de Strassen.

12. Méthode de Gauss.

Annales

Les annales de cette UE sont ici.