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

Complexité avancée (48h, 6 ECTS)

Responsable : Jean Goubault-Larrecq (LSV, ENS Cachan).

Plan et intervenants du cours 2019-2020

Intervenants: Philippe Schnoebelen puis Jean Goubault-Larrecq pour le cours, et Aliaume Lopez puis Rémy Poulain 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 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.

Partial exam : Oct 23rd from 10h45 to 12h45. Final exam : TBA

Motivations et objectifs du cours

La théorie de la complexité va bien au-delà de celle de la NP-complétude. Le but de ce cours est d'aller regarder un certain nombre d'autres constructions fondamentales de la théorie de la complexité: complexité en espace, notions de machines alternantes, ou randomisées. On y verra quelques théorèmes fascinants: l'équivalence du temps alternant et de l'espace déterministe par exemple, ou le théorème IP=PSPACE de Shamir.

Description du cours

The course is based on the following lecture notes polycopié (1st part) and 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.

Langues du cours :

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 étudiants seront autorisés à rédiger leur copie d'examen en français ou en anglais.

Pré-requis

On s'attend à ce que les étudiants aient une certaine familiarité avec la notion de Machine de Turing, la classe P (temps polynomial déterministe), la classe NP (temps polynomial non-déterministe), les notions de réductions en temps polynomial, le théorème de Cook (SAT est NP-complet) même si toutes ses notions seront rapidement revues au début du cours.

Cours liés

Bibliographie

Livres:

  • 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/)

Examens et devoirs

Le corrigé du DM de l'année 2009-2010.

Le corrigé de l'examen de l'année 2009-2010.

Le DM de l'année 2011-2012, et son corrigé.

L'examen de l'année 2011-2012, et son corrigé.

Le DM (avec corrigé) de l'année 2017-2018.

L'examen de l'année 2017-2018, et son corrigé.

Le 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