TCS 2024 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
Строка 32: Строка 32:
 
  || 14.03 || Circuits and completeness of 3SAT. More reductions. || [https://www.dropbox.com/scl/fi/19s582oohxvdv2l8zqb6j/circuits.pdf?rlkey=4t88ofltyq4www15zj3o4cy9v&dl=0 circuits.pdf]  ||
 
  || 14.03 || Circuits and completeness of 3SAT. More reductions. || [https://www.dropbox.com/scl/fi/19s582oohxvdv2l8zqb6j/circuits.pdf?rlkey=4t88ofltyq4www15zj3o4cy9v&dl=0 circuits.pdf]  ||
 
|-
 
|-
  || 21.03 || Parameterized complexity, the class FPT, kernelization. ||   ||  
+
  || 21.03 || Parameterized complexity, the class FPT, kernelization. || [https://www.dropbox.com/scl/fi/uo9oga7blo0omy7rro8l6/5_HW.pdf?rlkey=m9hu2bwsm12gfu8g9zvx97jz8&dl=0 hw5] ||  
 
|-  
 
|-  
 
  || 25.03? || Treewidth and the W-hierarchy  ||  ||  
 
  || 25.03? || Treewidth and the W-hierarchy  ||  ||  

Версия 00:28, 16 марта 2024

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
21.03 Parameterized complexity, the class FPT, kernelization. hw5
25.03? Treewidth and the W-hierarchy


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.