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>
{{---}} Для каждого нечетного простого <tex>N, A</tex> определим симол Якоби и <tex>(\frac{N}{A})</tex> как <tex>\prod\limits_{i=in [1}^k QR_{P(i)}(A)</tex>, где <tex>P_1, ... , P_kN - 1]</tex> это простые делители (не обязательно различные) числа выполняется: <tex>N QR_N(N A) = A^{\prod\limits_frac{i=N - 1}^k P_i)</tex>. Cуществует алгоритм для вычисления символа Якоби за <tex>O{2}} (logA mod \cdot logNN)</tex>. Можно посмотреть на [https://en.wikipedia.org/wiki/Jacobi_symbol википедии]{{---}} формула Лежандра
{{---}} Для Также доказано что для каждого нечетного составного <tex>N, |\{A \in [1\,..\,N - 1]: gcd(N, A) = 1 \ \land \ </tex> и <tex>(\frac{N}{A}) = A^{\frac{N - 1}{2}}(mod \ N)\}| \le \frac{1N}{2}</tex> <tex>\,| \{A \in [N - 1]: gcd(N, A) = 1\}|</tex>
Мы решим эту проблему с помощью вычислений по модулю <tex>k</tex>, где <tex>k</tex> - слуйчайное число <tex>\le 2^{2^m}</tex>. Таким образом вместо вычисления <tex>y = C(x_1, x_2, ..., x_m)</tex>, мы считаем значение <tex>y \ (mod \ k)</tex>. Очевидно что если <tex>y = 0</tex>, то <tex>y \ mod \ k = 0</tex>. Утверждается что если <tex>y \ne 0</tex>, то с вероятностью хотя бы <tex>\delta = \frac{1}{10m}</tex>, <tex>k</tex> не делится на <tex>y</tex>. Действительно, пусть <tex>y \ne 0</tex> и пусть <tex>S = {p_1, ..., p_l}</tex> {{---}} множество простых делителей <tex>y</tex>. Достаточно показать что с вероятностью <tex>\ge \delta</tex>, <tex>k</tex> будет простым числов <tex>\notin S</tex>. По теореме о простых числах верятность того что <tex>k</tex> будет простым числом <tex>\ge \frac{1}{5m} = 2 \delta</tex>. А так как <tex>y</tex> может иметь максимум <tex>log(y) \le 5m2^m</tex> различных простых делителей, вероятность того что <tex>k \in S \le \frac{5m2^m}{2^{2^m}} << \frac{1}{[10m]} = \delta</tex>. Объединяя эти факты получаем что с вероятнотью хотя бы <tex>\delta</tex>, <tex>y</tex> не будет делиться на <tex>k</tex>.
== См. также ==
* [[Вероятностные вычисления. Вероятностная машина Тьюринга]]
*[[Лемма Шварца-Зиппеля]]
== Литература ==
* [http://www.cs.princeton.edu/theory/complexity/ Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach]
== Ссылки ==
* [https://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D0%BC%D0%B2%D0%BE%D0%BB_%D0%AF%D0%BA%D0%BE%D0%B1%D0%B8 Символ Якоби]
* [https://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D0%BC%D0%B2%D0%BE%D0%BB_%D0%9B%D0%B5%D0%B6%D0%B0%D0%BD%D0%B4%D1%80%D0%B0 Символ Лежандра]
* [https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE_%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B8_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%8B%D1%85_%D1%87%D0%B8%D1%81%D0%B5%D0%BB Теорема о распределении простых чисел]
* [https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D1%81%D1%82_%D0%A1%D0%BE%D0%BB%D0%BE%D0%B2%D0%B5%D1%8F_%E2%80%94_%D0%A8%D1%82%D1%80%D0%B0%D1%81%D1%81%D0%B5%D0%BD%D0%B0 Тест Соловея — Штрассена]
[[Категория: Теория сложности]]
