Theoretical Computer Science 2022 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
Bbauwens (обсуждение | вклад) |
Bbauwens (обсуждение | вклад) |
||
Строка 29: | Строка 29: | ||
|| 25.01 || Turing machines, undecidability of: Halting program, Wang tiling, Fractran || | || 25.01 || Turing machines, undecidability of: Halting program, Wang tiling, Fractran || | ||
|- | |- | ||
− | || 02.02 || Godel's incompleteness theorems, classes P and NP || | + | || 02.02 || Godel's incompleteness theorems, classes P and NP || [https://www.dropbox.com/s/jslijos3lp03m83/turingDef.pdf?dl=0 lecture 2.A] [https://www.dropbox.com/s/nj7hw8udpbaha37/undecidable.pdf?dl=0 lecture 2.B] (drafts) |
|- | |- | ||
|| 09.02 || NP-hardness, EXP, PSPACE, PSPACE-hardness, BPP, Polynomial time hierarchy|| | || 09.02 || NP-hardness, EXP, PSPACE, PSPACE-hardness, BPP, Polynomial time hierarchy|| |
Версия 18:06, 25 января 2022
Содержание
Classes
Wednesdays 18:10–21:00, on zoom
Teacher: Bruno Bauwens
Grading
Exam: 40%
Homework: 20%
Project: 40%
There are 3 homeworks with deadlines: 09.02, 16.02, 23.02, 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, undecidability of: Halting program, Wang tiling, Fractran | |
02.02 | Godel's incompleteness theorems, classes P and NP | lecture 2.A lecture 2.B (drafts) |
09.02 | NP-hardness, EXP, PSPACE, PSPACE-hardness, BPP, Polynomial time hierarchy | |
16.02 | Parameterized complexity (1): the class FPT and kernelization | |
23.02 | Parameterized complexity (2): W-hierarchy, graph domination | |
02.03 | Projects | |
09.03 | Projects | |
16.03 | Final exam |
Office hours
Person | Monday | Tuesday | Wednesday | Thursday | Friday |
---|---|---|---|---|---|
Bruno Bauwens, S834, Zoom | 14:00-20:00 |