Table of Contents
Complexité avancée (48h, 6 ECTS)Responsable : Jean Goubault-Larrecq (LSV, ENS Cachan). Plan et intervenants du cours 2022-2023Lecturers: Philippe Schnoebelen then Jean Goubault-Larrecq for the course, and Guillaume Scerri for the exercise sessions (TD). For the first half (until partial exam on November 9th) the lectures take place in room 1-E-14 at ENS Paris-Saclay (Bât. Sud-Ouest), each Monday, from 08h30 to 10h30, followed by exercise sessions from 10h45 to 12h45. Planning: début du cours le 18 sept 2023. Début de la 2ème partie du cours: 13 nov 2023. Evaluation: Two written exams (see exams from previous years at bottom of page). Partial exam : Nov. 6th, 2023 from 08h30 to 10h00. See the exam questions and some sketch answers. Final exam : Jan. 11th, 2023. Motivations et objectifs du coursLa 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 coursThe 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.) Starting Sep. 18, 2023: 1st part of the courseAfter each class, this section will be updated with a summary of the material actually covered. Numbers, e.g. ”(2.1)”, refer to statement in the lecture notes. Sep. 18, 2023What we covered in class:
Corresponding exercise sheet : TD1 Sep. 25, 2023What we covered in class:
Corresponding exercise sheet : TD2 Oct. 2, 2023What we covered in class:
Corresponding exercise sheet : TD3 Oct. 9, 2023What we covered in class:
Corresponding exercise sheet : TD4 Oct. 16, 2022What we covered in class:
What we did not have time to see but should read in the lecture notes:
Corresponding exercise sheet : TD5 Oct. 23, 2023What we covered in class:
Corresponding exercise sheet : TD6 Starting Nov. 13, 2023: 2nd part of the courseThe slides of the second part of the course:
Langues du cours :The class will be taught in English. 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é-requisStudents are expected to be familiar with the concepts and formal definitions for Turing Machines, the class P (problems decidable in deterministic polynomial time), the class NP (non-deterministic polynomial-time), Cook's Theorem (SAT is NP-complete). These notions will only be very quickly recalled during the first classes. Cours liésBibliographieLivres:
Archive: examens et devoirs des années précédentesL'examen final 2021-22, en temps limité. Voici un corrigé. Le partiel 2022-23, en temps limité. Voici un corrigé. L'examen final 2022-23, en temps limité. Voici un corrigé. Le partiel 2023-24, en temps limité. Voici un corrigé. |