Теория вычислений 2022 — различия между версиями
м |
м |
||
(не показаны 52 промежуточные версии этого же участника) | |||
Строка 9: | Строка 9: | ||
'''Преподаватель:''' [https://www.hse.ru/org/persons/208499388 Павел Захаров], телеграм: [https://t.me/duckbinladen @DuckBinLaden], Анна Енгоян, телеграм: [https://t.me/yaognennaya @yaognennaya] | '''Преподаватель:''' [https://www.hse.ru/org/persons/208499388 Павел Захаров], телеграм: [https://t.me/duckbinladen @DuckBinLaden], Анна Енгоян, телеграм: [https://t.me/yaognennaya @yaognennaya] | ||
− | '''Время и место (с 31 января):''' понедельник, 16:20, корпус на Покровском бульваре, аудитория | + | '''Время и место (с 31 января):''' понедельник, 16:20, корпус на Покровском бульваре, аудитория R406. |
− | ''' | + | '''Телеграм-чат:''' [https://t.me/+lnowoF11XNMyYmJi ссылка]. |
− | ''' | + | '''Таблица с результатами:''' [https://docs.google.com/spreadsheets/d/1Opr-0V_HzaCrMbLVssBwdhlCXi9TDm4QlugU6CVF4pA/edit?usp=sharing ссылка]. |
− | ''' | + | ==Примерная программа== |
+ | |||
+ | Из обязательных тем предполагаются первые 3 ± 1, после чего планируется сделать гибкую программу, учитывающую пожелания слушающих. | ||
+ | |||
+ | * Временная сложность, классы P и NP ['''пройдено''']. | ||
+ | * NP-трудные и NP-полные задачи, NP-полнота некоторых задач ['''пройдено''']. | ||
+ | * Space complexity, PSPACE-полные задачи ['''пройдено''']. | ||
+ | * Сложность вычислений с помощью схем из функциональных элементов, класс P/poly. | ||
+ | * Сложностные характеристики булевых функций ['''пройдено''']. | ||
+ | * Разрешающие деревья. Гипотеза Аандераа—Карпа—Розенберга ['''пройдено''']. | ||
+ | * Коммуникационная сложность. | ||
+ | * Булев анализ. Теорема Эрроу ['''пройдено''']. | ||
+ | * Спектральный экспандер. Зиг-заг произведение. Детерменированный алгоритм для задачи UPATH. | ||
+ | * Линейное программирование. Метод исключения переменных. Метод эллипсоидов. Симплекс-метод ['''частично пройдено''']. | ||
+ | * Аппроксимационные алгоритмы. ЛП релаксация для задачи MIN-VC. ЛП релаксация для задачи MAX-CUT ['''пройдено''']. | ||
+ | * Вероятностная сложность, класс BPP (и другие), вероятностные алгоритмы проверки числа на простоту и проверки полиномов на равенство. | ||
+ | * Апериодические замощения. Плитки Вана ['''пройдено''']. | ||
==История== | ==История== | ||
− | '''31 января | + | '''31 января 2022. Занятие 1.''' Машина Тьюринга. Классы P и NP. [https://drive.google.com/file/d/1XHzZEZ268RATHsPTaqHBMca0S4FF1xpR/view?usp=sharing Конспект] |
+ | <br> | ||
+ | <br> | ||
+ | '''7 февраля 2022. Занятие 2.''' Классы NP-hard и NP-complete. Теорема Кука-Левина. [https://drive.google.com/file/d/1YSqiVL9FKDxEG3sxNO-hG74sNg3zJUdJ/view?usp=sharing Конспект] | ||
+ | <br> | ||
+ | <br> | ||
+ | '''14 февраля 2022. Занятие 3.''' Space complexity, space hierarchy theorem. [https://drive.google.com/file/d/1ZcU19VpiXnk1RiXfxQhG_zBhatmEam7Q/view?usp=sharing Конспект] | ||
+ | <br> | ||
+ | <br> | ||
+ | '''21 февраля 2022. Занятие 4.''' Линейное программирование. Приближённые алгоритмы, MAX-IND, TSP. [https://drive.google.com/file/d/1_Ihx-ddhkleRK9CHKeJ7YpqqtpiL-7P7/view?usp=sharing Конспект] | ||
+ | <br> | ||
+ | <br> | ||
+ | '''28 февраля 2022. Занятие 5.''' ЛП релаксации, MIN-VC, MAX-SAT. [https://drive.google.com/file/d/1agITnxTqtpLwBSWsUD1zIqHgq6B4Pike/view?usp=sharing Конспект] | ||
+ | <br> | ||
+ | <br> | ||
+ | '''7 марта 2022. Занятие 6.''' Разложение булевой функции в ряд Фурье: существование и единственность. [https://drive.google.com/file/d/1bfcBqbU4NW1n68-75ue-uZ5kMBsCX-P8/view?usp=sharing Конспект] | ||
+ | <br> | ||
+ | <br> | ||
+ | '''14 марта 2022. Занятие 7.''' Функции голосования. Теорема Эрроу. [https://drive.google.com/file/d/1cM7anTWm6qqe202kP-pZtQ1dcjS4G03l/view?usp=sharing Конспект] | ||
+ | <br> | ||
+ | <br> | ||
+ | '''14 марта 2022. Занятие 8.''' Сертификатная сложность, чувствительность, блочная чувствительность. Гипотеза Карпа. Тернарные функции. [https://drive.google.com/file/d/15eQNzuMIMafmJPy-TrWVAczws8nCQIHi/view?usp=sharing Конспект] | ||
+ | <br> | ||
+ | <br> | ||
+ | '''28 марта 2022. Занятие 8½.''' Случайные графы. Пороговая вероятность. Метод интерполяции. | ||
+ | <br> | ||
+ | <br> | ||
+ | '''4 апреля 2022. Занятие 9.''' Информационная энтропия. [https://drive.google.com/file/d/1f-xDRSCxEToVbvKj0-xgLDQv_VBs4CNZ/view?usp=sharing Конспект] | ||
+ | <br> | ||
+ | <br> | ||
+ | '''11 апреля 2022. Занятие 10.''' Неравенство Ширера. Теорема Кана о независимых множествах. [https://drive.google.com/file/d/1fCtggFf1qY-YstEHQ_Ut68ErRmOIoPOZ/view?usp=sharing Конспект] | ||
+ | <br> | ||
+ | <br> | ||
+ | '''18 апреля 2022. Занятие 11.''' Апериодические замощения. Плитки Вана. [ Конспект] | ||
+ | <br> | ||
+ | <br> | ||
+ | '''25 апреля 2022. Занятие 12.''' Регулярные выражения. Конечные автоматы [ Конспект] | ||
+ | <br> | ||
+ | <br> | ||
+ | '''23 мая 2022. Занятие 13.''' Криптография на решётках. LLL-алгоритм [https://drive.google.com/file/d/1iB0xESfwbN2H4hr8m_ebXTBZFADHXYdF/view Конспект] | ||
+ | <br> | ||
+ | <br> | ||
+ | '''30 мая 2022. Занятие 14.''' Задача MCSP. Её NP-полнота [ Конспект] | ||
<br> | <br> | ||
<br> | <br> | ||
==Правила оценивания== | ==Правила оценивания== | ||
− | + | Оценка складывается из двух пунктов: | |
− | * '''Задачи.''' Решать и сдавать задачи из нижеприведённого списка. Сдачу | + | * '''Задачи.''' Решать и сдавать задачи из нижеприведённого списка. Сдачу планируется проводить только лишь устную. Сдавать можно любому из (двоих) преподавателей. Время и место выбирается по договорённости. |
− | * '''Экзамен.''' Экзамен будет в формате мини-конференции. Каждый студент выбирает статью из нижеприведённого списка и делает по ней доклад минут на | + | * '''Экзамен.''' Экзамен будет в формате мини-конференции. Каждый студент выбирает статью из нижеприведённого списка и делает по ней доклад (минут на ДЛИНА_ПАРЫ / ЧИСЛО_СДАЮЩИХ). |
Итоговая оценка формируется как O<sub>итоговая</sub> = 0,7 * O<sub>задачки</sub> + 0,3 * О<sub>экз</sub>. | Итоговая оценка формируется как O<sub>итоговая</sub> = 0,7 * O<sub>задачки</sub> + 0,3 * О<sub>экз</sub>. | ||
Строка 33: | Строка 91: | ||
====Наборы задач==== | ====Наборы задач==== | ||
− | * | + | * [https://drive.google.com/file/d/1ZopQKQKdnKj-ae7pZHUAJHiswB_duqpr/view?usp=sharing Вычислимость], дедлайн 5 апреля. |
+ | * [https://drive.google.com/file/d/1QuDQg9pBa-WAx3Jkttq68tRhuDybyCYC/view?usp=sharing Приближённые алгоритмы], дедлайн 10 апреля. | ||
+ | * [https://drive.google.com/file/d/1ceV9kzmdENfp6vcdfafmun5R23VMMMk2/view?usp=sharing Булев анализ], дедлайн 10 апреля. | ||
+ | * [https://drive.google.com/file/d/1hZoWDN9RxhMBC-DWz3WWXiFCwaU4rWxv/view?usp=sharing Сложностные характеристики булевых функций], дедлайн 22 апреля. | ||
+ | * [https://drive.google.com/file/d/1WB4J7onWSABbDCmCdkjc2nJbrGwFUIZm/view?usp=sharing Энтропия], дедлайн 22 апреля. | ||
==Интересные статьи== | ==Интересные статьи== | ||
+ | Пока что заранее заготовленные примеры, список будет пополняться (учитывая предпочтения слушающих). | ||
* J. Hartmanis & R. E. Stearns. [http://www.cs.albany.edu/~res/comp_complexity_ams_1965.pdf On the complexity of algorithms] (1965). (Статья, с которой началась теория сложности вычислений). | * J. Hartmanis & R. E. Stearns. [http://www.cs.albany.edu/~res/comp_complexity_ams_1965.pdf On the complexity of algorithms] (1965). (Статья, с которой началась теория сложности вычислений). | ||
Строка 42: | Строка 105: | ||
* Stephen A. Cook. [https://dl.acm.org/doi/10.1145/800157.805047 The complexity of theorem-proving procedures] (1971). (Определение полноты (осторожно: не совсем такое, как у нас) и теорема Кука-Левина). | * Stephen A. Cook. [https://dl.acm.org/doi/10.1145/800157.805047 The complexity of theorem-proving procedures] (1971). (Определение полноты (осторожно: не совсем такое, как у нас) и теорема Кука-Левина). | ||
− | + | * Л. А. Левин. [http://www.mathnet.ru/links/efc20ed39c74803d8ecb1011962ba4b3/ppi914.pdf Универсальные задачи перебора] (1973). (Внушительный список комбинаторных задач с доказательствами их NP-полноты) | |
− | + | ||
− | * Л. А. Левин. [http://www.mathnet.ru/links/efc20ed39c74803d8ecb1011962ba4b3/ppi914.pdf Универсальные задачи перебора] (1973). ( | + | |
* M. Agrawal, N. Kayal & N. Saxena. [https://annals.math.princeton.edu/wp-content/uploads/annals-v160-n2-p12.pdf PRIMES is in P] (2004). (Полиномиальный алгоритм проверки числа на простоту) | * M. Agrawal, N. Kayal & N. Saxena. [https://annals.math.princeton.edu/wp-content/uploads/annals-v160-n2-p12.pdf PRIMES is in P] (2004). (Полиномиальный алгоритм проверки числа на простоту) | ||
Строка 50: | Строка 111: | ||
* Alexander A. Razborov & Steven Rudich. [https://reader.elsevier.com/reader/sd/pii/S002200009791494X?token=FA3F4242B7E505CE6CB80008B59A32F704FAF5C15051D9694B44548A3AFFF4F47B4E03BAFC6B8357EC27E4FCE360652C Natural Proofs] | * Alexander A. Razborov & Steven Rudich. [https://reader.elsevier.com/reader/sd/pii/S002200009791494X?token=FA3F4242B7E505CE6CB80008B59A32F704FAF5C15051D9694B44548A3AFFF4F47B4E03BAFC6B8357EC27E4FCE360652C Natural Proofs] | ||
− | * | + | * U. Feige & Sh. Jozpeh. [https://sci-hub.ru/https://doi.org/10.1145/2688073.2688101 Separation between estimation and approximation] (Классика приближённых алгоритмов: разделение по сложности задач нахождения оценки и нахождения приближённого решения) |
+ | |||
+ | * M. Goldmann, J. Hastad & A. Razborov. [https://sci-hub.ru/https://doi.org/10.1007/BF01200426 Majority gates vs. general weighted threshold gates] (Фундаментальная, но простая для понимания статья по булевым схемам) | ||
+ | |||
+ | * J. Hastad. [https://sci-hub.ru/https://doi.org/10.1137/S0895480192235878 On the Size of Weights for Threshold Gates] (Результат, схожий с предыдущим, только с доказательством конкретной оценки) | ||
+ | |||
+ | * R. Moser & G. Tardos. [https://arxiv.org/pdf/0903.0544.pdf A constructive proof of the general Lovasz Local Lemma] (Фундаментальная вещь из вероятностных алгоритмов (которую, кстати, планировал рассказывать Дмитрий Александрович на курсе ТВиМС)) | ||
− | * | + | * C. Gotsman & N. Linial. [https://www.sciencedirect.com/science/article/pii/0097316592900608 The equivalence of two problems on the cube] (Один из кусков так называемой "гипотезы о чувствительности", её связь с максимальной степенью подграфа булева куба) |
==Литература== | ==Литература== | ||
# Dexter C. Kozen. Theory of Computation. (Замечательная книга по теории сложности вычислений, малоизвестная, по непонятным причинам, в нашей стране. Изложение структурировано в виде "лекций", часть из которых "обычные", а часть "продвинутые") | # Dexter C. Kozen. Theory of Computation. (Замечательная книга по теории сложности вычислений, малоизвестная, по непонятным причинам, в нашей стране. Изложение структурировано в виде "лекций", часть из которых "обычные", а часть "продвинутые") | ||
# Michael Sipser. Introduction to the Theory of Computation (Очень хороший вводный учебник) | # Michael Sipser. Introduction to the Theory of Computation (Очень хороший вводный учебник) | ||
− | # | + | # Михаил Вялый. [https://www.dropbox.com/s/4qqlhubkf6uq7si/approx-lec.pdf?dl=0 Черновик учебника по приближённым алгоритмам]. |
+ | # Ryan O’Donnell. Analysis of boolean functions. (Невероятно качественная книга про булев анализ) |
Текущая версия на 19:36, 25 июня 2022
Факультатив представляет собой введение в, пожалуй, центральную подобласть теоретической информатики, а именно в теорию вычислений. Данную науку можно противопоставить всем известной теории алгоритмов. Цель алгоритмического подхода -- придумать максимально быстрое решение для отдельно взятой задачи. Теория вычислений же исследует общие подходы к построению эффективного решения или, что не менее важно, доказывает его отсутствие. Для данной постановки задачи были введены так называемые сложностные классы, в том числе всем известные P и NP, задача взаимосвязи которых объявлена одной из семи Millennium Prize Problems.
Каждую неделю будет проходить одна лекция. Также в случайные моменты семестра будут выдаваться задачи для самостоятельного решения.
Содержание
Общая информация
Официальное название: «Теория вычислений».
Преподаватель: Павел Захаров, телеграм: @DuckBinLaden, Анна Енгоян, телеграм: @yaognennaya
Время и место (с 31 января): понедельник, 16:20, корпус на Покровском бульваре, аудитория R406.
Телеграм-чат: ссылка.
Таблица с результатами: ссылка.
Примерная программа
Из обязательных тем предполагаются первые 3 ± 1, после чего планируется сделать гибкую программу, учитывающую пожелания слушающих.
- Временная сложность, классы P и NP [пройдено].
- NP-трудные и NP-полные задачи, NP-полнота некоторых задач [пройдено].
- Space complexity, PSPACE-полные задачи [пройдено].
- Сложность вычислений с помощью схем из функциональных элементов, класс P/poly.
- Сложностные характеристики булевых функций [пройдено].
- Разрешающие деревья. Гипотеза Аандераа—Карпа—Розенберга [пройдено].
- Коммуникационная сложность.
- Булев анализ. Теорема Эрроу [пройдено].
- Спектральный экспандер. Зиг-заг произведение. Детерменированный алгоритм для задачи UPATH.
- Линейное программирование. Метод исключения переменных. Метод эллипсоидов. Симплекс-метод [частично пройдено].
- Аппроксимационные алгоритмы. ЛП релаксация для задачи MIN-VC. ЛП релаксация для задачи MAX-CUT [пройдено].
- Вероятностная сложность, класс BPP (и другие), вероятностные алгоритмы проверки числа на простоту и проверки полиномов на равенство.
- Апериодические замощения. Плитки Вана [пройдено].
История
31 января 2022. Занятие 1. Машина Тьюринга. Классы P и NP. Конспект
7 февраля 2022. Занятие 2. Классы NP-hard и NP-complete. Теорема Кука-Левина. Конспект
14 февраля 2022. Занятие 3. Space complexity, space hierarchy theorem. Конспект
21 февраля 2022. Занятие 4. Линейное программирование. Приближённые алгоритмы, MAX-IND, TSP. Конспект
28 февраля 2022. Занятие 5. ЛП релаксации, MIN-VC, MAX-SAT. Конспект
7 марта 2022. Занятие 6. Разложение булевой функции в ряд Фурье: существование и единственность. Конспект
14 марта 2022. Занятие 7. Функции голосования. Теорема Эрроу. Конспект
14 марта 2022. Занятие 8. Сертификатная сложность, чувствительность, блочная чувствительность. Гипотеза Карпа. Тернарные функции. Конспект
28 марта 2022. Занятие 8½. Случайные графы. Пороговая вероятность. Метод интерполяции.
4 апреля 2022. Занятие 9. Информационная энтропия. Конспект
11 апреля 2022. Занятие 10. Неравенство Ширера. Теорема Кана о независимых множествах. Конспект
18 апреля 2022. Занятие 11. Апериодические замощения. Плитки Вана. [ Конспект]
25 апреля 2022. Занятие 12. Регулярные выражения. Конечные автоматы [ Конспект]
23 мая 2022. Занятие 13. Криптография на решётках. LLL-алгоритм Конспект
30 мая 2022. Занятие 14. Задача MCSP. Её NP-полнота [ Конспект]
Правила оценивания
Оценка складывается из двух пунктов:
- Задачи. Решать и сдавать задачи из нижеприведённого списка. Сдачу планируется проводить только лишь устную. Сдавать можно любому из (двоих) преподавателей. Время и место выбирается по договорённости.
- Экзамен. Экзамен будет в формате мини-конференции. Каждый студент выбирает статью из нижеприведённого списка и делает по ней доклад (минут на ДЛИНА_ПАРЫ / ЧИСЛО_СДАЮЩИХ).
Итоговая оценка формируется как Oитоговая = 0,7 * Oзадачки + 0,3 * Оэкз.
Наборы задач
- Вычислимость, дедлайн 5 апреля.
- Приближённые алгоритмы, дедлайн 10 апреля.
- Булев анализ, дедлайн 10 апреля.
- Сложностные характеристики булевых функций, дедлайн 22 апреля.
- Энтропия, дедлайн 22 апреля.
Интересные статьи
Пока что заранее заготовленные примеры, список будет пополняться (учитывая предпочтения слушающих).
- J. Hartmanis & R. E. Stearns. On the complexity of algorithms (1965). (Статья, с которой началась теория сложности вычислений).
- Stephen A. Cook. The complexity of theorem-proving procedures (1971). (Определение полноты (осторожно: не совсем такое, как у нас) и теорема Кука-Левина).
- Л. А. Левин. Универсальные задачи перебора (1973). (Внушительный список комбинаторных задач с доказательствами их NP-полноты)
- M. Agrawal, N. Kayal & N. Saxena. PRIMES is in P (2004). (Полиномиальный алгоритм проверки числа на простоту)
- Alexander A. Razborov & Steven Rudich. Natural Proofs
- U. Feige & Sh. Jozpeh. Separation between estimation and approximation (Классика приближённых алгоритмов: разделение по сложности задач нахождения оценки и нахождения приближённого решения)
- M. Goldmann, J. Hastad & A. Razborov. Majority gates vs. general weighted threshold gates (Фундаментальная, но простая для понимания статья по булевым схемам)
- J. Hastad. On the Size of Weights for Threshold Gates (Результат, схожий с предыдущим, только с доказательством конкретной оценки)
- R. Moser & G. Tardos. A constructive proof of the general Lovasz Local Lemma (Фундаментальная вещь из вероятностных алгоритмов (которую, кстати, планировал рассказывать Дмитрий Александрович на курсе ТВиМС))
- C. Gotsman & N. Linial. The equivalence of two problems on the cube (Один из кусков так называемой "гипотезы о чувствительности", её связь с максимальной степенью подграфа булева куба)
Литература
- Dexter C. Kozen. Theory of Computation. (Замечательная книга по теории сложности вычислений, малоизвестная, по непонятным причинам, в нашей стране. Изложение структурировано в виде "лекций", часть из которых "обычные", а часть "продвинутые")
- Michael Sipser. Introduction to the Theory of Computation (Очень хороший вводный учебник)
- Михаил Вялый. Черновик учебника по приближённым алгоритмам.
- Ryan O’Donnell. Analysis of boolean functions. (Невероятно качественная книга про булев анализ)