Теория вычислений 2022
Факультатив представляет собой введение в, пожалуй, центральную подобласть теоретической информатики, а именно в теорию вычислений. Данную науку можно противопоставить всем известной теории алгоритмов. Цель алгоритмического подхода -- придумать максимально быстрое решение для отдельно взятой задачи. Теория вычислений же исследует общие подходы к построению эффективного решения или, что не менее важно, доказывает его отсутствие. Для данной постановки задачи были введены так называемые сложностные классы, в том числе всем известные P и NP, задача взаимосвязи которых объявлена одной из семи Millennium Prize Problems.
Каждую неделю будет проходить одна лекция. Также в случайные моменты семестра будут выдаваться задачи для самостоятельного решения.
Содержание
Общая информация
Официальное название: «Теория вычислений».
Преподаватель: Павел Захаров, телеграм: @DuckBinLaden, Анна Енгоян, телеграм: @yaognennaya
Время и место (с 31 января): понедельник, 16:20, корпус на Покровском бульваре, аудитория TBA.
Записи занятий: А надо ли?
Телеграм-чат: TBA
Таблица с оценками: TBA
Примерная программа
Из обязательных тем предполагаются первые 3 ± 1, после чего планируется сделать гибкую программу, учитывающую пожелания слушающих.
Временная сложность, классы P и NP. NP-трудные и NP-полные задачи, NP-полнота некоторых задач. Сложность вычислений с помощью схем из функциональных элементов, класс P/poly. Разрешающие деревья. Гипотеза Аандераа—Карпа—Розенберга. Коммуникационная сложность. Булев анализ. Теорема Эрроу. Спектральный экспандер. Зиг-заг произведение. Детерменированный алгоритм для задачи UPATH. Линейное программирование. Метод исключения переменных. Метод эллипсоидов. Симплекс-метод. Аппроксимационные алгоритмы. ЛП релаксация для задачи MIN-VC. ЛП релаксация для задачи MAX-CUT. Вероятностная сложность, класс BPP (и другие), вероятностные алгоритмы проверки числа на простоту и проверки полиномов на равенство. Апериодические замощения. Плитки Вана.
История
31 января 2021. Занятие 1. TBA
Правила оценивания
Оценка складывается из двух пунктов:
- Задачи. Решать и сдавать задачи из нижеприведённого списка. Сдачу планируется проводить только лишь устную. Сдавать можно любому из (двоих) преподавателей. Время и место выбирается по договорённости.
- Экзамен. Экзамен будет в формате мини-конференции. Каждый студент выбирает статью из нижеприведённого списка и делает по ней доклад (минут на ДЛИНА_ПАРЫ / ЧИСЛО_СДАЮЩИХ).
Итоговая оценка формируется как Oитоговая = 0,7 * Oзадачки + 0,3 * Оэкз.
Наборы задач
- TBA
Интересные статьи
Пока что заранее заготовленные примеры, список будет пополняться (учитывая предпочтения слушающих).
- 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-полноты).
- Л. А. Левин. Универсальные задачи перебора (1973). (Примерно про то же in Soviet Russia)
- M. Agrawal, N. Kayal & N. Saxena. PRIMES is in P (2004). (Полиномиальный алгоритм проверки числа на простоту)
- Alexander A. Razborov & Steven Rudich. Natural Proofs
- S. Goldwasser & M. Sipser. Private Coins versus Public Coins in Interactive Proof Systems (Открытые случайные биты (почти) не хуже, чем закрытые)
- O. Goldreich et al. On Completeness and Soundness in Interactive Proof Systems (Распознавание x \in L с вероятностью 1 для систем интерактивных доказательств)
Литература
- Dexter C. Kozen. Theory of Computation. (Замечательная книга по теории сложности вычислений, малоизвестная, по непонятным причинам, в нашей стране. Изложение структурировано в виде "лекций", часть из которых "обычные", а часть "продвинутые")
- Michael Sipser. Introduction to the Theory of Computation (Очень хороший вводный учебник)
- Sanjeev Arora & Boaz Barak. Computational Complexity: A Modern Approach. (Большая книга, которая входит во все списки литературы по теории сложности вычислений)