course language
course duration
needed to educate
for credit at your university
Чем отличается простая алгоритмическая задача от сложной? Каким задачам сложность внутренне присуща, а не связана с конкретным алгоритмом или особенностями практической реализации? И можно ли этот факт доказать? В курсе мы познакомимся с «зоопарком» сложностных классов, научимся классифицировать по ним алгоритмические задачи, изучим связи между ними и обнаружим, что доказывать факт сложности мы обычно не умеем. А ещё мы увидим, как можно использовать нерешаемые задачи во благо, ведь именно на них основана современная криптография.
Курс состоит из 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. Реализует новые методы при решении конкретных прикладных задач в сфере своей профессиональной деятельности
course language
course duration
needed to educate
for credit at your university
Кандидат физико-математических наук
Position: Преподаватель кафедры дискретной математики МФТИ