Theoretical Computer Science 2022 — различия между версиями
Bbauwens (обсуждение | вклад) |
Bbauwens (обсуждение | вклад) |
||
(не показано 13 промежуточных версии 3 участников) | |||
Строка 1: | Строка 1: | ||
− | |||
− | |||
− | |||
= Classes = | = Classes = | ||
Строка 19: | Строка 16: | ||
{| class="wikitable" | {| class="wikitable" | ||
|- | |- | ||
− | ! Video !! Summary !! Notes | + | ! Video !! Summary !! Notes ! |
|- | |- | ||
− | || [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 and register machines || [https://www.dropbox.com/s/jslijos3lp03m83/turingDef.pdf?dl=0 lecture 2] | + | || 25.01 || Turing machines and register machines || [https://www.dropbox.com/s/jslijos3lp03m83/turingDef.pdf?dl=0 lecture 2] |
|- | |- | ||
− | || 09.02 || undecidability of: Halting program, Wang tiling, Fractran Godel's incompleteness theorems || [https://www.dropbox.com/s/nj7hw8udpbaha37/undecidable.pdf?dl=0 lecture 3.A] [https://www.dropbox.com/s/ykbkpjm4as46nay/incompleteness.pdf?dl=0 3.B] | + | || 09.02 || undecidability of: Halting program, Wang tiling, Fractran Godel's incompleteness theorems || [https://www.dropbox.com/s/nj7hw8udpbaha37/undecidable.pdf?dl=0 lecture 3.A] [https://www.dropbox.com/s/ykbkpjm4as46nay/incompleteness.pdf?dl=0 3.B] |
|- | |- | ||
− | || 16.02 || The classes P, EXP, PSPACE, EXPSPACE. Dynamic programming. Time and space hierarchy theorems. || [https://www.dropbox.com/s/5amd18ey45qs4x3/cc_seminar.pdf?dl=0 seminar] | + | || 16.02 || The classes P, EXP, PSPACE, EXPSPACE. Dynamic programming. Time and space hierarchy theorems. || [https://www.dropbox.com/s/5amd18ey45qs4x3/cc_seminar.pdf?dl=0 seminar] |
|- | |- | ||
− | || <span style="color:gray">23.02</span> || <span style="color:gray">Holliday</span> || | + | || <span style="color:gray">23.02</span> || <span style="color:gray">Holliday</span> || |
|- | |- | ||
− | || 02.03 || The class NP and NP-completeness || [https://www.dropbox.com/s/90m0yxt62f02mmm/classNP.pdf?dl=0 notes] | + | || 02.03 || The class NP and NP-completeness || [https://www.dropbox.com/s/90m0yxt62f02mmm/classNP.pdf?dl=0 notes] |
|- | |- | ||
|| 02.03 || Circuits, proof of the Levin-Cook theorem (see also Mertens&Moore chapter 5), more reductions || [https://www.dropbox.com/s/nen161dakmq3646/circuits.pdf?dl=0 circuits] | || 02.03 || Circuits, proof of the Levin-Cook theorem (see also Mertens&Moore chapter 5), more reductions || [https://www.dropbox.com/s/nen161dakmq3646/circuits.pdf?dl=0 circuits] | ||
Строка 41: | Строка 38: | ||
|| 30.03 || Parameterized complexity I: the class FPT and kernelization || [https://www.dropbox.com/s/khol9uoy24l6rmg/paramComp.pdf?dl=0 notes] | || 30.03 || Parameterized complexity I: the class FPT and kernelization || [https://www.dropbox.com/s/khol9uoy24l6rmg/paramComp.pdf?dl=0 notes] | ||
|- | |- | ||
− | || 13.04 || Parameterized complexity II: the W-hierarchy || | + | || 13.04 || Parameterized complexity II: the W-hierarchy || [https://www.mpi-inf.mpg.de/fileadmin/inf/d1/teaching/summer20/paraalg/Lectures/lecture_3.pdf slides] (by Daniel Max) [https://www.dropbox.com/s/caigywrx80v08g3/exercises.pdf?dl=0 exercises] |
|- | |- | ||
− | || 20.04 || Projects || | + | || <span style="color:gray">20.04</span> || <span style="color:gray">No lecture</span> |
+ | |- | ||
+ | || 27.04 || Projects || | ||
|} | |} | ||
+ | |||
Строка 57: | Строка 57: | ||
[https://www.dropbox.com/s/w3d6hetx65se8hx/4_HW.pdf?dl=0 HW4 NP and PSPACE completeness] | [https://www.dropbox.com/s/w3d6hetx65se8hx/4_HW.pdf?dl=0 HW4 NP and PSPACE completeness] | ||
− | [https://www.dropbox.com/s/q9afprj9wwgj7qy/5_HW.pdf?dl=0 HW5 parameterized complexity] | + | [https://www.dropbox.com/s/q9afprj9wwgj7qy/5_HW.pdf?dl=0 HW5 parameterized complexity] |
+ | |||
Текущая версия на 21:11, 9 февраля 2023
Classes
Wednesdays 18:10–21:00, on zoom
Teacher: Bruno Bauwens
For practical information join the telegram group
Course Materials
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 |
09.02 | undecidability of: Halting program, Wang tiling, Fractran Godel's incompleteness theorems | lecture 3.A 3.B |
16.02 | The classes P, EXP, PSPACE, EXPSPACE. Dynamic programming. Time and space hierarchy theorems. | seminar |
23.02 | Holliday | |
02.03 | The class NP and NP-completeness | notes |
02.03 | Circuits, proof of the Levin-Cook theorem (see also Mertens&Moore chapter 5), more reductions | circuits |
16.03 | More NP-complete problems | reductions |
23.03 | Games, PSPACE, Savich theorem, completeness of TQBF | pspace |
30.03 | Parameterized complexity I: the class FPT and kernelization | notes |
13.04 | Parameterized complexity II: the W-hierarchy | slides (by Daniel Max) exercises |
20.04 | No lecture | |
27.04 | Projects |
Homeworks
HW3 P, NP, hierarchy theorems, circuits
HW4 NP and PSPACE completeness
Grading
Homework: 50%
Project: 50%
References
Computational complexity
Sipser, Introduction to the theory of computation", 3rd edition, 2013, chapters 1, 2–8. (Short and good for basic understanding.)
Mertens and Moore, The Nature of Computation, 2011. (Pleasant reading, loads of interesting background, but rather large.)
Arora and Barak, Computational Complexity, 2009. (Use this after you made many exercises in the above books.)
Parameterized algorithms
Marx and Misra, Algorithms and Complexity, course website, 2020.
Fomin and 7 others. Parameterized algorithms, 2015. (This is an advanced book.)
Mathematical writing
Sosinsky, Как написать математическую статью по-английски, 2000.
Knuth, Technical writing, transcripts of lectures, 1987.
Gillman, Writing Mathematics Well, 1987.
Office hours
Person | Monday | Tuesday | Wednesday | Thursday | Friday |
---|---|---|---|---|---|
Bruno Bauwens, S834, Zoom | 14:00-20:00 |
Warn me in advance by email.