Теория вычислений 2022 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
м
м
 
(не показано 46 промежуточных версии этого же участника)
Строка 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, корпус на Покровском бульваре, аудитория TBA.
+
'''Время и место (с 31 января):''' понедельник, 16:20, корпус на Покровском бульваре, аудитория R406.
  
−
'''Записи занятий:''' А надо ли?
+
'''Телеграм-чат:''' [https://t.me/+lnowoF11XNMyYmJi ссылка].
  
−
'''Телеграм-чат:''' TBA
+
'''Таблица с результатами:''' [https://docs.google.com/spreadsheets/d/1Opr-0V_HzaCrMbLVssBwdhlCXi9TDm4QlugU6CVF4pA/edit?usp=sharing ссылка].
  
−
'''Таблица с оценками:''' TBA
+
==Примерная программа==
 +
 
 +
Из обязательных тем предполагаются первые 3 ± 1, после чего планируется сделать гибкую программу, учитывающую пожелания слушающих.
 +
 
 +
* Временная сложность, классы P и NP ['''пройдено'''].
 +
* NP-трудные и NP-полные задачи, NP-полнота некоторых задач ['''пройдено'''].
 +
* Space complexity, PSPACE-полные задачи ['''пройдено'''].
 +
* Сложность вычислений с помощью схем из функциональных элементов, класс P/poly.
 +
* Сложностные характеристики булевых функций ['''пройдено'''].
 +
* Разрешающие деревья. Гипотеза Аандераа—Карпа—Розенберга ['''пройдено'''].
 +
* Коммуникационная сложность.
 +
* Булев анализ. Теорема Эрроу ['''пройдено'''].
 +
* Спектральный экспандер. Зиг-заг произведение. Детерменированный алгоритм для задачи UPATH.
 +
* Линейное программирование. Метод исключения переменных. Метод эллипсоидов. Симплекс-метод ['''частично пройдено'''].
 +
* Аппроксимационные алгоритмы. ЛП релаксация для задачи MIN-VC. ЛП релаксация для задачи MAX-CUT ['''пройдено'''].
 +
* Вероятностная сложность, класс BPP (и другие), вероятностные алгоритмы проверки числа на простоту и проверки полиномов на равенство.
 +
* Апериодические замощения. Плитки Вана ['''пройдено'''].
  
 
==История==
 
==История==
−
'''31 января 2021. Занятие 1.''' TBA
+
'''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>
Строка 33: Строка 91:
 
====Наборы задач====
 
====Наборы задач====
  
−
* TBA
+
* [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 апреля.
  
 
==Интересные статьи==
 
==Интересные статьи==
Строка 43: Строка 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). (Определение полноты (осторожно: не совсем такое, как у нас)  и теорема Кука-Левина).
  
−
* Richard M. Karp. [https://people.eecs.berkeley.edu/~luca/cs172/karp.pdf Reducibility among combinatorial problems] (1972). (Внушительный список комбинаторных задач с доказательствами их NP-полноты).
+
* Л. А. Левин. [http://www.mathnet.ru/links/efc20ed39c74803d8ecb1011962ba4b3/ppi914.pdf Универсальные задачи перебора] (1973). (Внушительный список комбинаторных задач с доказательствами их NP-полноты)
−
 
+
−
* Л. А. Левин. [http://www.mathnet.ru/links/efc20ed39c74803d8ecb1011962ba4b3/ppi914.pdf Универсальные задачи перебора] (1973). (Примерно про то же in Soviet Russia)
+
  
 
* 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). (Полиномиальный алгоритм проверки числа на простоту)
Строка 51: Строка 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]
  
−
* S. Goldwasser & M. Sipser. [https://dl.acm.org/doi/abs/10.1145/12130.12137 Private Coins versus Public Coins in Interactive Proof Systems] (Открытые случайные биты (почти) не хуже, чем закрытые)
+
* 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] (Фундаментальная вещь из вероятностных алгоритмов (которую, кстати, планировал рассказывать Дмитрий Александрович на курсе ТВиМС))
  
−
* O. Goldreich et al. [http://www.wisdom.weizmann.ac.il/~oded/PSX/fgmsz.pdf On Completeness and Soundness in Interactive Proof Systems] (Распознавание x \in L с вероятностью 1 для систем интерактивных доказательств)
+
* 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 (Очень хороший вводный учебник)
−
# Sanjeev Arora & Boaz Barak. Computational Complexity: A Modern Approach. (Большая книга, которая входит во все списки литературы по теории сложности вычислений)
+
# Михаил Вялый. [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 * Оэкз.

Наборы задач

Интересные статьи

Пока что заранее заготовленные примеры, список будет пополняться (учитывая предпочтения слушающих).

  • J. Hartmanis & R. E. Stearns. On the complexity of algorithms (1965). (Статья, с которой началась теория сложности вычислений).
  • Stephen A. Cook. The complexity of theorem-proving procedures (1971). (Определение полноты (осторожно: не совсем такое, как у нас) и теорема Кука-Левина).
  • M. Agrawal, N. Kayal & N. Saxena. PRIMES is in P (2004). (Полиномиальный алгоритм проверки числа на простоту)
  • U. Feige & Sh. Jozpeh. Separation between estimation and approximation (Классика приближённых алгоритмов: разделение по сложности задач нахождения оценки и нахождения приближённого решения)
  • 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 (Один из кусков так называемой "гипотезы о чувствительности", её связь с максимальной степенью подграфа булева куба)

Литература

  1. Dexter C. Kozen. Theory of Computation. (Замечательная книга по теории сложности вычислений, малоизвестная, по непонятным причинам, в нашей стране. Изложение структурировано в виде "лекций", часть из которых "обычные", а часть "продвинутые")
  2. Michael Sipser. Introduction to the Theory of Computation (Очень хороший вводный учебник)
  3. Михаил Вялый. Черновик учебника по приближённым алгоритмам.
  4. Ryan O’Donnell. Analysis of boolean functions. (Невероятно качественная книга про булев анализ)
Источник — «http://wiki.cs.hse.ru/index.php?title=Теория_вычислений_2022&oldid=70884»