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

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

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

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

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