Theoretical computer science spring 2023 — различия между версиями
Bbauwens (обсуждение | вклад) |
Bbauwens (обсуждение | вклад) |
||
| Строка 25: | Строка 25: | ||
|| 15.02 || Regular languages 2: nondeterministic automata and regular expressions || || [https://www.dropbox.com/s/4ylwf3hdoncym8v/2_HW.pdf?dl=0 hw2] | || 15.02 || Regular languages 2: nondeterministic automata and regular expressions || || [https://www.dropbox.com/s/4ylwf3hdoncym8v/2_HW.pdf?dl=0 hw2] | ||
|- | |- | ||
| − | || 01.03 || Warmup in discrete math | + | || 01.03 || Warmup in discrete math: Chapter 1 of discrete math for computer science (see 1st book below). Turing machines || [https://www.dropbox.com/s/jslijos3lp03m83/turingDef.pdf?dl=0 Turing machines] || [https://www.dropbox.com/s/f3q0q0378y1o2y6/3_HW.pdf?dl=0 hw3] |
|- | |- | ||
|| 15.03 || Undecidability and incompleteness || [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] || | || 15.03 || Undecidability and incompleteness || [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.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] || |
|- | |- | ||
| − | || | + | || 29.03 || NP-completeness, circuits, proof of the Levin-Cook theorem (see 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] || |
|- | |- | ||
| − | || | + | || 05.04 || Reductions. The classes RP, coRP and BPP, primes in BPP || || |
|- | |- | ||
| − | || | + | || || Exam |
| − | + | ||
| − | + | ||
|} | |} | ||
= Grading = | = Grading = | ||
| − | Homework: | + | Homework: 35% |
| − | Theory exam: | + | Theory exam: 35% |
| − | Problem solving exam: | + | Problem solving exam: 30% |
| − | |||
Passing threshold is 4/10. Grades above 5/10 are rounded up, the other grades are rounded down. | Passing threshold is 4/10. Grades above 5/10 are rounded up, the other grades are rounded down. | ||
| Строка 54: | Строка 51: | ||
= References = | = References = | ||
| + | |||
| + | '''Basic math''' | ||
| + | |||
| + | Golovnev, Kulikov, Podolskii, Shen, Discrete mathematics for computer science, 2020. | ||
| + | |||
| + | [http://www.cs.elte.hu/~lovasz/dmbook.ps Lecture notes: Discrete Mathematics], L. Lovasz, K. Vesztergombi | ||
| + | |||
| + | [http://rubtsov.su/public/DM-HSE-Draft.pdf Лекции по дискретной математике] (черновик учебника, in Russian) | ||
| + | |||
Версия 23:30, 2 марта 2023
Classes
Wednesdays 18:10–21:00, in room S834.
Teacher: Bruno Bauwens
Homeworks need to be emailed to brbauwens -at- gmail.com before the start of the lecture next lecture. Put tcs in the subject line.
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 & 2 | hw1 |
| 15.02 | Regular languages 2: nondeterministic automata and regular expressions | hw2 | |
| 01.03 | Warmup in discrete math: Chapter 1 of discrete math for computer science (see 1st book below). Turing machines | Turing machines | hw3 |
| 15.03 | Undecidability and incompleteness | lecture 3.A 3.B | |
| 22.03 | The classes P, EXP, PSPACE, EXPSPACE and NP. Time and space hierarchy theorems | seminar | |
| 29.03 | NP-completeness, circuits, proof of the Levin-Cook theorem (see Mertens&Moore chapter 5) | notes circuits reductions | |
| 05.04 | Reductions. The classes RP, coRP and BPP, primes in BPP | ||
| Exam |
Grading
Homework: 35%
Theory exam: 35%
Problem solving exam: 30%
Passing threshold is 4/10. Grades above 5/10 are rounded up, the other grades are rounded down.
References
Basic math
Golovnev, Kulikov, Podolskii, Shen, Discrete mathematics for computer science, 2020.
Lecture notes: Discrete Mathematics, L. Lovasz, K. Vesztergombi
Лекции по дискретной математике (черновик учебника, in Russian)
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.
