Theoretical Computer Science 2022 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
Bbauwens (обсуждение | вклад) |
Bbauwens (обсуждение | вклад) |
||
| Строка 27: | Строка 27: | ||
|| [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] | || [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 | + | || 25.01 || Turing machines and register machines || [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) |
|- | |- | ||
| − | || <span style="color:red">09.02</span> || Godel's incompleteness theorems | + | || <span style="color:red">09.02</span> || undecidability of: Halting program, Wang tiling, Fractran Godel's incompleteness theorems || |
|- | |- | ||
| − | || 16.02 || NP | + | || 16.02 || time and space hierarchy theorems classes P and NP, || |
|- | |- | ||
| − | || 23.02 || | + | || 23.02 || NP-completeness || |
|- | |- | ||
| − | || 02.03 || | + | || 02.03 || PSPACE, PSPACE-hardness, EXP, BPP, Polynomial time hierarchy || |
|- | |- | ||
| − | || 09.03 || | + | || 09.03 || Parameterized complexity (1): the class FPT and kernelization || |
|- | |- | ||
| − | || 16.03 || | + | || 16.03 || Parameterized complexity (2): W-hierarchy, graph domination || |
|- | |- | ||
|| 23.03 || Final exam || | || 23.03 || Final exam || | ||
Версия 14:05, 9 февраля 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: 16.02, 23.02, 02.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.A lecture 2.B (drafts) |
| 09.02 | undecidability of: Halting program, Wang tiling, Fractran Godel's incompleteness theorems | |
| 16.02 | time and space hierarchy theorems classes P and NP, | |
| 23.02 | NP-completeness | |
| 02.03 | PSPACE, PSPACE-hardness, EXP, BPP, Polynomial time hierarchy | |
| 09.03 | Parameterized complexity (1): the class FPT and kernelization | |
| 16.03 | Parameterized complexity (2): W-hierarchy, graph domination | |
| 23.03 | Final exam |
Office hours
| Person | Monday | Tuesday | Wednesday | Thursday | Friday |
|---|---|---|---|---|---|
| Bruno Bauwens, S834, Zoom | 14:00-20:00 |
Warn me in advance by email.
