Содержание

Classes

Wednesdays 18:10–21:00, in room S834.

For practical information ask to join the telegram group.

Video	Summary	Notes
08.02	Regular languages 1: deterministic automata, pumping lemma, closure properties	lecture 1
15.02	Regular languages (2): equivalence between deterministic and nondeterministic automata, regular expressions]
22.02	Turing machines, the Halting problem, Godel incompleteness theorems	lecture 2 lecture 3.A 3.B
02.03	Famous polynomial time algorithms: Dijkstra, Kruskal, dynamic programming
09.03	The classes P, EXP, PSPACE, EXPSPACE and NP. Time and space hierarchy theorems.	seminar
16.03	NP-completeness, circuits, proof of the Levin-Cook theorem, reductions (see also Mertens&Moore chapter 5)	notes circuits reductions
23.03	Finishing previous lecture, the classes RP, coRP and BPP, primes in BPP
30.03(?)	Exam
may	Projects

Homework: 25%

Theory exam: 25%

Problem solving exam: 25%

Project: 25%

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.)

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-18:00

Warn me in advance by email.