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

Недетерминированные и вероятностные вычисления
Казань / весна 2016, посмотреть все семестры

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

Слова "недетерминизм" и "случайность" часто воспринимаются как синонимы. Однако в контексте моделей вычислений они означают совсем разное. И там, и там есть некоторое дерево вычислений, но при использовании случайности выбирается одна ветвь равновероятно, а при использовании недетерминизма все ветви обрабатываются параллельно. И случайность, и недетерминизм позволяют решать алгоритмические задачи эффективнее. Хотя мы и не умеем это доказывать: для недетерминизма это знаменитая проблема равенства классов P и NP, для случайности - классов P и BPP. В курсе будет рассказано об обеих моделях вычислений, дан обзор известных результатов с детальным разбором некоторых конструкций. Много внимания будет уделено вопросам сводимости и полноты.

Дата и время Занятие Место Материалы
04 апреля
15:20–16:50
Недетерминированные и вероятностные вычисления: обзор, Лекция 2-й учебный корпус К(П)ФУ, ауд. 907 Нет
04 апреля
17:00–18:20
Недетерминированные и вероятностные вычисления: обзор, Лекция 2-й учебный корпус К(П)ФУ, ауд. 907 Нет
05 апреля
15:20–16:50
NP-сводимость и NP- полнота, Лекция 2-й учебный корпус К(П)ФУ, ауд. 1113 Нет
05 апреля
17:00–18:20
NP-сводимость и NP- полнота, Лекция 2-й учебный корпус К(П)ФУ, ауд. 1113 Нет
06 апреля
15:20–16:50
P и NP для вычислений с оракулом, Лекция 2-й учебный корпус К(П)ФУ, ауд. 1006 Нет
06 апреля
17:00–18:20
Задачи поиска для класса NP, Лекция 2-й учебный корпус К(П)ФУ, ауд. 1010 Нет
07 апреля
15:20–16:50
Недетерминированные вычисления на логарифмической памяти, Лекция 2-й учебный корпус К(П)ФУ, ауд. 708 Нет
07 апреля
17:00–18:20
Недетерминированные вычисления на логарифмической памяти, Лекция 2-й учебный корпус К(П)ФУ, ауд. 907 Нет
08 апреля
15:20–16:50
Вероятностные сложностные классы, Лекция 2-й учебный корпус К(П)ФУ, ауд. 216 Нет
08 апреля
17:00–18:20
Вероятностные сложностные классы, Лекция 2-й учебный корпус К(П)ФУ, ауд. 216 Нет