Теория вычислений 2022 — различия между версиями
м (→История) |
м (→История) |
||
Строка 68: | Строка 68: | ||
<br> | <br> | ||
'''18 апреля 2022. Занятие 11.''' Апериодические замощения. Плитки Вана. [ Конспект] | '''18 апреля 2022. Занятие 11.''' Апериодические замощения. Плитки Вана. [ Конспект] | ||
+ | <br> | ||
+ | <br> | ||
+ | '''25 апреля 2022. Занятие 12.''' Регулярные выражения. Конечные автоматы [ Конспект] | ||
<br> | <br> | ||
<br> | <br> |
Версия 16:52, 12 мая 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. Регулярные выражения. Конечные автоматы [ Конспект]
Правила оценивания
Оценка складывается из двух пунктов:
- Задачи. Решать и сдавать задачи из нижеприведённого списка. Сдачу планируется проводить только лишь устную. Сдавать можно любому из (двоих) преподавателей. Время и место выбирается по договорённости.
- Экзамен. Экзамен будет в формате мини-конференции. Каждый студент выбирает статью из нижеприведённого списка и делает по ней доклад (минут на ДЛИНА_ПАРЫ / ЧИСЛО_СДАЮЩИХ).
Итоговая оценка формируется как 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). (Определение полноты (осторожно: не совсем такое, как у нас) и теорема Кука-Левина).
- 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 (Очень хороший вводный учебник)
- Михаил Вялый. Черновик учебника по приближённым алгоритмам.
- Ryan O’Donnell. Analysis of boolean functions. (Невероятно качественная книга про булев анализ)