|
Systèmes polynomiaux, calcul formel et applications (24h, 3 ECTS)
Responsable : Jean-Charles Faugère
Intervenants 2012-2013
Objectifs
-
Cette annee le cours 2-13-1 est centré sur la résolution des systèmes polynomiaux sur les reels par le calcul de bases de Gröbner et leurs applications (c'est a dire que les solutions des polynomes sont dans des reels).
Les systèmes polynomiaux interviennent dans de nombreux de domaines des sciences de l’ingénieur ou de l’informatique, notamment en cryptologie, robotique, théorie du signal, et géométrie algorithmique. Le calcul formel peut se definir comme la manipulation par l’ordinateur des expressions mathématiques. Les algorithmes algébriques du Calcul Formel constituent un outil privilégié pour la résolution exacte et certifiée des systèmes polynomiaux (la non-linéarité de ces derniers rendant délicates les approches purement numériques). Le but de ce cours est de donner les algorithmes efficaces de résolution de ces systèmes ainsi que de décrire quelques applicationss phares de ces méthodes. Le cours s’articule autour de deux axes. Le premier traite du calcul de base de Gröbner et constitue le moteur de la résolution algébrique utilisé dans la suite. Dans cette partie du cours nous donnerons des resultats de complexite pour le calcul des bases de Groebner qui seront utilises pour les applications et la deuxieme partie du cours. Pour illustrer l'efficacite des algorithmes des bases de Grobner, nous donnerons des exemples provenant d'applications en Cryptologie. Le second axe étudie la résolution de ces problemes sur les reels (qui est un cas frequent des solutions de type ingenierie). Cette deuxieme partie s'articule autour des algorithmes pour l'elimination des quantificateurs et le calcul d'au moins un point par composante connexe des solutions.
-
Plan du cours
-
Systèmes polynomiaux, calcul formel et applications
-
Le cours s’articule autour des deux axes suivants :
- Calcul de bases de Gröbner pour la résolution des systèmes polynomiaux : cet
axe constitue le noyau d’algorithmique algébrique sur lequel repose l’ensemble
des algorithmes donnés dans la suite ; les algorithmes les plus récemment introduits
seront étudiés ; ceux-ci reposent sur une réduction à des problèmes d’algèbre
linéaire ; ils permettent en outre d’effectuer efficacement des opérations
de base sur les idéaux polynômiaux (élimination de variables, saturation, intersection).
- Elimination des quantificateurs et calcul d'un point par composante connexe par reduction aux problemes d'optimisation globale.
-
-
Bibliographie
- Introduction et rappels:
- Pour les aspects systèmes algébriques
- D. Cox, J. Little, and D. O'Shea. Ideals, Varieties, and Algorithms.
Undergraduate Texts in Mathematics. Springer-Verlag, 1996.
second edition.
- T. Becker and V. Weispfenning. Gröbner bases.
Springer-Verlag, New York-Berlin-Heidelberg, 1993.
Prérequis
De bonnes connaissances de base en algèbre élémentaire
(linéaire, multi-linéaire) ainsi que les structures fondamentales que sont les groupes
anneaux et corps sont fortement souhaitables. Des connaissances solides en analyse
de base (niveau L1 ou L2) sont aussi recommandées (notions de continuité, dérivées,
théorème des fonctions implicites).
Il est aussi recommandé d’avoir quelques notions d’algorithmique élémentaire et de
complexité (notation “grand O”) ainsi qu’une connaissance des structures de données
élémentaires que sont les tableaux, listes, et arbres.
Cours liés
2.22 Algorithmes efficaces en calcul formel. Pour ceux qui veulent voir d'autres aspects du calcul formel.
2.14-1 Analyse Géométrique des Données. Pour des applications potentielles du Calcul Formel.
Stages/internships
Des stages seront proposé par l'équipe-projet POLSYS de l'INRIA Rocquencourt tout au long de l'annee 2012/2013.
-
Stage de Master M2: Modélisation de mécanismes et Algorithmes incrémentaux de Calcul des Bases de Gröbner.
- Sujet de these (Ph.D.): Algorithme incrémentaux pour le Calcul des Bases de Gröbner avec paramètres et implantation.
-
-
English Policy
We accept to do the lectures in English if there is at least one non French speaking student in the audience, and no French speaking student is opposed to lectures in English.
-
-
Slides in English will be available.
Les années précédentes
Équipe pédagogique
J.C. Faugère |
DR |
INRIA |
Paris-Rocquencourt |
M. Safey El Din |
PR |
UPMC |
Lip6 |
|