Theory of Computation 2022 — различия между версиями
Bbauwens (обсуждение | вклад) |
Bbauwens (обсуждение | вклад) |
||
Строка 19: | Строка 19: | ||
If you score at least 8 and solve some extra problems that do not contribute to this score, we will evaluate each of these extra problems on the scale [0, 1] and will add two maximal scores to your homework grade. | If you score at least 8 and solve some extra problems that do not contribute to this score, we will evaluate each of these extra problems on the scale [0, 1] and will add two maximal scores to your homework grade. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
= Course Materials = | = Course Materials = |
Версия 20:09, 2 сентября 2022
Classes
Lectures: Monday 13:00 - 14:20 by Bruno Bauwens and Alexey Talambutsa
Seminars: Monday 14:40 - 16:00 by Pavel Zakharov
Dates and Deadlines
Grading
Colloquium: 35%
Homework: 35%
Exam: 30%
Homework Grading
Some homework assignments contain extra problems. Let us call all other problems regular. The weight of each problem (whether regular or extra) in the overall homework grade is 8/n, where n is the total number of regular problems in all homework assignments. Partial credit is possible for some problems.
If you score at least 8 and solve some extra problems that do not contribute to this score, we will evaluate each of these extra problems on the scale [0, 1] and will add two maximal scores to your homework grade.
Course Materials
The main reference is Sipser's book "Introduction to the theory of computation", chapters 3, 7–10.
If you need some background in math, consider these two sources:
Lecture notes: Discrete Mathematics, L. Lovasz, K. Vesztergombi
Лекции по дискретной математике (черновик учебника, in Russian)
Video | Summary | Problem list |
---|---|---|
05.09 | Turing machines, multitape Turing machines, connection between them. Universal Turing machine. Examples (one, two). Time and space complexity. Complexity classes P, PSPACE, EXP. | Problem set 1 |