TCS 2024

Материал из Wiki - Факультет компьютерных наук
Версия от 22:10, 4 апреля 2024; Bauwens (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Classes

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

Teacher: Bruno Bauwens

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

Grades homework

For practical information click the this link to join the telegram group.


Course Materials

Video Summary Notes Homework
01.02 Regular languages 1: deterministic automata, pumping lemma, closure properties (old recording) lecture 1 & 2 hw1
08.02 Regular languages 2: nondeterministic automata and regular expressions. Definition of Turing machines. Turing machines hw2
15.02 Undecidable problems and computability theory Turing completeness hw3
07.03 The classes P, EXP, PSPACE, EXPSPACE, NP, reductions and completeness. Sipser chapt 7, class_NP.pdf hw4
14.03 Circuits and completeness of 3SAT. More reductions. circuits.pdf hw5
21.03 Parameterized complexity, the class FPT, kernelization, colorcoding. Colorcoding and background: in this lecture presentation hw6
25.03? Treewidth. (this course) Slides hw7 ex 1,2,4


References

Main reference

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


Basic math

Golovnev, Kulikov, Podolskii, Shen, Discrete mathematics for computer science, 2020.

Lecture notes: Discrete Mathematics, L. Lovasz, K. Vesztergombi

Лекции по дискретной математике (черновик учебника, in Russian)


Computational complexity

Mertens and Moore, The Nature of Computation, 2011. (Pleasant reading with a lot of interesting background, but perhaps too much.)

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


Mathematical writing

Sosinsky, Как написать математическую статью по-английски, 2000.

Knuth, Technical writing, transcripts of lectures, 1987.

Gillman, Writing Mathematics Well, 1987.


Parameterized complexity

M. Cygan, F. Fomin and 6 others, Parameterized algorithms, 2016


Office hours

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

Warn me in advance by email.