Город: Санкт-Петербург Казань Язык: Русский 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 Нет