Theoretical Computer Science 2022 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
 
(не показаны 72 промежуточные версии 3 участников)
Строка 1: Строка 1:
 
= Classes =
 
= Classes =
 
   
 
   
−
Wednesdays 18:10–21:00, room TBA, [https://us02web.zoom.us/j/82300259484?pwd=NWxXekxBeE5yMm9UTmwvLzNNNGlnUT09 zoomlink]
+
Wednesdays 18:10–21:00, on [https://us02web.zoom.us/j/82300259484?pwd=NWxXekxBeE5yMm9UTmwvLzNNNGlnUT09 zoom]
  
−
= Dates and Deadlines =
+
Teacher: [https://www.hse.ru/en/org/persons/160550073 Bruno Bauwens]
  
−
= Grading =
+
For practical information join the [https://t.me/+fjwhc1N_Cn1iNmEy telegram group]
−
[https://docs.google.com/spreadsheets/d/1WFBuyjv_D-8EZRhMm39fI_X69daPk2VZwzBXlchW4Mk/edit?usp=sharing Grades]
+
−
 
+
−
Exam: 40%<br>
+
−
Homework: 20%<br>
+
−
Project: 40%
+
  
  
 
= Course Materials =
 
= 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:<br>
+
<!-- If you need some background in math, consider these two sources:<br>
 
[http://www.cs.elte.hu/~lovasz/dmbook.ps Lecture notes: Discrete Mathematics], L. Lovasz, K. Vesztergombi<br>
 
[http://www.cs.elte.hu/~lovasz/dmbook.ps Lecture notes: Discrete Mathematics], L. Lovasz, K. Vesztergombi<br>
−
[http://rubtsov.su/public/DM-HSE-Draft.pdf Лекции по дискретной математике] (черновик учебника, in Russian)
+
[http://rubtsov.su/public/DM-HSE-Draft.pdf Лекции по дискретной математике] (черновик учебника, in Russian)-->
−
 
+
−
 
+
 
{| class="wikitable"
 
{| class="wikitable"
 
|-
 
|-
−
! Video !! Summary !! Notes
+
! Video !! Summary !! Notes !
 
|-
 
|-
−
  || 19.01 || Regular languages  ||  
+
  || [https://youtu.be/BHm2eHFnC6U 19.01] || Regular languages: (non)deterministic automata and their equivalence, pumping lemma, closure properties || [https://www.dropbox.com/s/uz1gyurwjvfwe77/automata.pdf?dl=0 lecture 1]
−
<!--
+
|-  
−
|-
+
|| 25.01 || Turing machines and register machines || [https://www.dropbox.com/s/jslijos3lp03m83/turingDef.pdf?dl=0 lecture 2]
−
|| 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]
+
|-  
−
|-
+
  || 09.02 || undecidability of: Halting program, Wang tiling, Fractran Godel's incompleteness theorems || [https://www.dropbox.com/s/nj7hw8udpbaha37/undecidable.pdf?dl=0 lecture 3.A] [https://www.dropbox.com/s/ykbkpjm4as46nay/incompleteness.pdf?dl=0 3.B]  
−
  || 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]
+
  || 16.02 || The classes P, EXP, PSPACE, EXPSPACE. Dynamic programming. Time and space hierarchy theorems. || [https://www.dropbox.com/s/5amd18ey45qs4x3/cc_seminar.pdf?dl=0 seminar]  
−
|-
+
|-  
−
  || 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]
+
  || <span style="color:gray">23.02</span> || <span style="color:gray">Holliday</span> ||
−
|-
+
|-
−
  || 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]
+
|| 02.03 || The class NP and NP-completeness || [https://www.dropbox.com/s/90m0yxt62f02mmm/classNP.pdf?dl=0 notes]
−
|-
+
|-  
−
|| 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]
+
|| 02.03 || Circuits, proof of the Levin-Cook theorem (see also Mertens&Moore chapter 5), more reductions || [https://www.dropbox.com/s/nen161dakmq3646/circuits.pdf?dl=0 circuits]  
−
|-
+
|-  
−
  || [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]
+
  || 16.03 || More NP-complete problems || [https://www.dropbox.com/s/wlrssw0q1tfx49p/moreReductions.pdf?dl=0 reductions]  
 +
|-
 +
|| 23.03 || Games, PSPACE, Savich theorem, completeness of TQBF  || [https://www.dropbox.com/s/77sr5nhne411ahz/classPSPACE.pdf?dl=0 pspace]
 +
|-
 +
|| 30.03 || Parameterized complexity I: the class FPT and kernelization  || [https://www.dropbox.com/s/khol9uoy24l6rmg/paramComp.pdf?dl=0 notes]
 
|-  
 
|-  
−
|| [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]
+
|| 13.04 || Parameterized complexity II: the W-hierarchy || [https://www.mpi-inf.mpg.de/fileadmin/inf/d1/teaching/summer20/paraalg/Lectures/lecture_3.pdf slides] (by Daniel Max) [https://www.dropbox.com/s/caigywrx80v08g3/exercises.pdf?dl=0 exercises]
 
|-
 
|-
−
  || 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]
+
  || <span style="color:gray">20.04</span> || <span style="color:gray">No lecture</span>
 
|-
 
|-
−
  || [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]
+
  || 27.04 || Projects ||
−
|-
+
−
|| [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]
+
−
-->
+
 
|}
 
|}
 +
 +
 +
 +
= Homeworks =
 +
 +
[https://www.dropbox.com/s/uhi35jl4ofm1ws1/1_HW.pdf?dl=0 HW1 automata]
 +
 +
[https://www.dropbox.com/s/j4o5bqz0o1r171o/2_HW.pdf?dl=0 HW2 computability]
 +
 +
[https://www.dropbox.com/s/4mgniv56j9qg2c8/3_HW.pdf?dl=0 HW3 P, NP, hierarchy theorems, circuits]
 +
 +
[https://www.dropbox.com/s/w3d6hetx65se8hx/4_HW.pdf?dl=0 HW4 NP and PSPACE completeness]
 +
 +
[https://www.dropbox.com/s/q9afprj9wwgj7qy/5_HW.pdf?dl=0 HW5 parameterized complexity]
 +
 +
 +
 +
= Grading =
 +
 +
Homework: 50%<br>
 +
 +
Project: 50%
 +
 +
 +
= References =
 +
 +
 +
'''Computational complexity'''
 +
 +
Sipser, Introduction to the theory of computation", 3rd edition, 2013, chapters 1, 2–8. (Short and good for basic understanding.)
 +
 +
Mertens and Moore, The Nature of Computation, 2011. (Pleasant reading, loads of interesting background, but rather large.)
 +
 +
Arora and Barak, Computational Complexity, 2009. (Use this after you made many exercises in the above books.)
 +
 +
 +
'''Parameterized algorithms'''
 +
 +
Marx and Misra, [https://www.mpi-inf.mpg.de/departments/algorithms-complexity/teaching/summer20/parameterized-algorithms Algorithms and Complexity], course website, 2020.
 +
 +
Fomin and 7 others. Parameterized algorithms, 2015. (This is an advanced book.)
 +
 +
 +
'''Mathematical writing'''
 +
 +
Sosinsky, [http://www.ega-math.narod.ru/Quant/ABS.htm Как написать математическую статью по-английски], 2000.
 +
 +
Knuth,  [https://jmlr.csail.mit.edu/reviewing-papers/knuth_mathematical_writing.pdf Technical writing], transcripts of lectures, 1987.
 +
 +
Gillman, Writing Mathematics Well, 1987.
 +
<!-- Strunk and White, [https://www.dropbox.com/s/7e6fcdpx3nubvko/strunk-white-1979-elements-of-style.pdf?dl=0 The elements of style], 1979.-->
 +
  
 
= Office hours =
 
= Office hours =
Строка 68: Строка 105:
 
|  [https://www.hse.ru/en/org/persons/160550073 Bruno Bauwens], S834, [https://us02web.zoom.us/j/82300259484?pwd=NWxXekxBeE5yMm9UTmwvLzNNNGlnUT09 Zoom] ||  || ||  ||  || 14:00-20:00
 
|  [https://www.hse.ru/en/org/persons/160550073 Bruno Bauwens], S834, [https://us02web.zoom.us/j/82300259484?pwd=NWxXekxBeE5yMm9UTmwvLzNNNGlnUT09 Zoom] ||  || ||  ||  || 14:00-20:00
 
|}
 
|}
 +
Warn me in advance by email.

Текущая версия на 21:11, 9 февраля 2023

Classes

Wednesdays 18:10–21:00, on zoom

Teacher: Bruno Bauwens

For practical information join the telegram group


Course Materials

Video Summary Notes !
19.01 Regular languages: (non)deterministic automata and their equivalence, pumping lemma, closure properties lecture 1
25.01 Turing machines and register machines lecture 2
09.02 undecidability of: Halting program, Wang tiling, Fractran Godel's incompleteness theorems lecture 3.A 3.B
16.02 The classes P, EXP, PSPACE, EXPSPACE. Dynamic programming. Time and space hierarchy theorems. seminar
23.02 Holliday
02.03 The class NP and NP-completeness notes
02.03 Circuits, proof of the Levin-Cook theorem (see also Mertens&Moore chapter 5), more reductions circuits
16.03 More NP-complete problems reductions
23.03 Games, PSPACE, Savich theorem, completeness of TQBF pspace
30.03 Parameterized complexity I: the class FPT and kernelization notes
13.04 Parameterized complexity II: the W-hierarchy slides (by Daniel Max) exercises
20.04 No lecture
27.04 Projects


Homeworks

HW1 automata

HW2 computability

HW3 P, NP, hierarchy theorems, circuits

HW4 NP and PSPACE completeness

HW5 parameterized complexity


Grading

Homework: 50%

Project: 50%


References

Computational complexity

Sipser, Introduction to the theory of computation", 3rd edition, 2013, chapters 1, 2–8. (Short and good for basic understanding.)

Mertens and Moore, The Nature of Computation, 2011. (Pleasant reading, loads of interesting background, but rather large.)

Arora and Barak, Computational Complexity, 2009. (Use this after you made many exercises in the above books.)


Parameterized algorithms

Marx and Misra, Algorithms and Complexity, course website, 2020.

Fomin and 7 others. Parameterized algorithms, 2015. (This is an advanced book.)


Mathematical writing

Sosinsky, Как написать математическую статью по-английски, 2000.

Knuth, Technical writing, transcripts of lectures, 1987.

Gillman, Writing Mathematics Well, 1987.


Office hours

Person Monday Tuesday Wednesday Thursday Friday
Bruno Bauwens, S834, Zoom 14:00-20:00

Warn me in advance by email.

Источник — «http://wiki.cs.hse.ru/index.php?title=Theoretical_Computer_Science_2022&oldid=76355»