|
|
| Строка 27: |
Строка 27: |
| | |- | | |- |
| | || 19.01 || Regular languages || | | || 19.01 || Regular languages || |
| − | <!--
| |
| − | |-
| |
| − | || 14.09 || Time and space hierarchy theorems. Time and space constructible functions. || [https://www.dropbox.com/s/ow4m1z8u8r211qs/prob_2.pdf?dl=0 Problem set 2]
| |
| − | |-
| |
| − | || 21.09 || Complexity class NP. Examples. Polynomial reductions. NP-hardness and NP-completeness.
| |
| − | || [https://www.dropbox.com/s/bf68zicg4uh051x/prob_03.pdf?dl=0 Problem set 3]
| |
| − | |-
| |
| − | || 28.09 || Non-deterministic TMs. Another definition of NP. Proving NP-hardness by reduction from an NP-complete problem. Examples of NP-complete problems. || [https://www.dropbox.com/s/g817m6v0ygb8h4n/prob_04.pdf?dl=0 Problem set 4]
| |
| − | |-
| |
| − | || 05.10 || Inclusions between P, NP, and PSPACE. Circuit complexity. Examples. All functions are computed by circuits. Existence of functions with exponential circuit complexity. P is in P/poly.|| [https://www.dropbox.com/s/qkc5p4795rualwn/prob_05.pdf?dl=0 Problem set 5]
| |
| − | |-
| |
| − | || 12.10 || P is a subset of P/poly, Cook–Levin theorem, NP-completeness of: subsetsum, set-splitting, 3-colorability and exactly 1-in-3 SAT. || [https://www.dropbox.com/s/y2y1lu29936xy9n/prob_06.pdf?dl=0 Problem set 6]
| |
| − | |-
| |
| − | || [https://drive.google.com/drive/folders/1loJWyo9TK6ucCp8RnD3xx3DAVPDs0OiF?usp=sharing 26.10] || Space complexity. Classes L, NL, PSPACE and NPSPACE. Directed Reachability is in SPACE(log^2 n). Configuration graph. Inclusions between time and space classes. TQBF problem, its PSPACE-completeness. PSPACE = NPSPACE. NSPACE(s(n)) is in SPACE(s(n)^2) for space constructible s. || [https://www.dropbox.com/s/b6m0u5vqtutdhq1/prob_07.pdf?dl=0 Problem set 7]
| |
| − | |-
| |
| − | || [https://drive.google.com/drive/folders/1w4W15sPS1nCIpQZQWasqPq8wSVLle5Ik?usp=sharing 02.11] || PSPACE completeness of generalized geography. Oracle computation definitions. There exists an oracle ''A'' for which P<sup>''A''</sup> = NP<sup>''A''</sup>. There is an oracle B such that P<sup>''B''</sup> is not equal to NP<sup>''B''</sup>. || [https://www.dropbox.com/s/bvfrar2p5w3fcie/prob_08.pdf?dl=0 Problem set 8]
| |
| − | |-
| |
| − | || 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. Most of it is also [https://www.youtube.com/watch?v=YSMgVbOqB-8&list=PLm3J0oaFux3YL5vLXpzOyJiLtqLp6dCW2&index=23 here]|| [https://www.dropbox.com/s/dciqvmire4ze4n2/prob_09.pdf?dl=0 Problem set 9]
| |
| − | |-
| |
| − | || [https://youtu.be/ToxNJ9p32Ec 16.11] || Streaming algorithms: finding the majority element, computation of the number of different elements <!-- ''F''<sub>2</sub>--> in logarithmic space. See Chapts 6.1-6.2 in [https://home.ttic.edu/~avrim/book.pdf foundations of datascience] by Avrim Blum and others. Another nice chapter in [http://theory.stanford.edu/~tim/w15/l/l1.pdf Tim Roughgarden's lecture notes] || [https://www.dropbox.com/s/ztg8wxuhbkhzh9e/prob_10.pdf?dl=0 Problem set 10]
| |
| − | |-
| |
| − | || [https://drive.google.com/file/d/1mDd3HjabwwzNPMa7oPcnAeHRSymVmsvE/view?usp=sharing 23.11] || Finding the frequent items in streams of data: SpaceSaving and Count-Min Sketch. [https://www.dropbox.com/s/6u27au11u00n59p/tc-11-streaming.pdf?dl=0 Slides] || [https://www.dropbox.com/s/8fvpntf1n4hjoyu/prob_11.pdf?dl=0 Problem set 11]
| |
| − | |-
| |
| − | || [https://youtu.be/H7hF07mMPzk 30.11] || Approximation algorithms. Approximate solutions for Vertex Cover, Weighted Vertex Cover, and TSP. [https://www.dropbox.com/s/wvtcsl6crkj8zeq/tc-12-approximation.pdf?dl=0 Slides.] [https://youtu.be/6ng15Bc8Dlw Seminar.]|| [https://www.dropbox.com/s/qug480ss98pq78p/prob_12.pdf?dl=0 Problem set 12]
| |
| − |
| |
| − | |-
| |
| − | || 07.12 || Colloquium. ||
| |
| − | |-
| |
| − | || [https://www.dropbox.com/s/emvoow009xjvf5q/tc-14-clustering.pdf?dl=0 14.12] || Complexity of clustering: an exact algorithm for maximizing the inter-cluster distance and an approximate algorithm for minimizing the intra-class distance.
| |
| − | || [https://www.dropbox.com/s/37gdsbv2it8omnm/tc-sample-exam.pdf?dl=0 Sample exam]
| |
| − | -->
| |
| | |} | | |} |
| | | | |
Версия 15:37, 19 января 2022
Classes
Wednesdays 18:10–21:00, room TBA, zoomlink
Dates and Deadlines
Grading
Grades
Exam: 40%
Homework: 20%
Project: 40%
Course Materials
The main reference for the first 4 lectures is Sipser's book "Introduction to the theory of computation", chapters 1, 2–7.
If you need some background in math, consider these two sources:
Lecture notes: Discrete Mathematics, L. Lovasz, K. Vesztergombi
Лекции по дискретной математике (черновик учебника, in Russian)
| Video |
Summary |
Notes
|
| 19.01 |
Regular languages |
|
Office hours
| Person |
Monday |
Tuesday |
Wednesday |
Thursday |
Friday
|
| Bruno Bauwens, S834, Zoom |
|
|
|
|
14:00-20:00
|
