Theory of Computing 2019 2020 — различия между версиями

Версия 12:33, 7 сентября 2019

Classes: Fridays, 15:10-18:00, R406

Homework 1, deadline: 4 October, before the lecture

In the first several lecture we follow Sipser's book "Introduction to the theory of computation"

If you need some background in math, consider these two sourses:
Lecure notes: Discrete Mathematics, L. Lovasz, K. Vesztergombi
Лекции по дискретной математике (черновик учебника, in Russian)

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 Updated: 07.09.19

Person	Monday	Tuesday	Wednesday	Thursday	Friday
Vladimir Podolskii, room S830
Bruno Bauwens, room S834

@@ Строка 22: / Строка 22: @@
 ! Date !! Summary !! Problem list
 |-
-  || 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 ]
+  || 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 ] <span style="color:red">Updated: 07.09.19</span>
 <!---|-
   || 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 ]