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 [2020/01/15 15:08]
chyzak
cours:c-2-22 [2020/07/30 10:06] (current)
chyzak [Attention : des indéterminations subsistent sur les dates de quelques séances, qui seront levée d'ici la rentrée.]
Line 10: Line 10:
  
 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]]). 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 2020-2021 ====
  
   * Première période : Algorithmes fondamentaux   * Première période : Algorithmes fondamentaux
Line 28: Line 29:
 Livre : [[https://hal.archives-ouvertes.fr/AECF/|AECF]] Livre : [[https://hal.archives-ouvertes.fr/AECF/|AECF]]
  
-==== Séance 1. 12/09 ====+==== //Attention : des indéterminations subsistent sur les dates de quelques séances, qui seront levées d'ici la rentrée.// ==== 
 + 
 +==== Séance 1. 21/09 ====
  
 == F. Chyzak == == F. Chyzak ==
Line 37: Line 40:
 /* [[http://perso.ens-lyon.fr/bruno.salvy/mpri/exo_cours1.pdf|Exercices]] */ /* [[http://perso.ens-lyon.fr/bruno.salvy/mpri/exo_cours1.pdf|Exercices]] */
  
-==== Séance 2. 19/09 ====+==== Séance 2. 28/09 ====
  
 == A. Bostan == == A. Bostan ==
Line 43: Line 46:
 Algèbre linéaire dense : de Gauss à Strassen. (Chap. 8) Algèbre linéaire dense : de Gauss à Strassen. (Chap. 8)
  
-[[http://specfun.inria.fr/bostan/mpri/exos-chap-8.pdf|Exercices]] +/* [[http://specfun.inria.fr/bostan/mpri/exos-chap-8.pdf|Exercices]] */ 
-==== Séance 3. 26/09 ====+ 
 +==== Séance 3. 5/10 ====
  
 == F. Chyzak == == F. Chyzak ==
Line 50: Line 54:
 Calculs rapides sur les séries, séries différentiellement finies. (Chap. 3 et 14) Calculs rapides sur les séries, séries différentiellement finies. (Chap. 3 et 14)
  
-[[http://specfun.inria.fr/chyzak/mpri/exos-chap-3-et-14.pdf|Exercices]]+/* [[http://specfun.inria.fr/chyzak/mpri/exos-chap-3-et-14.pdf|Exercices]] */
  
-==== Séance 4. 3/10 ====+==== Séance 4. 12/10 ====
  
 == A. Bostan == == A. Bostan ==
Line 58: Line 62:
 É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-chap-5-et-6.pdf|Exercices]] +/* [[http://specfun.inria.fr/bostan/mpri/exos-chap-5-et-6.pdf|Exercices]] */
-==== ATTENTION : PAS DE SÉANCE LE 10/10 ! ====+
  
-==== Séance 5. 17/10 ====+/* ==== ATTENTION : PAS DE SÉANCE LE 10/10 ! ==== */ 
 + 
 +==== Séance 5. 19/10 ====
  
 == F. Chyzak == == F. Chyzak ==
Line 68: Line 73:
 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://specfun.inria.fr/chyzak/mpri/exos-chap-4-et-15.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]]. */+
  
-==== Séance 6. 24/10 ====+==== Séance 6. 26/10 ====
  
 == A. Bostan == == A. Bostan ==
Line 77: Line 81:
 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-chap-7-et-9.pdf|Exercices]]. +/* [[http://specfun.inria.fr/bostan/mpri/exos-chap-7-et-9.pdf|Exercices]]. */
-==== ATTENTION : PAS DE SÉANCE LE 31/10 ! ====+
  
-==== Séance 7. 7/11 ====+/* ==== ATTENTION : PAS DE SÉANCE LE 31/10 ! ==== */ 
 + 
 +==== Séance 7. 2/11 ====
  
 == A. Bostan == == A. Bostan ==
Line 86: Line 91:
 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-chap-10-et-11.pdf|Exercices]]. +/* [[http://specfun.inria.fr/bostan/mpri/exos-chap-10-et-11.pdf|Exercices]]. */ 
-==== Séance 8. 14/11 ====+ 
 +==== Séance 8. 9/11 ====
  
 == A. Bostan == == A. Bostan ==
  
-[[http://specfun.inria.fr/bostan/mpri/revision1.pdf|Exercices de révision]]+Exercices de révision.
  
-==== ATTENTION PAS DE SÉANCE LE 21/11 ! ====+/* [[http://specfun.inria.fr/bostan/mpri/revision1.pdf|Exercices de révision]] */
  
-==== EXAMEN SUR LA PREMIÈRE PÉRIODE le 28/11 ====+==== ATTENTION : PAS DE SÉANCE LE 16/11 ====
  
-[[http://algo.inria.fr/salvy/mpri/Partiel2013.pdf|Sujet de 2013]]+==== EXAMEN SUR LA PREMIÈRE PÉRIODE LE 23/11 OU LE 30/11 (À DÉTERMINER) ====
  
-==== ATTENTION PAS DE SÉANCE LE 5/12 ====+[[http://algo.inria.fr/salvy/mpri/Partiel2013.pdf|Sujet de 2013]]
  
-==== Séance 9. 12/12 ====+==== Séance 9. 7/12 ====
  
 == F. Chyzak == == F. Chyzak ==
Line 107: Line 113:
 Séries hypergéométriques, algorithmes de Gosper, de Zeilberger et de Petkovšek. (Chap. 29 et un bout du Chap. 16) Séries hypergéométriques, algorithmes de Gosper, de Zeilberger et de Petkovšek. (Chap. 29 et un bout du Chap. 16)
  
-[[http://specfun.inria.fr/chyzak/mpri/exos-chap-29.pdf|Exercices]].+/* [[http://specfun.inria.fr/chyzak/mpri/exos-chap-29.pdf|Exercices]]. */
  
 +/* ==== ATTENTION : PAS DE SÉANCE LE 14/12 ==== */
  
-==== Séance 10. 19/12 ====+==== Séance 10. 14/12 OU 04/01 (À DÉTERMINER) ====
  
 == F. Chyzak == == F. Chyzak ==
Line 122: Line 129:
  
  
-==== Séance 11. 9/01 ====+==== Séance 11. 11/01 ====
  
 == F. Chyzak. == == F. Chyzak. ==
Line 128: Line 135:
 É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-chap-30.pdf|Exercices]]. */
-[[http://specfun.inria.fr/chyzak/mpri/exos-chap-30.pdf|Exercices]].+
  
-/* ==== Séance 12. 9/01 ==== */+/* ==== Séance 12. 18/01 ==== */
  
 /* == F. Chyzak == */ /* == F. Chyzak == */
Line 138: Line 144:
  
  
-==== Séance 12. 16/01 ====+==== Séance 12. 18/01 ====
  
 == F. Chyzak == == F. Chyzak ==
  
 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-BGSF.pdf|Exercices]]. */+/* [[http://specfun.inria.fr/chyzak/mpri/exos-chap-31.pdf|Exercices]]. */
  
- +==== Séance 13. 25/01 ====
-==== Séance 13. 23/01 ====+
  
 == F. Chyzak == == F. Chyzak ==
Line 154: Line 159:
 /* [[http://algo.inria.fr/chyzak/mpri/exos-SISFS.pdf|Exercices]]. */ /* [[http://algo.inria.fr/chyzak/mpri/exos-SISFS.pdf|Exercices]]. */
  
-==== Séance 14. 30/01 ====+==== //Attention : les dates suivantes sont sujettes à anticipation ou modification.// ==== 
 + 
 + 
 +==== Séance 14. 8/02 ====
  
 == A. Bostan == == A. Bostan ==
  
-Calcul formel pour la combinatoire+Diagonals and Creative Telescoping — From 1G to 4G algorithms
-/* [[http://specfun.inria.fr/bostan/mpri/mpri19-p1.pdf|Slides]] */ +/* [[http://specfun.inria.fr/bostan/mpri/DiagRedCT-ex.pdf | Exercices.]] */
-/* [[http://specfun.inria.fr/bostan/mpri/mpri19-ex.pdf|Exercice]] */+
  
-==== Séance 15. 6/02 ====+==== Séance 15. 15/02 ====
  
 == A. Bostan == == A. Bostan ==
  
-Intégration des fractions rationnelles : algorithmes et complexité.+Calcul formel pour la combinatoire.
 /* [[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]] */
 +/* [[http://specfun.inria.fr/bostan/mpri/mpri19-ex.pdf|Exercice]] */
  
- +==== Séance 16. 22/02 ====
-==== Séance 16. 13/02 ====+
  
 == A. Bostan == == A. Bostan ==
Line 178: Line 185:
 Exercices de révision. Exercices de révision.
  
-==== ATTENTION : PAS DE SÉANCE LE 20/02 ! ====+/* ==== ATTENTION : PAS DE SÉANCE LE 22/02 ! ==== */
  
-==== EXAMEN SUR LA DEUXIÈME PÉRIODE le 27/02 ====+==== EXAMEN SUR LA DEUXIÈME PÉRIODE LE 8/03 ====
  
 ==== Bibliographie ==== ==== Bibliographie ====
  
-Quelques ouvrages des années 1990 :+Quelques ouvrages des années 1990-2000 :
  
   * D. Cox, J. Little, D. O'Shea, //Ideals, Varieties and Algorithms//. Undergraduate Texts in Mathematics, Springer Verlag, 2nd edition, 1996.   * D. Cox, J. Little, D. O'Shea, //Ideals, Varieties and Algorithms//. Undergraduate Texts in Mathematics, Springer Verlag, 2nd edition, 1996.
 
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