Просмотр кода страницы Complexity theory 2026

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

Также курс затронет другие подходы к оценке сложности той или иной задачи, например деревья решений. Также планируется рассказать некоторый обзор результатов из разных предметов, которые будут затрагиваться на специализации "теоретическая информатика": приближенные алгоритмы, экспандеры, конечно, сложность. Этот курс может быть неплохим введением, если вы задумываетесь о поступлении на таковую специалзацию ПМИ.


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


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

'''Преподаватель:''' [https://www.hse.ru/org/persons/510416882 Артём Парфенов], телеграм: [https://t.me/dunno_0 @dunno_0]

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

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

'''Таблица с результатами:''' [ ссылка появится].


==История==
'''12 февраля 2026. Занятие 1.''' Введние. Конечный автомат.. [ Конспект]
<br>
<br>

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

* '''Задачи.''' Решать и сдавать задачи из нижеприведённого списка. Формат сдачи и дедлайны будут оговорены в листке.

* '''Экзамен.''' Экзамен будет в формате мини-конференции. Каждый студент выбирает статью из нижеприведённого списка и делает по ней доклад.

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

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


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

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

* 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] (Один из кусков так называемой "гипотезы о чувствительности", её связь с максимальной степенью подграфа булева куба)

==Литература==
# S. Arora and B. Barak, Computational Complexity: A Modern Approach, 2009 (Более полный учебник конкретно по теории сложности)
# 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. (Невероятно качественная книга про булев анализ)