Сложность вычислений

Чем отличается простая алгоритмическая задача от сложной? Каким задачам сложность внутренне присуща, а не связана с конкретным алгоритмом или особенностями практической реализации? И можно ли этот факт доказать? В курсе мы познакомимся с «зоопарком» сложностных классов, научимся классифицировать по ним алгоритмические задачи, изучим связи между ними и обнаружим, что доказывать факт сложности мы обычно не умеем. А ещё мы увидим, как можно использовать нерешаемые задачи во благо, ведь именно на них основана современная криптография.

Курс состоит из 12 учебных недель, промежуточного и итогового экзаменов.

Каждая неделя состоит из видео-лекций продолжительностью 10-15 минут, материалов для самостоятельного изучения слушателями, заданий для самостоятельного решения. Все задания могут включать себя теоретические вопросы с выбором вариантов ответа и задачи.

Основная литература.

Кузюрин Н. Н., Фомин С. А. Эффективные алгоритмы и сложность вычислений [Электронный ресурс] : учебное пособие / Н. Н. Кузюрин, С. А. Фомин . — Электрон. текстовые данные. — Москва: Издательство МФТИ, 2007. — 368 c. — Режим доступа: https://discopal.ispras.ru/Файл:Book-advanced-algorithms.pdf  — Загл. с экрана.

Крупский В. Н. Введение в сложность вычислений. / В. Н. Крупский — Москва: Факториал Пресс, 2006. — 128 с.

Дополнительная литература.

Хопкрофт Дж. Э., Мотвани Р., Ульман Дж. Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. / Дж. Э. Хопкрофт, Р. Мотвани, Дж. Д. Ульман. — Москва: Вильямс, 2002. — 528 с. : ил. — Парал. тит. англ.

Sipser M. Introduction to the Theory of Computation. 3rd edition. / M. Sipser — Boston: Cengage Learning, 2012. — 504 p.

Arora S., Barak B. Computational Complexity: A Modern Approach: illustrated edition / S. Arora, B. Barak. — Cambridge University Press, 2009. — 594 p.

Moore C., Mertens S. The Nature of Computation. 1st edition. / C. Moore, S. Mertens. — Oxford University Press, 2011. — 985 p

Знание основных понятий теории вероятностей, базовое знакомство с теорией алгоритмов, булевой логикой, теорией графов, комбинаторикой

Неделя 1

Основные модели вычислений и измерение сложности задач

Неделя 2

Классы P, NP и coNP, проблема равенства P и NP

Недели 3 и 4

Полиномиальная сводимость, NP-полнота

Неделя 5

Вычисления на полиномиальной памяти, класс PSPACE

Недели 6 и 7

Вычисления на логарифмической памяти, классы L и NL

Недели 8 и 9

Вероятностные вычисления

Неделя 10

Дерандомизация вероятностных алгоритмов

Неделя 11

Интерактивные протоколы

Неделя 12

Основания криптографии

Курс направлен на формирование универсальных компетенций:

УК-6. Способен определять и реализовывать приоритеты собственной деятельности и способы ее совершенствования на основе самооценки.

Индикаторы

УК-6.1 Оценивает возможности и ограничения, проектирует процесс саморазвития

УК-6.2 Определяет приоритеты своей деятельности, реализует и совершенствует ее на основе самоконтроля результатов

Курс направлен на формирование общепрофессиональных компетенций:  

ОПК-2. Способен совершенствовать и реализовывать новые математические методы решения прикладных задач

Индикаторы

ОПК-2.1. Оценивает достоинства и недостатки применения конкретных методов для решения поставленных прикладных задач, аргументированно обосновывая критерии оценки и сравнения методов

ОПК-2.2. Совершенствует существующие методы при решении конкретных прикладных задач, аргументированно обосновывая критерии, по которым проводились изменения и сравнение методов

ОПК-2.3. Реализует новые методы при решении конкретных прикладных задач в сфере своей профессиональной деятельности

• Понятие вычислительной сложности алгоритмической задачи, не связанной с особенностями реализации, а внутренне ей присущей
• Неклассические подходы к понятию алгоритма: недетерминированные, вероятностные и интерактивные алгоритмы
• Понятие сложностного класса, соотношения и связи между классами
• Сложностные классы P, NP, coNP, PSPACE, L, NL, BPP, IP и др.
• Полные задачи в классах NP, PSPACE, NL и др.
• Вероятностные алгоритмы, не имеющие детерминированных аналогов
• Языки, для которых есть интерактивные доказательства
• Базовые криптографические примитивы: нулевое разглашение, протоколы привязки к биту, распределённая генерация случайных битов

• Оценивать сложность алгоритмической задачи
• Выбирать нужную концепцию алгоритма для решения данной задачи
• Классифицировать задачи по сложностным классам
• Проверять задачи на полноту в сложностных классах
• Дерандомизировать вероятностные алгоритмы методами условных мат. ожиданий и попарно независимых случайных величин

• Замечать алгоритмическую природу вещей и связи между напрямую не относящимися друг к другу задачами
• Оценивать сложность алгоритма или алгоритмической задачи по её описанию, без детального анализа
• Формулировать в виде математических свойств требования к надёжности интерактивных систем и криптографических протоколов