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

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