Версия 17:57, 2 марта 2022

Содержание

Wednesdays 18:10–21:00, on zoom

For practical information join the telegram group

Exam: 40%
Homework: 20%
Project: 40%

There are 2 homeworks with deadlines: 23.02, 09.03 before the lecture

The main reference for the first 4 lectures is Sipser's book "Introduction to the theory of computation", chapters 1, 2–7.

Video	Summary	Notes
19.01	Regular languages: (non)deterministic automata and their equivalence, pumping lemma, closure properties	lecture 1
25.01	Turing machines and register machines	lecture 2
09.02	undecidability of: Halting program, Wang tiling, Fractran Godel's incompleteness theorems	lecture 3.A 3.B
16.02	The classes P, EXP, PSPACE, EXPSPACE. Dynamic programming. Time and space hierarchy theorems.	seminar
23.02	Holliday
02.03	NP-completeness	notes
09.03	PSPACE, PSPACE-hardness, EXP, BPP, Polynomial time hierarchy
16.03	Parameterized complexity (1): the class FPT and kernelization
23.03	Parameterized complexity (2): W-hierarchy, graph domination
30.03	Projects
06.04	Exam

Person	Monday	Tuesday	Wednesday	Thursday	Friday
Bruno Bauwens, S834, Zoom					14:00-20:00

Warn me in advance by email.

@@ Строка 37: / Строка 37: @@
   || <span style="color:gray">23.02</span> || <span style="color:gray">Holliday</span> ||
 |-
-  || 02.03 || NP-completeness ||
+  || 02.03 || NP-completeness || [https://www.dropbox.com/s/90m0yxt62f02mmm/classNP.pdf?dl=0 notes]
 |-
   || 09.03 || PSPACE, PSPACE-hardness, EXP, BPP, Polynomial time hierarchy ||