63
правки
Изменения
→Алгоритм
==Примеры рандомизированных алгоритмов==
===Позиция числа в массиве===
====Задача====
Задан массив <tex>A</tex> в котором половина чисел единицы, а половина нули. Найти позицию какой-нибудь единицы.
====Алгоритм====
Выбираем случайную позицию и проверяем стоит ли на этой позиции единица. Если да то берем если нет про продолжаем пока не найдем. Ассимптотика {{---}} <tex>\lim\limits_{n \to \infty}\sum\limits_{i=1}^n \frac{i}{2^i} = 2</tex>
Хоть у этого алгоритма такая же ассимптотика как и у детерминированного алгоритма, который просто начиная с первой позиции перебирает все числа, у рандомизированного алгоритма есть приемущество. Для детерминированного алгоритма можно подобрать такой вход на котором он будет гарантированно работать плохо. А для рандомизированного нельзя.
===Проверка числа на простоту ===
Дано целое число <tex>N</tex>. Определить является ли оно простым.
====Алгоритм====
Формально, нам нужно проверить принадлежит ли число языку <tex>PRIMES = \{ \llcorner N \lrcorner : N -</tex> простое <tex>\}</tex>. Предоставим алгоритм который покажет что <tex>PRIMES \in BPP</tex>. Для каждого <tex>N</tex> и <tex>A \in [1 .. N - 1]</tex>, определим символ Лежандра:
{{---}} Для каждого нечетного простого <tex>N</tex> и <tex>A \in [1 .. N - 1]</tex> выполняется: <tex>QR_N(A) = A^{\frac{N - 1}{2}} (mod \ N)</tex> {{---}} формула Лежандра
{{---}} Для Также доказано что для каждого нечетного составного <tex>N, |\{A \in [1\,..\,N - 1]: gcd(N, A) = 1</tex> и <tex>(\frac{N}{A}) = A^{\frac{N - 1}{2}}(mod \ N)\}| \le \frac{N}{2}</tex>
