Theory of Computation 2022 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
м
м
Строка 7: Строка 7:
 
= Dates and Deadlines =
 
= Dates and Deadlines =
  
Homeworks 1, 2, 3: September 26<big>th</big>
+
Homeworks 1, 2, 3: September 26
Homeworks 4, 5, 6: October 17<big>th</big>
+
 
Homeworks 7, 8, 9: November 14<big>th</big>
+
Homeworks 4, 5, 6: October 17
Homeworks 10, 11, 12: December 5<big>th</big>
+
 
 +
Homeworks 7, 8, 9: November 14
 +
 
 +
Homeworks 10, 11, 12: December 5
  
 
= Grading =
 
= Grading =

Версия 18:44, 9 сентября 2022

Classes

Lectures: Monday 13:00 - 14:20 by Bruno Bauwens and Alexey Talambutsa

Seminars: Monday 14:40 - 16:00 by Pavel Zakharov

Dates and Deadlines

Homeworks 1, 2, 3: September 26

Homeworks 4, 5, 6: October 17

Homeworks 7, 8, 9: November 14

Homeworks 10, 11, 12: December 5

Grading

Colloquium: 35%
Homework: 35%
Exam: 30%

Homework Grading

Some homework assignments contain extra problems. Each solution of an extra problem will give 1 extra point on the final exam. There will be around 6 extra problems.

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)

Summary Problem list
05.09 Turing machines, multitape Turing machines, connection between them. Universal Turing machine. Examples. Time and space complexity. Complexity classes P, PSPACE, EXP. Problem set 1
12.09 Time and space hierarchy theorems. Time and space constructible functions.
19.09 Complexity class NP. Examples. Polynomial reductions. NP-hardness and NP-completeness.
26.09 Non-deterministic TMs. Another definition of NP. Proving NP-hardness by reduction from an NP-complete problem. Examples of NP-complete problems.
3.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.
10.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.
17.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.
31.10 PSPACE completeness of generalized geography. 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.
07.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 here
14.11 Streaming algorithms: finding the majority element, computation of the number of different elements in logarithmic space. See Chapts 6.1-6.2 in foundations of datascience by Avrim Blum and others. Another nice chapter in Tim Roughgarden's lecture notes
21.11 Finding the frequent items in streams of data: SpaceSaving and Count-Min Sketch.
28.11 Approximation algorithms. Approximate solutions for Vertex Cover, Weighted Vertex Cover, and TSP. Slides.
05.12 Colloquium.
12.12 Complexity of clustering: an exact algorithm for maximizing the inter-cluster distance and an approximate algorithm for minimizing the intra-class distance. Sample exam

For interested students, there are 3 lectures in parameterized complexity.

12 Sept: Fixed parameter tracktability and examples, presentation.

19 Sept: Topics from chapters 1 and 2 in "Parameterized algorithms" by Cygan, Fomin and others, 2016.

26 Sept: The W-hierarchy, chapter 13 in the same book.

Office hours

Bruno Bauwens: Tuesdays 14h-20h. It is best to warn a day ahead on brbauwens -a- gmail.com

Alexey Talambutsa: First contact by email.