TCS 2024 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
 
(не показана одна промежуточная версия этого же участника)
Строка 6: Строка 6:
  
 
Homeworks need to be emailed to brbauwens -at- gmail.com before the start of the lecture next lecture. Start the subject line with: tcs
 
Homeworks need to be emailed to brbauwens -at- gmail.com before the start of the lecture next lecture. Start the subject line with: tcs
 +
 +
[https://www.dropbox.com/scl/fi/ngqkqhkr4yz1mwcvunf2y/scores.ods?rlkey=u42sqn9z8mynpo6t5x25kfcip&dl=0 Grades homework]
  
 
For practical information click the [https://t.me/+jGeMKgaxMwE1YTZk this link] to join the telegram group.  
 
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 =
 
= Course Materials =
Строка 21: Строка 22:
 
! Video !! Summary !! Notes !! Homework  
 
! 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]
+
  || [https://youtu.be/BHm2eHFnC6U 01.02] || Regular languages 1: deterministic automata, pumping lemma, closure properties (old recording) || [https://www.dropbox.com/s/l764sm569b9ygic/automata.pdf?dl=0 lecture 1 & 2] || [https://www.dropbox.com/scl/fi/3dyzonjk30mnx5hn6u5qr/1_HW.pdf?rlkey=8to3ggky49jk7bvdegbtefh3p&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]
+
  || 08.02 || Regular languages 2: nondeterministic automata and regular expressions. Definition of Turing machines. || [https://www.dropbox.com/s/jslijos3lp03m83/turingDef.pdf?dl=0 Turing machines] || [https://www.dropbox.com/scl/fi/oxyywmkssmkgs6ucqnyf1/2_HW.pdf?rlkey=fffsptkcqcflb3hnnbsxzba7f&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]
+
  || 15.02 || Undecidable problems and computability theory || [https://www.dropbox.com/scl/fi/5dwc8heloau7wi5nrw5j1/undecidable.pdf?rlkey=9uj9rsciuhbjkjf77e4b7eg4k&dl=0 Turing completeness] || [https://www.dropbox.com/scl/fi/tpfeo2chpu1btvznn28uz/3_HW.pdf?rlkey=xzpvgcj5gj0w64iq10voydjw7&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]
+
  || 07.03 || The classes P, EXP, PSPACE, EXPSPACE, NP, reductions and completeness. || Sipser chapt 7, [https://www.dropbox.com/scl/fi/6d1ogvurx6bnrb4dhvpzv/classNP.pdf?rlkey=pf6cchn2rp9whgcxjxctm158q&dl=0 class_NP.pdf]|| [https://www.dropbox.com/scl/fi/sci194w0llp4onk27g5by/4_HW.pdf?rlkey=nt6v0kfxw3l9ejtv0x7edlfrf&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]
+
  || 14.03 || Circuits and completeness of 3SAT. More reductions.  || [https://www.dropbox.com/scl/fi/19s582oohxvdv2l8zqb6j/circuits.pdf?rlkey=4t88ofltyq4www15zj3o4cy9v&dl=0 circuits.pdf]  || [https://www.dropbox.com/scl/fi/uo9oga7blo0omy7rro8l6/5_HW.pdf?rlkey=m9hu2bwsm12gfu8g9zvx97jz8&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]
+
  || 21.03 || Parameterized complexity, the class FPT, kernelization, colorcoding. Colorcoding and background: [https://www.dropbox.com/scl/fi/fh16rk0x8ox7z4bygd6dt/maxPlank_introLecture.pdf?rlkey=awxztmxjb5obnk0z6r79ump2o&dl=0 in this lecture] || [https://www.dropbox.com/s/zzzaulpmzql7x7u/parameterizedComplexity.pdf?dl=0 presentation] || [https://www.dropbox.com/scl/fi/l00lmr5hjgx8i7prqj9ow/6_HW.pdf?rlkey=5hsea6m39lq0fjoat97vx4myr&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]
+
  || 25.03? || Treewidth.  ([https://cms.cispa.saarland/paramalg/ this course]) || [https://www.mpi-inf.mpg.de/fileadmin/inf/d1/teaching/winter21/paraalg/Lectures/lecture_11.pdf Slides] ||[https://www.mpi-inf.mpg.de/fileadmin/inf/d1/teaching/winter21/paraalg/Exercises/ex05.pdf hw7] ex 1,2,4
−
|-
+
−
|| 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%
+
= References =
  
−
Theory exam: 35%
+
'''Main reference'''
  
−
Problem solving exam: 30%
+
Sipser, Introduction to the theory of computation", 3rd edition, 2013, chapters 1, 3–8. (Short and good for basic understanding.)
  
−
 
−
Passing threshold is 4/10. Grades above 5/10 are rounded up, the other grades are rounded down.
 
−
 
−
 
−
= References =
 
  
 
'''Basic math'''
 
'''Basic math'''
Строка 63: Строка 52:
  
 
[http://rubtsov.su/public/DM-HSE-Draft.pdf Лекции по дискретной математике] (черновик учебника, in Russian)
 
[http://rubtsov.su/public/DM-HSE-Draft.pdf Лекции по дискретной математике] (черновик учебника, in Russian)
−
 
  
  
 
'''Computational complexity'''
 
'''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 with a lot of interesting background, but perhaps too much.)
−
 
+
−
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.)
 
Arora and Barak, Computational Complexity, 2009. (Use this after you made many exercises in the above books.)
Строка 83: Строка 69:
 
Gillman, Writing Mathematics Well, 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.-->
 
<!-- Strunk and White, [https://www.dropbox.com/s/7e6fcdpx3nubvko/strunk-white-1979-elements-of-style.pdf?dl=0 The elements of style], 1979.-->
 +
 +
 +
'''Parameterized complexity'''
 +
 +
M. Cygan, F. Fomin and 6 others, Parameterized algorithms, 2016
  
  
Строка 91: Строка 82:
 
!  Person !! Monday !! Tuesday !! Wednesday !! Thursday !! Friday  
 
!  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 || ||
+
|  [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.
 
Warn me in advance by email.

Текущая версия на 22:10, 4 апреля 2024

Classes

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

Teacher: 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

Grades homework

For practical information click the this link to join the telegram group.


Course Materials

Video Summary Notes Homework
01.02 Regular languages 1: deterministic automata, pumping lemma, closure properties (old recording) lecture 1 & 2 hw1
08.02 Regular languages 2: nondeterministic automata and regular expressions. Definition of Turing machines. Turing machines hw2
15.02 Undecidable problems and computability theory Turing completeness hw3
07.03 The classes P, EXP, PSPACE, EXPSPACE, NP, reductions and completeness. Sipser chapt 7, class_NP.pdf hw4
14.03 Circuits and completeness of 3SAT. More reductions. circuits.pdf hw5
21.03 Parameterized complexity, the class FPT, kernelization, colorcoding. Colorcoding and background: in this lecture presentation hw6
25.03? Treewidth. (this course) Slides hw7 ex 1,2,4


References

Main reference

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


Basic math

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

Lecture notes: Discrete Mathematics, L. Lovasz, K. Vesztergombi

Лекции по дискретной математике (черновик учебника, in Russian)


Computational complexity

Mertens and Moore, The Nature of Computation, 2011. (Pleasant reading with a lot of interesting background, but perhaps too much.)

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


Mathematical writing

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

Knuth, Technical writing, transcripts of lectures, 1987.

Gillman, Writing Mathematics Well, 1987.


Parameterized complexity

M. Cygan, F. Fomin and 6 others, Parameterized algorithms, 2016


Office hours

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

Warn me in advance by email.

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