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

Вероятностные алгоритмы это алгоритмы, которые в своей работе могут использовать значения случайных последовательностей. Различают два вида вероятностных алгоритмов: вероятностные алгоритмы типа Лас-Вегас и вероятностные алгоритмы типа Монте-Карло. Первый тип вероятностных алгоритмов дает всегда правильный результат обработки данных, но время работы может варьироваться в зависимости от структуры исходных данных. Типичным примером Лас-Вегас алгоритмов является вероятностный алгоритм быстрой сортировки (Quicksort). Второй тип алгоритмов предусматривает возможность ошибочной работы алгоритма (как правило, с малой вероятностью), но при этом позволяет экономить время вычислений по сравнению с детерминированными алгоритмами. Примерами Монте-Карло алгоритмов являются алгоритмы проверки совпадений различного вида (“checking identities”).

В рамках курса Вероятностные модели вычислений будут даны понятия моделей вероятностных вычислений, их сравнительных характеристик с детерминированными моделями вычислений. Большая часть времени будет посвящена алгоритмам типа Монте- Карло, вопросам checking identities и их реализации в различных моделях вычислений: автоматах, коммуникационных вычислений. Будет проведен сравнительный анализ вероятностных и детерминированных моделей вычислений для checking identities.

Дата и время Название Место Материалы
23 октября
14:00–15:30
Лекция 1, лекция 2-й учебный корпус К(П)ФУ, ауд 1008 Нет
23 октября
17:20–18:50
Лекция 2, лекция 2-й учебный корпус К(П)ФУ, ауд 1211 Нет
24 октября
15:40–17:10
Лекция 3, лекция Физический корпус КФУ, ауд. 305 Нет
24 октября
17:20–18:50
Лекция 4, лекция КФУ, Физический корпус, Ауд 902 Нет
30 октября
14:00–15:30
Лекция 5, лекция 2-й учебный корпус К(П)ФУ, ауд 1008 Нет
30 октября
17:20–18:50
Лекция 6, лекция 2-й учебный корпус К(П)ФУ, ауд 1211 Нет
31 октября
15:40–17:10
Лекция 7, лекция Физический корпус, Ауд 117 Нет
31 октября
17:20–18:50
Лекция 8, лекция КФУ, Физический корпус, Ауд 902 Нет