Theoretical Computer Science 2022: различия между версиями
Перейти к навигации
Перейти к поиску
Bbauwens (обсуждение | вклад) Нет описания правки |
Bbauwens (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
= Classes = | = Classes = | ||
Wednesdays 18:10–21:00, | Wednesdays 18:10–21:00, on [https://us02web.zoom.us/j/82300259484?pwd=NWxXekxBeE5yMm9UTmwvLzNNNGlnUT09 zoom] | ||
= Dates and Deadlines = | = Dates and Deadlines = | ||
= Grading = | = Grading = | ||
Exam: 40%<br> | Exam: 40%<br> | ||
| Строка 12: | Строка 11: | ||
Project: 40% | Project: 40% | ||
There are 3 homeworks with deadlines: 09.02, 16.02, 23.02 | |||
= Course Materials = | = Course Materials = | ||
| Строка 26: | Строка 26: | ||
! Video !! Summary !! Notes | ! Video !! Summary !! Notes | ||
|- | |- | ||
|| [https://youtu.be/BHm2eHFnC6U 19.01] || Regular languages || [https://www.dropbox.com/s/uz1gyurwjvfwe77/automata.pdf?dl=0 lecture 1] | || [https://youtu.be/BHm2eHFnC6U 19.01] || Regular languages: (non)deterministic automata and their equivalence, pumping lemma, closure properties || [https://www.dropbox.com/s/uz1gyurwjvfwe77/automata.pdf?dl=0 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 | |||
|} | |} | ||
Версия от 20:07, 19 января 2022
Classes
Wednesdays 18:10–21:00, on zoom
Dates and Deadlines
Grading
Exam: 40%
Homework: 20%
Project: 40%
There are 3 homeworks with deadlines: 09.02, 16.02, 23.02
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 |
Office hours
| Person | Monday | Tuesday | Wednesday | Thursday | Friday |
|---|---|---|---|---|---|
| Bruno Bauwens, S834, Zoom | 14:00-20:00 |