TCS 2024 — различия между версиями
Bauwens (обсуждение | вклад) |
Bauwens (обсуждение | вклад) |
||
| Строка 26: | Строка 26: | ||
|| 08.02 || Regular languages 2: nondeterministic automata and regular expressions. Definition of Turing machines. || [https://www.dropbox.com/s/jslijos3lp03m83/turingDef.pdf?dl=0 Turing machines] || [https://www.dropbox.com/scl/fi/oxyywmkssmkgs6ucqnyf1/2_HW.pdf?rlkey=fffsptkcqcflb3hnnbsxzba7f&dl=0 hw2] | || 08.02 || Regular languages 2: nondeterministic automata and regular expressions. Definition of Turing machines. || [https://www.dropbox.com/s/jslijos3lp03m83/turingDef.pdf?dl=0 Turing machines] || [https://www.dropbox.com/scl/fi/oxyywmkssmkgs6ucqnyf1/2_HW.pdf?rlkey=fffsptkcqcflb3hnnbsxzba7f&dl=0 hw2] | ||
|- | |- | ||
| − | || 15.02 || Undecidable problems and computability theory || [https://www.dropbox.com/ | + | || 15.02 || Undecidable problems and computability theory || [https://www.dropbox.com/scl/fi/5dwc8heloau7wi5nrw5j1/undecidable.pdf?rlkey=9uj9rsciuhbjkjf77e4b7eg4k&dl=0 Turing completeness] || [https://www.dropbox.com/scl/fi/tpfeo2chpu1btvznn28uz/3_HW.pdf?rlkey=xzpvgcj5gj0w64iq10voydjw7&dl=0 hw3] |
|- | |- | ||
|| 07.03 || The classes P, EXP, PSPACE, EXPSPACE, NP, reductions and completeness. || Sipser chapt 7, [https://www.dropbox.com/scl/fi/6d1ogvurx6bnrb4dhvpzv/classNP.pdf?rlkey=pf6cchn2rp9whgcxjxctm158q&dl=0 class_NP.pdf]|| [https://www.dropbox.com/scl/fi/sci194w0llp4onk27g5by/4_HW.pdf?rlkey=nt6v0kfxw3l9ejtv0x7edlfrf&dl=0 hw4] | || 07.03 || The classes P, EXP, PSPACE, EXPSPACE, NP, reductions and completeness. || Sipser chapt 7, [https://www.dropbox.com/scl/fi/6d1ogvurx6bnrb4dhvpzv/classNP.pdf?rlkey=pf6cchn2rp9whgcxjxctm158q&dl=0 class_NP.pdf]|| [https://www.dropbox.com/scl/fi/sci194w0llp4onk27g5by/4_HW.pdf?rlkey=nt6v0kfxw3l9ejtv0x7edlfrf&dl=0 hw4] | ||
Версия 18:27, 7 марта 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
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. | ||
| 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.
