Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)
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
- Algorithmes fondamentaux
- Systèmes polynomiaux et leur géométrie
- Sommation et intégration de suites et fonctions spéciales
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
- D. Cox, J. Little, D. O'Shea, Ideals, Varieties and Algorithms. Undergraduate Texts in Mathematics, Springer Verlag, 2nd edition 1996.
- J. von zur Gathen, J. Gerhard, Modern Computer Algebra, Cambridge University Press, 1999.
- M. Petkovšek, W. Wilf, D. Zeilberger, A=B, A. K. Peters, 1996.
- K. O. Geddes, S. R. Czapor, G. Labahn, Algorithms for Computer Algebra, Kluwer Academic Publishers, 1992.
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 |
