Descriptif
Ce cours (ACCQ partie I et II) approfondira sous l'angle algorithmique les notions de base d'algèbre et d'arithmétique utilisées pour leurs applications aux télécommunications et à l'informatique.
Il passera en revue :
la théorie des modules sur un anneau (leur structure, la réduction de Hermite et de Smith dune matrice, invariants de similitude, étude des suites linéaires récurrentes - LFSR)
la théorie des réseaux euclidiens (liens avec des problèmes arithmétiques classiques et le codage, algorithme de réduction LLL)
factorisation des polynômes tests de primalité, factorisation des entiers, log discret
manipulation de systèmes d'équations polynomiales (bases de Groebner)
introduction à diverses questions de complexité algébrique (produits de polynômes ou de matrices).
Il passera en revue :
la théorie des modules sur un anneau (leur structure, la réduction de Hermite et de Smith dune matrice, invariants de similitude, étude des suites linéaires récurrentes - LFSR)
la théorie des réseaux euclidiens (liens avec des problèmes arithmétiques classiques et le codage, algorithme de réduction LLL)
factorisation des polynômes tests de primalité, factorisation des entiers, log discret
manipulation de systèmes d'équations polynomiales (bases de Groebner)
introduction à diverses questions de complexité algébrique (produits de polynômes ou de matrices).
Objectifs pédagogiques
Acquis d'apprentissageÀ l'issue de l'UE, l'élève sera capable de:
- Représenter des éléments mathématiques sophistiques (corps finis, polynômes, réseaux euclidiens) comme objets informatiques
- Conduire des calculs d'algèbre linéaire lorsque les scalaires proviennent d'un anneau principal
- Calculer un base LLL réduite d'un réseau
- Factoriser un polynôme à coefficient entier ou dans un corps fini
- Manipuler des idéaux de polynômes à travers des bases de Groebner.
Compétences de rattachement (et justification)
- BC1.3 – Elaborer une ou plusieurs solutions technologiques, en s’appuyant sur la modélisation théorique et la méthode scientifique de manière à faire ressortir la pertinence desdites solutions permettant une prise de décision; Justification : Les choix des contenus thématiques du cours sont fixés en fonction des besoins des technologies contemporaines.
- BC5.1 – Modéliser mathématiquement une situation, des données, des phénomènes physiques dans le contexte du numérique; Justification : Des petits exercices d'application montrent comment diverses situations pratiques peuvent être traitées par les théories mathématiques étudiées dans ce cours
- BC10.2 – Analyser et résoudre des problèmes mathématiques et algorithmiques nécessaires dans des étapes de réalisation d’un projet en s’appuyant, si besoin est, sur des simulations et dans l’objectif d’implémenter des solutions compétitives; Justification : La démarche d'implémentation systématique des mathématiques étudiées force à se pencher sur l'analyse des différentes étapes de résolution
- BC10.3 – Analyser une résolution par des approches formelles ou mathématiques; Justification : Chaque TP contient une partie critique et réflexive sur les algorithmes qui ont été implémentés.
24 heures en présentiel (16 blocs ou créneaux)
20 heures de travail personnel estimé pour l’étudiant.
effectifs minimal / maximal:
1/100Diplôme(s) concerné(s)
Parcours de rattachement
Pour les étudiants du diplôme Diplôme d'ingénieur
ACCQ201
Cours d'algèbre général (groupe, anneaux, corps) orienté vers la théorie des nombres (anneaux Z/nZ, corps finis, fonction indicatrice dEuler, réciprocité quadratique, polynôme primitif)
Format des notes
Numérique sur 20Littérale/grade européenPour les étudiants du diplôme Diplôme d'ingénieur
Vos modalités d'acquisition :
Note de TP ; examen final.
L'UE est acquise si Note finale >= 10- Crédits ECTS acquis : 2.5 ECTS
- Crédit d'UE électives acquis : 2.5
La note obtenue rentre dans le calcul de votre GPA.
L'UE est évaluée par les étudiants.
Pour les étudiants du diplôme Echange international non diplomant
Vos modalités d'acquisition :
Note de TP ; examen final.
L'UE est acquise si Note finale >= 10- Crédits ECTS acquis : 2.5 ECTS
La note obtenue rentre dans le calcul de votre GPA.
Programme détaillé
Mots clés
Corps finis, modules sur un anneau principal, réseaux euclidiens, factorisation de polynômes univariés, bases de Groebner. SageMéthodes pédagogiques
Classe inversée : le cours est fourni sous forme d'un polycopié avec leçon et exercices à travailler en amont ; la séance est consacrée à des TP d'implémentation.Support pédagogique multimédia
