63
правки
Изменения
→Примеры рандомизированных алгоритмов
==Примеры рандомизированных алгоритмов==
===Проверка числа на простот ===
====Задача====
Дано целое число <tex>N</tex>. Определить является ли оно простым.
====Алгоритм====
Нам нужен детерминированный алгоритм работающий за <tex>p(\log|n|)</tex>, где <tex>p</tex> {{---}} полином. Однако не существует такого эффективного алгоритма. Однако существует эффективный рандомизированный алгоритм.
Формально, нам нужно проверить принадлежит ли число языку <tex>PRIMES = \{ \llcorner N \lrcorner : N -</tex> простое <tex>\}</tex>.
===Проверка двудольного графа на существование в нем полного паросочетания===
