Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Тип рандомизированного алгоритма
Type of randomized algorithm
В информатике алгоритм Монте-Карло — это рандомизированный алгоритм, результат работы которого может быть неверным с определённой (обычно небольшой) вероятностью. Два примера таких алгоритмов — алгоритм Каргера — Стейна и алгоритм Монте-Карло для задачи о минимальном наборе обратных рёбер. Название отсылает к казино Монте-Карло в Княжестве Монако, всемирно известному как символ азартных игр. Термин «Монте-Карло» впервые был предложен Николасом Метрополисом в 1947 году. Алгоритмы Лас-Вегаса являются двойственными к алгоритмам Монте-Карло и никогда не возвращают неверный ответ. Однако они могут совершать случайный выбор в процессе своей работы. В результате время выполнения может меняться от запуска к запуску, даже при одинаковых входных данных. Если существует процедура проверки корректности ответа, полученного алгоритмом Монте-Карло, и вероятность получения верного ответа ограничена снизу положительным числом, то с вероятностью один, многократный запуск алгоритма с проверкой результатов в конечном итоге даст верный ответ. То, является ли этот процесс алгоритмом Лас-Вегаса, зависит от того, считается ли завершение с вероятностью один соответствующим определению.
In computing, a Monte Carlo algorithm is a randomized algorithm whose output may be incorrect with a certain (typically small) probability. Two examples of such algorithms are the Karger–Stein algorithm and the Monte Carlo algorithm for minimum feedback arc set. The name refers to the Monte Carlo casino in the Principality of Monaco, which is well known around the world as an icon of gambling. The term "Monte Carlo" was first introduced in 1947 by Nicholas Metropolis. Las Vegas algorithms are a dual of Monte Carlo algorithms and never return an incorrect answer. However, they may make random choices as part of their work. As a result, the time taken might vary between runs, even with the same input. If there is a procedure for verifying whether the answer given by a Monte Carlo algorithm is correct, and the probability of a correct answer is bounded above zero, then with probability one, running the algorithm repeatedly while testing the answers will eventually give a correct answer. Whether this process is a Las Vegas algorithm depends on whether halting with probability one is considered to satisfy the definition.
Односторонняя и двусторонняя ошибки
Хотя ответ, возвращаемый детерминированным алгоритмом, всегда ожидается как правильный, это не так для алгоритмов Монте-Карло. Для задач принятия решений эти алгоритмы обычно классифицируются как ложно-смещенные или истинно-смещенные. Ложно-смещенный алгоритм Монте-Карло всегда корректен, когда он возвращает ложь; истинно-смещенный алгоритм всегда корректен, когда он возвращает истину. В то время как это описывает алгоритмы с односторонними ошибками, другие могут не иметь смещения; говорят, что у них двухсторонние ошибки. Ответ, который они предоставляют (истина или ложь), будет неверным или правильным с некоторой ограниченной вероятностью. Например, тест простоты Соловая-Штрассена используется для определения, является ли данное число простым. Он всегда отвечает истиной для простых чисел; для составных чисел он отвечает ложью с вероятностью не менее 1/2 и истиной с вероятностью менее 1/2. Таким образом, ложные ответы алгоритма гарантированно правильны, в то время как истинные ответы остаются неопределенными; такой алгоритм называется 1/2-правильным ложно-смещенным алгоритмом.
While the answer returned by a deterministic algorithm is always expected to be correct, this is not the case for Monte Carlo algorithms. For decision problems, these algorithms are generally classified as either false biased or true biased. A false biased Monte Carlo algorithm is always correct when it returns false; a true biased algorithm is always correct when it returns true. While this describes algorithms with one sided errors, others might have no bias; these are said to have two sided errors. The answer they provide (either true or false) will be incorrect, or correct, with some bounded probability. For instance, the Solovay–Strassen primality test is used to determine whether a given number is a prime number. It always answers true for prime number inputs; for composite inputs, it answers false with probability at least 1/2 and true with probability less than 1/2. Thus, false answers from the algorithm are certain to be correct, whereas the true answers remain uncertain; this is said to be a 1/2 correct false biased algorithm.
Усиление
Для алгоритма Монте-Карло с односторонними ошибками вероятность ошибки может быть уменьшена (а вероятность правильного ответа увеличена) путем k-кратного запуска алгоритма. Рассмотрим еще раз алгоритм Соловая-Штрассена, который выдает правильный ответ с вероятностью 1/2, и в противном случае – ошибочный. Можно запускать этот алгоритм несколько раз, возвращая ложный ответ, если он выдает ошибочный результат хотя бы в одной из k итераций, и в противном случае возвращая истинный. Таким образом, если число простое, то ответ всегда правильный, а если число составное, то ответ будет правильным с вероятностью не менее 1−(1−1/2)k = 1−2−k. Для алгоритмов Монте-Карло с двусторонней ошибкой вероятность ошибки также может быть уменьшена путем k-кратного запуска алгоритма и возврата значения, полученного большинством голосов.
For a Monte Carlo algorithm with one sided errors, the failure probability can be reduced (and the success probability amplified) by running the algorithm k times. Consider again the Solovay–Strassen algorithm which is 1/2 correct false biased. One may run this algorithm multiple times returning a false answer if it reaches a false response within k iterations, and otherwise returning true. Thus, if the number is prime then the answer is always correct, and if the number is composite then the answer is correct with probability at least 1−(1−1/2)k = 1−2−k. For Monte Carlo decision algorithms with two sided error, the failure probability may again be reduced by running the algorithm k times and returning the majority function of the answers.
Классы сложности
Класс сложности BPP описывает задачи принятия решений, которые могут быть решены алгоритмами Монте-Карло за полиномиальное время с ограниченной вероятностью двусторонней ошибки, а класс сложности RP описывает задачи, которые могут быть решены алгоритмом Монте-Карло с ограниченной вероятностью односторонней ошибки: если правильный ответ – ложь, алгоритм всегда так и отвечает, но он может ошибочно ответить «ложь» для некоторых случаев, когда правильный ответ – истина. В отличие от этого, класс сложности ZPP описывает задачи, разрешимые алгоритмами Лас-Вегаса с ожидаемым полиномиальным временем работы. ZPP ⊆ RP ⊆ BPP, но неизвестно, различны ли какие-либо из этих классов сложности друг от друга; то есть, алгоритмы Монте-Карло могут обладать большей вычислительной мощностью, чем алгоритмы Лас-Вегаса, но это не доказано. Таким образом, недостаток SO был устранен, и уверенность в решении была достигнута.
The complexity class BPP describes decision problems that can be solved by polynomial time Monte Carlo algorithms with a bounded probability of two sided errors, and the complexity class RP describes problems that can be solved by a Monte Carlo algorithm with a bounded probability of one sided error: if the correct answer is false, the algorithm always says so, but it may answer false incorrectly for some instances where the correct answer is true. In contrast, the complexity class ZPP describes problems solvable by polynomial expected time Las Vegas algorithms. ZPP ⊆ RP ⊆ BPP, but it is not known whether any of these complexity classes is distinct from each other; that is, Monte Carlo algorithms may have more computational power than Las Vegas algorithms, but this has not been proven. In this way, "drawback of SO has been mitigated, and a confidence in a solution has been established."