Вероятностные алгоритм – это алгоритм, в котором помимо детерминированных действий присутствуют случайные события, т.е. алгоритм, который будет зависеть от каких-то вероятностей.
Расширяется класс решаемых задач.
Вероятностная машинаТьюринга (ВМТ) – машина Тьюринга, в которой каждое правило имеет вид:
Каждому переходу соответствует некоторая вероятность, такая что
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: Класс ВРР является более широким, чем Р