Theoretical computer science spring 2023 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
 
(не показано 26 промежуточных версии 2 участников)
Строка 5: Строка 5:
 
Teacher: [https://www.hse.ru/en/org/persons/160550073 Bruno Bauwens]
 
Teacher: [https://www.hse.ru/en/org/persons/160550073 Bruno Bauwens]
  
−
For practical information ask to join the telegram group.
+
Homeworks need to be emailed to brbauwens -at- gmail.com before the start of the lecture next lecture. Put tcs in the subject line.
  
 +
For practical information ask to join the telegram group.
 +
 +
[https://www.dropbox.com/scl/fi/2opgvanhsuuqyrt1z5zhl/scores.ods?dl=0&rlkey=v0htrtejs04c1pujinri7ozqj Scores]
  
 
= Course Materials =
 
= Course Materials =
Строка 18: Строка 21:
 
! 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/uz1gyurwjvfwe77/automata.pdf?dl=0 lecture 1] ||
+
  || [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): equivalence between deterministic and nondeterministic automata, regular expressions] || ||
+
  || 15.02 || Regular languages 2: nondeterministic automata and regular expressions || || [https://www.dropbox.com/s/4ylwf3hdoncym8v/2_HW.pdf?dl=0 hw2]
 
|-  
 
|-  
−
  || 22.02 || Turing machines, the Halting problem, Godel incompleteness theorems || [https://www.dropbox.com/s/jslijos3lp03m83/turingDef.pdf?dl=0 lecture 2][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] ||
+
  || 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]
 
|-  
 
|-  
−
  || 02.03 || Famous polynomial time algorithms: Dijkstra, Kruskal, dynamic programming || ||
+
  || 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]
 
|-
 
|-
−
  || 09.03 || The classes P, EXP, PSPACE, EXPSPACE and NP. Time and space hierarchy theorems. || [https://www.dropbox.com/s/5amd18ey45qs4x3/cc_seminar.pdf?dl=0 seminar] ||
+
  || 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]
 
|-  
 
|-  
−
  || 16.03 || NP-completeness, circuits, proof of the Levin-Cook theorem, reductions (see also Mertens&Moore chapter 5) || [https://www.dropbox.com/s/90m0yxt62f02mmm/classNP.pdf?dl=0 notes] [https://www.dropbox.com/s/nen161dakmq3646/circuits.pdf?dl=0 circuits] [https://www.dropbox.com/s/wlrssw0q1tfx49p/moreReductions.pdf?dl=0 reductions] ||
+
  || 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]
 
|-  
 
|-  
−
|| 23.03 || Finishing previous lecture, the classes RP, coRP and BPP, primes in BPP || ||
+
|| 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]
 
|-  
 
|-  
−
|| 30.03(?) || Exam 
+
|| 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]
 
|-  
 
|-  
−
  || may || Projects
+
  || 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 =
 
= Grading =
  
−
Homework: 25%
+
Homework: 35%
  
−
Theory exam: 25%
+
Theory exam: 35%
  
−
Problem solving exam: 25%
+
Problem solving exam: 30%
  
−
Project: 25%
+
 
 +
Passing threshold is 4/10. Grades above 5/10 are rounded up, the other grades are rounded down.
  
  
 
= References =
 
= 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)
 +
  
  

Текущая версия на 17:59, 26 апреля 2023

Classes

Wednesdays 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. Put tcs in the subject line.

For practical information ask to join the telegram group.

Scores

Course Materials

Video Summary Notes Homework
08.02 Regular languages 1: deterministic automata, pumping lemma, closure properties lecture 1 & 2 hw1
15.02 Regular languages 2: nondeterministic automata and regular expressions hw2
01.03 Chapter 1 of discrete math for computer science (see 1st book below). Turing machines Turing machines hw3
16.03 Recursion and induction. (Chapt 3 of discrete math book.) Turing machines. hw4
23.03 Invariants (Chapt 5). Undecidability lecture 3.A hw5
29.03 Completeness 3.B hw6
12.04 (online, in zoom) The classes P, EXP, PSPACE, EXPSPACE. Time and space hierarchy theorems. See Sipser chapts 7 and 8 hw7
19.04 The class NP, NP-completeness, reduction from SAT to IND-SET notes hw8
26.04 Reductions. Proof of the Levin-Cook theorem. circuitsreductions hw9
17.05 Exam. Start at 16h00. 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.

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

Лекции по дискретной математике (черновик учебника, 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, Как написать математическую статью по-английски, 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-18:00

Warn me in advance by email.

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