imported>Pein rules: Migrated current public revision from wiki.cs.hse.ru

2022-06-25T16:36:53Z

Migrated current public revision from wiki.cs.hse.ru

Новая страница

Факультатив представляет собой введение в, пожалуй, центральную подобласть теоретической информатики, а именно в теорию вычислений. Данную науку можно противопоставить всем известной теории алгоритмов. Цель алгоритмического подхода -- придумать максимально быстрое решение для отдельно взятой задачи. Теория вычислений же исследует общие подходы к построению эффективного решения или, что не менее важно, доказывает его отсутствие. Для данной постановки задачи были введены так называемые сложностные классы, в том числе всем известные P и NP, задача взаимосвязи которых объявлена одной из семи Millennium Prize Problems.

Каждую неделю будет проходить одна лекция. Также в случайные моменты семестра будут выдаваться задачи для самостоятельного решения.

==Общая информация==
'''Официальное название:''' «Теория вычислений».

'''Преподаватель:''' [https://www.hse.ru/org/persons/208499388 Павел Захаров], телеграм: [https://t.me/duckbinladen @DuckBinLaden], Анна Енгоян, телеграм: [https://t.me/yaognennaya @yaognennaya]

'''Время и место (с 31 января):''' понедельник, 16:20, корпус на Покровском бульваре, аудитория R406.

'''Телеграм-чат:''' [https://t.me/+lnowoF11XNMyYmJi ссылка].

'''Таблица с результатами:''' [https://docs.google.com/spreadsheets/d/1Opr-0V_HzaCrMbLVssBwdhlCXi9TDm4QlugU6CVF4pA/edit?usp=sharing ссылка].

==Примерная программа==

Из обязательных тем предполагаются первые 3 ± 1, после чего планируется сделать гибкую программу, учитывающую пожелания слушающих.

* Временная сложность, классы P и NP ['''пройдено'''].
* NP-трудные и NP-полные задачи, NP-полнота некоторых задач ['''пройдено'''].
* Space complexity, PSPACE-полные задачи ['''пройдено'''].
* Сложность вычислений с помощью схем из функциональных элементов, класс P/poly.
* Сложностные характеристики булевых функций ['''пройдено'''].
* Разрешающие деревья. Гипотеза Аандераа—Карпа—Розенберга ['''пройдено'''].
* Коммуникационная сложность.
* Булев анализ. Теорема Эрроу ['''пройдено'''].
* Спектральный экспандер. Зиг-заг произведение. Детерменированный алгоритм для задачи UPATH.
* Линейное программирование. Метод исключения переменных. Метод эллипсоидов. Симплекс-метод ['''частично пройдено'''].
* Аппроксимационные алгоритмы. ЛП релаксация для задачи MIN-VC. ЛП релаксация для задачи MAX-CUT ['''пройдено'''].
* Вероятностная сложность, класс BPP (и другие), вероятностные алгоритмы проверки числа на простоту и проверки полиномов на равенство.
* Апериодические замощения. Плитки Вана ['''пройдено'''].

==История==
'''31 января 2022. Занятие 1.''' Машина Тьюринга. Классы P и NP. [https://drive.google.com/file/d/1XHzZEZ268RATHsPTaqHBMca0S4FF1xpR/view?usp=sharing Конспект]
 
 
'''7 февраля 2022. Занятие 2.''' Классы NP-hard и NP-complete. Теорема Кука-Левина. [https://drive.google.com/file/d/1YSqiVL9FKDxEG3sxNO-hG74sNg3zJUdJ/view?usp=sharing Конспект]
 
 
'''14 февраля 2022. Занятие 3.''' Space complexity, space hierarchy theorem. [https://drive.google.com/file/d/1ZcU19VpiXnk1RiXfxQhG_zBhatmEam7Q/view?usp=sharing Конспект]
 
 
'''21 февраля 2022. Занятие 4.''' Линейное программирование. Приближённые алгоритмы, MAX-IND, TSP. [https://drive.google.com/file/d/1_Ihx-ddhkleRK9CHKeJ7YpqqtpiL-7P7/view?usp=sharing Конспект]
 
 
'''28 февраля 2022. Занятие 5.''' ЛП релаксации, MIN-VC, MAX-SAT. [https://drive.google.com/file/d/1agITnxTqtpLwBSWsUD1zIqHgq6B4Pike/view?usp=sharing Конспект]
 
 
'''7 марта 2022. Занятие 6.''' Разложение булевой функции в ряд Фурье: существование и единственность. [https://drive.google.com/file/d/1bfcBqbU4NW1n68-75ue-uZ5kMBsCX-P8/view?usp=sharing Конспект]
 
 
'''14 марта 2022. Занятие 7.''' Функции голосования. Теорема Эрроу. [https://drive.google.com/file/d/1cM7anTWm6qqe202kP-pZtQ1dcjS4G03l/view?usp=sharing Конспект]
 
 
'''14 марта 2022. Занятие 8.''' Сертификатная сложность, чувствительность, блочная чувствительность. Гипотеза Карпа. Тернарные функции. [https://drive.google.com/file/d/15eQNzuMIMafmJPy-TrWVAczws8nCQIHi/view?usp=sharing Конспект]
 
 
'''28 марта 2022. Занятие 8½.''' Случайные графы. Пороговая вероятность. Метод интерполяции.
 
 
'''4 апреля 2022. Занятие 9.''' Информационная энтропия. [https://drive.google.com/file/d/1f-xDRSCxEToVbvKj0-xgLDQv_VBs4CNZ/view?usp=sharing Конспект]
 
 
'''11 апреля 2022. Занятие 10.''' Неравенство Ширера. Теорема Кана о независимых множествах. [https://drive.google.com/file/d/1fCtggFf1qY-YstEHQ_Ut68ErRmOIoPOZ/view?usp=sharing Конспект]
 
 
'''18 апреля 2022. Занятие 11.''' Апериодические замощения. Плитки Вана. [ Конспект]
 
 
'''25 апреля 2022. Занятие 12.''' Регулярные выражения. Конечные автоматы [ Конспект]
 
 
'''23 мая 2022. Занятие 13.''' Криптография на решётках. LLL-алгоритм [https://drive.google.com/file/d/1iB0xESfwbN2H4hr8m_ebXTBZFADHXYdF/view Конспект]
 
 
'''30 мая 2022. Занятие 14.''' Задача MCSP. Её NP-полнота [ Конспект]
 
 

==Правила оценивания==
Оценка складывается из двух пунктов:

* '''Задачи.''' Решать и сдавать задачи из нижеприведённого списка. Сдачу планируется проводить только лишь устную. Сдавать можно любому из (двоих) преподавателей. Время и место выбирается по договорённости.

* '''Экзамен.''' Экзамен будет в формате мини-конференции. Каждый студент выбирает статью из нижеприведённого списка и делает по ней доклад (минут на ДЛИНА_ПАРЫ / ЧИСЛО_СДАЮЩИХ).

Итоговая оценка формируется как Oитоговая = 0,7 * Oзадачки + 0,3 * Оэкз.

====Наборы задач====

* [https://drive.google.com/file/d/1ZopQKQKdnKj-ae7pZHUAJHiswB_duqpr/view?usp=sharing Вычислимость], дедлайн 5 апреля.
* [https://drive.google.com/file/d/1QuDQg9pBa-WAx3Jkttq68tRhuDybyCYC/view?usp=sharing Приближённые алгоритмы], дедлайн 10 апреля.
* [https://drive.google.com/file/d/1ceV9kzmdENfp6vcdfafmun5R23VMMMk2/view?usp=sharing Булев анализ], дедлайн 10 апреля.
* [https://drive.google.com/file/d/1hZoWDN9RxhMBC-DWz3WWXiFCwaU4rWxv/view?usp=sharing Сложностные характеристики булевых функций], дедлайн 22 апреля.
* [https://drive.google.com/file/d/1WB4J7onWSABbDCmCdkjc2nJbrGwFUIZm/view?usp=sharing Энтропия], дедлайн 22 апреля.

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

Пока что заранее заготовленные примеры, список будет пополняться (учитывая предпочтения слушающих).

* J. Hartmanis & R. E. Stearns. [http://www.cs.albany.edu/~res/comp_complexity_ams_1965.pdf On the complexity of algorithms] (1965). (Статья, с которой началась теория сложности вычислений).

* Stephen A. Cook. [https://dl.acm.org/doi/10.1145/800157.805047 The complexity of theorem-proving procedures] (1971). (Определение полноты (осторожно: не совсем такое, как у нас) и теорема Кука-Левина).

* Л. А. Левин. [http://www.mathnet.ru/links/efc20ed39c74803d8ecb1011962ba4b3/ppi914.pdf Универсальные задачи перебора] (1973). (Внушительный список комбинаторных задач с доказательствами их NP-полноты)

* M. Agrawal, N. Kayal & N. Saxena. [https://annals.math.princeton.edu/wp-content/uploads/annals-v160-n2-p12.pdf PRIMES is in P] (2004). (Полиномиальный алгоритм проверки числа на простоту)

* Alexander A. Razborov & Steven Rudich. [https://reader.elsevier.com/reader/sd/pii/S002200009791494X?token=FA3F4242B7E505CE6CB80008B59A32F704FAF5C15051D9694B44548A3AFFF4F47B4E03BAFC6B8357EC27E4FCE360652C Natural Proofs]

* U. Feige & Sh. Jozpeh. [https://sci-hub.ru/https://doi.org/10.1145/2688073.2688101 Separation between estimation and approximation] (Классика приближённых алгоритмов: разделение по сложности задач нахождения оценки и нахождения приближённого решения)

* M. Goldmann, J. Hastad & A. Razborov. [https://sci-hub.ru/https://doi.org/10.1007/BF01200426 Majority gates vs. general weighted threshold gates] (Фундаментальная, но простая для понимания статья по булевым схемам)

* J. Hastad. [https://sci-hub.ru/https://doi.org/10.1137/S0895480192235878 On the Size of Weights for Threshold Gates] (Результат, схожий с предыдущим, только с доказательством конкретной оценки)

* R. Moser & G. Tardos. [https://arxiv.org/pdf/0903.0544.pdf A constructive proof of the general Lovasz Local Lemma] (Фундаментальная вещь из вероятностных алгоритмов (которую, кстати, планировал рассказывать Дмитрий Александрович на курсе ТВиМС))

* C. Gotsman & N. Linial. [https://www.sciencedirect.com/science/article/pii/0097316592900608 The equivalence of two problems on the cube] (Один из кусков так называемой "гипотезы о чувствительности", её связь с максимальной степенью подграфа булева куба)

==Литература==
# Dexter C. Kozen. Theory of Computation. (Замечательная книга по теории сложности вычислений, малоизвестная, по непонятным причинам, в нашей стране. Изложение структурировано в виде "лекций", часть из которых "обычные", а часть "продвинутые")
# Michael Sipser. Introduction to the Theory of Computation (Очень хороший вводный учебник)
# Михаил Вялый. [https://www.dropbox.com/s/4qqlhubkf6uq7si/approx-lec.pdf?dl=0 Черновик учебника по приближённым алгоритмам].
# Ryan O’Donnell. Analysis of boolean functions. (Невероятно качественная книга про булев анализ)

Теория вычислений 2022 - История изменений

imported>Pein rules: Migrated current public revision from wiki.cs.hse.ru