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 Zm→Zn/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 RSA, partie
eq. linéaires, partie
Berlekamp.
Examen du 10 janvier et un corrigé.
La page du cours en : 2018-19,
2017-18, 2016-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)
|