Université Paris 7 École Normale Supérieure de Cachan École Normale Supérieure École Polytechnique
Université Paris 6 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

Parisian Master of Research in Computer Science

Master Parisien de Recherche en Informatique (MPRI)

[Home page] [The MPRI course] [Practical information]


Algorithmes efficaces en calcul formel (48h, 6 ECTS)

Responsables : M. Giusti, B. Salvy

Objectifs

Le calcul formel (computer algebra ou symbolic computation en anglais) consiste à représenter et manipuler sur ordinateur des objets mathématiques. Les objets sont représentés de manière exacte. La contrepartie est une explosion de la taille mémoire nécessaire au calcul. Dans ce cours, nous présentons les algorithmes de base du calcul formel en nous attachant à donner des versions de complexité quasi-optimale. Ces algorithmes sont ensuite appliqués à des thèmes actifs de recherche comme la sommation et l'intégration symbolique ou l'algèbre commutative effective.

Plan du cours et intervenants prévus pour 2010-2011

  1. Algorithmes fondamentaux
  2. Systèmes polynomiaux et leur géométrie
  3. Sommation et intégration de suites et fonctions spéciales

Alin Bostan (12h), Frédéric Chyzak (12h), Marc Giusti (12h), Bruno Salvy (12h)

Cette page contient le programme de l'ensemble du cours et sera modifiée hebdomadairement pour incorporer les divers supports et éventuellement faire évoluer les sujets des séances en fonction de ce qui aura été présenté en cours.

Langues du cours : Le cours sera en français. Les étudiants sont autorisés à rédiger leurs examens en français ou en anglais.

La note du cours est la moyenne des notes obtenues au partiel et à l'examen final. Les documents autorisés aux examens sont le poly et les notes de cours de l'étudiant.


Poly (version du 06/01/10).

Cours 1. 21/09

Bruno Salvy. Présentation générale du cours, multiplication rapide.

Cours 2. 28/09

Alin Bostan. Algèbre linéaire dense : de Gauss à Strassen.

Cours 3. 05/10

Bruno Salvy. Calculs rapides sur les séries, séries D-finies.

Cours 4. 12/10

Alin Bostan. Évaluation-interpolation rapide. Pgcd, résultant.

Cours 5. 19/10

Bruno Salvy. Récurrences linéaires : coefficients constants et fractions rationnelles, coefficients polynomiaux : n-ième terme, n premiers termes.

Cours 6. 26/10

Alin Bostan. Approximants de Padé et de Padé-Hermite. Matrices creuses.

Cours 7. 02/11

Bruno Salvy. Solutions polynomiales et rationnelles d'équations différentielles linéaires, de récurrences linéaires.

Cours 8. 09/11

Alin Bostan. Matrices structurées. Matrices polynomiales.

Séance d'exercices I. 16/11

Alin Bostan

Séance d'exercices II. 23/11

Alin Bostan

PARTIEL. 30/11

Cours 9. 07/12

Frédéric Chyzak. Solutions polynomiales et rationnelles d'équations différentielles et de récurrences linéaires : la complexité binaire. Sommation indéfinie  algorithme de Gosper.

Cours 10. 14/12

Frédéric Chyzak. Sommation hypergéométrique par l'algorithme de Zeilberger, polynômes de Ore.

Cours 11. 04/01

Marc Giusti. Bases standard, syzygies et construction des bases standard pour des idéaux homogènes.

Cours 12. 11/01

Marc Giusti. Fonction et polynôme de Hilbert, dimension, degré, triangularisation des idéaux, Nullstellensatz, mise en position de Noether.

Cours 13. 18/01

Marc Giusti. Théorie de la dimension. Géométrie affine/géométrie projective. Clôture projective.

Cours 14. 25/01

Marc Giusti. Résolution géométrique : algorithme et complexité.

Cours 15. 01/02

Frédéric Chyzak. Bases de Gröbner pour les fonctions spéciales. D-finitude multivariée.

Cours 16. 08/02

Frédéric Chyzak. Intégration et sommation définies par création téléscopique.

Séance d'exercices I. 15/02

Séance d'exercices II. 22/02

EXAMEN le 01/03

Exam2007.pdf: sujet de l'examen 2007.

Bibliographie

Les années précédentes

Équipe pédagogique

A. Bostan CR INRIA Rocquencourt
F. Chyzak CR INRIA Rocquencourt
M. Giusti DR CNRS LIX
B. Salvy DR INRIA Rocquencourt