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/10/09 11:27]
phs [Oct. 2, 2019]
cours:c-1-17 [2019/10/23 10:47] (current)
phs [Plan et intervenants du cours 2019-2020]
Line 12: Line 12:
 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 Cournot 321, à l'ENS Paris-Saclay.  Voir le [[http://www.lsv.ens-cachan.fr/info-acces|plan]].
  
-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: 6 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: 6 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. 
 + 
 +Here is this year's [[http://www.lsv.ens-cachan.fr/~phs/partiel_complexite_avance_oct2019.pdf|partiel exam + correction]].
  
-Partial exam : Oct 23rd from 10h45 to 12h45.  
 Final exam : TBA Final exam : TBA
  
Line 59: Line 62:
 ===== Oct. 9, 2019 ===== ===== Oct. 9, 2019 =====
  
-  * (2.12) Def. logspace reductions & basic properties.  +  * (2.12) Def. logspace reductions, complete problems & basic properties.  
-  * REACH aka GAP is NL-complete for logspace reductions, SAT is NP-complete for logspace reductions.+  * REACH aka GAP is NL-complete
 +  * SAT is NP-complete.
  
-/* +===== Oct. 162019 =====
-===== Oct. 102018 =====+
  
-  * (2.21) Thm (Stockmeyer-Meyer 1973) QBF is PSPACE-complete +  * Alternating Turing machines. 
-  * CIRCUIT_VALUE is PTIME-complete+  * (2.21) Thm (Stockmeyer-Meyer 1973) QBF is PSPACE-complete, hence PSPACE=APTIME. 
 +  * (3.8) Padding lemma, allowing (3.9) SPACE(poly(f(n)) = TIME(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.
  
 +/*
 ===== Oct. 17, 2017 ===== ===== Oct. 17, 2017 =====
  
 
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