Theory of Computation 2024 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
Bauwens (обсуждение | вклад) (Новая страница: « <br> = Classes = Lectures: TBA in Pokrovkaya TBA and in [https://us02web.zoom.us/j/82300259484?pwd=NWxXekxBeE5yMm9UTmwvLzNNNGlnUT09 zoom] by [https://www.hse.r…») |
Bauwens (обсуждение | вклад) |
||
| (не показано 9 промежуточных версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
| − | |||
| − | |||
= Classes = | = Classes = | ||
| − | Lectures: TBA in Pokrovkaya TBA and in [https://us02web.zoom.us/j/82300259484?pwd=NWxXekxBeE5yMm9UTmwvLzNNNGlnUT09 zoom] by [https://www.hse.ru/en/org/persons/160550073 Bruno Bauwens] | + | Lectures: TBA in Pokrovkaya TBA and in [https://us02web.zoom.us/j/82300259484?pwd=NWxXekxBeE5yMm9UTmwvLzNNNGlnUT09 zoom] by [https://www.hse.ru/en/org/persons/160550073 Bruno Bauwens] 1st lecture is on 21.09 at 11h40--13h. |
| − | Seminars: | + | Seminars: After the lecture in room TBA and on the same zoomlink by [https://www.hse.ru/en/org/persons/190890122 Yaroslav Ivanashev] |
| − | Telegram group for announcements and discussions [https://t.me/+axdYo-H6h35iNWU0 invite link.] The course is similar to [http://wiki.cs.hse.ru/Theory_of_Computation_2023 last year's one] | + | Telegram group for announcements and discussions [https://t.me/+axdYo-H6h35iNWU0 invite link.] The course is similar to [http://wiki.cs.hse.ru/Theory_of_Computation_2023 last year's one] For PI students the course is called ''computational complexity'' and has a 2nd part in Febr--March 2025. |
| − | |||
= Homeworks = | = Homeworks = | ||
| Строка 16: | Строка 13: | ||
Deadlines: every 2 weeks, before the lecture at 17h30. Submit in pdf or fotos of handwritten text in (link google classrooms TBA), code TBA. Results TBA. Questions [https://t.me/ivanashev Yaroslav Ivanashev]. | Deadlines: every 2 weeks, before the lecture at 17h30. Submit in pdf or fotos of handwritten text in (link google classrooms TBA), code TBA. Results TBA. Questions [https://t.me/ivanashev Yaroslav Ivanashev]. | ||
| − | Tasks are in the problem lists from the seminar. Deadlines: | + | Tasks are in the problem lists from the seminar. Deadlines: problem lists 1 and 2: at the start of 3rd lecture, lists 3 and 4 at the start of the 5th lecture, etc. |
| − | + | ||
= Course Materials = | = Course Materials = | ||
| Строка 23: | Строка 20: | ||
The main reference is Sipser's book "Introduction to the theory of computation", chapters 3, 4, 7–10. | The main reference is Sipser's book "Introduction to the theory of computation", chapters 3, 4, 7–10. | ||
| − | + | If you need some background in math, consider: | |
| − | + | [http://www.cs.elte.hu/~lovasz/dmbook.ps Lecture notes: Discrete Mathematics], L. Lovasz, K. Vesztergombi and | |
| − | If you need some background in math, consider | + | |
| − | [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) | [http://rubtsov.su/public/DM-HSE-Draft.pdf Лекции по дискретной математике] (черновик учебника, in Russian) | ||
| − | |||
{| class="wikitable" | {| class="wikitable" | ||
| Строка 34: | Строка 28: | ||
! Rec !! Summary !! Problem list | ! Rec !! Summary !! Problem list | ||
|- | |- | ||
| − | || [https://www.youtube.com/watch?v=XcApxCiymew | + | || [https://www.youtube.com/watch?v=XcApxCiymew 21.09] || Turing machines, multitape Turing machines, connection between them. Universal Turing machine. Examples. Time and space complexity. Complexity classes P, PSPACE, EXP. || [https://drive.google.com/file/d/19T2NKv8gWpLyYQtittxr9lzISdlIJguN/view?usp=sharing problem list 1] |
|- | |- | ||
|- | |- | ||
| − | || [https://www.youtube.com/watch?v=tnq5BkcGfk0 ??.09] || Time and space hierarchy theorems. Time and space constructible functions. || | + | || [https://www.youtube.com/watch?v=tnq5BkcGfk0 ??.09] || Time and space hierarchy theorems. Time and space constructible functions. || |
|- | |- | ||
| − | || [https://www.youtube.com/watch?v=iwaqw60aZV0 ??.09] || Complexity class NP. Examples. Non-deterministic machines and another definition of NP. Polynomial reductions. NP-hardness and NP-completeness. || | + | || [https://www.youtube.com/watch?v=iwaqw60aZV0 ??.09] || Complexity class NP. Examples. Non-deterministic machines and another definition of NP. Polynomial reductions. NP-hardness and NP-completeness. || |
|- | |- | ||
| − | || [https://www.youtube.com/watch?v=sGfulQ1YoUU ??.10] || NP-completenes of independent set, vertex cover, dominating set, NAE-3SAT, 3colorability. || | + | || [https://www.youtube.com/watch?v=sGfulQ1YoUU ??.10] || NP-completenes of independent set, vertex cover, dominating set, NAE-3SAT, 3colorability. || |
|- | |- | ||
| − | || [https://www.youtube.com/watch?v=Jqy89FPbFj4 ??.10] || Circuit complexity. Classes AC^i, NC^i, P/poly. All functions are computed by circuits. Existence of functions with exponential circuit complexity. NC1 = Boolean formulas of polynomial size. P is in P/poly (without proof). Addition in AC0. Multiplication is in NC1. [https://www.dropbox.com/scl/fi/ulrlsa5tw7kz1x0aj7bp1/circuits.pdf?rlkey=q3cx7akryx9hnsgc19yhvv0e3&dl=0 circuit_notes.pdf] || | + | || [https://www.youtube.com/watch?v=Jqy89FPbFj4 ??.10] || Circuit complexity. Classes AC^i, NC^i, P/poly. All functions are computed by circuits. Existence of functions with exponential circuit complexity. NC1 = Boolean formulas of polynomial size. P is in P/poly (without proof). Addition in AC0. Multiplication is in NC1. [https://www.dropbox.com/scl/fi/ulrlsa5tw7kz1x0aj7bp1/circuits.pdf?rlkey=q3cx7akryx9hnsgc19yhvv0e3&dl=0 circuit_notes.pdf] || |
|- | |- | ||
| + | || [https://www.youtube.com/watch?v=NNorKIxgTGU ??.10] || Proof that P is in P/poly. Proof of Cook Levin theorem. NP-completeness of: exact 1-in-3SAT, subsetsum, Hamiltonian path. Strong NP-completeness. coNP and coNP-completeness.|| | ||
|- | |- | ||
| − | + | || [https://youtube.com/live/_xE0y_4Jb9o ??.11] || Directed Reachability is in SPACE(log^2 n). TQBF problem, its PSPACE-completeness. PSPACE = NPSPACE. NSPACE(s(n)) is in SPACE(s(n)^2) for space constructible s.|| | |
| − | + | ||
| − | || [https://youtube.com/live/_xE0y_4Jb9o ??.11] || Directed Reachability is in SPACE(log^2 n). TQBF problem, its PSPACE-completeness. PSPACE = NPSPACE. NSPACE(s(n)) is in SPACE(s(n)^2) for space constructible s.|| | + | |
|- | |- | ||
| − | || [https://www.youtube.com/watch?v=rK5_1KPL9Ko ??.11] || Oracle computation definitions. There exists an oracle ''A'' for which P<sup>''A''</sup> = NP<sup>''A''</sup>. There is an oracle B such that P<sup>''B''</sup> is not equal to NP<sup>''B''</sup>. || | + | || [https://www.youtube.com/watch?v=rK5_1KPL9Ko ??.11] || Oracle computation definitions. There exists an oracle ''A'' for which P<sup>''A''</sup> = NP<sup>''A''</sup>. There is an oracle B such that P<sup>''B''</sup> is not equal to NP<sup>''B''</sup>. || |
|- | |- | ||
| − | || [https://www.youtube.com/watch?v=X67F8P0dcAA ??.11] || Probabilistic computation. Probabilistic machines, the class BPP, invariance of the definition BPP for different thresholds, RP, coRP, PP, ZPP. BPP is in P/poly. Most of it is also [https://www.youtube.com/watch?v=YSMgVbOqB-8&list=PLm3J0oaFux3YL5vLXpzOyJiLtqLp6dCW2&index=23 here]|| | + | || [https://www.youtube.com/watch?v=X67F8P0dcAA ??.11] || Probabilistic computation. Probabilistic machines, the class BPP, invariance of the definition BPP for different thresholds, RP, coRP, PP, ZPP. BPP is in P/poly. Most of it is also [https://www.youtube.com/watch?v=YSMgVbOqB-8&list=PLm3J0oaFux3YL5vLXpzOyJiLtqLp6dCW2&index=23 here]|| |
|- | |- | ||
|| [https://www.youtube.com/watch?v=f7pYWzRLflg&t=20s ??.11] || Approximation algorithms. Definition c-approximation algorithm. 2-approximation for vertex cover and greedy vertex cover is not optimal. (ln n + 1)-approximation for set cover. PTAS for the makespan problem. Based on [https://www.youtube.com/watch?v=MEz1J9wY2iM&pp=ygUYYXBwcm94aW1hdGlvbiBhbGdvcml0aG1z MIT lecture]. | || [https://www.youtube.com/watch?v=f7pYWzRLflg&t=20s ??.11] || Approximation algorithms. Definition c-approximation algorithm. 2-approximation for vertex cover and greedy vertex cover is not optimal. (ln n + 1)-approximation for set cover. PTAS for the makespan problem. Based on [https://www.youtube.com/watch?v=MEz1J9wY2iM&pp=ygUYYXBwcm94aW1hdGlvbiBhbGdvcml0aG1z MIT lecture]. | ||
| − | || | + | || |
|- | |- | ||
| − | || ??.12 || Parameterized complexity: The classes FPT and XP. Kernelization. Examples for vertex cover. [https://www.dropbox.com/scl/fi/x5gwdae4ny4u3zixoy4pw/student_vc_branching.ipynb?rlkey=5oowq1u3jhy490s84ogojg1s7&dl=0 programming task.] [https://www.dropbox.com/s/zzzaulpmzql7x7u/parameterizedComplexity.pdf?dl=0 presentation]. || | + | || ??.12 || Parameterized complexity: The classes FPT and XP. Kernelization. Examples for vertex cover. [https://www.dropbox.com/scl/fi/x5gwdae4ny4u3zixoy4pw/student_vc_branching.ipynb?rlkey=5oowq1u3jhy490s84ogojg1s7&dl=0 programming task.] [https://www.dropbox.com/s/zzzaulpmzql7x7u/parameterizedComplexity.pdf?dl=0 presentation]. || |
|- | |- | ||
| − | || ??.12 || Parameterized complexity, techniques for obtaining FPT algorithms: branching (feedback vertex), color coding (k-path problem), dynamic programming (set cover) || | + | || ??.12 || Parameterized complexity, techniques for obtaining FPT algorithms: branching (feedback vertex), color coding (k-path problem), dynamic programming (set cover) || |
|- | |- | ||
| − | || ??.12 || ''Colloquium'' || [https://www.dropbox.com/s/37gdsbv2it8omnm/tc-sample-exam.pdf?dl=0 Sample exam] | + | || ??.12 || ''Colloquium'' see below for questions || [https://www.dropbox.com/s/37gdsbv2it8omnm/tc-sample-exam.pdf?dl=0 Sample exam] |
|} | |} | ||
| Строка 130: | Строка 123: | ||
Final score = 0.3 * [score homework] + 0.3 * [score colloquium] + 0.2 * [score exam] + 0.2 * [score project] <br> | Final score = 0.3 * [score homework] + 0.3 * [score colloquium] + 0.2 * [score exam] + 0.2 * [score project] <br> | ||
| − | Some homework assignments contain extra problems. Each solution of an extra problem will give 1 extra point on the final exam. There will be around 6 extra problems. | + | Some homework assignments contain extra problems. Each solution of an extra problem will give 1 extra point on the final exam. There will be around 6 extra problems. Rounding is applied only when the final score is transferred to the official grade. Arithmetic rounding is used. Autogrades. If only 6/10 for the exam is needed to get a final score of 10/10, then this will be given automatically. |
| − | + | ||
| − | + | ||
| − | Rounding is applied only when the final score is transferred to the official grade. Arithmetic rounding is used. | + | |
| − | + | ||
| − | Autogrades. If only 6/10 for the exam is needed to get a final score of 10/10, then this will be given automatically. | + | |
| − | + | ||
| − | + | ||
= Colloquium and exam = | = Colloquium and exam = | ||
| Строка 144: | Строка 130: | ||
Exam: Copies of Sipser's book, Arora&Barak, Mertens&Moore, will be available. (I you have these books or printed parts of them, please bring it.) Also, personal handwritten notes are allowed, but nothing else. [https://www.dropbox.com/s/37gdsbv2it8omnm/tc-sample-exam.pdf?dl=0 Sample exam]. | Exam: Copies of Sipser's book, Arora&Barak, Mertens&Moore, will be available. (I you have these books or printed parts of them, please bring it.) Also, personal handwritten notes are allowed, but nothing else. [https://www.dropbox.com/s/37gdsbv2it8omnm/tc-sample-exam.pdf?dl=0 Sample exam]. | ||
| − | |||
| − | |||
= Office hours = | = Office hours = | ||
| − | Bruno Bauwens: | + | Bruno Bauwens: TBA. Better send me an email in advance. |
| − | + | Yaroslav Ivanashev: Write in telegram. | |
Версия 14:54, 19 сентября 2024
Содержание
Classes
Lectures: TBA in Pokrovkaya TBA and in zoom by Bruno Bauwens 1st lecture is on 21.09 at 11h40--13h.
Seminars: After the lecture in room TBA and on the same zoomlink by Yaroslav Ivanashev
Telegram group for announcements and discussions invite link. The course is similar to last year's one For PI students the course is called computational complexity and has a 2nd part in Febr--March 2025.
Homeworks
Deadlines: every 2 weeks, before the lecture at 17h30. Submit in pdf or fotos of handwritten text in (link google classrooms TBA), code TBA. Results TBA. Questions Yaroslav Ivanashev.
Tasks are in the problem lists from the seminar. Deadlines: problem lists 1 and 2: at the start of 3rd lecture, lists 3 and 4 at the start of the 5th lecture, etc.
Course Materials
The main reference is Sipser's book "Introduction to the theory of computation", chapters 3, 4, 7–10.
If you need some background in math, consider: Lecture notes: Discrete Mathematics, L. Lovasz, K. Vesztergombi and Лекции по дискретной математике (черновик учебника, in Russian)
| Rec | Summary | Problem list |
|---|---|---|
| 21.09 | Turing machines, multitape Turing machines, connection between them. Universal Turing machine. Examples. Time and space complexity. Complexity classes P, PSPACE, EXP. | problem list 1 |
| ??.09 | Time and space hierarchy theorems. Time and space constructible functions. | |
| ??.09 | Complexity class NP. Examples. Non-deterministic machines and another definition of NP. Polynomial reductions. NP-hardness and NP-completeness. | |
| ??.10 | NP-completenes of independent set, vertex cover, dominating set, NAE-3SAT, 3colorability. | |
| ??.10 | Circuit complexity. Classes AC^i, NC^i, P/poly. All functions are computed by circuits. Existence of functions with exponential circuit complexity. NC1 = Boolean formulas of polynomial size. P is in P/poly (without proof). Addition in AC0. Multiplication is in NC1. circuit_notes.pdf | |
| ??.10 | Proof that P is in P/poly. Proof of Cook Levin theorem. NP-completeness of: exact 1-in-3SAT, subsetsum, Hamiltonian path. Strong NP-completeness. coNP and coNP-completeness. | |
| ??.11 | Directed Reachability is in SPACE(log^2 n). TQBF problem, its PSPACE-completeness. PSPACE = NPSPACE. NSPACE(s(n)) is in SPACE(s(n)^2) for space constructible s. | |
| ??.11 | Oracle computation definitions. There exists an oracle A for which PA = NPA. There is an oracle B such that PB is not equal to NPB. | |
| ??.11 | Probabilistic computation. Probabilistic machines, the class BPP, invariance of the definition BPP for different thresholds, RP, coRP, PP, ZPP. BPP is in P/poly. Most of it is also here | |
| ??.11 | Approximation algorithms. Definition c-approximation algorithm. 2-approximation for vertex cover and greedy vertex cover is not optimal. (ln n + 1)-approximation for set cover. PTAS for the makespan problem. Based on MIT lecture. | |
| ??.12 | Parameterized complexity: The classes FPT and XP. Kernelization. Examples for vertex cover. programming task. presentation. | |
| ??.12 | Parameterized complexity, techniques for obtaining FPT algorithms: branching (feedback vertex), color coding (k-path problem), dynamic programming (set cover) | |
| ??.12 | Colloquium see below for questions | Sample exam |
| Date | Software engineering: parameterized complexity | Problem list |
|---|---|---|
| ??.02 | Recap from last lecture, more examples of kernelization. | |
| ??.02 | Linear programming kernel for vertex cover, tree decompositions | |
| ??.02 | hardness from ETH (exponential time hypothesis) and W-hierarchy |
Project (for PI students)
During the 3rd module Januari till March 2024 there are projects where you need to implement algorithms from parameterized complexity. (For example, for the vertex cover algorithm and disjoint paths problems.) A grader will check whether your algorithm reaches certain time limits.
There are 3 tasks: 2 of them about branching and kernelization, 1 task about linear programming bounds. See the table with lectures. The tasks have equal weight for the grade.
Deadline March 31st, 23h59.
Additional reading
Both books below contain a lot of extra materials and describe more recent discoveries in computational complexity. The first book has a gentle and pleasant style. The second book is a rigorous textbook for students theoretical computer science at the beginning master level.
C. Moore and S. Mertens, The nature of computation, 2011.
S. Arora and B. Barak, Computational Complexity: A Modern Approach, 2009.
This is an advanced textbook with background on parameterized algorithms.
M. Cygan, F. Fomin and 6 others, Parameterized algorithms, 2016
Grading
For AMI students:
Final score = 0.35 * [score homework] + 0.35 * [score colloquium] + 0.3 * [score exam]
For PI students (the course is called "computational complexity" and takes 3 modules):
Final score = 0.3 * [score homework] + 0.3 * [score colloquium] + 0.2 * [score exam] + 0.2 * [score project]
Some homework assignments contain extra problems. Each solution of an extra problem will give 1 extra point on the final exam. There will be around 6 extra problems. Rounding is applied only when the final score is transferred to the official grade. Arithmetic rounding is used. Autogrades. If only 6/10 for the exam is needed to get a final score of 10/10, then this will be given automatically.
Colloquium and exam
Colloquium: in the middel of December, a list with about 20 questions will be provided. Last year's rules and questions.
Exam: Copies of Sipser's book, Arora&Barak, Mertens&Moore, will be available. (I you have these books or printed parts of them, please bring it.) Also, personal handwritten notes are allowed, but nothing else. Sample exam.
Office hours
Bruno Bauwens: TBA. Better send me an email in advance.
Yaroslav Ivanashev: Write in telegram.
