https://wikicshse.ru/index.php?action=history&feed=atom&title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D0%B9_22Теория вычислений 22 - История изменений2026-06-08T04:40:54ZИстория изменений этой страницы в викиMediaWiki 1.45.3https://wikicshse.ru/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D0%B9_22&diff=1736&oldid=previmported>Pein rules: Migrated current public revision from wiki.cs.hse.ru2022-01-15T20:36:46Z<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 />
'''Преподаватель:''' [https://www.hse.ru/org/persons/208499388 Павел Захаров], телеграм: [https://t.me/duckbinladen @DuckBinLaden], Анна Енгоян, телеграм: [https://t.me/yaognennaya @yaognennaya]<br />
<br />
'''Время и место (с 31 января):''' понедельник, 16:20, корпус на Покровском бульваре, аудитория TBA.<br />
<br />
'''Записи занятий:''' А надо ли?<br />
<br />
'''Телеграм-чат:''' TBA<br />
<br />
Таблица с оценками: TBA<br />
<br />
==История==<br />
'''31 января 2021. Занятие 1.''' TBA<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 />
* TBA<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 />
* Richard M. Karp. [https://people.eecs.berkeley.edu/~luca/cs172/karp.pdf Reducibility among combinatorial problems] (1972). (Внушительный список комбинаторных задач с доказательствами их NP-полноты).<br />
<br />
* Л. А. Левин. [http://www.mathnet.ru/links/efc20ed39c74803d8ecb1011962ba4b3/ppi914.pdf Универсальные задачи перебора] (1973). (Примерно про то же in Soviet Russia)<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 />
* S. Goldwasser & M. Sipser. [https://dl.acm.org/doi/abs/10.1145/12130.12137 Private Coins versus Public Coins in Interactive Proof Systems] (Открытые случайные биты (почти) не хуже, чем закрытые)<br />
<br />
* O. Goldreich et al. [http://www.wisdom.weizmann.ac.il/~oded/PSX/fgmsz.pdf On Completeness and Soundness in Interactive Proof Systems] (Распознавание x \in L с вероятностью 1 для систем интерактивных доказательств)<br />
<br />
==Литература==<br />
# Dexter C. Kozen. Theory of Computation. (Замечательная книга по теории сложности вычислений, малоизвестная, по непонятным причинам, в нашей стране. Изложение структурировано в виде "лекций", часть из которых "обычные", а часть "продвинутые")<br />
# Michael Sipser. Introduction to the Theory of Computation (Очень хороший вводный учебник)<br />
# Sanjeev Arora & Boaz Barak. Computational Complexity: A Modern Approach. (Большая книга, которая входит во все списки литературы по теории сложности вычислений)</div>imported>Pein rules