Версия от 20:10, 19 января 2022

Classes

Wednesdays 18:10–21:00, on zoom

Exam: 40%
Homework: 20%
Project: 40%

There are 3 homeworks with deadlines: 09.02, 16.02, 23.02, before the lecture

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

Person	Monday	Tuesday	Wednesday	Thursday	Friday
Bruno Bauwens, S834, Zoom					14:00-20:00

@@ Строка 3: / Строка 3: @@
 Wednesdays 18:10–21:00, on [https://us02web.zoom.us/j/82300259484?pwd=NWxXekxBeE5yMm9UTmwvLzNNNGlnUT09 zoom]
-= Dates and Deadlines =
+Teacher: [https://www.hse.ru/en/org/persons/160550073 Bruno Bauwens]
 = Grading =
@@ Строка 11: / Строка 11: @@
 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 =