|
|
| (не показана одна промежуточная версия этого же участника) |
| Строка 1: |
Строка 1: |
| − | Факультатив представляет собой введение в науку о сложности вычислений – красивую и богатую глубокими результатами область математики. Если теория алгоритмов пытается ответить на вопрос "что можно и чего нельзя вычислить на компьютере?", то теория сложности уточняет "что можно вычислить быстро?", "что принципиально невозможно вычислить быстро?", "что делает трудные задачи трудными?", "можно ли использовать случайность, чтобы ускорить вычисления?". Чтобы (попытаться) ответить на эти вопросы, мы разобьём задачи на классы сложности и будем сравнивать разные классы между собой. Некоторые из наших теорем будут чисто теоретическими (зато очень красивыми!), а некоторые будут иметь прямые приложения в алгоритмической практике, на которые мы постараемся явно указывать.
| + | Прямая ссылка на эту страницу: [https://tinyurl.com/logicomp tinyurl.com/logicomp] |
| − | | + | |
| − | Каждую неделю будет проходить «занятие» (одна пара) – смесь лекции и семинара в меняющейся пропорции. Будут задачи для самостоятельного решения, расширяющие и дополняющие материал занятий.
| + | |
| − | | + | |
| − | Для успешного прохождения курса достаточно иметь общее представление об алгоритмах, алгоритмических задачах и математических доказательствах. В примерах и задачах мы будем использовать стандартные вещи: булевы функции, графы, простые числа и так далее, однако никаких специальных предварительных знаний не предполагается.
| + | |
| − | | + | |
| − | ==Общая информация==
| + | |
| − | '''Официальное название:''' «Теория вычислений». (Никакой "и логики" в названии нет, хотя в программе она может появиться (см. курсив в программе курса)).
| + | |
| − | | + | |
| − | '''Преподаватель:''' [https://www.hse.ru/org/persons/305069360 Антон Гнатенко], почта: [mailto:agnatenko@hse.ru agnatenko@hse.ru], телеграм: [https://t.me/antongnatenko @antongnatenko]. Всюду на этой странице местоимение «я» обозначает именно этого человека.
| + | |
| − | | + | |
| − | '''Время и место (с 1 февраля):''' понедельник, 16:20,
| + | |
| − | онлайн (по крайней мере, до возвращения оффлайн занятий, но, возможно, и после). Zoom: чтобы узнать ссылку, добавляйтесь в чат.
| + | |
| − | | + | |
| − | '''Записи занятий:''' https://www.youtube.com/playlist?list=PLbjUsKUoAqLMSKdVtO89OhR3J1alX4Q83
| + | |
| − | | + | |
| − | '''Доски:''' https://drive.google.com/drive/folders/1Qw4L9QccTVEpyG3Md_4ji1coDovKiMMy?usp=sharing
| + | |
| − | | + | |
| − | '''Телеграм-чат:''' https://t.me/joinchat/FehKYBXfk1Mu7npLZ3Tt_w
| + | |
| − | | + | |
| − | Ссылка на эту страницу: https://tinyurl.com/logicomp
| + | |
| − | | + | |
| − | Форма для задач: https://forms.gle/fvZhCKN4BmRTRRB76
| + | |
| − | | + | |
| − | Таблица с оценками:
| + | |
| − | | + | |
| − | ==История==
| + | |
| − | '''1 февраля 2021. Занятие 1.''' Машины Тьюринга и класс P.
| + | |
| − | | + | |
| − | Видеозапись: https://youtu.be/_9OeqVJ0Lpw
| + | |
| − | <br>
| + | |
| − | <br>
| + | |
| − | | + | |
| − | '''5 февраля 2021. Появились тренировочные задачи по машинам Тьюринга.''' См. раздел "Задачи".
| + | |
| − | <br>
| + | |
| − | <br>
| + | |
| − | | + | |
| − | '''8 февраля 2021. Занятие 2.''' Недетерминированные машины и класс NP.
| + | |
| − | | + | |
| − | Видеозапись: https://youtu.be/HlYOfCfgQEM
| + | |
| − | <br>
| + | |
| − | <br>
| + | |
| − | | + | |
| − | '''15 февраля 2021. Занятие 3.''' Полиномиальная сводимость и NP-полнота. Теорема Кука-Левина.
| + | |
| − | | + | |
| − | Видеозапись: https://youtu.be/XokMRfTbKkQ
| + | |
| − | | + | |
| − | '''Появилась первая порция задач.''' Мягкий дедлайн - 28 марта. Вероятно, у второй порции задач дедлайн будет ''тот же''. У бонусных задач дедлайна нет. См. раздел "Задачи".
| + | |
| − | <br>
| + | |
| − | <br>
| + | |
| − | | + | |
| − | '''22 февраля 2021. Занятие 4.''' NP-полнота задач о клике, о раскраске в 3 цвета, о гамильтоновом цикле.
| + | |
| − | | + | |
| − | Видеозапись: https://youtu.be/ffv1WXM4EJ4
| + | |
| − | <br>
| + | |
| − | <br>
| + | |
| − | | + | |
| − | '''Первая порция задач пополнилась.''' Добавилось ещё немного задач на доказательство NP-полноты. Мягкий дедлайн тот же - 28 марта. См. раздел "Задачи".
| + | |
| − | <br>
| + | |
| − | <br>
| + | |
| − | | + | |
| − | '''1 марта 2021. Занятие 5.''' Полиномиальная иерархия. Иерархия по времени.
| + | |
| − | | + | |
| − | Видеозапись: https://youtu.be/FcTpfNlO4b8
| + | |
| − | | + | |
| − | ==Программа курса (примерная)==
| + | |
| − | | + | |
| − | Темы, написанные прямым шрифтом – обязательные, это классика теории сложности вычислений. Темы, написанные курсивом, – дополнительные. Мы рассмотрим некоторые из них, если будет на то желание слушателей. Если ''курсивные темы'' станут реальностью, они могут вытеснить обычные темы и занять их место.
| + | |
| − | | + | |
| − | * Временная сложность, классы P и NP.
| + | |
| − | * NP-трудные и NP-полные задачи, NP-полнота задачи о выполнимости КНФ, о клике, о раскраске графа в 3 цвета, о существовании гамильтонова пути и других.
| + | |
| − | * ''Решение NP-полных задач на практике (общий обзор).''
| + | |
| − | * Класс coNP. ''Полиномиальная иерархия. Теорема о коллапсе полиномиальной иерархии.''
| + | |
| − | * Пространственная сложность, класс PSPACE, PSPACE-полные задачи ''и попытки решать их на практике (общий обзор)''.
| + | |
| − | * ''Сложность вычислений с помощью схем из функциональных элементов, класс P/poly.''
| + | |
| − | * ''Коммуникационная сложность.''
| + | |
| − | * ''Вероятностная сложность, класс BPP (и другие), вероятностные алгоритмы проверки числа на простоту и проверки полиномов на равенство.''
| + | |
| − | * ''Интерактивные доказательства и вероятностно проверяемые доказательства.''
| + | |
| − | * ''Разрешимость и сложность некоторых логических теорий, автоматы над бесконечными словами.''
| + | |
| − | * ''Вычисления с оракулом. Арифметическая иерархия и аналитическая иерархия.''
| + | |
| − | | + | |
| − | * '''''...''''' (это многоточие написано ''курсивом'')
| + | |
| − | | + | |
| − | ==Правила оценивания==
| + | |
| − | Чтобы получить оценку, нужно набирать баллы (обычные и бонусные). Вот как это сделать:
| + | |
| − | | + | |
| − | * '''Решать задачи''', которые предлагаются на занятиях и появляются на этой страничке в разделе [http://wiki.cs.hse.ru/%D0%A4%D0%B0%D0%BA%D1%83%D0%BB%D1%8C%D1%82%D0%B0%D1%82%D0%B8%D0%B2_%22%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_%D0%B8_%D0%BB%D0%BE%D0%B3%D0%B8%D0%BA%D0%B0%22#.D0.97.D0.B0.D0.B4.D0.B0.D1.87.D0.B8 «Задачи»]. Для каждой задачи указано количество баллов, которые можно получить за правильное решение. У каждой задачи есть мягкий дедлайн — после него правильные решения получат половину баллов. Задачи можно сдавать устно или письменно. В случае письменной сдачи может потребоваться дополнительное обсуждение некоторых неслучайно выбранных задач. Во время обсуждения нужно продемонстрировать понимание сданного решения. Зато можно исправить ошибки, если они там есть.
| + | |
| − | | + | |
| − | * '''Решать бонусные задачи''', которые появляются там же. За бонусные задачи даются '''бонусные баллы''' (см. ниже).
| + | |
| − | | + | |
| − | * '''Участвовать в занятиях'''. Иногда можно получить немного '''бонусных баллов''' за высказанную идею решения задачи, идею доказательства, ответ на вопрос.
| + | |
| − | | + | |
| − | Пусть теперь M = «максимально возможное количество обычных баллов», а S = «сумма всех баллов (обычных и бонусных), набранных студентом за семестр».
| + | |
| − | Тогда оценка за курс вычисляется по формуле P = min{S / M * 10, 10}.
| + | |
| − | | + | |
| − | Таким образом, можно получить 10 баллов, просто решая обычные задачи. Но это проще сделать, если набирать бонусные баллы.
| + | |
| − | | + | |
| − | ==Задачи==
| + | |
| − | '''Письменные решения нужно сдавать [https://forms.gle/fvZhCKN4BmRTRRB76 вот этой гугл-форме].''' Пожалуйста, оформляйте решения аккуратно. Для оцифровки записей лучше всего использовать не фото, а специальные приложения-сканеры. Например, Camscanner. Если вы сдаёте несколько задач сразу, объединяйте их в один пдф или в один архив.
| + | |
| − | | + | |
| − | Для сдачи файлов в форму нужен гугл-аккаунт. Если его нет и по каким-то причинам вы совсем не хотите его заводить, можно сдавать задачи устно или договориться о каком-либо ещё варианте. Но лучше всё-таки завести аккаунт.
| + | |
| − | | + | |
| − | '''Правила оформления решений.''' При изложении решений рекомендуется соблюдать разумный баланс между строгостью и размахиванием руками. Если требуется доказать, например, принадлежность некоторого языка классу NP, то достаточно предоставить словесное описание соответствующей машины (если только в условии явно не просят построить машину). Описание должно быть, тем не менее, чётким и подробным (но без фанатизма). Если какие-то важные детали из этого описания будут неясны, я попрошу сделать пояснения (возможно, устные).
| + | |
| − | | + | |
| − | '''Можно сдавать задачи устно.''' Для этого нужно связаться со мной в зуме, включить демонстрацию экрана (либо ещё каким-то образом добиться того, чтобы я видел какие-то записи и понимал, о чём вы говорите) и рассказать своё решение, отвечая на возникающие вопросы. Нужно предупредить меня о желании сдавать хотя бы за день (например, написав в телеграм), и мы договоримся о времени. Можно предупреждать раньше, чем за день – это приветствуется. Можно попробовать договориться прямо в день сдачи, но успех в таком случае маловероятен.
| + | |
| − | | + | |
| − | | + | |
| − | ====Наборы задач====
| + | |
| − | | + | |
| − | * [https://drive.google.com/file/d/1jwjO29czncdbgozvNjdn0ZFjXsZo_e28/view?usp=sharing Тренировочные задачи по машинам Тьюринга]. Дедлайна нет.
| + | |
| − | * [https://drive.google.com/file/d/16Ae7UVOWY2-HhH8yG3DS8eBwJstz7O7D/view?usp=sharing Первая порция задач: класс NP, полиномиальная сводимость и NP-полнота]. Мягкий дедлайн 28 марта. По бонусным задачам дедлайна нет.
| + | |
| − | | + | |
| − | ==Интересные статьи==
| + | |
| − | === Классика ===
| + | |
| − | | + | |
| − | * 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). (Определение полноты (осторожно: не совсем такое, как у нас) и теорема Кука-Левина). Статья, по непонятным причинам, недоступна. Можно получить к ней доступ через библиотеку Вышки: https://library.hse.ru/e-resources (см. "Базы данных зарубежной периодики" и там "издания ACM"; у вас должны быть логин/пароль для библиотеки: https://elib.hse.ru/e-resources/ez/ezregulation.htm).
| + | |
| − | | + | |
| − | * Richard M. Karp. [https://people.eecs.berkeley.edu/~luca/cs172/karp.pdf Reducibility among combinatorial problems] (1972). (Внушительный список комбинаторных задач с доказательствами их NP-полноты).
| + | |
| − | | + | |
| − | * Л. А. Левин. [http://www.mathnet.ru/links/efc20ed39c74803d8ecb1011962ba4b3/ppi914.pdf Универсальные задачи перебора] (1973). (Примерно про то же in Soviet Russia)
| + | |
| − | | + | |
| − | === Неоклассика ===
| + | |
| − | * 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]
| + | |
| − | | + | |
| − | ==Литература==
| + | |
| − | # Dexter C. Kozen. Theory of Computation. (Замечательная книга по теории сложности вычислений, малоизвестная, по непонятным причинам, в нашей стране. Изложение структурировано в виде "лекций", часть из которых "обычные", а часть "продвинутые")
| + | |
| − | # Michael Sipser. Introduction to the Theory of Computation (Очень хороший вводный учебник)
| + | |
| − | # Sanjeev Arora & Boaz Barak. Computational Complexity: A Modern Approach. (Большая книга, которая входит во все списки литературы по теории сложности вычислений)
| + | |
| − | # Д.В. Мусатов. Лекции по сложности вычислений в МФТИ (видеозаписи). https://mipt.lectoriy.ru/course/Maths-ComputationalComplexity-14L (Очень хороший курс лекций, существенно пересекающийся с нашим)
| + | |
| | | | |
| | ==Архив== | | ==Архив== |
| | * [http://wiki.cs.hse.ru/%D0%A4%D0%B0%D0%BA%D1%83%D0%BB%D1%8C%D1%82%D0%B0%D1%82%D0%B8%D0%B2_%22%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_%D0%B8_%D0%BB%D0%BE%D0%B3%D0%B8%D0%BA%D0%B0%22_(%D0%9E%D1%81%D0%B5%D0%BD%D1%8C_2020) Факультатив "Вычислимость и логика", осень 2020] | | * [http://wiki.cs.hse.ru/%D0%A4%D0%B0%D0%BA%D1%83%D0%BB%D1%8C%D1%82%D0%B0%D1%82%D0%B8%D0%B2_%22%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_%D0%B8_%D0%BB%D0%BE%D0%B3%D0%B8%D0%BA%D0%B0%22_(%D0%9E%D1%81%D0%B5%D0%BD%D1%8C_2020) Факультатив "Вычислимость и логика", осень 2020] |
| | + | |
| | + | * [http://wiki.cs.hse.ru/%D0%A4%D0%B0%D0%BA%D1%83%D0%BB%D1%8C%D1%82%D0%B0%D1%82%D0%B8%D0%B2_%22%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_(%D0%92%D0%B5%D1%81%D0%BD%D0%B0_2021) Факультатив "Теория вычислений", весна 2021] |
