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 2009-2010
- 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. 15/09
Bruno Salvy.
Présentation générale du cours,
multiplication rapide.
Exercices.
Cours 2. 22/09
Alin Bostan.
Algèbre linéaire dense : de Gauss à Strassen.
Exercices.
Cours 3. 29/09
Bruno Salvy.
Calculs rapides sur les séries,
séries D-finies.
Exercices.
Cours 4. 06/10
Alin Bostan.
Évaluation-interpolation rapide. Pgcd, résultant, approximants de Padé et de Padé-Hermite.
Exercices.
Cours 5. 13/10
Bruno Salvy.
Récurrences linéaires : coefficients constants et fractions rationnelles,
coefficients polynomiaux : n-ième terme, n
premiers termes.
Exercices.
Cours 6. 20/10
Alin Bostan.
Matrices structurées, matrices creuses, matrices polynomiales.
Exercices.
Cours 7. 27/10
Bruno Salvy.
Solutions polynomiales et rationnelles d'équations différentielles linéaires,
de récurrences linéaires.
Exercices.
Cours 8. 03/11
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.
Partiel 10/11
Cours 9. 17/11
Alin Bostan.
Correction du Partiel.
Cours 10. 24/11
Marc Giusti.
Bases standard,
syzygies et construction des bases standard pour des idéaux homogènes.
Cours 11. 01/12
Frédéric Chyzak.
Sommation hypergéométrique par l'algorithme de Zeilberger,
polynômes de Ore.
Exercices.
Cours 12. 08/12
Frédéric Chyzak.
Bases de Gröbner pour les fonctions spéciales. D-finitude multivariée, intégration et sommation définies par création téléscopique.
Pas de cours le 15/12
Cours 13. 05/01
Marc Giusti.
Fonction et polynôme de Hilbert, dimension, degré,
triangularisation des idéaux, Nullstellensatz, mise en position de Noether.
Cours 14. 12/01
Marc Giusti. Théorie de la dimension.
Géométrie affine/géométrie projective. Clôture projective.
Cours 15. 19/01
Marc Giusti. Résolution géométrique : algorithme et complexité.
Cours 16. 26/01
Frédéric Chyzak.
Révision.
A href="http://algo.inria.fr/bostan/mpri/Revision2008.pdf"/A&
-->
EXAMEN le 02/02
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 |
