Теория вычислений 2022

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск

Факультатив представляет собой введение в, пожалуй, центральную подобласть теоретической информатики, а именно в теорию вычислений. Данную науку можно противопоставить всем известной теории алгоритмов. Цель алгоритмического подхода -- придумать максимально быстрое решение для отдельно взятой задачи. Теория вычислений же исследует общие подходы к построению эффективного решения или, что не менее важно, доказывает его отсутствие. Для данной постановки задачи были введены так называемые сложностные классы, в том числе всем известные 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»