Вероятностные алгоритмы. Класс BPP. Вероятностный алгоритм поиска максимального элемента

Вероятностные алгоритм – это алгоритм, в котором помимо детерминированных действий присутствуют случайные события, т.е. алгоритм, который будет зависеть от каких-то вероятностей.

Расширяется класс решаемых задач.

Вероятностная машинаТьюринга (ВМТ) – машина Тьюринга, в которой каждое правило имеет вид:

Каждому переходу соответствует некоторая вероятность, такая что

BPP- класс – (для задач распознавания) задача распознавания Q принадлежит классу BPP, если существует ВМТ М и полином р(), а также некоторое вещественное число c> 0,5, такие что машина М остановится за время не превосходящее p(|x|):

· Если Q(x)=1, то ВМТ М даст ответ «да» с вероятностью больше с

· Если Q(x)=0, то ВМТ М даст ответ «нет» с вероятностью больше с.

Замечание:

Если Q € BPP, то многократным запуском ВМТ можно добиться получения правильного ответа с вероятностью 1-q^n, где q=2*sqrt(c(1-c)), n – количество запусков ВМТ.

Чем больше с, тем быстрее это выражение будет стремиться к 1.

Пример: Вероятностный алгоритм поиска max элемента в массиве

Пусть k сравнений заменены на «подбрасывание монеты», тогда оптимальный вероятностный алгоритм получается из обычного линейного алгоритма путем замены k первых сравнений. В этом случае вероятность правильного ответа р определяется по формуле р=(n-k)/n

Утверждение: вероятность (n-k)/n является неулучшаемой точной верхней оценкой вероятности правильного решения задачи поиска max элемента с заменой k сравнений.

Утверждение 1: Класс P содержится в классе ВРР

Утверждение 2: Класс ВРР является более широким, чем Р