Сложность вычислений и основы криптографии

Общая информация
ЛекторЭ. А. Гирш
Семестрвесна 2012
Дата начала14.02.2012
Количество пар12
Язык курсарусский
Вопросы к экзамену
Видеоhttp://www.lektorium.tv/course/?id=22844
Анонсы
Встреча на сайте T&Phttp://theoryandpractice.ru/courses/7924-slozhnost-vychisleniy-i-osnovy-kriptogr...
Анонс habrahabr.ruhttp://habrahabr.ru/events/411/
Аннотация

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

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

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

Материалы:

Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Лекция
(14.02.2012 - 18:30 - 20:05)

Недетерминированные машины Тьюринга. Классы P и NP. Оптимальный алгоритм Левина. Сводимости, NP-полнота.

http://www.lektorium.tv/lecture/?id=13520
2. Лекция
(21.02.2012 - 18:30 - 20:05)

NP-полнота задач CIRCUIT-SAT и SAT. Сведение поиска к распознаванию. Существование не NP-полной не полиномиально разрешимой задачи в NP.

http://www.lektorium.tv/lecture/?id=13563
3. Лекция
(28.02.2012 - 18:30 - 20:05)

Оракульные вычисления. Полиномиальная иерархия. Полнота задачи $ QBF_k $. Теоремы о коллапсе. Семейства схем полиномиального размера. Коллапс полиномиальной иерархии как следствие $ NP\subseteq P/poly $. Языки во втором уровне полиномиальной иерархии, не имеющие схем фиксированного полиномиального размера.

http://www.lektorium.tv/lecture/?id=13589
4. Лекция
(06.03.2012 - 18:30 - 20:05)

Вычисления с ограничениями по памяти. Схемы полилогарифмической глубины.

http://www.lektorium.tv/lecture/?id=13611
5. Лекция
(13.03.2012 - 18:30 - 20:05)

QBF is PSPACE-complete. Hierarchies DSpace, DTime, NTime.

http://www.lektorium.tv/lecture/?id=13637
6. Лекция
(20.03.2012 - 18:30 - 20:05)

Вероятностные алгоритмы.

http://www.lektorium.tv/lecture/?id=13655
7. Лекция
(27.03.2012 - 18:30 - 20:05)

Интерактивные протоколы.

http://www.lektorium.tv/lecture/?id=13675
8. Лекция
(03.04.2012 - 18:30 - 20:05)

Сложность в среднем. Односторонние функции.

http://www.lektorium.tv/lecture/?id=13704
9. Лекция
(10.04.2012 - 18:30 - 20:05)

Трудный бит. Псевдослучайный генератор.

http://www.lektorium.tv/lecture/?id=13727
10. Лекция
(17.04.2012 - 18:30 - 20:05)

Односторонние функции с секретом, криптосистемы с открытым ключом.

http://www.lektorium.tv/lecture/?id=13743
11. Лекция
(24.04.2012 - 18:30 - 20:05)

Цифровые подписи.

http://www.lektorium.tv/lecture/?id=13750
Ваша оценка: Пусто Средняя: 5 (2 голосов)
Share |