https://www.wikicshse.ru/index.php?action=history&feed=atom&title=TCS_2024
TCS 2024 - История изменений
2026-06-06T14:43:50Z
История изменений этой страницы в вики
MediaWiki 1.45.3
https://www.wikicshse.ru/index.php?title=TCS_2024&diff=738&oldid=prev
imported>Bauwens: Migrated current public revision from wiki.cs.hse.ru
2024-04-04T19:10:20Z
<p>Migrated current public revision from wiki.cs.hse.ru</p>
<p><b>Новая страница</b></p><div>= Classes =<br />
<br />
Thursdays 18:10–21:00, in room S834. <br />
<br />
Teacher: [https://www.hse.ru/en/org/persons/160550073 Bruno Bauwens]<br />
<br />
Homeworks need to be emailed to brbauwens -at- gmail.com before the start of the lecture next lecture. Start the subject line with: tcs<br />
<br />
[https://www.dropbox.com/scl/fi/ngqkqhkr4yz1mwcvunf2y/scores.ods?rlkey=u42sqn9z8mynpo6t5x25kfcip&dl=0 Grades homework]<br />
<br />
For practical information click the [https://t.me/+jGeMKgaxMwE1YTZk this link] to join the telegram group. <br />
<br />
<br />
= Course Materials =<br />
<br />
<br />
<!-- If you need some background in math, consider these two sources:<br><br />
[http://www.cs.elte.hu/~lovasz/dmbook.ps Lecture notes: Discrete Mathematics], L. Lovasz, K. Vesztergombi<br><br />
[http://rubtsov.su/public/DM-HSE-Draft.pdf Лекции по дискретной математике] (черновик учебника, in Russian)--><br />
{| class="wikitable"<br />
|-<br />
! Video !! Summary !! Notes !! Homework <br />
|-<br />
|| [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]<br />
|- <br />
|| 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]<br />
|- <br />
|| 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]<br />
|- <br />
|| 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]<br />
|-<br />
|| 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]<br />
|-<br />
|| 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] <br />
|- <br />
|| 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<br />
|}<br />
<br />
<br />
= References =<br />
<br />
'''Main reference'''<br />
<br />
Sipser, Introduction to the theory of computation", 3rd edition, 2013, chapters 1, 3–8. (Short and good for basic understanding.)<br />
<br />
<br />
'''Basic math'''<br />
<br />
Golovnev, Kulikov, Podolskii, Shen, Discrete mathematics for computer science, 2020. <br />
<br />
[http://www.cs.elte.hu/~lovasz/dmbook.ps Lecture notes: Discrete Mathematics], L. Lovasz, K. Vesztergombi<br />
<br />
[http://rubtsov.su/public/DM-HSE-Draft.pdf Лекции по дискретной математике] (черновик учебника, in Russian)<br />
<br />
<br />
'''Computational complexity'''<br />
<br />
Mertens and Moore, The Nature of Computation, 2011. (Pleasant reading with a lot of interesting background, but perhaps too much.)<br />
<br />
Arora and Barak, Computational Complexity, 2009. (Use this after you made many exercises in the above books.)<br />
<br />
<br />
'''Mathematical writing'''<br />
<br />
Sosinsky, [http://www.ega-math.narod.ru/Quant/ABS.htm Как написать математическую статью по-английски], 2000.<br />
<br />
Knuth, [https://jmlr.csail.mit.edu/reviewing-papers/knuth_mathematical_writing.pdf Technical writing], transcripts of lectures, 1987.<br />
<br />
Gillman, Writing Mathematics Well, 1987.<br />
<!-- Strunk and White, [https://www.dropbox.com/s/7e6fcdpx3nubvko/strunk-white-1979-elements-of-style.pdf?dl=0 The elements of style], 1979.--><br />
<br />
<br />
'''Parameterized complexity'''<br />
<br />
M. Cygan, F. Fomin and 6 others, Parameterized algorithms, 2016 <br />
<br />
<br />
= Office hours =<br />
<br />
{| class="wikitable"<br />
|-<br />
! Person !! Monday !! Tuesday !! Wednesday !! Thursday !! Friday <br />
|-<br />
| [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<br />
|}<br />
Warn me in advance by email.</div>
imported>Bauwens