https://wikicshse.ru/index.php?action=history&feed=atom&title=Complexity_theory_2026Complexity theory 2026 - История изменений2026-06-06T11:04:22ZИстория изменений этой страницы в викиMediaWiki 1.45.3https://wikicshse.ru/index.php?title=Complexity_theory_2026&diff=136&oldid=previmported>Avparfenov: Migrated current public revision from wiki.cs.hse.ru2026-02-11T11:58:48Z<p>Migrated current public revision from wiki.cs.hse.ru</p>
<p><b>Новая страница</b></p><div>Факультатив представляет собой введение в, пожалуй, центральную подобласть теоретической информатики, а именно в теорию вычислений. Данную науку монжно противопоставить всем известной теории алгоритмов. Цель алгоритмического подхода -- придумать максимально быстрое решение для отдельно взятой задачи. Теория вычислений же исследует общие подходы к построению эффективного решения или, что не менее важно, доказывает его отсутствие. Для данной постановки задачи были введены так называемые сложностные классы, в том числе всем известные P и NP, задача взаимосвязи которых объявлена одной из семи Millennium Prize Problems. <br />
<br />
Также курс затронет другие подходы к оценке сложности той или иной задачи, например деревья решений. Также планируется рассказать некоторый обзор результатов из разных предметов, которые будут затрагиваться на специализации "теоретическая информатика": приближенные алгоритмы, экспандеры, конечно, сложность. Этот курс может быть неплохим введением, если вы задумываетесь о поступлении на таковую специалзацию ПМИ.<br />
<br />
<br />
Каждую неделю будет проходить одна лекция. Также в случайные моменты семестра будут выдаваться задачи для самостоятельного решения.<br />
<br />
<br />
==Общая информация==<br />
'''Официальное название:''' «Теория вычислений».<br />
<br />
'''Преподаватель:''' [https://www.hse.ru/org/persons/510416882 Артём Парфенов], телеграм: [https://t.me/dunno_0 @dunno_0]<br />
<br />
'''Время и место (с 12 февраля):''' четверг, 18:10, корпус на Покровском бульваре, аудитория N504. ВРЕМЯ И МЕСТО ПРОВЕДЕНИЯ БУДЕТ УТОЧНЯТЬСЯ НА ПЕРВОМ ЗАНЯТИИ<br />
<br />
'''Телеграм-чат:''' [https://t.me/+8d_60eyRFvNhNDJi ссылка].<br />
<br />
'''Таблица с результатами:''' [ ссылка появится].<br />
<br />
<br />
==История==<br />
'''12 февраля 2026. Занятие 1.''' Введние. Конечный автомат.. [ Конспект]<br />
<br><br />
<br><br />
<br />
==Правила оценивания==<br />
Оценка складывается из двух пунктов:<br />
<br />
* '''Задачи.''' Решать и сдавать задачи из нижеприведённого списка. Формат сдачи и дедлайны будут оговорены в листке.<br />
<br />
* '''Экзамен.''' Экзамен будет в формате мини-конференции. Каждый студент выбирает статью из нижеприведённого списка и делает по ней доклад.<br />
<br />
Итоговая оценка формируется как O<sub>итоговая</sub> = 0,7 * O<sub>задачки</sub> + 0,3 * О<sub>экз</sub>.<br />
<br />
====Наборы задач====<br />
<br />
<br />
==Интересные статьи==<br />
<br />
Пока что заранее заготовленные примеры, список будет пополняться (учитывая предпочтения слушающих).<br />
<br />
* J. Hartmanis & R. E. Stearns. [http://www.cs.albany.edu/~res/comp_complexity_ams_1965.pdf On the complexity of algorithms] (1965). (Статья, с которой началась теория сложности вычислений).<br />
<br />
* Stephen A. Cook. [https://dl.acm.org/doi/10.1145/800157.805047 The complexity of theorem-proving procedures] (1971). (Определение полноты (осторожно: не совсем такое, как у нас) и теорема Кука-Левина).<br />
<br />
* Л. А. Левин. [http://www.mathnet.ru/links/efc20ed39c74803d8ecb1011962ba4b3/ppi914.pdf Универсальные задачи перебора] (1973). (Внушительный список комбинаторных задач с доказательствами их NP-полноты)<br />
<br />
* M. Agrawal, N. Kayal & N. Saxena. [https://annals.math.princeton.edu/wp-content/uploads/annals-v160-n2-p12.pdf PRIMES is in P] (2004). (Полиномиальный алгоритм проверки числа на простоту)<br />
<br />
* Alexander A. Razborov & Steven Rudich. [https://reader.elsevier.com/reader/sd/pii/S002200009791494X?token=FA3F4242B7E505CE6CB80008B59A32F704FAF5C15051D9694B44548A3AFFF4F47B4E03BAFC6B8357EC27E4FCE360652C Natural Proofs]<br />
<br />
* U. Feige & Sh. Jozpeh. [https://sci-hub.ru/https://doi.org/10.1145/2688073.2688101 Separation between estimation and approximation] (Классика приближённых алгоритмов: разделение по сложности задач нахождения оценки и нахождения приближённого решения)<br />
<br />
* M. Goldmann, J. Hastad & A. Razborov. [https://sci-hub.ru/https://doi.org/10.1007/BF01200426 Majority gates vs. general weighted threshold gates] (Фундаментальная, но простая для понимания статья по булевым схемам)<br />
<br />
* J. Hastad. [https://sci-hub.ru/https://doi.org/10.1137/S0895480192235878 On the Size of Weights for Threshold Gates] (Результат, схожий с предыдущим, только с доказательством конкретной оценки)<br />
<br />
* R. Moser & G. Tardos. [https://arxiv.org/pdf/0903.0544.pdf A constructive proof of the general Lovasz Local Lemma] (Фундаментальная вещь из вероятностных алгоритмов (которую, кстати, планировал рассказывать Дмитрий Александрович на курсе ТВиМС))<br />
<br />
* C. Gotsman & N. Linial. [https://www.sciencedirect.com/science/article/pii/0097316592900608 The equivalence of two problems on the cube] (Один из кусков так называемой "гипотезы о чувствительности", её связь с максимальной степенью подграфа булева куба)<br />
<br />
==Литература==<br />
# S. Arora and B. Barak, Computational Complexity: A Modern Approach, 2009 (Более полный учебник конкретно по теории сложности)<br />
# Michael Sipser. Introduction to the Theory of Computation (Очень хороший вводный учебник)<br />
# Михаил Вялый. [https://www.dropbox.com/s/4qqlhubkf6uq7si/approx-lec.pdf?dl=0 Черновик учебника по приближённым алгоритмам].<br />
# Ryan O’Donnell. Analysis of boolean functions. (Невероятно качественная книга про булев анализ)</div>imported>Avparfenov