up

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

 width=
27 November 2020 - 29 March 2021 г.
Start day after tomorrow
123 days
До конца записи
  • 14 недели

    длительность курса

  • от 12 до 13 часов в неделю

    понадобится для освоения

  • 5 зачётных единицы

    для зачета в своем вузе

О курсе

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

Формат

Курс состоит из 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 и др.
  • Вероятностные алгоритмы, не имеющие детерминированных аналогов
  • Языки, для которых есть интерактивные доказательства
  • Базовые криптографические примитивы: нулевое разглашение, протоколы привязки к биту, распределённая генерация случайных битов

Умения

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

Навыки

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

Мусатов Даниил Владимирович

Кандидат физико-математических наук
Должность: Преподаватель кафедры дискретной математики МФТИ

Похожие курсы