Теория вычислений

Модуль: 3-4

Кредиты: 2

Аннотация:

Факультатив представляет собой введение в науку о сложности вычислений – красивую и богатую глубокими результатами область математики. Если теория алгоритмов пытается ответить на вопрос "что можно и чего нельзя вычислить на компьютере?", то теория сложности уточняет "что можно вычислить быстро?", "что принципиально невозможно вычислить быстро?", "что делает трудные задачи трудными?", "можно ли использовать случайность, чтобы ускорить вычисления?". Чтобы (попытаться) ответить на эти вопросы, мы разобьём задачи на классы сложности и будем сравнивать разные классы между собой. Некоторые из наших теорем будут чисто теоретическими (зато очень красивыми!), а некоторые будут иметь прямые приложения в алгоритмической практике, на которые мы постараемся явно указывать.

Курс состоит из занятий (смесь лекций и семинаров в меняющейся пропорции) и задач для самостоятельного решения (обычных и бонусных). Если всего за решение обычных задач можно набрать M баллов, а слушатель набрал S баллов (обычных и бонусных), то оценка выставляется по формуле P = min{S / M * 10, 10}. Подробнее про курс можно будет почитать на его страничке: https://tinyurl.com/logicomp (информация станет актуальной после окончания осеннего семестра).

План занятий:

Каждую неделю будет проходить «занятие» (одна пара) – смесь лекции и семинара в меняющейся пропорции. Ниже приводится примерный план тем, которые планируется обсудить. Темы, написанные прямым шрифтом – обязательные, это классика теории сложности вычислений. Темы, написанные курсивом – дополнительные. Некоторые из них, по совместному выбору слушателей и преподавателя, будут обсуждаться во второй части курса или после прохождения соответствующих основных тем.

1. Временная сложность, классы P и NP.

2. NP-трудные и NP-полные задачи, NP-полнота задачи о выполнимости КНФ, о клике, о раскраске графа в 3 цвета, о существовании гамильтонова пути и других.

3. Решение NP-полных задач на практике (общий обзор).

4. Класс coNP. Полиномиальная иерархия. Теорема о коллапсе полиномиальной иерархии.

5. Пространственная сложность, класс PSPACE, PSPACE-полные задачи и попытки решать их на практике (общий обзор).

6. Сложность вычислений с помощью схем из функциональных элементов, класс P/poly.

7. Коммуникационная сложность.

8. Вероятностная сложность, класс BPP (и другие), вероятностные алгоритмы проверки числа на простоту и проверки полиномов на равенство.

9. Интерактивные доказательства и вероятностно проверяемые доказательства.

10. Разрешимость и сложность некоторых логических теорий, автоматы над бесконечными словами.

11. Вычисления с оракулом. Арифметическая иерархия и аналитическая иерархия.

Требования: Базовое представление об алгоритмах, функциях, множествах и математических доказательствах. Все необходимые специальные знания будут даны в течение курса.

Для кого: 2 курс ПМИ и все желающие

Расписание: понедельник 16:20-17:40 с февраля