https://wikicshse.ru/index.php?action=history&feed=atom&title=Theoretical_Computer_Science_2022
Theoretical Computer Science 2022 - История изменений
2026-06-06T12:12:56Z
История изменений этой страницы в вики
MediaWiki 1.45.3
https://wikicshse.ru/index.php?title=Theoretical_Computer_Science_2022&diff=743&oldid=prev
imported>Bbauwens: Migrated current public revision from wiki.cs.hse.ru
2023-02-09T18:11:38Z
<p>Migrated current public revision from wiki.cs.hse.ru</p>
<p><b>Новая страница</b></p><div>= Classes =<br />
<br />
Wednesdays 18:10–21:00, on [https://us02web.zoom.us/j/82300259484?pwd=NWxXekxBeE5yMm9UTmwvLzNNNGlnUT09 zoom]<br />
<br />
Teacher: [https://www.hse.ru/en/org/persons/160550073 Bruno Bauwens]<br />
<br />
For practical information join the [https://t.me/+fjwhc1N_Cn1iNmEy 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 !<br />
|-<br />
|| [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] <br />
|- <br />
|| 25.01 || Turing machines and register machines || [https://www.dropbox.com/s/jslijos3lp03m83/turingDef.pdf?dl=0 lecture 2]<br />
|- <br />
|| 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] <br />
|- <br />
|| 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] <br />
|- <br />
|| <span style="color:gray">23.02</span> || <span style="color:gray">Holliday</span> || <br />
|- <br />
|| 02.03 || The class NP and NP-completeness || [https://www.dropbox.com/s/90m0yxt62f02mmm/classNP.pdf?dl=0 notes] <br />
|- <br />
|| 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] <br />
|- <br />
|| 16.03 || More NP-complete problems || [https://www.dropbox.com/s/wlrssw0q1tfx49p/moreReductions.pdf?dl=0 reductions] <br />
|- <br />
|| 23.03 || Games, PSPACE, Savich theorem, completeness of TQBF || [https://www.dropbox.com/s/77sr5nhne411ahz/classPSPACE.pdf?dl=0 pspace] <br />
|- <br />
|| 30.03 || Parameterized complexity I: the class FPT and kernelization || [https://www.dropbox.com/s/khol9uoy24l6rmg/paramComp.pdf?dl=0 notes]<br />
|- <br />
|| 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]<br />
|-<br />
|| <span style="color:gray">20.04</span> || <span style="color:gray">No lecture</span><br />
|-<br />
|| 27.04 || Projects ||<br />
|}<br />
<br />
<br />
<br />
= Homeworks =<br />
<br />
[https://www.dropbox.com/s/uhi35jl4ofm1ws1/1_HW.pdf?dl=0 HW1 automata]<br />
<br />
[https://www.dropbox.com/s/j4o5bqz0o1r171o/2_HW.pdf?dl=0 HW2 computability]<br />
<br />
[https://www.dropbox.com/s/4mgniv56j9qg2c8/3_HW.pdf?dl=0 HW3 P, NP, hierarchy theorems, circuits]<br />
<br />
[https://www.dropbox.com/s/w3d6hetx65se8hx/4_HW.pdf?dl=0 HW4 NP and PSPACE completeness]<br />
<br />
[https://www.dropbox.com/s/q9afprj9wwgj7qy/5_HW.pdf?dl=0 HW5 parameterized complexity] <br />
<br />
<br />
<br />
= Grading =<br />
<br />
Homework: 50%<br><br />
<br />
Project: 50%<br />
<br />
<br />
= References =<br />
<br />
<br />
'''Computational complexity'''<br />
<br />
Sipser, Introduction to the theory of computation", 3rd edition, 2013, chapters 1, 2–8. (Short and good for basic understanding.)<br />
<br />
Mertens and Moore, The Nature of Computation, 2011. (Pleasant reading, loads of interesting background, but rather large.)<br />
<br />
Arora and Barak, Computational Complexity, 2009. (Use this after you made many exercises in the above books.)<br />
<br />
<br />
'''Parameterized algorithms'''<br />
<br />
Marx and Misra, [https://www.mpi-inf.mpg.de/departments/algorithms-complexity/teaching/summer20/parameterized-algorithms Algorithms and Complexity], course website, 2020.<br />
<br />
Fomin and 7 others. Parameterized algorithms, 2015. (This is an advanced book.)<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 />
= 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-20:00<br />
|}<br />
Warn me in advance by email.</div>
imported>Bbauwens