L3Math  -  Algèbre effective  -  2019-20


10 semaines de cours le lundi 10h15-12h15 en M36 ; 1er cours le 16 septembre
TD (M37?) ou TP sur ordinateur avec Sagemath (PV201-202) le mardi 13h-15h avec Ch. Cazanave.
1er TP mardi 17 sept. dans les salles PV314, 315, 317.

Objectifs du cours :
  • Aspects effectif de l'algèbre sur les entiers et les polynômes et de l'algèbre linéaire (structuration des objets, algorithme exhibant une solution à un problème d'existence).
  • Calculs sur ordinateur : TP avec Sagemath

La page du cours en 2018-19
La page du cours de F. Eyssette en 2015-16
La page du cours d'arithmétique en L2Math (Ch. Pauly), notes de cours.

Progression du cours :
0 (10sept) "Mise à niveau" - présentation : cadre mathématique : anneaux Z, Q, Q[X], Fp[X] et leurs quotients (cf cours arithmétique en L2) ; algèbre linéaire sur Q (cf cours de L1 et L2) et sur Z.
Aspect effectif : algorithmes explicitant les solutions (calcul piloté = règles de réécriture de formules). Implémentation des algorithmes avec le langage Python ou Sagemath.
Présentation de SageMathCell et Cocalc : (vidéos de présentation en lien avec un TP de statistiques).
Premiers exemples d'algorithme de calcul : fonction 2^n, suite de Fibonacci. Définition itérative (succession de réécritures conditionnelles), définition récursive

Lecture : 1er chapitre de [Demazure, Cours d'algèbre, 1997]

Thème 1 : l'anneau Z/nZ

1. (16sept) Rappel Z/nZ : classes de congruence dans Z : a+nZ, addition, multiplication héritées de celles de Z, bijection avec {0,...,n-1} via le reste de la division euclidienne par n (notation Python : a%n).
Calculs : représentation d'un entier n (développement décimal, binaire, triadique,...), algorithmes de calcul de la division euclidienne de a par n à partir des seules opérations +,- et relation <, algorithme amélioré ("binaire"), algorithme du CM2 avec la représentation décimale des entiers, implémentation itérative et récursive en Python.
Sous-groupe <g> engendré par un élt g d'un groupe G, notation multiplicative ou additive, isomorphisme Z/nZ → <g> (au passage noyau d'une application, factorisation canonique de l'application), ordre de g, ex ordre de la permutation (1 5 3)(2 4) ? Sous-gp de Z/nZ.

Lecture : la division des entiers en CM2.

2. (23sept) Noyau de Z→<g>⊂G, les ss gp de Z sont de la forme nZ (preuve, effectivité de la preuve) ; générateurs de Z/nZ, gp multiplicatif (Z/nZ)x, indicatrice d'Euler φ(n), calcul : φ(p) avec p premier, φ(pn), lemme chinois et φ(mn).
Ordre d'un élt de (Z/nZ)x : il divise φ(n) (cf thm de Lagrange) ; affirmation : lorsque n est premier (Z/nZ)x est cyclique mais l'ordre d'un élt est imprévisible.

3. (30sept) (7oct) (14oct) En TP : algorithme RSA

Thème 2 : corps finis

(21oct.) Représentation, matrice de la multiplication par un élt. , Lemme chinois et l'algorithme de Berlekamp (irréductibilité, recherche des racines d'un polynôme de Fp[X] )

(4nov.) Corps intermédiaires Fp ⊂ k ⊂ Fp[X]/(Q), polynôme minimal.

Thème 3 : algèbre linéaire sur k, Z, k[X]

18nov. 1h30 Problèmes d'algèbre linéaire, ex. dimension et base de l'intersection de sous espaces donnés par des familles génératrices. Résolution de AX=B par transformations élémentaires de A suivant les lignes et les colonnes : on se ramène à A nulle hors de la diagonale.

25nov. A∈Mn(k) est inversible ssi det(A) est inversible dans k. Solutions de AX=B lorsque k est un corps et A est nulle hors de la diagonale. Solutions dans le cas A quelconque : Ker(A)=QKer(PAQ),Im(PAQ)=PIm(A) (cf l'ex.4 de l'examen de session 2 2019 ou l'ex.3 de la feuille de TD 3 de 2018-19). Extension au cas k=anneau euclidien, algorithme du pivot "arithmétique" (forme normale de Smith). Exemple avec l'ex.3 de l'examen de session 2 2019.

2déc. Sous-groupes de Zn, base adaptée, équation modulaire ; Présentation d'un groupe abélien de type fini

9déc. Retour sur la forme normale de Smith : invariants par opérations sur les lignes seules (pgcd des colonnes, déterminant d'une matrice carré), opérations sur les lignes d'une matrice inversible. Exercices type : complétion d'une famille de vecteurs de Zn en une base, solution d'un système d'équations modulaires, surjectivité d'une application ZmZn/Im(A).
Discussion sur les TP.


Documents du cours 2019-20 :

Feuilles de TD - TP sur la page de Ch. Cazanave.

Notes de cours-TD Z/nZ (8oct19)
Interrogation du 15 oct et un corrigé.
Notes de cours Corps finis (7nov19)
TD corps intermédiaires (18nov19)
Notes de cours et TP Algèbre linéaire et matricielle (3dec19), source ipynb du TP, version pdf.
3 exo type d'algèbre linéaire (9déc)
Interrogation sur machine du 16 déc.  Corrigé partie RSApartie eq. linéairespartie Berlekamp.

Examen du 10 janvier et un corrigé.

La page du cours en : 2018-192017-182016-17

Lectures :

M. Demazure, Cours d'algèbre, Cassini 1997
P. Wassef, Algèbre Arithmétique pour l'informatique, Vuibert (disponible à la BU Sciences)
Calcul mathématique avec Sage
P. Audibert, Algorithmes et théorie des nombres, Ellipses 2014

TP de calcul formel avec Maple par C. Cazanave (systèmes d'équations linéaires, codes correcteurs)