Рандомизированный алгоритм

Алгоритм, который использует некоторую степень случайности как часть своей логики или процедуры.

Рандомизированный алгоритм — это алгоритм , который использует степень случайности как часть своей логики или процедуры. Алгоритм обычно использует равномерно случайные биты в качестве вспомогательного входа для управления своим поведением в надежде достичь хорошей производительности в «среднем случае» по всем возможным вариантам случайности, определяемым случайными битами; таким образом, либо время выполнения, либо выход (или оба) являются случайными величинами.

Существует различие между алгоритмами, которые используют случайный ввод, так что они всегда завершаются с правильным ответом, но где ожидаемое время выполнения конечно ( алгоритмы Лас-Вегаса , например, быстрая сортировка ^[1] ), и алгоритмами, которые имеют вероятность выдать неправильный результат ( алгоритмы Монте-Карло , например, алгоритм Монте-Карло для задачи MFAS ^[2] ) или не выдать результат, либо сигнализируя об ошибке, либо не завершаясь. В некоторых случаях вероятностные алгоритмы являются единственным практическим средством решения проблемы. ^[3]

В обычной практике рандомизированные алгоритмы аппроксимируются с использованием генератора псевдослучайных чисел вместо истинного источника случайных битов; такая реализация может отклоняться от ожидаемого теоретического поведения и математических гарантий, которые могут зависеть от существования идеального истинного генератора случайных чисел.

Мотивация

В качестве мотивирующего примера рассмотрим задачу поиска буквы « a » в массиве из n элементов.

Входные данные : массив из n ≥2 элементов, в котором половина — это « a », а другая половина — это « b ».

Вывод : найти « a » в массиве.

Мы приводим две версии алгоритма: алгоритм Лас-Вегаса и алгоритм Монте-Карло .

Алгоритм Лас-Вегаса:

findA_LV ( array A , n ) begin repeat Случайным образом выбрать один элемент из n элементов . пока не будет найден 'a' end               

Этот алгоритм успешен с вероятностью 1. Количество итераций варьируется и может быть произвольно большим, но ожидаемое количество итераций равно

${\displaystyle \lim _{n\to \infty }\sum _{i=1}^{n}{\frac {i}{2^{i}}}=2}$

Поскольку это константа, ожидаемое время выполнения для многих вызовов составляет . (См. нотацию Big Theta ) ${\displaystyle \Theta (1)}$

Алгоритм Монте-Карло:

findA_MC ( array A , n , k ) begin i := 0 repeat Случайным образом выбрать один элемент из n элементов . i := i + 1 пока не будет найдено i = k или 'a' end                            

Если найдено ' a ', алгоритм успешен, в противном случае алгоритм терпит неудачу. После k итераций вероятность нахождения ' a ' равна:

${\displaystyle \Pr[\mathrm {find~a} ]=1-(1/2)^{k}}$

Этот алгоритм не гарантирует успеха, но время выполнения ограничено. Количество итераций всегда меньше или равно k. Принимая k за константу, время выполнения (ожидаемое и абсолютное) равно . ${\displaystyle \Theta (1)}$

Рандомизированные алгоритмы особенно полезны, когда сталкиваются со злонамеренным «противником» или злоумышленником , который намеренно пытается подать в алгоритм неверные входные данные (см. сложность в худшем случае и конкурентный анализ (онлайн-алгоритм) ), например, в дилемме заключенного . Именно по этой причине случайность повсеместно распространена в криптографии . В криптографических приложениях псевдослучайные числа использоваться не могут, поскольку противник может их предсказать, что делает алгоритм фактически детерминированным. Поэтому требуется либо источник действительно случайных чисел, либо криптографически безопасный генератор псевдослучайных чисел . Другая область, в которой случайность присуща, — это квантовые вычисления .

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

Сложность вычислений

Теория вычислительной сложности моделирует рандомизированные алгоритмы как вероятностные машины Тьюринга . Рассматриваются как алгоритмы Лас-Вегаса , так и алгоритмы Монте-Карло , и изучается несколько классов сложности . Самый базовый класс рандомизированной сложности — RP , который является классом задач принятия решений , для которых существует эффективный (полиномиальное время) рандомизированный алгоритм (или вероятностная машина Тьюринга), который распознает экземпляры НЕТ с абсолютной уверенностью и распознает экземпляры ДА с вероятностью не менее 1/2. Дополнительным классом для RP является co-RP. Классы задач, имеющие (возможно, незавершающиеся) алгоритмы со средним временем выполнения случая полиномиальным временем, вывод которых всегда верен, называются классами ZPP .

Класс задач, для которых допускается идентификация как ДА, так и НЕТ-экземпляров с некоторой ошибкой, называется BPP . Этот класс действует как рандомизированный эквивалент P , т.е. BPP представляет собой класс эффективных рандомизированных алгоритмов.

Ранняя история

Сортировка

Быстрая сортировка была открыта Тони Хоаром в 1959 году и впоследствии опубликована в 1961 году. ^[4] В том же году Хоар опубликовал алгоритм quickselect , ^[5] который находит медианный элемент списка за линейное ожидаемое время. До 1973 года оставался открытым вопрос о существовании детерминированного алгоритма с линейным временем. ^[6]

Теория чисел

В 1917 году Генри Кэбурн Поклингтон представил рандомизированный алгоритм, известный как алгоритм Поклингтона, для эффективного нахождения квадратных корней по модулю простых чисел. ^[7] В 1970 году Элвин Берлекамп представил рандомизированный алгоритм для эффективного вычисления корней многочлена над конечным полем. ^[8] В 1977 году Роберт М. Соловей и Фолькер Штрассен открыли рандомизированный тест на простоту за полиномиальное время (т. е. определение простоты числа). Вскоре после этого Майкл О. Рабин продемонстрировал, что тест на простоту Миллера 1976 года также можно превратить в рандомизированный алгоритм за полиномиальное время. В то время не было известно ни одного доказуемо детерминированного алгоритма для проверки простоты за полиномиальное время .

Структуры данных

Одной из самых ранних рандомизированных структур данных является хэш-таблица , которая была представлена ​​в 1953 году Гансом Петером Луном в IBM . ^[9] Хэш-таблица Луна использовала цепочку для разрешения коллизий и также была одним из первых применений связанных списков . ^[9] Впоследствии, в 1954 году, Джин Амдал , Элейн М. Макгроу , Натаниэль Рочестер и Артур Сэмюэл из IBM Research представили линейное зондирование , ^[9] хотя Андрей Ершов независимо высказал ту же идею в 1957 году. ^[9] В 1962 году Дональд Кнут выполнил первый правильный анализ линейного зондирования, ^[9] хотя меморандум, содержащий его анализ, был опубликован гораздо позже. ^[10] Первый опубликованный анализ был предоставлен Конхеймом и Вайсом в 1966 году. ^[11]

Ранние работы по хеш-таблицам либо предполагали доступ к полностью случайной хеш-функции, либо предполагали, что сами ключи являются случайными. ^[9] В 1979 году Картер и Вегман представили универсальные хеш-функции , ^[12] которые, как они показали, можно использовать для реализации цепочечных хеш-таблиц с постоянным ожидаемым временем на операцию.

Ранние работы по рандомизированным структурам данных также вышли за рамки хэш-таблиц. В 1970 году Бертон Говард Блум представил структуру данных с приблизительным членством, известную как фильтр Блума . ^[13] В 1989 году Раймунд Зайдель и Сесилия Р. Арагон представили рандомизированное сбалансированное дерево поиска, известное как treap . ^[14] В том же году Уильям Пью представил еще одно рандомизированное дерево поиска, известное как skip list . ^[15]

Неявное использование в комбинаторике

До популяризации рандомизированных алгоритмов в информатике Пол Эрдёш популяризировал использование рандомизированных конструкций в качестве математического метода для установления существования математических объектов. Этот метод стал известен как вероятностный метод . ^[16] Эрдёш впервые применил вероятностный метод в 1947 году, когда он использовал простую рандомизированную конструкцию для установления существования графов Рамсея. ^[17] Он прославился тем, что использовал гораздо более сложный рандомизированный алгоритм в 1959 году для установления существования графов с высоким обхватом и хроматическим числом. ^{[18] [16]}

Примеры

Быстрая сортировка

Быстрая сортировка — это знакомый, часто используемый алгоритм, в котором случайность может быть полезна. Многие детерминированные версии этого алгоритма требуют O ( n ² ) времени для сортировки n чисел для некоторого четко определенного класса вырожденных входов (например, уже отсортированного массива), при этом конкретный класс входов, который генерирует это поведение, определяется протоколом для выбора опорных элементов. Однако, если алгоритм выбирает опорные элементы равномерно случайным образом, он имеет доказуемо высокую вероятность завершения за время O ( n  log  n ) независимо от характеристик входных данных.

Рандомизированные инкрементные конструкции в геометрии

В вычислительной геометрии стандартный метод построения структуры, такой как выпуклая оболочка или триангуляция Делоне, заключается в случайной перестановке входных точек и последующей вставке их по одной в существующую структуру. Рандомизация гарантирует, что ожидаемое количество изменений в структуре, вызванных вставкой, мало, и поэтому ожидаемое время выполнения алгоритма может быть ограничено сверху. Этот метод известен как рандомизированное инкрементное построение. ^[19]

Мин. разрез

Вход : Граф G ( V , E )

Выход : Разрез , разделяющий вершины на L и R , с минимальным числом ребер между L и R.

Напомним, что стягивание двух узлов, u и v , в (мульти)графе дает новый узел u ' с ребрами, которые являются объединением ребер, инцидентных либо u , либо v , за исключением любого ребра(ей), соединяющих u и v . На рисунке 1 приведен пример стягивания вершины A и B . После стягивания результирующий граф может иметь параллельные ребра, но не содержит петель.

Рисунок 2: Успешный запуск алгоритма Каргера на графе с 10 вершинами. Минимальный разрез имеет размер 3 и обозначен цветами вершин.

Рисунок 1: Сокращение вершины A и B

Базовый алгоритм Каргера ^[20] :

начинать я = 1 повторить  повторить Возьмем случайное ребро (u,v) ∈ E в G замените u и v сокращением u' пока не останется только 2 узла получить соответствующий результат разреза C i я = я + 1 пока я = м вывести минимальный разрез среди C 1 , C 2 , ..., C m . конец

При каждом выполнении внешнего цикла алгоритм повторяет внутренний цикл до тех пор, пока не останется только 2 узла, получается соответствующий разрез. Время выполнения одного выполнения равно , а n обозначает количество вершин. После m выполнений внешнего цикла мы выводим минимальный разрез среди всех результатов. На рисунке 2 показан пример одного выполнения алгоритма. После выполнения мы получаем разрез размером 3. ${\displaystyle O(n)}$

Лемма 1  —  Пусть k будет минимальным размером разреза, и пусть C = { e ₁ , e ₂ , ..., e _k } будет минимальным разрезом. Если во время итерации i ни одно ребро e ∈ C не выбрано для сжатия, то C _i = C .

Доказательство

Если G не связен, то G можно разбить на L и R без какого-либо ребра между ними. Таким образом, минимальный разрез в несвязном графе равен 0. Теперь предположим, что G связен. Пусть V = L ∪ R — разбиение V , индуцированное C  : C = { { u , v } ∈ E  : u ∈ L , v ∈ R } (хорошо определенное, поскольку G связен). Рассмотрим ребро { u , v } графа C . Изначально u , v являются различными вершинами. Пока мы выбираем ребро ⁠ ⁠ ${\displaystyle f\neq e}$ , u и v не объединяются. Таким образом, в конце алгоритма у нас есть два составных узла, покрывающих весь граф, один из которых состоит из вершин L , а другой — из вершин R . Как и на рисунке 2, размер минимального разреза равен 1, а C = {( A , B )}. Если мы не выберем ( A , B ) для сжатия, мы можем получить минимальный разрез.

Лемма 2  —  Если G — мультиграф с p вершинами и минимальный разрез которого имеет размер k , то G имеет по крайней мере pk /2 ребер.

Доказательство

Поскольку минимальный разрез равен k , каждая вершина v должна удовлетворять degree( v ) ≥ k . Следовательно, сумма степеней не менее pk . Но хорошо известно, что сумма степеней вершин равна 2| E |. Лемма следует.

Анализ алгоритма

Вероятность того, что алгоритм сработает, равна 1 − вероятность того, что все попытки потерпят неудачу. По независимости вероятность того, что все попытки потерпят неудачу, равна $${\displaystyle \prod _{i=1}^{m}\Pr(C_{i}\neq C)=\prod _{i=1}^{m}(1-\Pr(C_{i}=C)).}$$

По лемме 1 вероятность того, что C _i = C, является вероятностью того, что ни одно ребро C не будет выбрано во время итерации i . Рассмотрим внутренний цикл и пусть G _j обозначает граф после j стягиваний ребер, где j ∈ {0, 1, …, n − 3} . G _j имеет n − j вершин. Мы используем цепное правило условных возможностей . Вероятность того, что ребро, выбранное на итерации j, не находится в C , учитывая, что ни одно ребро C не было выбрано ранее, равна . Обратите внимание, что G _j по-прежнему имеет минимальный разрез размера k , поэтому по лемме 2 он по-прежнему имеет не менее ребер. ${\displaystyle 1-{\frac {k}{|E(G_{j})|}}}$ ${\displaystyle {\frac {(n-j)k}{2}}}$

Таким образом, . ${\displaystyle 1-{\frac {k}{|E(G_{j})|}}\geq 1-{\frac {2}{n-j}}={\frac {n-j-2}{n-j}}}$

Таким образом, по правилу цепочки вероятность нахождения минимального разреза C равна $${\displaystyle \Pr[C_{i}=C]\geq \left({\frac {n-2}{n}}\right)\left({\frac {n-3}{n-1}}\right)\left({\frac {n-4}{n-2}}\right)\ldots \left({\frac {3}{5}}\right)\left({\frac {2}{4}}\right)\left({\frac {1}{3}}\right).}$$

Отмена дает . Таким образом, вероятность того, что алгоритм сработает, составляет не менее . Для , это эквивалентно . Алгоритм находит минимальный разрез с вероятностью , за время . ${\displaystyle \Pr[C_{i}=C]\geq {\frac {2}{n(n-1)}}}$ ${\displaystyle 1-\left(1-{\frac {2}{n(n-1)}}\right)^{m}}$ ${\displaystyle m={\frac {n(n-1)}{2}}\ln n}$ ${\displaystyle 1-{\frac {1}{n}}}$ ${\displaystyle 1-{\frac {1}{n}}}$ ${\displaystyle O(mn)=O(n^{3}\log n)}$

Дерандомизация

Случайность можно рассматривать как ресурс, как пространство и время. Тогда дерандомизация — это процесс удаления случайности (или использования ее как можно меньшего количества). В настоящее время неизвестно ^{[ по состоянию на? ]} , все ли алгоритмы могут быть дерандомизированы без значительного увеличения времени их выполнения. Например, в вычислительной сложности неизвестно, P = BPP , т. е. мы не знаем, можем ли мы взять произвольный рандомизированный алгоритм, который работает за полиномиальное время с малой вероятностью ошибки, и дерандомизировать его для работы за полиномиальное время без использования случайности.

Существуют специальные методы, которые можно использовать для дерандомизации определенных рандомизированных алгоритмов:

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

Где случайность помогает

Когда модель вычислений ограничивается машинами Тьюринга , в настоящее время остается открытым вопрос о том, позволяет ли способность делать случайный выбор решать некоторые задачи за полиномиальное время, которые не могут быть решены за полиномиальное время без этой способности; это вопрос о том, P = BPP. Однако в других контекстах существуют конкретные примеры задач, где рандомизация дает строгие улучшения.

• На основе начального мотивирующего примера: если задана экспоненциально длинная строка из 2k ^{символов} , половина из которых — «a», а половина — «b», то машине с произвольным доступом в худшем случае потребуется ^{2k −1} поисков, чтобы найти индекс « a» ; если ей разрешено делать случайный выбор, она может решить эту задачу за ожидаемое полиномиальное число поисков.
• Естественным способом выполнения численных вычислений во встроенных системах или киберфизических системах является предоставление результата, который с высокой вероятностью приближается к правильному (или Вероятно Приблизительно Корректное Вычисление (PACC)). Сложная проблема, связанная с оценкой потери расхождения между приближенным и правильным вычислением, может быть эффективно решена путем обращения к рандомизации ^[21]
• В сложности связи равенство двух строк может быть проверено с некоторой надежностью с использованием битов связи с рандомизированным протоколом. Любой детерминированный протокол требует битов, если защищает от сильного противника. ^[22] ${\displaystyle \log n}$ ${\displaystyle \Theta (n)}$
• Объем выпуклого тела можно оценить с помощью рандомизированного алгоритма с произвольной точностью за полиномиальное время. ^[23] Барани и Фюреди показали, что ни один детерминированный алгоритм не может сделать то же самое. ^[24] Это верно безоговорочно, т. е. без опоры на какие-либо предположения теории сложности, предполагая, что выпуклое тело можно опрашивать только как черный ящик.
• Более сложным теоретическим примером места, где случайность, по-видимому, помогает, является класс IP . IP состоит из всех языков, которые могут быть приняты (с высокой вероятностью) посредством полиномиально долгого взаимодействия между всемогущим доказывающим и верификатором, который реализует алгоритм BPP. IP = PSPACE . ^[25] Однако, если требуется, чтобы верификатор был детерминированным, то IP = NP .
• В сети химических реакций (конечном наборе реакций, таких как A+B → 2C + D, работающих на конечном числе молекул) возможность когда-либо достичь заданного целевого состояния из начального состояния разрешима, в то время как даже аппроксимация вероятности когда-либо достичь заданного целевого состояния (используя стандартную основанную на концентрации вероятность того, для какой реакции произойдет следующая) неразрешима. Более конкретно, ограниченная машина Тьюринга может быть смоделирована с произвольно высокой вероятностью правильной работы в течение всего времени, только если используется случайная сеть химических реакций. С простой недетерминированной сетью химических реакций (любая возможная реакция может произойти следующая), вычислительная мощность ограничена примитивными рекурсивными функциями . ^[26]

Смотрите также

• Приблизительный алгоритм подсчета
• Алгоритм Атлантик-Сити
• Богосорт
• Граф–мин эскиз
• HyperLogLog
• Алгоритм Каргера
• Алгоритм Лас-Вегаса
• Алгоритм Монте-Карло
• Принцип отложенного решения
• Вероятностный анализ алгоритмов
• Вероятностная дорожная карта
• Рандомизированные алгоритмы как игры с нулевой суммой

Примечания

1. Hoare, CAR (июль 1961 г.). «Алгоритм 64: Быстрая сортировка». Commun. ACM . 4 (7): 321–. doi :10.1145/366622.366644. ISSN  0001-0782.
2. Куделич, Роберт (2016-04-01). «Рандомизированный алгоритм Монте-Карло для задачи минимальной обратной связи с дугой». Прикладные мягкие вычисления . 41 : 235–246. doi :10.1016/j.asoc.2015.12.018.
3. "При проверке простоты очень больших чисел, выбранных случайным образом, вероятность наткнуться на значение, которое обманет тест Ферма , меньше, чем вероятность того, что космическое излучение заставит компьютер совершить ошибку при выполнении "правильного" алгоритма. Рассмотрение алгоритма как неадекватного по первой причине, но не по второй, иллюстрирует разницу между математикой и инженерией". Хэл Абельсон и Джеральд Дж. Сассман (1996). Структура и интерпретация компьютерных программ . MIT Press , раздел 1.2.
4. Hoare, CAR (июль 1961). "Алгоритм 64: Быстрая сортировка". Сообщения ACM . 4 (7): 321. doi :10.1145/366622.366644. ISSN  0001-0782.
5. Hoare, CAR (июль 1961). «Алгоритм 65: найти». Сообщения ACM . 4 (7): 321–322. doi :10.1145/366622.366647. ISSN  0001-0782.
6. Блум, Мануэль; Флойд, Роберт У.; Пратт, Воган; Ривест, Рональд Л.; Тарьян, Роберт Э. (август 1973 г.). «Временные рамки для выбора». Журнал компьютерных и системных наук . 7 (4): 448–461. doi :10.1016/S0022-0000(73)80033-9.
7. Уильямс, ХК ; Шаллит, ДЖО (1994), «Разложение целых чисел до компьютеров», в Gautschi, Вальтер (ред.), Математика вычислений 1943–1993: полвека вычислительной математики; Статьи симпозиума по численному анализу и мини-симпозиума по вычислительной теории чисел, состоявшихся в Ванкувере, Британская Колумбия, 9–13 августа 1993 г. , Труды симпозиумов по прикладной математике, т. 48, Amer. Math. Soc., Providence, RI, стр. 481–531, doi :10.1090/psapm/048/1314885, ISBN 978-0-8218-0291-5, г-н  1314885; см. стр. 504, «Возможно, Поклингтон также заслуживает признания как изобретатель рандомизированного алгоритма».
8. Berlekamp, ​​ER (1971). "Разложение многочленов над большими конечными полями". Труды второго симпозиума ACM по символическим и алгебраическим манипуляциям - SYMSAC '71 . Лос-Анджелес, Калифорния, США: ACM Press. стр. 223. doi :10.1145/800204.806290. ISBN 9781450377867. S2CID  6464612.
9. Кнут, Дональд Э. (1998). Искусство программирования, том 3: (2-е изд.) сортировка и поиск. США: Addison Wesley Longman Publishing Co., Inc. стр. 536–549. ISBN 978-0-201-89685-5.
10. Кнут, Дональд (1963), Заметки об «открытом» адресовании , архивировано из оригинала 2016-03-03
11. Конхейм, Алан Г.; Вайс, Бенджамин (ноябрь 1966 г.). «Дисциплина занятости и ее применение». Журнал SIAM по прикладной математике . 14 (6): 1266–1274. doi :10.1137/0114101. ISSN  0036-1399.
12. Картер, Дж. Лоуренс; Вегман, Марк Н. (1979-04-01). «Универсальные классы хэш-функций». Журнал компьютерных и системных наук . 18 (2): 143–154. doi : 10.1016/0022-0000(79)90044-8 . ISSN  0022-0000.
13. Блум, Бертон Х. (июль 1970 г.). «Компромиссы пространства/времени в хэш-кодировании с допустимыми ошибками». Сообщения ACM . 13 (7): 422–426. doi : 10.1145/362686.362692 . ISSN  0001-0782. S2CID  7931252.
14. Арагон, CR; Зайдель, RG (октябрь 1989). «Рандомизированные деревья поиска». 30-й ежегодный симпозиум по основам компьютерной науки . стр. 540–545. doi :10.1109/SFCS.1989.63531. ISBN 0-8186-1982-1.
15. Pugh, William (апрель 1989). Concurrent Maintenance of Skip Lists (PS, PDF) (технический отчет). Кафедра компьютерных наук, Университет Мэриленда. CS-TR-2222.
16. Alon, Noga (2016). Вероятностный метод. Джоэл Х. Спенсер (четвертое изд.). Хобокен, Нью-Джерси. ISBN 978-1-119-06195-3. OCLC  910535517.{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
17. П. Эрдёш: Некоторые замечания по теории графов, Bull. Amer. Math. Soc. 53 (1947), 292--294 MR 8,479d; Zentralblatt 32,192.
18. Эрдёш, П. (1959). «Теория графов и вероятность». Канадский математический журнал . 11 : 34–38. doi : 10.4153/CJM-1959-003-9 . ISSN  0008-414X. S2CID  122784453.
19. Сейдель Р. Обратный анализ рандомизированных геометрических алгоритмов.
20. Каргер, Дэвид Р. (1999). «Случайная выборка в задачах проектирования разрезов, потоков и сетей». Математика исследования операций . 24 (2): 383–413. CiteSeerX 10.1.1.215.794 . doi :10.1287/moor.24.2.383. 
21. Алиппи, Чезаре (2014), Интеллект для встроенных систем , Springer, ISBN 978-3-319-05278-6.
22. Кушилевиц, Эяль; Нисан, Ноам (2006), Сложность коммуникации , Cambridge University Press, ISBN 9780521029834. Для детерминированной нижней границы см. стр. 11; для логарифмической рандомизированной верхней границы см. стр. 31–32.
23. Дайер, М.; Фриз, А.; Каннан, Р. (1991), «Случайный полиномиальный алгоритм для аппроксимации объема выпуклых тел» (PDF) , Журнал ACM , 38 (1): 1–17, doi :10.1145/102782.102783, S2CID  13268711
24. Фюреди, З.; Барани, И. (1986), «Вычислить объем сложно», Труды 18-го симпозиума ACM по теории вычислений (Беркли, Калифорния, 28–30 мая 1986 г.) (PDF) , Нью-Йорк, штат Нью-Йорк: ACM, стр. 442–447, CiteSeerX 10.1.1.726.9448 , doi : 10.1145/12130.12176, ISBN  0-89791-193-8, S2CID  17867291
25. Шамир, А. (1992), «IP = PSPACE», Журнал ACM , 39 (4): 869–877, doi : 10.1145/146585.146609 , S2CID  315182
26. Кук, Мэтью ; Соловейчик, Дэвид; Уинфри, Эрик ; Брук, Иегошуа (2009), «Программируемость сетей химических реакций», в Кондон, Энн ; Харел, Дэвид ; Кок, Йост Н.; Саломаа, Арто ; Уинфри, Эрик (ред.), Алгоритмические биопроцессы (PDF) , Серия Natural Computing, Springer-Verlag, стр. 543–584, doi :10.1007/978-3-540-88869-7_27, ISBN 978-3-540-88868-0.

Ссылки

• Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стайн . Введение в алгоритмы , второе издание. MIT Press и McGraw–Hill, 1990. ISBN 0-262-03293-7 . Глава 5: Вероятностный анализ и рандомизированные алгоритмы, стр. 91–122. 
• Дирк Драхейм. «Семантика вероятностного типизированного лямбда-исчисления (семантика цепи Маркова, поведение завершения и денотационная семантика)». Springer, 2017.
• Джон Клейнберг и Эва Тардос . Разработка алгоритмов . Глава 13: «Рандомизированные алгоритмы».
• Fallis, D. (2000). «Надежность рандомизированных алгоритмов». Британский журнал философии науки . 51 (2): 255–271. doi :10.1093/bjps/51.2.255.
• М. Митценмахер и Э. Упфал . Вероятность и вычисления: рандомизированные алгоритмы и вероятностный анализ . Cambridge University Press, Нью-Йорк (NY), 2005.
• Раджив Мотвани и П. Рагхаван. Рандомизированные алгоритмы . Cambridge University Press, Нью-Йорк (NY), 1995.
• Раджив Мотвани и П. Рагхаван. Рандомизированные алгоритмы. Обзор рандомизированных алгоритмов.
• Христос Пападимитриу (1993), Computational Complexity (1-е изд.), Addison Wesley, ISBN 978-0-201-53082-7Глава 11: Рандомизированные вычисления, стр. 241–278.
• Рабин, Майкл О. (1980). «Вероятностный алгоритм проверки простоты». Журнал теории чисел . 12 : 128–138. doi : 10.1016/0022-314X(80)90084-0 .
• AA Tsay, WS Lovejoy, David R. Karger, Случайная выборка в задачах проектирования разрезов, потоков и сетей , Математика исследования операций, 24(2):383–413, 1999.
• «Рандомизированные алгоритмы для научных вычислений» (RASC), OSTI.GOV (10 июля 2021 г.).