Спецкурс является введением в теорию сложности вычислений. Вот краткий список освещаемых вопросов: временнАя и емкостная сложности; машина Тьюринга как абстрация алгоритма; иерархия классов (P, NP, NPC); детерминированные, недетерминированные и вероятностные алгоритмы; теоретико-сложностные вопросы криптографии (односторонние функции, псевдослучайные генераторы, интерактивные доказательства).

Программа спецкурса.

Методические указания по спецкурсу.

Этот курс посвящен оценке сложности конкретных задач и алгоритмов, а также стратегиям разработки эффективных алгоритмов. Основные темы: стратегия "разделяй и властвуй"; динамическое программирование; "жадные" алгоритмы; сортировка и порядковые статистки.

Вопросы к экзамену (лето 2004 г.).

Название спецкурса говорит само за себя. В дополнение к алгоритмам рассматриваются некоторые общие сведения о графах (теоремы, напрямую не связанные с алгоритмами).

Вопросы к экзамену (лето 2004 г.).