Theory of Computing 2019 2020 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
| Строка 15: | Строка 15: | ||
! Date !! Summary !! Problem list | ! Date !! Summary !! Problem list | ||
|- | |- | ||
| − | || 06.09 || | + | || 06.09 || Turing machines, multitape Turing machines, connection between them. Examples. Time and space complexity. Complexity classes P, PSPACE, EXP. || [https://www.dropbox.com/s/lxoenwqohopsoca/prob_1.pdf?dl=0 Problem list 1 ] |
<!---|- | <!---|- | ||
|| 11/9 || Complexity class NP. Examples. Inclusions between P, NP and EXP. Non-deterministic TMs. Another definition of NP. Polynomial reductions, their properties. NP-hardness and NP-completeness, their properties. || [http://www.mi.ras.ru/~podolskii/files/computability1819/prob_2.pdf Problem list 2 ] | || 11/9 || Complexity class NP. Examples. Inclusions between P, NP and EXP. Non-deterministic TMs. Another definition of NP. Polynomial reductions, their properties. NP-hardness and NP-completeness, their properties. || [http://www.mi.ras.ru/~podolskii/files/computability1819/prob_2.pdf Problem list 2 ] | ||
Версия 12:19, 7 сентября 2019
General Information
Classes: Fridays, 15:10-18:00, R406
Dates and Deadlines
Homework 1, deadline: 4 October, before the lecture
Course Materials
| Date | Summary | Problem list |
|---|---|---|
| 06.09 | Turing machines, multitape Turing machines, connection between them. Examples. Time and space complexity. Complexity classes P, PSPACE, EXP. | Problem list 1 |
Office hours
| Person | Monday | Tuesday | Wednesday | Thursday | Friday |
|---|---|---|---|---|---|
| Vladimir Podolskii, room S830 | |||||
| Bruno Bauwens, room S834 |
