Theoretical Computer Science 2022 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
Bbauwens (обсуждение | вклад) |
Bbauwens (обсуждение | вклад) |
||
| Строка 39: | Строка 39: | ||
|| 02.03 || The class NP and NP-completeness || [https://www.dropbox.com/s/90m0yxt62f02mmm/classNP.pdf?dl=0 notes] | || 02.03 || The class NP and NP-completeness || [https://www.dropbox.com/s/90m0yxt62f02mmm/classNP.pdf?dl=0 notes] | ||
|- | |- | ||
| − | || 02.03 || Circuits, proof of the Levin-Cook theorem (see also Mertens&Moore chapter 5, more reductions || [https://www.dropbox.com/s/nen161dakmq3646/circuits.pdf?dl=0 circuits | + | || 02.03 || Circuits, proof of the Levin-Cook theorem (see also Mertens&Moore chapter 5, more reductions || [https://www.dropbox.com/s/nen161dakmq3646/circuits.pdf?dl=0 circuits] |
|- | |- | ||
| − | || 16.03 || More reductions, | + | || 16.03 || More reductions, approximations, (PSPACE) || [https://www.dropbox.com/s/wlrssw0q1tfx49p/moreReductions.pdf?dl=0 reductions] [https://www.dropbox.com/s/mqcwutqk4nm9h8u/approximations.pdf?dl=0 approximations] |
|- | |- | ||
| − | || 23.03 || EXP, BPP, Polynomial-time hierarchy. | + | || 23.03 || PSPACE hardness, EXP, BPP, Polynomial-time hierarchy. || |
|- | |- | ||
| − | || 30.03 || Parameterized complexity | + | || 30.03 || Parameterized complexity: the class FPT and kernelization || |
|- | |- | ||
| − | || 13.04 || | + | || 13.04 || Parameterized complexity (2): W-hierarchy, graph domination || |
|- | |- | ||
| − | || 20.04 || | + | || 20.04 || Projects || |
|} | |} | ||
Версия 18:01, 16 марта 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
The main reference for the first 4 lectures is Sipser's book "Introduction to the theory of computation", 3rd edition, chapters 1, 2–7. Also, Mertens and Moore, The Nature of Computation, 2011.
| 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 reductions, approximations, (PSPACE) | reductions approximations |
| 23.03 | PSPACE hardness, EXP, BPP, Polynomial-time hierarchy. | |
| 30.03 | Parameterized complexity: the class FPT and kernelization | |
| 13.04 | Parameterized complexity (2): W-hierarchy, graph domination | |
| 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.
