Читается в весеннем семестре на третьем курсе бакалавриата МФТИ.
Преподаватель: Фомин Станислав Александрович.
Основные вопросы курса: какие бывают вычислительные ресурсы, как подсчитывать их необходимое количество для решения данной алгоритмической задачи, как отличить решаемые на практике задачи от нерешаемых и как наиболее эффективно работать с решаемыми. Много внимания уделяется изучению различных сложностных классов, связей между ними и классификации конкретных задач.
Планируемые результаты обучения:
- Оценивать вычислительную сложность алгоритмических задач (в терминах вычислительных ресурсов).
- Классифицировать алгоритмические задачи их в основных сложностных классах — базовое ориентирование в огромном «зоопарке» классов сложности — студенты познакомятся с известными теоремами и открытыми гипотезами о соотношении сложностей задач.
- Устанавливать связи между сложностными классами.
- Выделять сложнорешаемые и практически решаемые алгоритмические задачи.
- Для трудноразрешимых задач, строить приближенные и вероятностные алгоритмы и дерандомизировать некоторые из них — познакомиться с несколькими красивыми и широко используемыми в узких кругах полиномиальными алгоритмами.
- Практически решать на Python классические задачи (возможность в дальнейшем использовать полученные навыки в дальнейшей работе по окончании ВУЗа), применение классических эвристик — «жадность», «динамическое программирование», известных алгоритмов на сортировки и графы и т.п.
Рассматриваемые темы:
- Формально об алгоритмах. Вычислительные модели.
- Временная и пространственная сложность алгоритмов.
- Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC.
- Вероятностные вычисления. Классы RP, coRP, ZPP, BPP.
- Жадный алгоритм в задачах о покрытии.
- Жадный алгоритм в задаче о рюкзаке.
- Динамическое программирование для задачи о рюкзаке.
- Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке.
- Полиномиальный в среднем алгоритм для задачи о рюкзаке.
- Полиномиальный в среднем алгоритм для SAT.
- Полиномиальный в среднем алгоритм для задачи упаковки.
- Вероятностная проверка тождеств.
- MAX-SAT: вероятностное округление.
- MAX-SAT: дерандомизация.
- MAX-CUT: вероятностное округление.
- Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема.
- PCP и аппроксимируемость.
В зависимости от первоначальной подготовки слушателей темы курса могут сокращаться или добавляться.
Дополнительная литература:
- Н.Н. Кузюрин, С.А. Фомин, Эффективные алгоритмы и сложность вычислений», 2007 издательство МФТИ. ISBN 5-7417-0198-1.
- S. Arora, B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
- M. Sipser, Introduction to the Theory of Computation, Course Technology, 2005.
- C. Moore, S. Mertens, The Nature of Computation, Oxford University Press, 2011
- Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы: построение и анализ, 3-е издание, Вильямс, 2019.
- O. Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008.
- A. Wigderson. Mathematics and Computation: A Theory Revolutionizing Technology and Science, Princeton University Press, 2019.
- C. Papadimitriou, Computational Complexity, Addison Wesley, 1994
- В. Н. Крупский. Введение в сложность вычислений, Москва, Факториал Пресс, 2006
- С. А. Абрамов, Лекции о сложности алгоритмов, Москва, МЦНМО, 2009
- Д. В. Мусатов. Курс лекций по сложности вычислений (видеолекций, конспекты).
- М. Гэри, Д. Джонсон, Вычислительные машины и труднорешаемые задачи, Москва, Мир, 1982
- М. Вялый, А. Китаев, А. Шень, Классические и квантовые вычисления, Москва, МЦНМО, 1999.