INRIA SALSA
Université Paris 7 École Normale Supérieure de Cachan École Normale Supérieure École Polytechnique
UMPC Université Paris 11 École Nationale Supérieure des Télécommunications
Centre National de la Recherche Scientifique Commissariat à l'Energie Atomique Institut National de Recherche en Informatique et en Automatique
Home
Publications
Software
Teaching

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.
 

Planning 2012/2013


Bibliographie

 

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