TCS 2024 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
Bauwens (обсуждение | вклад) |
Bauwens (обсуждение | вклад) |
||
| Строка 21: | Строка 21: | ||
! Video !! Summary !! Notes !! Homework | ! Video !! Summary !! Notes !! Homework | ||
|- | |- | ||
| − | || [https://youtu.be/BHm2eHFnC6U | + | || [https://youtu.be/BHm2eHFnC6U 01.02] || Regular languages 1: deterministic automata, pumping lemma, closure properties (old recording) || [https://www.dropbox.com/s/l764sm569b9ygic/automata.pdf?dl=0 lecture 1 & 2] || [https://www.dropbox.com/s/okcga6o20qsrxe2/1_HW.pdf?dl=0 hw1] |
|- | |- | ||
| − | || | + | || 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/s/4ylwf3hdoncym8v/2_HW.pdf?dl=0 hw2] |
|- | |- | ||
| − | || | + | || 15.02 || Undecidable problems and computability theory || || [https://www.dropbox.com/s/f3q0q0378y1o2y6/3_HW.pdf?dl=0 hw3] |
|- | |- | ||
| − | || | + | || 22.02 || The classes P, EXP, PSPACE, EXPSPACE, NP, reductions and completeness. || || |
|- | |- | ||
| − | || | + | || 29.02 || Circuits and completeness of 3SAT. More reductions. || || |
|- | |- | ||
| − | || | + | || 07.03 || Parameterized complexity, the class FPT, kernelization. || [https://www.dropbox.com/s/ykbkpjm4as46nay/incompleteness.pdf?dl=0 3.B] || |
|- | |- | ||
| − | || | + | || 14.03 || Treewidth and the W-hierarchy || See Sipser chapts 7 and 8 || |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
|} | |} | ||
| − | |||
| − | + | = 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''' | '''Basic math''' | ||
| Строка 63: | Строка 51: | ||
[http://rubtsov.su/public/DM-HSE-Draft.pdf Лекции по дискретной математике] (черновик учебника, in Russian) | [http://rubtsov.su/public/DM-HSE-Draft.pdf Лекции по дискретной математике] (черновик учебника, in Russian) | ||
| − | |||
'''Computational complexity''' | '''Computational complexity''' | ||
| − | + | Mertens and Moore, The Nature of Computation, 2011. (Pleasant reading with a lot of interesting background, but perhaps too much.) | |
| − | + | ||
| − | Mertens and Moore, The Nature of Computation, 2011. (Pleasant reading | + | |
Arora and Barak, Computational Complexity, 2009. (Use this after you made many exercises in the above books.) | Arora and Barak, Computational Complexity, 2009. (Use this after you made many exercises in the above books.) | ||
| Строка 83: | Строка 68: | ||
Gillman, Writing Mathematics Well, 1987. | Gillman, Writing Mathematics Well, 1987. | ||
<!-- Strunk and White, [https://www.dropbox.com/s/7e6fcdpx3nubvko/strunk-white-1979-elements-of-style.pdf?dl=0 The elements of style], 1979.--> | <!-- Strunk and White, [https://www.dropbox.com/s/7e6fcdpx3nubvko/strunk-white-1979-elements-of-style.pdf?dl=0 The elements of style], 1979.--> | ||
| + | |||
| + | |||
| + | '''Parameterized complexity''' | ||
| + | |||
| + | M. Cygan, F. Fomin and 6 others, Parameterized algorithms, 2016 | ||
Версия 09:55, 10 февраля 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 | hw3 | |
| 22.02 | The classes P, EXP, PSPACE, EXPSPACE, NP, reductions and completeness. | ||
| 29.02 | Circuits and completeness of 3SAT. More reductions. | ||
| 07.03 | Parameterized complexity, the class FPT, kernelization. | 3.B | |
| 14.03 | Treewidth and the W-hierarchy | See Sipser chapts 7 and 8 |
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.
