Theory of Computation 2021 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
.obj (обсуждение | вклад) (→Course Materials) |
.obj (обсуждение | вклад) (→Office hours) |
||
Строка 59: | Строка 59: | ||
|- | |- | ||
! Person !! Monday !! Tuesday !! Wednesday !! Thursday !! Friday | ! Person !! Monday !! Tuesday !! Wednesday !! Thursday !! Friday | ||
− | |||
− | |||
|- | |- | ||
| [https://www.hse.ru/en/org/persons/160550073 Bruno Bauwens], [https://zoom.us/j/5579743402 Zoom] (email in advance) || 14h-18h || 16h15-19h || || || | | [https://www.hse.ru/en/org/persons/160550073 Bruno Bauwens], [https://zoom.us/j/5579743402 Zoom] (email in advance) || 14h-18h || 16h15-19h || || || | ||
+ | |- | ||
+ | | [https://www.hse.ru/en/staff/obiedkov Sergei Obiedkov], [https://zoom.us/j/99663354582 Zoom] || || || 16:30–18:00 || 16:30–18:00 || | ||
|} | |} |
Версия 15:45, 25 августа 2021
General Information
Classes: Tuesdays, 14:40–17:40.
Dates and Deadlines
Homework 1, deadline: October 5, 14:00
Homework 2, deadline: November 2, 14:00
Homework 3, deadline: December 7, 14:00
Colloquium: December 7, 14:40–17:40
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)
Date | Summary | Problem list |
---|---|---|
07.09 | Turing machines, multitape Turing machines, connection between them. Universal Turing machine. Examples. Time and space complexity. Complexity classes P, PSPACE, EXP. | |
14.09 | Time and space hierarchy theorem. Time and space constructible functions. | |
21.09 | Circuit complexity. Examples. All functions are computed by circuits. Existence of functions with exponential circuit complexity. P is in P/poly. | |
28.09 | Complexity class NP. Examples. Inclusions between P, NP and PSPACE. Non-deterministic TMs. Another definition of NP. Polynomial reductions, their properties. NP-hardness and NP-completeness, their properties. | |
05.10 | Proving NP-hardness by reduction from an NP-complete problem. Examples of NP-complete problems. | |
12.10 | Cook–Levin theorem. | |
26.10 | Space complexity. | |
02.11 | Oracle computation definitions. There exists an oracle A for which PA = NPA. There is an oracle B such that PB is not equal to NPB. | |
09.11 | Probabilistic computation. Probabilistic machines, the class BPP, invariance of the definition BPP for different thresholds, RP, coRP, PP, ZPP. BPP is in P/poly. | |
16.11 | Streaming algorithms: finding the majority element, computation of the moment F2 in logarithmic space. | |
23.11 | Finding the frequent items in streams of data: SpaceSaving and Count-Min Sketch. | |
30.11 | Approximation algorithms. Approximate solutions for Vertex Cover, Weighted Vertex Cover, and TSP. | |
07.12 | Colloquium | |
14.12 | Complexity of clustering: an exact algorithm for maximising the inter-cluster distance and an approximate algorithm for minimising the intra-class distance. |
Office hours
Person | Monday | Tuesday | Wednesday | Thursday | Friday |
---|---|---|---|---|---|
Bruno Bauwens, Zoom (email in advance) | 14h-18h | 16h15-19h | |||
Sergei Obiedkov, Zoom | 16:30–18:00 | 16:30–18:00 |