City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Non-deterministic and probabilistic computations
Kazan / spring 2016, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

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

Date and time Class|Name Venue|short Materials
04 April
15:20–16:50
Недетерминированные и вероятностные вычисления: обзор, Lecture 2-й учебный корпус К(П)ФУ, ауд. 907 No
04 April
17:00–18:20
Недетерминированные и вероятностные вычисления: обзор, Lecture 2-й учебный корпус К(П)ФУ, ауд. 907 No
05 April
15:20–16:50
NP-сводимость и NP- полнота, Lecture 2-й учебный корпус К(П)ФУ, ауд. 1113 No
05 April
17:00–18:20
NP-сводимость и NP- полнота, Lecture 2-й учебный корпус К(П)ФУ, ауд. 1113 No
06 April
15:20–16:50
P и NP для вычислений с оракулом, Lecture 2-й учебный корпус К(П)ФУ, ауд. 1006 No
06 April
17:00–18:20
Задачи поиска для класса NP, Lecture 2-й учебный корпус К(П)ФУ, ауд. 1010 No
07 April
15:20–16:50
Недетерминированные вычисления на логарифмической памяти, Lecture 2-й учебный корпус К(П)ФУ, ауд. 708 No
07 April
17:00–18:20
Недетерминированные вычисления на логарифмической памяти, Lecture 2-й учебный корпус К(П)ФУ, ауд. 907 No
08 April
15:20–16:50
Вероятностные сложностные классы, Lecture 2-й учебный корпус К(П)ФУ, ауд. 216 No
08 April
17:00–18:20
Вероятностные сложностные классы, Lecture 2-й учебный корпус К(П)ФУ, ауд. 216 No