L3Math  -  Algèbre effective  -  2016-17


12 semaines de cours le lundi 13h15-14h45 en M36 ; 1er cours le 5 septembre
TD (M36) et TP sur ordinateur avec Sagemath (PV212) en alternance le lundi 15h-16h30 ; début des TD le 5 septembre

Objectif du cours :

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 :
1. (5sept) Chap. 0 Entiers naturels : point de vue ensembliste, représentation des premiers entiers sur machine, point de vue fonctionnel (type entier : 0, successeur, construction et raisonnement par récurrence),  construction de +, ≤, ×, preuve par récurrence de leurs propriétés. Groupe (Z,+), anneau (Z,+,×), (Q,+,×), représentations des nombres entiers et rationnels à partir des entiers naturel. morphisme de groupes et d'anneaux.
Chap. 1 Sous-groupes de Z et pgcd, algorithmes de calcul.

A faire chez soi : révision des notions de groupe, sous-groupe, anneau, corps, découvrir SageMathCloud avec la feuille de TP1 (à importer dans SageMathCloud) du cours de F. Eyssette
Lecture : notice wikipedia pour Algèbre abstraite, Algorithme, Programmation fonctionnelle.

2. (12sept) TD : récurrence pour les ex. 2 et 3. TP : programmation des algorithmes de la feuille de TD 1.

A faire chez soi : révision algorithme d’Euclide, relation de Bézout.

3. (19sept) Equations linéaires sur Z avec second membre (eq. diophantienne d'ordre 1), lemme de Gauss

4. (26sept) Chap. 2 Algèbre linéaire sur Z, dictionnaire corps - anneau commutatif, sous espace vectoriel de kn - sous module de Zn engendré par une famille de vecteurs ou donné par un systèmes d'équations, ce qui reste du thm de la base incomplète sur Z, sous modules de Q2, de Z2, forme de Smith d'une matrice à coeff. ds Z (énoncé seult).
TP : feuille de TP2 : décryptage d'un algorithme Sage, preuve de ce qu'on affirme d'un algorithme.

A faire chez soi : le TP2 sur Sagemath

5. (3oct) cours-TD Preuve de terminaison d'un algorithme récursif par choix d'un bon ordre sur les arguments en entrée, preuve par récurrence sur le bon ordre du fait que l'algorithme calcule ce qui est souhaité, ex avec le calcul du pgcd de deux entiers puis d'une liste d'entiers. Algorithme de calcul d'une base des solutions d'une équation linéaire sur Z sans second membre.

Quelques algorithmes Sage pour le TP2, version pdf

6. (10oct) Solution d'une équation linéaire sur Z (suite et fin) : algorithme sur un exemple, comparaison avec les solutions à coeff. dans Q. Forme de Smith d'une matrice à coeff. dans Z : comparaison avec la situation à coefficient dans Q, interprétation en terme de base du noyau, base d'un supplémentaire adaptée à l'image.

TP : implémentation de l'algorithme sol0 (cf feuille Sage ci-dessus), expérimentation des opérations élémentaires sur les lignes et les colonnes (cf feuille Sage TP3)

7. (17oct) Forme matricielle des opérations élémentaires sur les lignes et les colonnes : multiplication à gauche ou à droite par une matrice carré inversible de type Mλ(k,l)=I+λEk,l, M(k,l) (matrice de la transposition (k,l)), D (matrice diagonale inversible), conservation du déterminant, exemple ; algorithme récursif pour la forme de Smith d'une matrice à coefficients dans Z (apparition du pgcd des coefficients comme coeff puis algorithme du pivot).

A faire : implémenter l'algorithme (voir feuille Sage TP3)

8. (31oct) TD 4 : exemple de recherche des solutions d'une équation linéaire sur Z, méthode matricielle.

9. (7nov) Interrogation 1
Corrigé de l'ex. 2 de la feuille TD4 (forme de Smith d'une matrice à une seule ligne, matrice de chgt de base). Algorithme pour la forme de Smith d'une matrice à p lignes et q colonnes.

Devoir : par groupe de 1 ou 2 implémenter dans Sagemath l'un des algorithmes suivants :
- sol (sol particulière, base des solutions de l'équation homogène pour une équation linéaire à coefficients ds Z).
- smith (forme de smith d'une matrice à coef. dans Z, liste des opérations élémentaires aboutissant à cette forme, matrices de chgt de base)

10. (14nov) TD forme de Smith d'une matrice : voir la feuille de TD 4.
TP : encoder les opérations dans l'algorithme de Smith : (no, taille, paramètres). Définir une fonction qui prend pour argument une matrice et un code d'opération et rend la matrice transformée par l'opération.

11. (21nov) Cours : Lemme chinois explicite via un système d'équations linéaires. Groupe multiplicatif de Z/n (rappel de 2ème année), ordre de 10 dans ce groupe lorsque n est premier, longueur de la période dans le développement décimal de 1/n. Voir la Feuille de TD 4

Aide au devoir : aide en ligne pour obtenir en python le minimum des éléments non nuls des coefficients d'une matrice. Voir le TP3.

12. (28nov) Cours : déf. d'un algorithme : suite d'opérations (ou instructions) transformant les données en entrée jusqu'à obtenir la sortie ; opérations disponibles pour l'algorithme (contexte), syntaxe ? (mixte entre langage naturel, formules mathématiques, syntaxe d'un langage de programmation) ; construction d'une liste par compréhension en Python.
Corrigé int1 ex2c ; ex1a : voir la feuille de TP4
TP en salles machines

Lecture : pseudocode sur Wikipedia

13 (5déc) Interrogation 2 (oral sur les devoirs)


Documents du cours :
Feuille de TP1 de 2015-16
Feuille de TD 1 (12 sept 16) :
Feuille de TD-TP 2 (26sept) sur SageMathCloud, début de corrigé
TP3 (17oct, dec)
Sujet et un corrigé de l'interrogation du 7 nov.
Feuille de TD 4 (version du 5 dec 16), réponse à l'exercice 2 dans la feuille Sage TP3
Feuille de TP4 (28nov) : autour de l'ex1a de l'int.1, liste définie par compréhension
Un corrigé du devoir "Smith"
Sujet de l'examen de session 1 (14dec) et un corrigé
Sujet de l'examen de session 2 (13juin), corrigé de la partie Python,

Devoir : à rendre avant le 5 décembre. Par groupe de 1 ou 2 implémenter dans Sagemath l'un des algorithmes suivants :
- Sol : doit contenir une fonction f(a,b) prenant en entrée une liste a=[a1,...,an] d'entiers de longueur quelconque et un entier b, et rendant la liste vide [] si l'équation Σaixi=b n'a pas de solution, ou bien une liste de vecteurs de Zn [x,e1,...,er] telle que x est une solution particulière de l'équation avec second membre et [e1,...,er] est une base sur Z des solutions de l'équation homogène.
Doit également contenir un exemple d'application de la fonction f et un test que les solutions trouvées pour l'exemple sont bien des solutions.
Cf corr-TP2 sur SageMathCloud

- Smith : doit contenir une fonction f(A) prenant en entrée une matrice A à coeff. entiers de taille quelconque (pas forcément carré), rendant une liste d'opérations élémentaires (encodage des opérations au choix) transformant A en la forme de Smith de A.
Doit également contenir une fonction g(A,op) prenant en entrée une matrice A et une liste d'opérations élémentaires op et rendant la matrice obtenue en transformant A suivant la liste d'opérations élémentaires op.
Doit également contenir un exemple d'application de la fonction g(A,f(A)) pour un choix de A, éventuellement la transformation réciproque h(op) d'une liste d'opérations op et la vérification A=g(g(A,f(A)),h(f(A))).
Cf TP3 sur SageMathCloud

Lectures :
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


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