Факультатив "Теория вычислений" (Весна 2021)

Материал из Wiki - Факультет компьютерных наук
Версия от 14:25, 4 сентября 2021; Antongnatenko (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Факультатив представляет собой введение в науку о сложности вычислений – красивую и богатую глубокими результатами область математики. Если теория алгоритмов пытается ответить на вопрос "что можно и чего нельзя вычислить на компьютере?", то теория сложности уточняет "что можно вычислить быстро?", "что принципиально невозможно вычислить быстро?", "что делает трудные задачи трудными?", "можно ли использовать случайность, чтобы ускорить вычисления?". Чтобы (попытаться) ответить на эти вопросы, мы разобьём задачи на классы сложности и будем сравнивать разные классы между собой. Некоторые из наших теорем будут чисто теоретическими (зато очень красивыми!), а некоторые будут иметь прямые приложения в алгоритмической практике, на которые мы постараемся явно указывать.

Каждую неделю будет проходить «занятие» (одна пара) – смесь лекции и семинара в меняющейся пропорции. Будут задачи для самостоятельного решения, расширяющие и дополняющие материал занятий.

Для успешного прохождения курса достаточно иметь общее представление об алгоритмах, алгоритмических задачах и математических доказательствах. В примерах и задачах мы будем использовать стандартные вещи: булевы функции, графы, простые числа и так далее, однако никаких специальных предварительных знаний не предполагается.

Общая информация

Официальное название: «Теория вычислений». (Никакой "и логики" в названии нет, хотя в программе она может появиться (см. курсив в программе курса)).

Преподаватель: Антон Гнатенко, почта: agnatenko@hse.ru, телеграм: @antongnatenko. Всюду на этой странице местоимение «я» обозначает именно этого человека.

Время и место (с 1 февраля): понедельник, 16:20, онлайн (по крайней мере, до возвращения оффлайн занятий, но, возможно, и после). Zoom: чтобы узнать ссылку, добавляйтесь в чат.

Записи занятий: https://www.youtube.com/playlist?list=PLbjUsKUoAqLMSKdVtO89OhR3J1alX4Q83

Доски: https://drive.google.com/drive/folders/1Qw4L9QccTVEpyG3Md_4ji1coDovKiMMy?usp=sharing

Телеграм-чат: https://t.me/joinchat/FehKYBXfk1Mu7npLZ3Tt_w

Ссылка на эту страницу: https://tinyurl.com/logicomp

Форма для задач: https://forms.gle/fvZhCKN4BmRTRRB76

Таблица с оценками: https://docs.google.com/spreadsheets/d/17KphnPJQ0AeRDcMryRnregEAJ2ZiupJN4OtK8XncAmA/edit?usp=sharing

История

1 февраля 2021. Занятие 1. Машины Тьюринга и класс P.

Видеозапись: https://youtu.be/_9OeqVJ0Lpw

5 февраля 2021. Появились тренировочные задачи по машинам Тьюринга. См. раздел "Задачи".

8 февраля 2021. Занятие 2. Недетерминированные машины и класс NP.

Видеозапись: https://youtu.be/HlYOfCfgQEM

15 февраля 2021. Занятие 3. Полиномиальная сводимость и NP-полнота. Теорема Кука-Левина.

Видеозапись: https://youtu.be/XokMRfTbKkQ

Появилась первая порция задач. Мягкий дедлайн - 28 марта. Вероятно, у второй порции задач дедлайн будет тот же. У бонусных задач дедлайна нет. См. раздел "Задачи".

22 февраля 2021. Занятие 4. NP-полнота задач о клике, о раскраске в 3 цвета, о гамильтоновом цикле.

Видеозапись: https://youtu.be/ffv1WXM4EJ4

Первая порция задач пополнилась. Добавилось ещё немного задач на доказательство NP-полноты. Мягкий дедлайн тот же - 28 марта. См. раздел "Задачи".

1 марта 2021. Занятие 5. Полиномиальная иерархия. Иерархия по времени.

Видеозапись: https://youtu.be/FcTpfNlO4b8

15 марта 2021. Занятие 6. Вероятностные алгоритмы. Задача Polynomial Identity Testing. Виды вероятностных алгоритмов и уменьшение вероятности ошибки. Определения (неформальные) классов RP, coRP, BPP и (совсем неформально) ZPP.

Видеозапись: https://youtu.be/YCXpXFN6Ryk

22 марта 2021. Занятие 7. Классы RP, coRP, BPP, ZPP. Теорема о равенстве ZPP и RP \cap coRP. Теорема о том, что BPP \subset P/poly (не слишком формально).

Видеозапись: https://youtu.be/UVrlzOCTiTI

26 марта 2021. Появилась вторая порция задач. Мягкий дедлайн - 30 апреля. У бонусных задач дедлайна нет. См. раздел "Задачи".

5 апреля 2021. Занятие 8. Интерактивные доказательства и протоколы Артура-Мерлина. Классы IP и AM. NP \subset IP. Протокол Артура-Мерлина для задачи не-изоморфизма графов.

Видеозапись: https://youtu.be/9k4iaxSyErU

12 апреля 2021. Занятие 9. MA \subset AM. Задача изоморфизма графов вряд ли NP-полная. IP \subset EXP.

Видеозапись: https://youtu.be/6hsOYTY7fcQ

Появилась третья порция задач. Мягкий дедлайн - 16 мая. См. раздел "Задачи".

19 апреля 2021. Занятие 10. Вероятностно проверяемые доказательства. Приближённые алгоритмы. PCP-теорема и трудность аппроксимации. Идея доказательства NP \subset PCP(poly, 1).

Видеозапись: https://youtu.be/I1WYYJKoluY

3 мая 2021. Появилась бонусная порция задач о сложности по памяти. См. раздел "Задачи".

24 мая 2021. Занятие 12. Коммуникационная сложность. Метод прямоугольников и метод ранга.

Видеозапись: https://youtu.be/eYLibOyBVsE

Появилась четвёртая порция задач. Дедлайн - конец курса. См. раздел "Задачи".

31 мая 2021. Занятие 13. Коммуникационная сложность. Покрытия и недетерминизм.

Видеозапись: https://youtu.be/5RfQGRykPyA

24 июня 2021. Разбор некоторых задач.

Видеозапись: https://youtu.be/n_SOjIzfxyw

Программа курса (примерная)

Темы, написанные прямым шрифтом – обязательные, это классика теории сложности вычислений. Темы, написанные курсивом, – дополнительные. Мы рассмотрим некоторые из них, если будет на то желание слушателей. Если курсивные темы станут реальностью, они могут вытеснить обычные темы и занять их место.

  • [пройдено] Временная сложность, классы P и NP.
  • [пройдено] NP-трудные и NP-полные задачи, NP-полнота задачи о выполнимости КНФ, о клике, о раскраске графа в 3 цвета, о существовании гамильтонова пути и других.
  • Решение NP-полных задач на практике (общий обзор).
  • [пройдено] Класс coNP. Полиномиальная иерархия. Теорема о коллапсе полиномиальной иерархии.
  • [пройдено в виде задач] Пространственная сложность, класс PSPACE, PSPACE-полные задачи и попытки решать их на практике (общий обзор).
  • Сложность вычислений с помощью схем из функциональных элементов, класс P/poly.
  • Коммуникационная сложность.
  • [пройдено] Вероятностная сложность, класс BPP (и другие), вероятностные алгоритмы проверки числа на простоту и проверки полиномов на равенство.
  • [пройдено] Интерактивные доказательства и вероятностно проверяемые доказательства.
  • Разрешимость и сложность некоторых логических теорий, автоматы над бесконечными словами.
  • Вычисления с оракулом. Арифметическая иерархия и аналитическая иерархия.
  • ... (это многоточие написано курсивом)

Правила оценивания

Чтобы получить оценку, нужно набирать баллы (обычные и бонусные). Вот как это сделать:

  • Решать задачи, которые предлагаются на занятиях и появляются на этой страничке в разделе «Задачи». Для каждой задачи указано количество баллов, которые можно получить за правильное решение. У каждой задачи есть мягкий дедлайн — после него правильные решения получат половину баллов. Задачи можно сдавать устно или письменно. В случае письменной сдачи может потребоваться дополнительное обсуждение некоторых неслучайно выбранных задач. Во время обсуждения нужно продемонстрировать понимание сданного решения. Зато можно исправить ошибки, если они там есть.
  • Решать бонусные задачи, которые появляются там же. За бонусные задачи даются бонусные баллы (см. ниже).
  • Участвовать в занятиях. Иногда можно получить немного бонусных баллов за высказанную идею решения задачи, идею доказательства, ответ на вопрос.

Пусть теперь M = «максимально возможное количество обычных баллов», а S = «сумма всех баллов (обычных и бонусных), набранных студентом за семестр». Тогда оценка за курс вычисляется по формуле P = min{S / M * 10, 10}.

Таким образом, можно получить 10 баллов, просто решая обычные задачи. Но это проще сделать, если набирать бонусные баллы.

Задачи

Письменные решения нужно сдавать вот этой гугл-форме. Пожалуйста, оформляйте решения аккуратно. Для оцифровки записей лучше всего использовать не фото, а специальные приложения-сканеры. Например, Camscanner. Если вы сдаёте несколько задач сразу, объединяйте их в один пдф или в один архив.

Для сдачи файлов в форму нужен гугл-аккаунт. Если его нет и по каким-то причинам вы совсем не хотите его заводить, можно сдавать задачи устно или договориться о каком-либо ещё варианте. Но лучше всё-таки завести аккаунт.

Правила оформления решений. При изложении решений рекомендуется соблюдать разумный баланс между строгостью и размахиванием руками. Если требуется доказать, например, принадлежность некоторого языка классу NP, то достаточно предоставить словесное описание соответствующей машины (если только в условии явно не просят построить машину). Описание должно быть, тем не менее, чётким и подробным (но без фанатизма). Если какие-то важные детали из этого описания будут неясны, я попрошу сделать пояснения (возможно, устные).

Можно сдавать задачи устно. Для этого нужно связаться со мной в зуме, включить демонстрацию экрана (либо ещё каким-то образом добиться того, чтобы я видел какие-то записи и понимал, о чём вы говорите) и рассказать своё решение, отвечая на возникающие вопросы. Нужно предупредить меня о желании сдавать хотя бы за день (например, написав в телеграм), и мы договоримся о времени. Можно предупреждать раньше, чем за день – это приветствуется. Можно попробовать договориться прямо в день сдачи, но успех в таком случае маловероятен.


Наборы задач

  • Бонусная порция задач: сложность по памяти. Все задачи в этой порции — бонусные. Несколько относительно простых задач позволят набрать баллов побольше. Есть и несколько трудных задач. Все определения и теоремы, нужные для понимания и решения, приводятся в листочке.

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

Некоторые статьи недоступны обычным пользователям. Но к ним можно получить доступ через библиотеку Вышки: https://library.hse.ru/e-resources (см. "Базы данных зарубежной периодики" и там "издания ACM"; у вас должны быть логин/пароль для библиотеки: https://elib.hse.ru/e-resources/ez/ezregulation.htm).

Классика

  • J. Hartmanis & R. E. Stearns. On the complexity of algorithms (1965). (Статья, с которой началась теория сложности вычислений).
  • Stephen A. Cook. The complexity of theorem-proving procedures (1971). (Определение полноты (осторожно: не совсем такое, как у нас) и теорема Кука-Левина).
  • Richard M. Karp. Reducibility among combinatorial problems (1972). (Внушительный список комбинаторных задач с доказательствами их NP-полноты).

Неоклассика

  • M. Agrawal, N. Kayal & N. Saxena. PRIMES is in P (2004). (Полиномиальный алгоритм проверки числа на простоту)

Литература

  1. Dexter C. Kozen. Theory of Computation. (Замечательная книга по теории сложности вычислений, малоизвестная, по непонятным причинам, в нашей стране. Изложение структурировано в виде "лекций", часть из которых "обычные", а часть "продвинутые")
  2. Michael Sipser. Introduction to the Theory of Computation (Очень хороший вводный учебник)
  3. Sanjeev Arora & Boaz Barak. Computational Complexity: A Modern Approach. (Большая книга, которая входит во все списки литературы по теории сложности вычислений)

Другие курсы по теории сложности вычислений

Здесь приведены ссылки на некоторые из курсов, которые пересекаются по тематике с нашим и дополняют его. Эти материалы, в том числе, помогают мне при подготовке к занятиям.

  1. Д.В. Мусатов. Лекции по сложности вычислений в МФТИ: видеолекции.
  2. Jonathan Katz. Курс в университете Мэриленда: страница курса (есть конспекты).
  3. Rafael Pass. Курс в Корнеллском университете: страница курса (есть конспекты).

Архив