Факультатив "Теория вычислений и логика" — различия между версиями
Материал из Wiki - Факультет компьютерных наук
(→История: Добавлено занятие 11 -- последнее) |
(Страница подготовлена к весне 2021) |
||
| Строка 1: | Строка 1: | ||
| − | Факультатив | + | Факультатив представляет собой введение в науку о сложности вычислений – красивую и богатую глубокими результатами область математики. Если теория алгоритмов пытается ответить на вопрос "что можно и чего нельзя вычислить на компьютере?", то теория сложности уточняет "что можно вычислить быстро?", "что принципиально невозможно вычислить быстро?", "что делает трудные задачи трудными?", "можно ли использовать случайность, чтобы ускорить вычисления?". Чтобы (попытаться) ответить на эти вопросы, мы разобьём задачи на классы сложности и будем сравнивать разные классы между собой. Некоторые из наших теорем будут чисто теоретическими (зато очень красивыми!), а некоторые будут иметь прямые приложения в алгоритмической практике, на которые мы постараемся явно указывать. |
| + | |||
| + | Каждую неделю будет проходить «занятие» (одна пара) – смесь лекции и семинара в меняющейся пропорции. Будут задачи для самостоятельного решения, расширяющие и дополняющие материал занятий. | ||
| + | |||
| + | Для успешного прохождения курса достаточно иметь общее представление об алгоритмах, алгоритмических задачах и математических доказательствах. В примерах и задачах мы будем использовать стандартные вещи: булевы функции, графы, простые числа и так далее, однако никаких специальных предварительных знаний не предполагается. | ||
==Общая информация== | ==Общая информация== | ||
| − | '''Официальное название:''' | + | '''Официальное название:''' «Теория вычислений». (Никакой "и логики" в названии нет, хотя в программе она может появиться (см. курсив в программе курса)). |
'''Преподаватель:''' [https://www.hse.ru/org/persons/305069360 Антон Гнатенко], почта: [mailto:agnatenko@hse.ru agnatenko@hse.ru], телеграм: [https://t.me/antongnatenko @antongnatenko]. Всюду на этой странице местоимение «я» обозначает именно этого человека. | '''Преподаватель:''' [https://www.hse.ru/org/persons/305069360 Антон Гнатенко], почта: [mailto:agnatenko@hse.ru agnatenko@hse.ru], телеграм: [https://t.me/antongnatenko @antongnatenko]. Всюду на этой странице местоимение «я» обозначает именно этого человека. | ||
| − | '''Время и место:''' | + | '''Время и место:''' уточняются |
| − | '''Записи занятий:''' | + | '''Записи занятий:''' |
| − | '''Доски | + | '''Доски:''' |
'''Телеграм-чат:''' https://t.me/joinchat/FehKYBXfk1Mu7npLZ3Tt_w | '''Телеграм-чат:''' https://t.me/joinchat/FehKYBXfk1Mu7npLZ3Tt_w | ||
| Строка 16: | Строка 20: | ||
Ссылка на эту страницу: https://tinyurl.com/logicomp | Ссылка на эту страницу: https://tinyurl.com/logicomp | ||
| − | Форма для задач: https://forms.gle/ | + | Форма для задач: https://forms.gle/fvZhCKN4BmRTRRB76 |
| − | Таблица с оценками: | + | Таблица с оценками: |
==История== | ==История== | ||
| − | + | Пока ничего не произошло | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
==Программа курса (примерная)== | ==Программа курса (примерная)== | ||
| − | Темы, | + | Темы, написанные прямым шрифтом – обязательные, это классика теории сложности вычислений. Темы, написанные курсивом, – дополнительные. Мы рассмотрим некоторые из них, если будет на то желание слушателей. Если ''курсивные темы'' станут реальностью, они могут вытеснить обычные темы и занять их место. |
| − | + | * Временная сложность, классы 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 «Задачи»]. Для каждой задачи указано количество баллов, которые можно получить за правильное решение. У каждой задачи есть мягкий дедлайн — после него правильные решения получат половину баллов. Задачи можно сдавать устно или письменно. В случае письменной сдачи может потребоваться | + | * '''Решать задачи''', которые предлагаются на занятиях и появляются на этой страничке в разделе [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 = «сумма всех баллов (обычных и бонусных), набранных студентом за семестр». | Пусть теперь M = «максимально возможное количество обычных баллов», а S = «сумма всех баллов (обычных и бонусных), набранных студентом за семестр». | ||
| − | Тогда | + | Тогда оценка за курс вычисляется по формуле P = min{S / M * 10, 10}. |
Таким образом, можно получить 10 баллов, просто решая обычные задачи. Но это проще сделать, если набирать бонусные баллы. | Таким образом, можно получить 10 баллов, просто решая обычные задачи. Но это проще сделать, если набирать бонусные баллы. | ||
| − | |||
| − | |||
==Задачи== | ==Задачи== | ||
| − | '''Письменные решения нужно сдавать [https://forms.gle/ | + | '''Письменные решения нужно сдавать [https://forms.gle/fvZhCKN4BmRTRRB76 вот этой гугл-форме].''' Пожалуйста, оформляйте решения аккуратно. Для оцифровки записей лучше всего использовать не фото, а специальные приложения-сканеры. Например, Camscanner. Если вы сдаёте несколько задач сразу, объединяйте их в один пдф или в один архив. |
Для сдачи файлов в форму нужен гугл-аккаунт. Если его нет и по каким-то причинам вы совсем не хотите его заводить, можно сдавать задачи устно или договориться о каком-либо ещё варианте. Но лучше всё-таки завести аккаунт. | Для сдачи файлов в форму нужен гугл-аккаунт. Если его нет и по каким-то причинам вы совсем не хотите его заводить, можно сдавать задачи устно или договориться о каком-либо ещё варианте. Но лучше всё-таки завести аккаунт. | ||
| − | '''Правила оформления решений.''' При изложении решений рекомендуется соблюдать разумный баланс между строгостью и размахиванием руками. Если требуется доказать, например, | + | '''Правила оформления решений.''' При изложении решений рекомендуется соблюдать разумный баланс между строгостью и размахиванием руками. Если требуется доказать, например, принадлежность некоторого языка классу NP, то достаточно предоставить словесное описание соответствующей машины (если только в условии явно не просят построить машину). Описание должно быть, тем не менее, чётким и подробным (но без фанатизма). Если какие-то важные детали из этого описания будут неясны, я попрошу сделать пояснения (возможно, устные). |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | '''Вероятно, можно будет сдавать задачи устно.''' Подробности появятся позже. | |
==Литература== | ==Литература== | ||
| − | # Dexter C. Kozen. | + | # 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 (Очень хороший курс лекций, существенно пересекающийся с нашим) |
| − | # | + | |
| − | + | ||
Версия 18:40, 10 января 2021
Факультатив представляет собой введение в науку о сложности вычислений – красивую и богатую глубокими результатами область математики. Если теория алгоритмов пытается ответить на вопрос "что можно и чего нельзя вычислить на компьютере?", то теория сложности уточняет "что можно вычислить быстро?", "что принципиально невозможно вычислить быстро?", "что делает трудные задачи трудными?", "можно ли использовать случайность, чтобы ускорить вычисления?". Чтобы (попытаться) ответить на эти вопросы, мы разобьём задачи на классы сложности и будем сравнивать разные классы между собой. Некоторые из наших теорем будут чисто теоретическими (зато очень красивыми!), а некоторые будут иметь прямые приложения в алгоритмической практике, на которые мы постараемся явно указывать.
Каждую неделю будет проходить «занятие» (одна пара) – смесь лекции и семинара в меняющейся пропорции. Будут задачи для самостоятельного решения, расширяющие и дополняющие материал занятий.
Для успешного прохождения курса достаточно иметь общее представление об алгоритмах, алгоритмических задачах и математических доказательствах. В примерах и задачах мы будем использовать стандартные вещи: булевы функции, графы, простые числа и так далее, однако никаких специальных предварительных знаний не предполагается.
Содержание
Общая информация
Официальное название: «Теория вычислений». (Никакой "и логики" в названии нет, хотя в программе она может появиться (см. курсив в программе курса)).
Преподаватель: Антон Гнатенко, почта: agnatenko@hse.ru, телеграм: @antongnatenko. Всюду на этой странице местоимение «я» обозначает именно этого человека.
Время и место: уточняются
Записи занятий:
Доски:
Телеграм-чат: https://t.me/joinchat/FehKYBXfk1Mu7npLZ3Tt_w
Ссылка на эту страницу: https://tinyurl.com/logicomp
Форма для задач: https://forms.gle/fvZhCKN4BmRTRRB76
Таблица с оценками:
История
Пока ничего не произошло
Программа курса (примерная)
Темы, написанные прямым шрифтом – обязательные, это классика теории сложности вычислений. Темы, написанные курсивом, – дополнительные. Мы рассмотрим некоторые из них, если будет на то желание слушателей. Если курсивные темы станут реальностью, они могут вытеснить обычные темы и занять их место.
- Временная сложность, классы P и NP.
- NP-трудные и NP-полные задачи, NP-полнота задачи о выполнимости КНФ, о клике, о раскраске графа в 3 цвета, о существовании гамильтонова пути и других.
- Решение NP-полных задач на практике (общий обзор).
- Класс coNP. Полиномиальная иерархия. Теорема о коллапсе полиномиальной иерархии.
- Пространственная сложность, класс PSPACE, PSPACE-полные задачи и попытки решать их на практике (общий обзор).
- Сложность вычислений с помощью схем из функциональных элементов, класс P/poly.
- Коммуникационная сложность.
- Вероятностная сложность, класс BPP (и другие), вероятностные алгоритмы проверки числа на простоту и проверки полиномов на равенство.
- Интерактивные доказательства и вероятностно проверяемые доказательства.
- Разрешимость и сложность некоторых логических теорий, автоматы над бесконечными словами.
- Вычисления с оракулом. Арифметическая иерархия и аналитическая иерархия.
- ... (это многоточие написано курсивом)
Правила оценивания
Чтобы получить оценку, нужно набирать баллы (обычные и бонусные). Вот как это сделать:
- Решать задачи, которые предлагаются на занятиях и появляются на этой страничке в разделе «Задачи». Для каждой задачи указано количество баллов, которые можно получить за правильное решение. У каждой задачи есть мягкий дедлайн — после него правильные решения получат половину баллов. Задачи можно сдавать устно или письменно. В случае письменной сдачи может потребоваться дополнительное обсуждение некоторых неслучайно выбранных задач. Во время обсуждения нужно продемонстрировать понимание сданного решения. Зато можно исправить ошибки, если они там есть.
- Решать бонусные задачи, которые появляются там же. За бонусные задачи даются бонусные баллы (см. ниже).
- Участвовать в занятиях. Иногда можно получить немного бонусных баллов за высказанную идею решения задачи, идею доказательства, ответ на вопрос.
Пусть теперь M = «максимально возможное количество обычных баллов», а S = «сумма всех баллов (обычных и бонусных), набранных студентом за семестр». Тогда оценка за курс вычисляется по формуле P = min{S / M * 10, 10}.
Таким образом, можно получить 10 баллов, просто решая обычные задачи. Но это проще сделать, если набирать бонусные баллы.
Задачи
Письменные решения нужно сдавать вот этой гугл-форме. Пожалуйста, оформляйте решения аккуратно. Для оцифровки записей лучше всего использовать не фото, а специальные приложения-сканеры. Например, Camscanner. Если вы сдаёте несколько задач сразу, объединяйте их в один пдф или в один архив.
Для сдачи файлов в форму нужен гугл-аккаунт. Если его нет и по каким-то причинам вы совсем не хотите его заводить, можно сдавать задачи устно или договориться о каком-либо ещё варианте. Но лучше всё-таки завести аккаунт.
Правила оформления решений. При изложении решений рекомендуется соблюдать разумный баланс между строгостью и размахиванием руками. Если требуется доказать, например, принадлежность некоторого языка классу NP, то достаточно предоставить словесное описание соответствующей машины (если только в условии явно не просят построить машину). Описание должно быть, тем не менее, чётким и подробным (но без фанатизма). Если какие-то важные детали из этого описания будут неясны, я попрошу сделать пояснения (возможно, устные).
Вероятно, можно будет сдавать задачи устно. Подробности появятся позже.
Литература
- 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 (Очень хороший курс лекций, существенно пересекающийся с нашим)
