Theoretical Computer Science 2022 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
Bbauwens (обсуждение | вклад) |
Bbauwens (обсуждение | вклад) |
||
Строка 18: | Строка 18: | ||
= Course Materials = | = Course Materials = | ||
− | + | References: | |
+ | |||
+ | Sipser, Introduction to the theory of computation", 3rd edition, 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 if you have already made many exercises in the previous books.) | ||
+ | |||
+ | Fomin and 7 others. Parameterized algorithms, 2015. (This is an advanced book.) | ||
<!-- If you need some background in math, consider these two sources:<br> | <!-- If you need some background in math, consider these two sources:<br> | ||
Строка 43: | Строка 51: | ||
|| 16.03 || More NP-complete problems || [https://www.dropbox.com/s/wlrssw0q1tfx49p/moreReductions.pdf?dl=0 reductions] | || 16.03 || More NP-complete problems || [https://www.dropbox.com/s/wlrssw0q1tfx49p/moreReductions.pdf?dl=0 reductions] | ||
|- | |- | ||
− | || 23.03 || PSPACE, completeness of TQBF | + | || 23.03 || Games, PSPACE, Savich theorem, completeness of TQBF || [https://www.dropbox.com/s/77sr5nhne411ahz/classPSPACE.pdf?dl=0 pspace] |
|- | |- | ||
− | || 30.03 || | + | || 30.03 || Parameterized complexity I: the class FPT and kernelization || |
|- | |- | ||
− | || 13.04 || Parameterized complexity: the | + | || 13.04 || Parameterized complexity II: the W-hierarchy || |
|- | |- | ||
|| 20.04 || Projects || | || 20.04 || Projects || |
Версия 22:04, 23 марта 2022
Содержание
Classes
Wednesdays 18:10–21:00, on zoom
Teacher: Bruno Bauwens
For practical information join the telegram group
Grading
Exam: 40%
Homework: 20%
Project: 40%
There are 2 homeworks with deadlines: 23.02, 09.03 before the lecture
Course Materials
References:
Sipser, Introduction to the theory of computation", 3rd edition, 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 if you have already made many exercises in the previous books.)
Fomin and 7 others. Parameterized algorithms, 2015. (This is an advanced book.)
Video | Summary | Notes |
---|---|---|
19.01 | Regular languages: (non)deterministic automata and their equivalence, pumping lemma, closure properties | lecture 1 |
25.01 | Turing machines and register machines | lecture 2 |
09.02 | undecidability of: Halting program, Wang tiling, Fractran Godel's incompleteness theorems | lecture 3.A 3.B |
16.02 | The classes P, EXP, PSPACE, EXPSPACE. Dynamic programming. Time and space hierarchy theorems. | seminar |
23.02 | Holliday | |
02.03 | The class NP and NP-completeness | notes |
02.03 | Circuits, proof of the Levin-Cook theorem (see also Mertens&Moore chapter 5), more reductions | circuits |
16.03 | More NP-complete problems | reductions |
23.03 | Games, PSPACE, Savich theorem, completeness of TQBF | pspace |
30.03 | Parameterized complexity I: the class FPT and kernelization | |
13.04 | Parameterized complexity II: the W-hierarchy | |
20.04 | Projects |
Office hours
Person | Monday | Tuesday | Wednesday | Thursday | Friday |
---|---|---|---|---|---|
Bruno Bauwens, S834, Zoom | 14:00-20:00 |
Warn me in advance by email.