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

Ицыксон Дмитрий Михайлович, Опарин Всеволод Владиславович, Computer Science Center

Курс знакомит со сложностью вероятностных вычислений и теоретическими основами криптографии. Мы изучим вероятностные классы сложности и основные приемы, которые используются для анализа и построения вероятностных алгоритмов, узнаем, что такое интерактивные протоколы, игры Артура и Мерлина, докажем знаменитую теорему Шамира IP=PSPACE, обсудим классы задач подсчета, поговорим о вероятностно проверяемых доказательства и PCP-теореме. В криптографической части курса мы поговорим об односторонних функциях, генераторах псевдослучайных чисел, протоколах с открытым и публичным ключом, привязке к биту и о доказательствах с нулевым разглашением.

Формально курс является продолжением курса Основы вычислимости и теории сложности, но на лекции приглашаются все желающие. Рекомендуется иметь представление о следующих понятиях: машины Тьюринга (детерминированные и недетерминированные), классы P, NP, PSPACE, NP-полнота, полиномиальная иерархия, булевы схемы. Все определения будут напоминаться по просьбе слушателей.

Сессии:
  • Свободный график
Характеристики онлайн курса:
  • Бесплатный:
  • Платный:
  • Сертификат:
  • MOOC:
  • Видеолекции:
  • Аудиолекции:
  • Email-курс:
  • Язык: Русский Ru

Отзывы

Пока никто не написал отзыв по этому курсу. Хотите быть первым?

Зарегистрируйтесь, чтобы оставить отзыв

Входит в подборки курсов:
Ещё из рубрики «Математика и статистика»:
B-teaser-0 Машинное обучение
Лектор: Константин Вячеславович Воронцов, старший научный сотрудник Вычисли...
B-teaser-0 Дискретный анализ и теория вероятностей
Обязательный курс первого семестра для отделения Computer Science. Препо...
Yury_lifshits Алгоритмы для Интернета
Лекции: - Построение суффиксного дерева (по Укконену) - Преобразование Бе...
Cscenter Математическая статистика
Лекция 0 «Обзор основных фактов теории вероятностей» Лекция 1 Выборка, ...
Extpicture Математическая теория формальных языков
Курс посвящён классическому разделу математической лингвистики и теоретичес...
Ещё от Computer Science Center:
Cscenter Дополнительные главы алгоритмов
Часть 1. Продвинутые структуры данных Приоритетные очереди, сливаемые кучи...
Cscenter Алгоритмы и структуры данных 2
Splay-дерево и декартово дерево Хеширование Числовые алгоритмы: проверка ...
Cscenter Технологии хранения и обработки больших объёмов данных
Курс посвящён теоретическим и практическим аспектам технологий, связанных с...
Cscenter Алгоритмы в биоинформатике
Биоинформатика — это быстро растущий раздел computer science, благодаря кот...
Cscenter Распределенные системы хранения и обработки данных
В курсе дано всестороннее представление о системах и сетях хранения данных,...

© 2013-2017