Theoretical Computer Science 2022 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
Bbauwens (обсуждение | вклад) |
Bbauwens (обсуждение | вклад) |
||
Строка 3: | Строка 3: | ||
Wednesdays 18:10–21:00, on [https://us02web.zoom.us/j/82300259484?pwd=NWxXekxBeE5yMm9UTmwvLzNNNGlnUT09 zoom] | Wednesdays 18:10–21:00, on [https://us02web.zoom.us/j/82300259484?pwd=NWxXekxBeE5yMm9UTmwvLzNNNGlnUT09 zoom] | ||
− | + | Teacher: [https://www.hse.ru/en/org/persons/160550073 Bruno Bauwens] | |
= Grading = | = Grading = | ||
Строка 11: | Строка 11: | ||
Project: 40% | Project: 40% | ||
− | There are 3 homeworks with deadlines: 09.02, 16.02, 23.02 | + | There are 3 homeworks with deadlines: 09.02, 16.02, 23.02, before the lecture |
= Course Materials = | = Course Materials = |
Версия 23:10, 19 января 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 theorem, Wang tiling, Fractran | ||
02.02 | Godel's incompleteness theorems, classes P and NP | ||
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 | ||
02.03 | Projects | ||
09.03 | Porjects | ||
16.03 | Final exam |
Office hours
Person | Monday | Tuesday | Wednesday | Thursday | Friday |
---|---|---|---|---|---|
Bruno Bauwens, S834, Zoom | 14:00-20:00 |