Теория вычислений 2022 — различия между версиями
м |
м (→История) |
||
Строка 34: | Строка 34: | ||
==История== | ==История== | ||
− | '''31 января | + | '''31 января 2022. Занятие 1.''' Машина Тьюринга. Классы P и NP. [https://drive.google.com/file/d/1XHzZEZ268RATHsPTaqHBMca0S4FF1xpR/view?usp=sharing Конспект] |
<br> | <br> | ||
<br> | <br> | ||
− | '''7 февраля | + | '''7 февраля 2022. Занятие 2.''' Классы NP-hard и NP-complete. Теорема Кука-Левина. [https://drive.google.com/file/d/1YSqiVL9FKDxEG3sxNO-hG74sNg3zJUdJ/view?usp=sharing Конспект] |
<br> | <br> | ||
<br> | <br> | ||
− | '''14 февраля | + | '''14 февраля 2022. Занятие 3.''' Space complexity, space hierarchy theorem. [https://drive.google.com/file/d/1ZcU19VpiXnk1RiXfxQhG_zBhatmEam7Q/view?usp=sharing Конспект] |
<br> | <br> | ||
<br> | <br> | ||
− | '''21 февраля | + | '''21 февраля 2022. Занятие 4.''' Линейное программирование. Приближённые алгоритмы, MAX-IND, TSP. [https://drive.google.com/file/d/1_Ihx-ddhkleRK9CHKeJ7YpqqtpiL-7P7/view?usp=sharing Конспект] |
<br> | <br> | ||
<br> | <br> | ||
− | '''28 февраля | + | '''28 февраля 2022. Занятие 5.''' ЛП релаксации, MIN-VC, MAX-SAT. [https://drive.google.com/file/d/1agITnxTqtpLwBSWsUD1zIqHgq6B4Pike/view?usp=sharing Конспект] |
<br> | <br> | ||
<br> | <br> | ||
− | '''7 марта | + | '''7 марта 2022. Занятие 6.''' Разложение булевой функции в ряд Фурье: существование и единственность. [https://drive.google.com/file/d/1bfcBqbU4NW1n68-75ue-uZ5kMBsCX-P8/view?usp=sharing Конспект] |
<br> | <br> | ||
<br> | <br> | ||
− | '''14 марта | + | '''14 марта 2022. Занятие 7.''' Функции голосования. Теорема Эрроу. [https://drive.google.com/file/d/1cM7anTWm6qqe202kP-pZtQ1dcjS4G03l/view?usp=sharing Конспект] |
<br> | <br> | ||
<br> | <br> | ||
− | '''14 марта | + | '''14 марта 2022. Занятие 8.''' Сертификатная сложность, чувствительность, блочная чувствительность. Гипотеза Карпа. Тернарные функции. [https://drive.google.com/file/d/1uHejpnPBu6KB4NtV6enRixY-Q_8g0etW/view?usp=sharing Конспект] |
<br> | <br> | ||
<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> | ||
<br> | <br> |
Версия 13:11, 11 апреля 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. Неравенство Ширера. Теорема Кана о независимых множествах. Конспект
Правила оценивания
Оценка складывается из двух пунктов:
- Задачи. Решать и сдавать задачи из нижеприведённого списка. Сдачу планируется проводить только лишь устную. Сдавать можно любому из (двоих) преподавателей. Время и место выбирается по договорённости.
- Экзамен. Экзамен будет в формате мини-конференции. Каждый студент выбирает статью из нижеприведённого списка и делает по ней доклад (минут на ДЛИНА_ПАРЫ / ЧИСЛО_СДАЮЩИХ).
Итоговая оценка формируется как 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. (Невероятно качественная книга про булев анализ)