Theory of Computation 2021 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
.obj (обсуждение | вклад) (→Schedule) |
.obj (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
− | + | = Classes = | |
Tuesdays, 14:40–17:40. | Tuesdays, 14:40–17:40. | ||
− | + | = Dates and Deadlines = | |
Homework 1, deadline: October 5, 14:00 <br> | Homework 1, deadline: October 5, 14:00 <br> | ||
Строка 10: | Строка 10: | ||
Colloquium: December 7, 14:40–17:40 | Colloquium: December 7, 14:40–17:40 | ||
− | == Course Materials | + | = Grading = |
+ | Colloquium: 0.35 | ||
+ | |||
+ | Homework: 0.35 | ||
+ | |||
+ | Written exam: 0.3 | ||
+ | |||
+ | = Course Materials = | ||
The main reference is Sipser's book "Introduction to the theory of computation" Chapters 3, 7–10. | The main reference is Sipser's book "Introduction to the theory of computation" Chapters 3, 7–10. | ||
Строка 54: | Строка 61: | ||
|} | |} | ||
− | + | = Office hours = | |
{| class="wikitable" | {| class="wikitable" |
Версия 16:04, 25 августа 2021
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
Grading
Colloquium: 0.35
Homework: 0.35
Written exam: 0.3
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 | |||||
Sergei Obiedkov, T915, Zoom | 16:30–18:00 | 16:30–18:00 |