Theoretical Computer Science 2022 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
Bbauwens (обсуждение | вклад) |
Bbauwens (обсуждение | вклад) |
||
Строка 35: | Строка 35: | ||
|| 16.02 || The classes P, EXP, PSPACE, EXPSPACE. Dynamic programming. Time and space hierarchy theorems. || [https://www.dropbox.com/s/5amd18ey45qs4x3/cc_seminar.pdf?dl=0 seminar] | || 16.02 || The classes P, EXP, PSPACE, EXPSPACE. Dynamic programming. Time and space hierarchy theorems. || [https://www.dropbox.com/s/5amd18ey45qs4x3/cc_seminar.pdf?dl=0 seminar] | ||
|- | |- | ||
− | || <span style="color:gray">23.02</span> | + | || <span style="color:gray">23.02</span> || <span style="color:gray">Holliday</span> || |
|- | |- | ||
|| 02.03 || NP-completeness || | || 02.03 || NP-completeness || |
Версия 11:22, 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
The main reference for the first 4 lectures is Sipser's book "Introduction to the theory of computation", chapters 1, 2–7.
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 | NP-completeness | |
09.03 | PSPACE, PSPACE-hardness, EXP, BPP, Polynomial time hierarchy | |
16.03 | Parameterized complexity (1): the class FPT and kernelization | |
23.03 | Parameterized complexity (2): W-hierarchy, graph domination | |
30.03 | Projects | |
06.04 | Exam |
Office hours
Person | Monday | Tuesday | Wednesday | Thursday | Friday |
---|---|---|---|---|---|
Bruno Bauwens, S834, Zoom | 14:00-20:00 |
Warn me in advance by email.