Версия 23:25, 2 марта 2023

Содержание

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

Homeworks need to be emailed to brbauwens -at- gmail.com before the start of the lecture next lecture. Put tcs in the subject line.

For practical information ask to join the telegram group.

Video	Summary	Notes	Homework
08.02	Regular languages 1: deterministic automata, pumping lemma, closure properties	lecture 1 & 2	hw1
15.02	Regular languages 2: nondeterministic automata and regular expressions		hw2
01.03	Warmup in discrete math. Chapter 1 of discrete math for computer science, by Golovnev, Kulikov, Podolskii, Shen. Turing machines	Turing machines	hw3
15.03	Undecidability and incompleteness	lecture 3.A 3.B
15.03	The classes P, EXP, PSPACE, EXPSPACE and NP. Time and space hierarchy theorems	seminar
22.03	NP-completeness, circuits, proof of the Levin-Cook theorem (see Mertens&Moore chapter 5)	notes circuits reductions
29.03	Reductions. The classes RP, coRP and BPP, primes in BPP
05.04(?)	Exam
May	Projects

Homework: 25%

Theory exam: 25%

Problem solving exam: 25%

Project: 25%

Passing threshold is 4/10. Grades above 5/10 are rounded up, the other grades are rounded down.

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.

@@ Строка 25: / Строка 25: @@
   || 15.02 || Regular languages 2: nondeterministic automata and regular expressions || || [https://www.dropbox.com/s/4ylwf3hdoncym8v/2_HW.pdf?dl=0 hw2]
 |-
-  || 22.02 || Turing machines, the Halting problem, Wang tiling, Fractran, Godel incompleteness theorems || [https://www.dropbox.com/s/jslijos3lp03m83/turingDef.pdf?dl=0 lecture 2][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] ||
+  || 01.03 || Warmup in discrete math. Chapter 1 of discrete math for computer science, by Golovnev, Kulikov, Podolskii, Shen.  Turing machines || [https://www.dropbox.com/s/jslijos3lp03m83/turingDef.pdf?dl=0 Turing machines] || [https://www.dropbox.com/s/f3q0q0378y1o2y6/3_HW.pdf?dl=0 hw3]
 |-
-  || 01.03 || Famous polynomial time algorithms: Dijkstra, Kruskal, dynamic programming || ||
+  || 15.03 || Undecidability and incompleteness || [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] ||
-|-
- || 08.03 || Woman's day, no lecture
 |-
   || 15.03 || The classes P, EXP, PSPACE, EXPSPACE and NP. Time and space hierarchy theorems || [https://www.dropbox.com/s/5amd18ey45qs4x3/cc_seminar.pdf?dl=0 seminar] ||