Theory of Computation 2021
Материал из Wiki - Факультет компьютерных наук
Версия от 15:45, 25 августа 2021; .obj (обсуждение | вклад)
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 |
---|---|---|---|---|---|
Sergei Obiedkov, Zoom | 16:30–18:00 | 16:30–18:00 | |||
Bruno Bauwens, Zoom (email in advance) | 14h-18h | 16h15-19h |