Master Parisien de Recherche en Informatique
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 2006-2007
- Algorithmes fondamentaux (16h30)
- Systèmes polynomiaux et leur géométrie (13h30)
- Équations différentielles et récurrences linéaires (9h)
- Algèbre linéaire avancée et factorisation (7h30)
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.
Il est recommandé aux élèves qui s'engagent dans ce cours d'assister au cours de mise à niveau Algèbre commutative
ou de s'assurer qu'ils ont déjà étudié les sujets qui y sont abordés.
Langues du cours :
Le cours sera en français. Les étudiants seront autorisés à rédiger leur examen en français ou anglais.
Poly en cours de rédaction. (Dernière mise à jour le 05/12/06; les chapitres ci-dessous pour les cours postérieurs à cette date sont souvent plus récents).
Cours 1 & 2. 26/09
Cours 3 & 4. 03/10
Cours 5 & 6. 10/10
Cours 7 & 8. 17/10
Cours 9 & 10. 24/10
Cours 11 & 12. 31/10
Cours 13 & 14. 07/11
Marc Giusti. Syzygies et construction des bases standard pour des idéaux
homogènes.
Partiel le 14/11
Cours 15 & 16. 21/11
Marc Giusti. Fonction et polynôme de Hilbert. Dimension, degré.
Cours 17 & 18. 28/11
Bruno Salvy. Correction du Partiel
Cours 19 & 20. 5/12
Marc Giusti. Triangularisation des idéaux, Nullstellensatz, mise en position de
Noether
Cours 21 & 22. 12/12
Marc Giusti. Théorie de la dimension.
Cours 23 & 24. 19/12
Marc Giusti. Géométrie affine/géométrie projective. Clôture projective.
Bruno Salvy. Solutions polynomiales et rationnelles d'équations différentielles et de récurrences linéaires : la complexité binaire.
Cours 25 & 26. 09/01
Cours 27 & 28. 16/01
Cours 29 & 30. 23/01
Marc Giusti. Quête d'une meilleure complexité : cas particulier des
intersections complètes projectives. Rôle crucial des structures
de données.
Marc Giusti. Résolution géométrique I : algorithme.
Cours 31 & 32. ATTENTION : 06/02
Marc Giusti. Résolution géométrique II : complexité.
Examen le 13/02
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.
- K. O. Geddes, S. R. Czapor, G. Labahn, Algorithms for Computer Algebra, Kluwer Academic Publishers.
Équipe pédagogique
| A. Bostan | CR | INRIA | Rocquencourt |
| F. Chyzak | CR | INRIA | Rocquencourt |
| M. Giusti | DR | CNRS | STIX |
| B. Salvy | DR | INRIA | Rocquencourt |
![[arobase]](./commercial_at.png){kind=small}
mpri![[point]](./full_stop.png){kind=small}
master![[English version]](./english_flag.png)