Город: Санкт-Петербург Казань Язык: Русский English

Сложность вычислений и основы криптографии
Санкт-Петербург / весна 2012, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

Учёным всегда было присуще стремление разрабатывать эффективные методы решения как можно более широких классов задач. Однако чем более общей является задача, тем менее эффективны алгоритмы для неё. Поэтому важно понимать, какую цену мы платим за усложнение решаемой задачи. Иначе говоря, важно уметь анализировать сложность вычислительных задач. Этим занимается теория сложности алгоритмов, современная быстро развивающаяся область, знание которой совершенно необходимо тем, кто интересуется теоретической информатикой.

Структурная теория сложности изучает классы вычислительных задач и взаимоотношения между ними. Эта область на стыке математики и информатики содержит как великие нерешенные задачи (например, P=?=NP, за решение которой, кстати, объявлен приз в $1,000,000), так и красивые теоремы и понятия (например, интерактивные протоколы). Первая часть курса будет посвящена базовым понятиям, конструкциям, фактам в этой области: вероятностные алгоритмы, вычисления с оракулами, полиномиальная иерархия, булевы схемы, интерактивные протоколы.

Сложность вычислительной задачи препятствует её эффективному решению. Однако зачастую именно это требуется, когда речь идёт о невозможности взлома криптографических протоколов. Вторая часть курса будет посвящена рассказу о криптографических понятиях (односторонних функциях, криптосистемах и т.д.) на языке теории сложности (на котором они, собственно, и определяются).

Материалы:

Условия сдачи курса и вопросы к экзамену.

Дата и время Название Место Материалы
14 февраля
18:30–19:50
Лекция, лекция ПОМИ РАН видео
21 февраля
18:30–20:05
Лекция, лекция ПОМИ РАН видео
28 февраля
18:30–20:05
Лекция, лекция ПОМИ РАН видео
06 марта
18:30–20:05
Лекция, лекция ПОМИ РАН видео
13 марта
18:30–20:05
Лекция, лекция ПОМИ РАН видео
20 марта
18:30–20:05
Лекция, лекция ПОМИ РАН видео
27 марта
18:30–20:05
Лекция, лекция ПОМИ РАН видео
03 апреля
18:30–20:05
Лекция, лекция ПОМИ РАН видео
10 апреля
18:30–20:05
Лекция, лекция ПОМИ РАН видео
17 апреля
18:30–20:05
Лекция, лекция ПОМИ РАН видео
24 апреля
18:30–20:05
Лекция, лекция ПОМИ РАН видео