Содержание

Classes

Wednesdays 18:10–21:00, on zoom

For practical information join the telegram group

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	The class NP and NP-completeness	notes
02.03	Circuits, proof of the Levin-Cook theorem (see also Mertens&Moore chapter 5), more reductions	circuits
16.03	More NP-complete problems	reductions
23.03	Games, PSPACE, Savich theorem, completeness of TQBF	pspace
30.03	Parameterized complexity I: the class FPT and kernelization	notes
13.04	Parameterized complexity II: the W-hierarchy	slides (by Daniel Max) exercises
20.04	No lecture
27.04	Projects

Homework: 50%

Project: 50%

Computational complexity

Sipser, Introduction to the theory of computation", 3rd edition, 2013, chapters 1, 2–8. (Short and good for basic understanding.)

Mertens and Moore, The Nature of Computation, 2011. (Pleasant reading, loads of interesting background, but rather large.)

Arora and Barak, Computational Complexity, 2009. (Use this after you made many exercises in the above books.)

Parameterized algorithms

Marx and Misra, Algorithms and Complexity, course website, 2020.

Fomin and 7 others. Parameterized algorithms, 2015. (This is an advanced book.)

Mathematical writing

Knuth, Technical writing, transcripts of lectures, 1987.

Gillman, Writing Mathematics Well, 1987.

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

Warn me in advance by email.