Версия 18:02, 9 февраля 2022

Содержание

Wednesdays 18:10–21:00, on zoom

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

There are 3 homeworks with deadlines: 16.02, 23.02, 02.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	time and space hierarchy theorems classes P and NP,
23.02	NP-completeness
02.03	PSPACE, PSPACE-hardness, EXP, BPP, Polynomial time hierarchy
09.03	Parameterized complexity (1): the class FPT and kernelization
16.03	Parameterized complexity (2): W-hierarchy, graph domination
23.03	Final exam

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

Warn me in advance by email.

@@ Строка 29: / Строка 29: @@
   || 25.01 || Turing machines and register machines || [https://www.dropbox.com/s/jslijos3lp03m83/turingDef.pdf?dl=0 lecture 2]
 |-
-  || <span style="color:red">09.02</span> || undecidability of: Halting program, Wang tiling, Fractran Godel's incompleteness theorems || [https://www.dropbox.com/s/nj7hw8udpbaha37/undecidable.pdf?dl=0 lecture 3] (draft)
+  || <span style="color:red">09.02</span> || undecidability of: Halting program, Wang tiling, Fractran Godel's incompleteness theorems || [https://www.dropbox.com/s/nj7hw8udpbaha37/undecidable.pdf?dl=0 lecture 3.A] [https://www.dropbox.com/s/ykbkpjm4as46nay/incompleteness.pdf?dl=0 3.B]
 |-
   || 16.02 || time and space hierarchy theorems classes P and NP, ||