Theoretical computer science spring 2023 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
Bbauwens (обсуждение | вклад) |
Bbauwens (обсуждение | вклад) |
||
| Строка 16: | Строка 16: | ||
{| class="wikitable" | {| class="wikitable" | ||
|- | |- | ||
| − | ! Video !! Summary !! Notes !! Homework ! | + | ! Video !! Summary !! Notes !! Homework !! |
|- | |- | ||
| − | || [https://youtu.be/BHm2eHFnC6U 08.02] || Regular languages 1: deterministic automata, pumping lemma, closure properties || [https://www.dropbox.com/s/uz1gyurwjvfwe77/automata.pdf?dl=0 lecture 1] | + | || [https://youtu.be/BHm2eHFnC6U 08.02] || Regular languages 1: deterministic automata, pumping lemma, closure properties || [https://www.dropbox.com/s/uz1gyurwjvfwe77/automata.pdf?dl=0 lecture 1] || |
|- | |- | ||
| − | || 15.02 || Regular languages (2): equivalence between deterministic and nondeterministic automata, regular expressions] | + | || 15.02 || Regular languages (2): equivalence between deterministic and nondeterministic automata, regular expressions] || || |
|- | |- | ||
| − | || 22.02 || Turing machines, the Halting problem, Godel incompleteness theorems || [https://www.dropbox.com/s/jslijos3lp03m83/turingDef.pdf?dl=0 lecture 2][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] | + | || 22.02 || Turing machines, the Halting problem, Godel incompleteness theorems || [https://www.dropbox.com/s/jslijos3lp03m83/turingDef.pdf?dl=0 lecture 2][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] || |
|- | |- | ||
| − | || 02.03 || Famous polynomial time algorithms: Dijkstra, Kruskal, dynamic programming || | + | || 02.03 || Famous polynomial time algorithms: Dijkstra, Kruskal, dynamic programming || || |
|- | |- | ||
| − | || 09.03 || The classes P, EXP, PSPACE, EXPSPACE and NP. Time and space hierarchy theorems. || [https://www.dropbox.com/s/5amd18ey45qs4x3/cc_seminar.pdf?dl=0 seminar] | + | || 09.03 || The classes P, EXP, PSPACE, EXPSPACE and NP. Time and space hierarchy theorems. || [https://www.dropbox.com/s/5amd18ey45qs4x3/cc_seminar.pdf?dl=0 seminar] || || |
|- | |- | ||
|| 16.03 || NP-completeness, circuits, proof of the Levin-Cook theorem, reductions (see also Mertens&Moore chapter 5) || [https://www.dropbox.com/s/90m0yxt62f02mmm/classNP.pdf?dl=0 notes] [https://www.dropbox.com/s/nen161dakmq3646/circuits.pdf?dl=0 circuits] [https://www.dropbox.com/s/wlrssw0q1tfx49p/moreReductions.pdf?dl=0 reductions] | || 16.03 || NP-completeness, circuits, proof of the Levin-Cook theorem, reductions (see also Mertens&Moore chapter 5) || [https://www.dropbox.com/s/90m0yxt62f02mmm/classNP.pdf?dl=0 notes] [https://www.dropbox.com/s/nen161dakmq3646/circuits.pdf?dl=0 circuits] [https://www.dropbox.com/s/wlrssw0q1tfx49p/moreReductions.pdf?dl=0 reductions] | ||
Версия 21:14, 9 февраля 2023
Classes
Wednesdays 18:10–21:00, in room S834.
Teacher: Bruno Bauwens
For practical information ask to join the telegram group.
Course Materials
| Video | Summary | Notes | Homework | |
|---|---|---|---|---|
| 08.02 | Regular languages 1: deterministic automata, pumping lemma, closure properties | lecture 1 | ||
| 15.02 | Regular languages (2): equivalence between deterministic and nondeterministic automata, regular expressions] | |||
| 22.02 | Turing machines, the Halting problem, Godel incompleteness theorems | lecture 2lecture 3.A 3.B | ||
| 02.03 | Famous polynomial time algorithms: Dijkstra, Kruskal, dynamic programming | |||
| 09.03 | The classes P, EXP, PSPACE, EXPSPACE and NP. Time and space hierarchy theorems. | seminar | ||
| 16.03 | NP-completeness, circuits, proof of the Levin-Cook theorem, reductions (see also Mertens&Moore chapter 5) | notes circuits reductions | ||
| 23.03 | Finishing previous lecture, the classes RP, coRP and BPP, primes in BPP | |||
| 30.03(?) | Exam | |||
| may | Projects |
Grading
Homework: 25%
Theory exam: 25%
Problem solving exam: 25%
Project: 25%
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.)
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-18:00 |
Warn me in advance by email.
