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-1-17 [2019/11/08 23:25]
phs [Oct. 16, 2019]
cours:c-1-17 [2020/09/18 16:18] (current)
goubault [Description du cours]
Line 7: Line 7:
 ====== Plan et intervenants du cours 2019-2020 ====== ====== Plan et intervenants du cours 2019-2020 ======
  
-Intervenants: [[http://www.lsv.fr/~phs|Philippe Schnoebelen]] puis [[http://www.lsv.fr/~goubault|Jean Goubault-Larrecq]] pour le cours, et [[http://perso.crans.org/alopez|Aliaume Lopez]] puis [[https://www.lip6.fr/actualite/personnes-fiche.php?ident=D2113|Rémy Poulain]] pour les TDs.+Intervenants: [[http://www.lsv.fr/~phs|Philippe Schnoebelen]] puis [[http://www.lsv.fr/~goubault|Jean Goubault-Larrecq]] pour le cours, et [[http://www.lsv.fr/~bordais|Benjamin Bordais]] pour les TDs.
  
  
-Les cours ont lieu le Mercredi de 8h30 à 10h30, suivis des TDs de 10h45 à 12h45, en salle Cournot 321, à l'ENS Paris-Saclay.  Voir le [[http://www.lsv.ens-cachan.fr/info-acces|plan]].+Les cours ont lieu le Mercredi de 8h30 à 10h30, suivis des TDs de 10h45 à 12h45, en salle 2E29, à l'ENS Paris-Saclay à Gif-s-Yvette.  Voir [[https://ens-paris-saclay.fr/lecole/venir-lecole|comment s'y rendre]].
  
-Planning: début du cours le 25 sept 2019. Pas de cours ni TDs le 30 oct. Début de la 2ème partie du cours: nov. +Planning: début du cours le 23 sept 2020. Pas de cours ni TDs le 28 oct. Début de la 2ème partie du cours: 18 nov. 
  
-**Partial exam : Oct 23rd from 10h30 to 12h30**. This will be a written exam, consisting of exercises similar to what has been done in TD class, and will count for half of the global mark. The exam assumes knowledge of chapters 1, 2 and 3 of the lecture notes (and not chapter 4 that was not covered in class). Documents, including your lecture notes, are not allowed. On that day, the partial exam replaces the usual class followed by TD.+/*  **Partial exam : Oct 21st from 10h30 to 12h30**. This will be a written exam, consisting of exercises similar to what has been done in TD class, and will count for half of the global mark. The exam assumes knowledge of chapters 1, 2 and 3 of the lecture notes (and not chapter 4 that was not covered in class). Documents, including your lecture notes, are not allowed. On that day, the partial exam replaces the usual class followed by TD.
  
 Here is this year's [[http://www.lsv.ens-cachan.fr/~phs/partiel_complexite_avance_oct2019.pdf|partiel exam + correction]]. Here is this year's [[http://www.lsv.ens-cachan.fr/~phs/partiel_complexite_avance_oct2019.pdf|partiel exam + correction]].
  
-Final exam : TBA+Final exam : TBA */
  
  
Line 36: Line 36:
  
 The course is based on the following lecture notes The course is based on the following lecture notes
-[[http://www.lsv.ens-cachan.fr/~goubault/Complexite/nl.pdf|polycopié (1st part)]] and  +[[http://www.lsv.fr/~goubault/Complexite/nl.pdf|polycopié (1st part)]] and  
-[[http://www.lsv.ens-cachan.fr/~goubault/Complexite/pcp.pdf|polycopié (2nd part)]].  (Note: il semble que le premier poly ait des problèmes de polices sous Acrobat Reader 9; aucun problème connu sous xpdf ou evince.)+[[http://www.lsv.fr/~goubault/Complexite/pcp.pdf|polycopié (2nd part)]].  (Note: il semble que le premier poly ait des problèmes de polices sous Acrobat Reader 9; aucun problème connu sous xpdf ou evince.)
  
 This page will be updated after each class with a summary of what has been covered. Numbers, e.g. "(2.1)", refer to statement in the lecture notes. This page will be updated after each class with a summary of what has been covered. Numbers, e.g. "(2.1)", refer to statement in the lecture notes.
 +
 +A small selection of slides:
 +
 +  * [[http://www.lsv.fr/~goubault/Complexite/rp-zpp_compressed.pdf|Randomized Turing machines, RP, coRP, ZPP]]: covers Sections 1.1 and 1.2 of the [[http://www.lsv.fr/~goubault/Complexite/pcp.pdf|polycopié (2nd part)]]
 +  * [[http://www.lsv.fr/~goubault/Complexite/bpp_compressed.pdf|BPP (part 1)]]: covers Section 1.3 and the Sipser-Gács-Lautemann theorem (Proposition 1.24) of the [[http://www.lsv.fr/~goubault/Complexite/pcp.pdf|polycopié (2nd part)]]
 +  * (more to come)
 +
  
 /* Exercices sheets and solutions are available on  [[http://www.lsv.ens-cachan.fr/~jacomme|Charlie's webpage]]. */ /* Exercices sheets and solutions are available on  [[http://www.lsv.ens-cachan.fr/~jacomme|Charlie's webpage]]. */
 +
 +/*
  
 ===== Sep. 25, 2019 ===== ===== Sep. 25, 2019 =====
Line 72: Line 81:
   * (3.8) Padding lemma, allowing (3.9) SPACE(poly(f(n)) = ATIME(poly(f(n)) for any f constructible and s.t. f(n) ≥ n for large enough n.   * (3.8) Padding lemma, allowing (3.9) SPACE(poly(f(n)) = ATIME(poly(f(n)) for any f constructible and s.t. f(n) ≥ n for large enough n.
   * (3.18) CIRCUIT_VALUE is PTIME-complete, allowing PTIME=ALOGSPACE, and more generally (3.19) TIME(2^O(f(n)) = ASPACE(f(n)) with f as above.   * (3.18) CIRCUIT_VALUE is PTIME-complete, allowing PTIME=ALOGSPACE, and more generally (3.19) TIME(2^O(f(n)) = ASPACE(f(n)) with f as above.
 +
 +*/
  
 /* /*
Line 157: Line 168:
  * Christos H. Papadimitriou.  Computational Complexity.  Addison-Wesley, 1994.  * Christos H. Papadimitriou.  Computational Complexity.  Addison-Wesley, 1994.
  * Sanjeev Arora and Boaz Barak. Computational Complexity. Cambridge University Press, 2009. \\ (une pré-version est gracieusement disponible ici [[http://www.cs.princeton.edu/theory/complexity/]])  * Sanjeev Arora and Boaz Barak. Computational Complexity. Cambridge University Press, 2009. \\ (une pré-version est gracieusement disponible ici [[http://www.cs.princeton.edu/theory/complexity/]])
 +
 +        * Sylvain Périfel. Complexité algorithmique.  Ellipses, 2014.  Disponible [[https://www.irif.fr/~sperifel/livre_complexite.html|en ligne]].
  
 ====== Examens et devoirs ====== ====== Examens et devoirs ======
Line 173: Line 186:
 L'[[http://www.lsv.ens-cachan.fr/~goubault/Complexite/exam18.pdf|examen]] de l'année 2017-2018, et son [[http://www.lsv.ens-cachan.fr/~goubault/Complexite/exam18_ans.pdf|corrigé]]. L'[[http://www.lsv.ens-cachan.fr/~goubault/Complexite/exam18.pdf|examen]] de l'année 2017-2018, et son [[http://www.lsv.ens-cachan.fr/~goubault/Complexite/exam18_ans.pdf|corrigé]].
  
-Le [[http://www.lsv.ens-cachan.fr/~phs/partiel_complexite_avance_oct2018.pdf|partiel (corrigé)]] de l'année 2018-2019.+Le [[http://www.lsv.ens-cachan.fr/~phs/partiel_complexite_avance_oct2018.pdf|partiel (corrigé)]] de l'année 2018-2019.  
 + 
 +Le [[http://www.lsv.ens-cachan.fr/~phs/partiel_complexite_avance_oct2019.pdf|partiel (corrigé)]] de l'année 2019-2020
  
 +L'[[http://www.lsv.ens-cachan.fr/~goubault/Complexite/exam20.pdf|examen]] de l'année 2019-2020, et son [[http://www.lsv.ens-cachan.fr/~goubault/Complexite/exam20_ans.pdf|corrigé]].
  
 
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