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 [2018/10/24 13:23]
phs [Plan et intervenants du cours 2017-2018]
cours:c-1-17 [2019/09/12 23:13] (current)
phs [Plan et intervenants du cours 2019-2020]
Line 5: Line 5:
 [[http://www.lsv.ens-cachan.fr/~goubault/|Jean Goubault-Larrecq]] (LSV, ENS Cachan). [[http://www.lsv.ens-cachan.fr/~goubault/|Jean Goubault-Larrecq]] (LSV, ENS Cachan).
  
-====== Plan et intervenants du cours 2017-2018 ======+====== 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://www.lsv.ens-cachan.fr/~jacomme|Charlie Jacomme]] 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://perso.crans.org/alopez|Aliaume Lopez]] puis [[https://www.lip6.fr/actualite/personnes-fiche.php?ident=D2113|Rémy Poulain]] pour les TDs.
  
  
-Les cours ont lieu le Mercredi de 8h30 à 10h30, suivis des TDs de 10h45 à 12h45, en salle Cournot 419, à l'ENS Cachan.  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 Cournot 321, à l'ENS Paris-Saclay.  Voir le [[http://www.lsv.ens-cachan.fr/info-acces|plan]].
  
-Planning: début du cours le 19 sept. 2018. Pas de cours ni TDs le 31 oct. Début de la 2ème partie du cours: nov.  +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. 
- +
-Partial exam : Thursday Oct 24th from 10h45 to 12h45.  +
-Here are [[http://www.lsv.ens-cachan.fr/~phs/partiel_complexite_avance_oct2018.pdf|the answers]] (thanks to J. Goubault-Larrecq for sharing an earlier version of this problem).+
  
 +Partial exam : Oct 23rd from 10h45 to 12h45. 
 Final exam : TBA Final exam : TBA
  
Line 34: Line 32:
 ====== Description du cours ====== ====== Description du cours ======
  
-Indexes between parentheses are as in the [[http://www.lsv.ens-cachan.fr/~goubault/Complexite/nl.pdf|lecture notes (1st part)]]+The course is based on the following lecture notes 
-Exercices sheets and solutions are available on  [[http://www.lsv.ens-cachan.fr/~jacomme|Charlie's webpage]].+[[http://www.lsv.ens-cachan.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.)
  
 +This page will be updated after each class with a summary of what has been covered.
 +
 +/* Exercices sheets and solutions are available on  [[http://www.lsv.ens-cachan.fr/~jacomme|Charlie's webpage]]. */
 +
 +/*
 ===== Sep. 19, 2018 ===== ===== Sep. 19, 2018 =====
  
Line 75: Line 79:
    * Between NP and PSPACE: the Polynomial-Time Hierarchy and the Boolean Hierarchy    * Between NP and PSPACE: the Polynomial-Time Hierarchy and the Boolean Hierarchy
  
 +*/
 /* /*
 ===== Oct. 11, 2017 ===== ===== Oct. 11, 2017 =====
Line 118: Line 123:
 ====== Langues du cours : ====== ====== Langues du cours : ======
    
-For 2018-2019 the class will be taught in English if at least one non-French-speaking student requires it. Le polycopié est en français et les élèves peuvent poser des questions, intervenir, etc. en français.+The class will be taught in English if at least one non-French-speaking student requires it. Le polycopié est en français et les élèves peuvent poser des questions, intervenir, etc. en français.
  
 Les questions des sujets d'examen seront en anglais. Les questions des sujets d'examen seront en anglais.
Line 145: Line 150:
  * 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/]])
- 
- Polycopiés: 
- 
- * [[http://www.lsv.ens-cachan.fr/~goubault/Complexite/nl.pdf|première partie]] et [[http://www.lsv.ens-cachan.fr/~goubault/Complexite/pcp.pdf|deuxième partie]].  (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.) 
  
 ====== Examens et devoirs ====== ====== Examens et devoirs ======
Line 164: Line 165:
  
 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.
 +
  
 
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