Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

cours:c-2-22 [2019/02/14 16:04]
salvy
cours:c-2-22 [2019/10/20 10:05] (current)
chyzak [Séance 5. 17/10]
Line 1: Line 1:
 ====== Algorithmes efficaces en calcul formel (48h, 6 ECTS) ====== ====== Algorithmes efficaces en calcul formel (48h, 6 ECTS) ======
  
-Responsable : BSalvy+Responsable : FChyzak
  
 ==== Objectifs ==== ==== Objectifs ====
Line 9: Line 9:
 Dans un deuxième temps nous abordons des thèmes actifs de recherche plus spécialisés, comme la sommation et l'intégration symbolique. Les méthodes de sommation et intégration symbolique que nous présentons ont conduit à des outils de calcul désormais incontournables pour la physique, l'évaluation numérique des fonctions spéciales, la modélisation des problèmes combinatoires, et plus largement pour les questions difficiles de simplification de formules. Dans un deuxième temps nous abordons des thèmes actifs de recherche plus spécialisés, comme la sommation et l'intégration symbolique. Les méthodes de sommation et intégration symbolique que nous présentons ont conduit à des outils de calcul désormais incontournables pour la physique, l'évaluation numérique des fonctions spéciales, la modélisation des problèmes combinatoires, et plus largement pour les questions difficiles de simplification de formules.
  
-Ce cours est particulièrement bien adapté pour comprendre avec rigueur les bases algorithmiques et leurs principes généraux en complément des cours //Systèmes polynomiaux, calcul formel et applications// ([[https://wikimpri.dptinfo.ens-cachan.fr/doku.php?id=cours:c-2-13-1|2-13-1]]), //Codes correcteurs d'erreurs et applications à la cryptographie// ([[https://wikimpri.dptinfo.ens-cachan.fr/doku.php?id=cours:c-2-13-2|2-13-2]]), //Techniques en cryptographie et cryptanalyse// ([[https://wikimpri.dptinfo.ens-cachan.fr/doku.php?id=cours:c-2-12-1|2-12-1]]), //Algorithmes arithmétiques pour la cryptologie// ([[https://wikimpri.dptinfo.ens-cachan.fr/doku.php?id=cours:c-2-12-2|2-12-2]]).+Ce cours est particulièrement bien adapté pour comprendre avec rigueur les bases algorithmiques et leurs principes généraux en complément des cours //Systèmes polynomiaux, calcul formel et applications// ([[https://wikimpri.dptinfo.ens-cachan.fr/doku.php?id=cours:c-2-13-1|2-13-1]]), //Codes correcteurs d'erreurs et applications à la cryptographie// ([[https://wikimpri.dptinfo.ens-cachan.fr/doku.php?id=cours:c-2-13-2|2-13-2]]), //Techniques en cryptographie et cryptanalyse// ([[https://wikimpri.dptinfo.ens-cachan.fr/doku.php?id=cours:c-2-12-1|2-12-1]]), //Algorithmes arithmétiques pour la cryptologie// ([[https://wikimpri.dptinfo.ens-cachan.fr/doku.php?id=cours:c-2-12-2|2-12-2]]) et //Analyse d'algorithmes// ([[https://wikimpri.dptinfo.ens-cachan.fr/doku.php?id=cours:c-2-15|2-15]]). 
 +==== Plan du cours et intervenants prévus pour 2019-2020 ====
  
-==== Plan du cours et intervenants prévus pour 2018-2019 ====+  * Première période : Algorithmes fondamentaux 
 +  * Deuxième période : Sommation et intégration de suites et fonctions spéciales
  
-  * Algorithmes fondamentaux +**//[[http://specfun.inria.fr/bostan/|Alin Bostan (24h)]],[[http://specfun.inria.fr/chyzak/|Frédéric Chyzak (24h)]]
-  * Sommation et intégration de suites et fonctions spéciales +
- +
-**//[[http://specfun.inria.fr/bostan/|Alin Bostan (27h)]],[[http://specfun.inria.fr/chyzak/|Frédéric Chyzak (12h)]],[[http://perso.ens-lyon.fr/bruno.salvy/|Bruno Salvy (9h)]]+
 //** //**
  
Line 23: Line 22:
 == Langues du cours, notation, documents autorisés == == Langues du cours, notation, documents autorisés ==
  
-Le cours sera en français. Les étudiants sont autorisés à rédiger leurs examens en français ou en anglais.+Selon la terminologie du MPRI, il s'agit d'un module « French by default », c'est-à-dire que le cours oral est enseigné en français, sauf si au moins un étudiant non francophone préfère l'anglais sans qu'aucun élève francophone n'exige le français. Néanmoins, le livre servant de référence au cours est rédigé totalement en français ; par ailleurs, certains cours, en français à l'oral, seront donnés sur transparents, lesquels seront écrits en anglaisDans tous les cas, 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.+Sauf pour le cas d'élève choisissant officiellement de ne suivre qu'une moitié du module (cours sécable), la note du cours sera la moyenne des notes obtenues au partiel et à l'examen final. Les documents autorisés aux examens sont le livre du cours et les notes de cours de l'étudiant.
  
-Poly : [[https://hal.archives-ouvertes.fr/AECF/|AECF]]+Livre : [[https://hal.archives-ouvertes.fr/AECF/|AECF]]
  
-==== Cours 1. 13/09 ====+==== Séance 1. 12/09 ====
  
-== Bruno Salvy. ==+== FChyzak ==
  
 Présentation générale du cours, Présentation générale du cours,
 multiplication rapide. (Chap. 1 et 2) multiplication rapide. (Chap. 1 et 2)
  
-[[http://perso.ens-lyon.fr/bruno.salvy/mpri/exo_cours1.pdf|Exercices]]+/* [[http://perso.ens-lyon.fr/bruno.salvy/mpri/exo_cours1.pdf|Exercices]] */
  
-==== Cours 2. 20/09 ====+==== Séance 2. 19/09 ====
  
-== Bruno Salvy. ==+== ABostan ==
  
-Calculs rapides sur les séries, séries différentiellement finies. (Chap. 3 et 14)+Algèbre linéaire dense : de Gauss à Strassen. (Chap. 8)
  
-[[http://perso.ens-lyon.fr/bruno.salvy/mpri/exos_cours2.pdf|Exercices]]+[[http://specfun.inria.fr/bostan/mpri/exos-chap-8.pdf|Exercices]] 
 +==== Séance 3. 26/09 ====
  
-==== Cours 327/09 ====+== FChyzak ==
  
-== Alin Bostan==+Calculs rapides sur les séries, séries différentiellement finies(Chap. 3 et 14)
  
-Algèbre linéaire dense : de Gauss à Strassen. (Chap. 8) +[[http://specfun.inria.fr/chyzak/mpri/exos-chap-3-et-14.pdf|Exercices]]
- +
-[[http://specfun.inria.fr/bostan/mpri/exos_cours3.pdf|Exercices]]+
  
-==== Cours 4. 04/10 ====+==== Séance 4. 3/10 ====
  
-== Alin Bostan. ==+== ABostan ==
  
 Évaluation-interpolation rapide. Pgcd, résultant. (Chap. 5 et 6) Évaluation-interpolation rapide. Pgcd, résultant. (Chap. 5 et 6)
  
-[[http://specfun.inria.fr/bostan/mpri/exos_cours4.pdf|Exercices]]+[[http://specfun.inria.fr/bostan/mpri/exos-chap-5-et-6.pdf|Exercices]] 
 +==== ATTENTION : PAS DE SÉANCE LE 10/10 ! ====
  
-==== Cours 5. 11/10 ====+==== Séance 5. 17/10 ====
  
-== Bruno Salvy. ==+== FChyzak ==
  
 Récurrences linéaires : coefficients constants et fractions rationnelles, Récurrences linéaires : coefficients constants et fractions rationnelles,
 coefficients polynomiaux : n-ième terme, n premiers termes. (Chap. 4 et 15) coefficients polynomiaux : n-ième terme, n premiers termes. (Chap. 4 et 15)
  
-[[http://perso.ens-lyon.fr/bruno.salvy/mpri/exos_cours5.pdf|Exercices]].+[[http://specfun.inria.fr/chyzak/mpri/exos-chap-4-et-15.pdf|Exercices]] 
 +/* [[http://perso.ens-lyon.fr/bruno.salvy/mpri/exos_cours5.pdf|Exercices]]. */
  
-==== Cours 6. 18/10 ====+==== Séance 6. 24/10 ====
  
-== Alin Bostan. ==+== ABostan ==
  
 Approximants de Padé et de Padé-Hermite. Matrices creuses. (Chap. 7 et 9) Approximants de Padé et de Padé-Hermite. Matrices creuses. (Chap. 7 et 9)
  
-[[http://specfun.inria.fr/bostan/mpri/exos_cours6.pdf|Exercices]].+/* [[http://specfun.inria.fr/bostan/mpri/exos_cours6.pdf|Exercices]]. */
  
-==== Cours 7. 25/10 ====+==== ATTENTION : PAS DE SÉANCE LE 31/10 ====
  
-== Alin Bostan. ==+==== Séance 77/11 ==== 
 + 
 +== A. Bostan ==
  
 Matrices structurées. Matrices polynomiales. (Chap. 10 et 11) Matrices structurées. Matrices polynomiales. (Chap. 10 et 11)
  
-[[http://specfun.inria.fr/bostan/mpri/exos_cours7.pdf|Exercices]].+/* [[http://specfun.inria.fr/bostan/mpri/exos_cours7.pdf|Exercices]]. */ 
 +==== Séance 8. 14/11 ====
  
-==== ATTENTION : PAS DE COURS LES 1/11 ET 8/11 ! ====+== A. Bostan ==
  
-==== Cours 815/11 ====+Exercices de révision.
  
-== Alin Bostan==+/* [[http://specfun.inria.fr/bostan/mpri/revision-Partiel2018.pdf|Exercices de révision]] */
  
-Solutions polynomiales et rationnelles d'équations différentielles linéaires, +==== ATTENTION : PAS DE SÉANCE LE 21/11 ! ====
-de récurrences linéaires. (Chap. 16 et 17)+
  
-[[http://specfun.inria.fr/bostan/mpri/exos_cours8.pdf|Exercices]].+==== EXAMEN SUR LA PREMIÈRE PÉRIODE le 28/11 ====
  
-==== Cours 922/11 ====+[[http://algo.inria.fr/salvy/mpri/Partiel2013.pdf|Sujet de 2013]]
  
-== Alin Bostan. ==+==== ATTENTION : PAS DE SÉANCE LE 5/12 ====
  
-Séance d'exercices.+==== Séance 912/12 ====
  
-[[http://specfun.inria.fr/bostan/mpri/revision-Partiel2018.pdf|Exercices de révision]]+== FChyzak ==
  
-==== PARTIEL le 29/11 ====+Solutions polynomiales et rationnelles d'équations différentielles linéaires, 
 +de récurrences linéaires. (Chap. 16 et 17) 
 + 
 +/* [[http://specfun.inria.fr/bostan/mpri/exos_cours8.pdf|Exercices]]. */
  
-[[http://algo.inria.fr/salvy/mpri/Partiel2013.pdf|Sujet de 2013]] 
  
-==== Cours 10. 06/12 ====+==== Séance 10. 19/12 ====
  
-== Frédéric Chyzak. ==+== FChyzak ==
  
 Séries hypergéométriques, algorithmes de Gosper, de Zeilberger et de Petkovšek. (Chap. 29) Séries hypergéométriques, algorithmes de Gosper, de Zeilberger et de Petkovšek. (Chap. 29)
  
-[[http://specfun.inria.fr/chyzak/mpri/exos-GZ.pdf|Exercices]].+/* [[http://specfun.inria.fr/chyzak/mpri/exos-GZ.pdf|Exercices]]. */
  
-==== Cours 11. 13/12 ==== 
  
-== Frédéric Chyzak. ==+ 
 +==== Séance 11. 9/01 ==== 
 + 
 +== F. Chyzak. ==
  
 Équations fonctionnelles linéaires et polynômes tordus. (Chap. 30) Équations fonctionnelles linéaires et polynômes tordus. (Chap. 30)
  
-[[http://specfun.inria.fr/chyzak/mpri/exos-SPR.pdf|Exercices]].+/* [[http://specfun.inria.fr/chyzak/mpri/exos-SPR.pdf|Exercices]]. */ 
 + 
 +/* ==== Séance 12. 9/01 ==== */ 
 + 
 +/* == F. Chyzak == */
  
-==== ATTENTION : PAS DE COURS LE 20/12 ====+/* Bases de Gröbner pour les systèmes polynomiaux. */
  
-==== Cours 12. 10/01 ====+==== Séance 12. 16/01 ====
  
-== Frédéric Chyzak. ==+== FChyzak ==
  
 Bases de Gröbner pour les fonctions spéciales. (Chap. 23 sec. 2 à 5, 24, 31) Bases de Gröbner pour les fonctions spéciales. (Chap. 23 sec. 2 à 5, 24, 31)
  
-[[http://specfun.inria.fr/chyzak/mpri/exos-BGFS.pdf|Exercices]].+/* [[http://specfun.inria.fr/chyzak/mpri/exos-BGFS.pdf|Exercices]]. */
  
-==== Cours 13. 17/01 ====+==== Séance 13. 23/01 ====
  
-== Frédéric Chyzak. ==+== FChyzak ==
  
 Intégration et sommation définies par création téléscopique. (Chap. 32) Intégration et sommation définies par création téléscopique. (Chap. 32)
  
-[[http://algo.inria.fr/chyzak/mpri/exos-SISFS.pdf|Exercices]].+/* [[http://algo.inria.fr/chyzak/mpri/exos-SISFS.pdf|Exercices]]. */
  
-==== Cours 14. 24/01 ====+==== Séance 14. 30/01 ====
  
-== Alin Bostan. ==+== ABostan ==
  
 Calcul formel pour la combinatoire. Calcul formel pour la combinatoire.
-[[http://specfun.inria.fr/bostan/mpri/mpri19-p1.pdf|Slides]] +/* [[http://specfun.inria.fr/bostan/mpri/mpri19-p1.pdf|Slides]] */ 
-[[http://specfun.inria.fr/bostan/mpri/mpri19-ex.pdf|Exercice]]+/* [[http://specfun.inria.fr/bostan/mpri/mpri19-ex.pdf|Exercice]] */
  
-==== Cours 15. 31/01 ====+==== Séance 15. 6/02 ====
  
-== Alin Bostan. ==+== ABostan ==
  
 Intégration des fractions rationnelles : algorithmes et complexité. Intégration des fractions rationnelles : algorithmes et complexité.
-[[http://specfun.inria.fr/bostan/mpri/mpri19-p2.pdf|Slides (II)]] +/* [[http://specfun.inria.fr/bostan/mpri/mpri19-p2.pdf|Slides (II)]]  */ 
-[[http://specfun.inria.fr/bostan/mpri/mpri19-p3.pdf|Slides (III)]] +/* [[http://specfun.inria.fr/bostan/mpri/mpri19-p3.pdf|Slides (III)]] */ 
-[[http://specfun.inria.fr/bostan/mpri/exos_cours15.pdf|Exercices]]+/* [[http://specfun.inria.fr/bostan/mpri/exos_cours15.pdf|Exercices]] */ 
  
-==== ATTENTION : PAS DE COURS LE 07/02 ====+==== Séance 16. 13/02 ====
  
-==== Cours 1614/02 ====+== ABostan ==
  
-== Alin Bostan==+Exercices de révision.
  
-Séance d'exercices.+==== ATTENTION : PAS DE SÉANCE LE 20/02 ! ====
  
-==== EXAMEN le 28/02 ====+==== EXAMEN SUR LA DEUXIÈME PÉRIODE le 27/02 ====
  
 ==== Bibliographie ==== ==== Bibliographie ====
Line 188: Line 199:
 |A. Bostan|CR|INRIA|Saclay| |A. Bostan|CR|INRIA|Saclay|
 |F. Chyzak|CR|INRIA|Saclay| |F. Chyzak|CR|INRIA|Saclay|
-|B. Salvy|DR|INRIA|Lyon| 
  
 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA