Вероятностные алгоритмы

71

При знакомстве с алгоритмами аппроксимации мы все еще были связаны требованием предоставить детерминированное (определенное) решение. Однако в некоторых случаях введение в алгоритм некоторого элемента случайности может помочь в получении вероятного результата, правда при этом уже не приходится говорить о корректности алгоритма или об ограниченности времени его выполнения.

Вероятностное решение задачи о максимальном разрезе

Как оказывается, результат, который дает алгоритм 2-аппроксимации решения задачи о максимальном разрезе из предыдущей статьи, можно получить, случайно выбирая два непересекающихся подмножества (например, для каждой вершины можно подбрасывать монету, чтобы решить, к какому подмножеству ее отнести, A или B). Согласно вероятностному анализу, ожидаемое количество ребер, пересекающих границу подмножеств, будет равно половине общего количества ребер.

Чтобы показать, что ожидаемое количество ребер, пересекающих границу подмножеств, будет равно половине общего количества ребер, рассмотрим вероятность пересечения границы для конкретного ребра (u,v). Существует четыре равновероятные альтернативы (с вероятностью 0,25 каждая): ребро находится в множестве A; ребро находится в множестве B; v находится в множестве A, а u - в множестве B; и v находится в множестве B, а u - в множестве A. То есть, вероятность, что ребро пересекает границу подмножеств равна 0.5.

Для ребра e ожидаемое значение индикаторной переменной Xe (которое равно 1, если ребро пересекает границу) равно 0.5. Согласно линейности ожидания, ожидаемое количество ребер, пересекающих границу, равно половине общего количества ребер в графе.

Обратите внимание, что мы больше не можем доверять результатам единственной попытки, однако существуют приемы уменьшения случайности (такие как метод условных вероятностей), способные увеличить вероятность успеха выполнением некоторого постоянного количества попыток. Мы должны были бы доказать маловероятность того, что количество ребер, пересекающих границу, окажется меньше половины общего количества ребер в графе - сделать это можно было бы с помощью нескольких вероятностных инструментов, включая неравенство Маркова. Но мы не будем делать это здесь.

Тест простоты Ферма

Поиск простых чисел в некотором диапазоне мы уже рассматривали при обсуждении параллельных вычислений, но мы не отвлекались на поиск более удачного алгоритма проверки простоты единственного числа. Эта операция играет важную роль в прикладной криптографии. Например, асимметричный алгоритм шифрования RSA, широко используемый в Интернете, опирается на поиск больших простых чисел для создания ключей шифрования.

В теории чисел существует простое следствие, известное как малая теорема Ферма, согласно которому, если p является простым числом, тогда для всех чисел 1 <= a <= p, число ap-1 делится на p с остатком 1 (обозначается как ap-1 % p = 1 (mod p)). Мы можем воспользоваться этой идеей и на ее основе реализовать вероятностную проверку простоты для произвольного числа n:

  1. Выбрать случайное число в интервале [1,n] и посмотреть, соответствует ли оно малой теореме Ферма (то есть, получается ли остаток 1 при делении ap-1 на p).

  2. Отвергнуть число как составное, если равенство не выполняется.

  3. Принять число как простое или повторять шаг 1, пока не будет достигнут желаемый уровень доверия.

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

К сожалению, существует бесконечное количество чисел (называются числами Кармайкла), не являющихся простыми, но способными пройти любое количество проверок для любого значения a. Хотя числа Кармайкла довольно редки, их наличие все же является веской причиной дополнить тест простоты Ферма дополнительными проверками, выявляющими числа Кармайкла. Одним из примеров может служить тест Миллера-Рабина (Miller-Rabin).

Для составных чисел, не являющихся числами Кармайкла, вероятность выбора числа, для которого равенство не выполняется, больше 0.5. То есть, вероятность принятия составного числа за простое уменьшается экспоненциально с ростом количества итераций: при достаточном количестве итераций можно уменьшить вероятность ошибки до вполне приемлемого уровня.

Пройди тесты
Лучший чат для C# программистов