Просмотр кода страницы TCS 2024

= Classes =
 
Thursdays 18:10–21:00, in room S834. 

Teacher: [https://www.hse.ru/en/org/persons/160550073 Bruno Bauwens]

Homeworks need to be emailed to brbauwens -at- gmail.com before the start of the lecture next lecture. Start the subject line with: tcs

For practical information click the [https://t.me/+jGeMKgaxMwE1YTZk this link] to join the telegram group. 

[https://www.dropbox.com/scl/fi/2opgvanhsuuqyrt1z5zhl/scores.ods?dl=0&rlkey=v0htrtejs04c1pujinri7ozqj Scores]

= Course Materials =


<!-- 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://rubtsov.su/public/DM-HSE-Draft.pdf Лекции по дискретной математике] (черновик учебника, in Russian)-->
{| class="wikitable"
|-
! Video !! Summary !! Notes !! Homework 
|-
 || [https://youtu.be/BHm2eHFnC6U 08.02] || Regular languages 1: deterministic automata, pumping lemma, closure properties  || [https://www.dropbox.com/s/l764sm569b9ygic/automata.pdf?dl=0 lecture 1 & 2] || [https://www.dropbox.com/s/okcga6o20qsrxe2/1_HW.pdf?dl=0 hw1]
|- 
 || 15.02 || Regular languages 2: nondeterministic automata and regular expressions || || [https://www.dropbox.com/s/4ylwf3hdoncym8v/2_HW.pdf?dl=0 hw2]
|- 
 || 01.03 || Chapter 1 of discrete math for computer science (see 1st book below).  Turing machines || [https://www.dropbox.com/s/jslijos3lp03m83/turingDef.pdf?dl=0 Turing machines] || [https://www.dropbox.com/s/f3q0q0378y1o2y6/3_HW.pdf?dl=0 hw3]
|- 
 || 16.03 || Recursion and induction. (Chapt 3 of discrete math book.) Turing machines. ||  || [https://www.dropbox.com/s/ee0kaxd8wrr5k7b/4_HW.pdf?dl=0 hw4]
|-
 || 23.03 || Invariants (Chapt 5). Undecidability || [https://www.dropbox.com/s/nj7hw8udpbaha37/undecidable.pdf?dl=0 lecture 3.A]  || [https://www.dropbox.com/s/17ogtcftqh7ybzo/5_HW.pdf?dl=0 hw5]
|-
 || 29.03 || Completeness ||  [https://www.dropbox.com/s/ykbkpjm4as46nay/incompleteness.pdf?dl=0 3.B] || [https://www.dropbox.com/s/5r16xyv2q65dt4m/6_HW.pdf?dl=0 hw6]
|- 
 || 12.04 || (online, in zoom) The classes P, EXP, PSPACE, EXPSPACE. Time and space hierarchy theorems.  ||  See Sipser chapts 7 and 8 || [https://www.dropbox.com/s/t25x38vop05xnlu/7_HW.pdf?dl=0 hw7]
|- 
|| 19.04 || The class NP, NP-completeness, reduction from SAT to IND-SET || [https://www.dropbox.com/s/90m0yxt62f02mmm/classNP.pdf?dl=0 notes] || [https://www.dropbox.com/s/pxawna41u2xumim/8_HW.pdf?dl=0 hw8]
|- 
|| 26.04 || Reductions. Proof of the Levin-Cook theorem. ||[https://www.dropbox.com/s/nen161dakmq3646/circuits.pdf?dl=0 circuits][https://www.dropbox.com/s/wlrssw0q1tfx49p/moreReductions.pdf?dl=0 reductions] || [https://www.dropbox.com/s/f3t6ob6fuvi9fhe/9_HW.pdf?dl=0 hw9]
|- 
 || 17.05 || Exam. Start at 16h00. [https://www.dropbox.com/s/dfv4vehr2mqbxrw/coll.pdf?dl=0 Theory questions.] Also solve 4 exercises as in the homework, including 1 NP-completeness proof.
|}

= Grading =

Homework: 35%

Theory exam: 35%

Problem solving exam: 30%


Passing threshold is 4/10. Grades above 5/10 are rounded up, the other grades are rounded down. 


= References =

'''Basic math'''

Golovnev, Kulikov, Podolskii, Shen, Discrete mathematics for computer science, 2020. 

[http://www.cs.elte.hu/~lovasz/dmbook.ps Lecture notes: Discrete Mathematics], L. Lovasz, K. Vesztergombi

[http://rubtsov.su/public/DM-HSE-Draft.pdf Лекции по дискретной математике] (черновик учебника, in Russian)



'''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.)


'''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 =

{| class="wikitable"
|-
!  Person !! Monday !! Tuesday !! Wednesday !! Thursday !! Friday 
|-
|  [https://www.hse.ru/en/org/persons/160550073 Bruno Bauwens], S834, [https://us02web.zoom.us/j/82300259484?pwd=NWxXekxBeE5yMm9UTmwvLzNNNGlnUT09 Zoom] ||  || || 14:00-18:00 || 14:00-18:00 || 
|}
Warn me in advance by email.