imported>Pein rules: /* История */

2023-04-03T08:26:27Z

История

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

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

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

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

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

'''Время и место (с 23 января):''' понедельник, 18:10, корпус на Покровском бульваре, аудитория R207. ВРЕМЯ И МЕСТО ПРОВЕДЕНИЯ БУДЕТ УТОЧНЯТЬСЯ НА ПЕРВОМ ЗАНЯТИИ

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

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

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

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

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

==История==
'''23 января 2023. Занятие 1.''' Машина Тьюринга. Классы P и NP. [https://drive.google.com/file/d/1XHzZEZ268RATHsPTaqHBMca0S4FF1xpR/view?usp=sharing Конспект]
 
 
'''30 января 2023. Занятие 2.''' Классы NP-hard и NP-complete. Теорема Кука-Левина. [https://drive.google.com/file/d/1YSqiVL9FKDxEG3sxNO-hG74sNg3zJUdJ/view?usp=sharing Конспект]
 
 
'''6 февраля 2023. Занятие 3.''' Space complexity, space hierarchy theorem. [https://drive.google.com/file/d/1ZcU19VpiXnk1RiXfxQhG_zBhatmEam7Q/view?usp=sharing Конспект]
 
 
'''13 февраля 2023. Занятие 4.''' Линейное программирование. Приближённые алгоритмы, MAX-IND, TSP. [https://drive.google.com/file/d/1_Ihx-ddhkleRK9CHKeJ7YpqqtpiL-7P7/view?usp=sharing Конспект]
 
 
'''20 февраля 2023. Занятие 5.''' ЛП релаксации, MIN-VC, MAX-SAT. [https://drive.google.com/file/d/1agITnxTqtpLwBSWsUD1zIqHgq6B4Pike/view?usp=sharing Конспект]
 
 
'''27 февраля 2023. Занятие 6.''' Разложение булевой функции в ряд Фурье: существование и единственность. [https://drive.google.com/file/d/1bfcBqbU4NW1n68-75ue-uZ5kMBsCX-P8/view?usp=sharing Конспект]
 
 
'''6 марта 2023. Занятие 7.''' Функции голосования. Теорема Эрроу. [https://drive.google.com/file/d/1cM7anTWm6qqe202kP-pZtQ1dcjS4G03l/view?usp=sharing Конспект]
 
 
'''13 марта 2023. Занятие 8.''' Сертификатная сложность, чувствительность, блочная чувствительность. Гипотеза Карпа. Тернарные функции. [https://drive.google.com/file/d/1XDn-7b0whjBKtCUGoY3ePoUEPjT8jOGG/view?usp=share_link Конспект]
 
 
'''20 марта 2023. Занятие 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 Конспект]
 
 

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

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

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

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

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

* [https://drive.google.com/file/d/1ZQLXGrRu8R-WTC8PtM2NjLSPLIJOK5-B/view?usp=share_link Вычислимость], дедлайн 11 марта.
* [https://drive.google.com/file/d/1uqnpUOsFUPoq_niMzskbgpJUh0KWQ_Xs/view?usp=share_link Приближённые алгоритмы], дедлайн 25 марта.
* [https://drive.google.com/file/d/1YFEF2426xI4vQpH2Apjd6r9qpDOWyk3y/view?usp=share_link Булев анализ], дедлайн 8 апреля.
* [https://drive.google.com/file/d/1WTtLDQWFwUcpTQ5UTIjOH252cyw1loDf/view?usp=share_link Сложностные характеристики булевых функций], дедлайн 22 апреля.
* [https://drive.google.com/file/d/1zc3-RdVyCVrwSG2gmkzWCAWcW4cVVRRa/view?usp=share_link Информационная энтропия], дедлайн 6 мая.

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

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

* 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. (Невероятно качественная книга про булев анализ)

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

imported>Pein rules: /* История */