랜덤화 알고리즘

랜덤화 알고리즘은 논리 또는 절차의 일부로 랜덤성의 정도를 사용하는 알고리즘입니다.알고리즘은 일반적으로 랜덤비트에 의해 결정되는 랜덤의 모든 가능한 선택에 걸쳐 "평균적인 경우"에서 양호한 성능을 얻을 수 있기를 바라며 동작을 안내하는 보조 입력으로 균일하게 랜덤비트를 사용합니다.따라서 실행시간 또는 출력(또는 둘 다)은 랜덤 변수입니다.

어느 항상 정확한 대답으로 종료되는 랜덤 입력을 사용한 알고리즘이 어디 것으로 예상되는 시간은 유한(라스 베이거스 알고리즘, 예를 들면 Quicksort[1]), 그리고 예를 들어 델 몬테 카를로 알고리즘, 몬테카를로 알고리즘은 부정확한 결과를 낳길 가능성을 가진 알고리즘을 구별하는 데 있다. 위해서또는^[2] 실패 신호를 보내거나 종료에 실패하여 결과를 생성하지 못할 수 있습니다.경우에 따라서는 확률적 알고리즘이 ^[3]문제 해결을 위한 유일한 실질적인 수단이다.

일반적으로 랜덤화된 알고리즘은 랜덤 비트의 진정한 소스 대신 의사 난수 발생기를 사용하여 근사된다. 이러한 구현은 이상적인 진정한 난수 발생기의 존재에 따라 달라질 수 있는 예상 이론적인 행동 및 수학적 보증에서 벗어날 수 있다.

동기

동기 부여의 예로서 n개의 요소 배열에서 'a'를 찾는 문제를 생각해 보자.

입력: n22 요소의 배열로, 절반은 'a'이고 나머지 절반은 'b'입니다.

출력: 배열에서 'a'를 찾습니다.

두 가지 버전의 알고리즘을 제공합니다. 하나는 라스베이거스 알고리즘이고 다른 하나는 몬테카를로 알고리즘입니다.

라스베이거스 알고리즘:

검색 A_LV(배열 A, n) 시작한다.     따라하다         랜덤으로 선택한다. 하나. 요소 나가. 의 n 요소들.     까지 'a' 이 찾았다 끝.

이 알고리즘은 확률 1로 성공합니다.반복 횟수는 다양하며 임의로 클 수 있지만 예상되는 반복 횟수는 다음과 같습니다.

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

일정하기 때문에 많은 콜에서 예상되는 실행시간은 $\Theta (1)$ ( $displaystyle \Theta$ (1) 입니다.('빅 Theta 표기법' 참조).

몬테카를로 알고리즘:

검색 A_MC(배열 A, n, k) 시작한다.     i := 0     따라하다         랜덤으로 선택한다. 하나. 요소 나가. 의 n 요소들.         i := i + 1     까지 i = k 또는 'a' 이 찾았다 끝.

'a'가 발견되면 알고리즘이 성공하고 그렇지 않으면 알고리즘이 실패합니다.k회 반복 후 'a'를 찾을 확률은 다음과 같습니다.

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

이 알고리즘이 성공을 보장하지는 않지만 실행 시간은 한정되어 있습니다.반복 횟수는 항상 k회 이하입니다.k를 일정하게 하려면 (예상 및 절대) $\Theta (1)$ ( $\Theta (1)$ ) \ $displaystyle$ \ $Theta$ ( $1)$

랜덤화 알고리즘은 특히 악의적인 "역행" 또는 공격자가 의도적으로 알고리즘에 잘못된 입력을 제공하려고 할 때 유용합니다(최악의 경우 복잡성과 경쟁 분석(온라인 알고리즘 참조).이런 이유로 암호학에서는 무작위성이 어디에나 존재한다.암호 어플리케이션에서는 상대방이 예측하기 때문에 의사 난수를 사용할 수 없기 때문에 알고리즘을 효과적으로 결정적으로 만들 수 없습니다.따라서 진정한 난수의 소스 또는 암호학적으로 안전한 의사 난수 발생기가 필요하다.랜덤성이 내재되어 있는 또 다른 분야는 양자 컴퓨팅입니다.

위의 예에서 Las Vegas 알고리즘은 항상 정답을 출력하지만 실행 시간은 랜덤 변수입니다.몬테카를로 알고리즘(시뮬레이션을 위한 몬테카를로 방법과 관련)은 입력 크기와 파라미터 k에 의해 제한될 수 있는 함수의 시간 내에 완료가 보장되지만, 약간의 오차 확률은 허용된다.라스베이거스 알고리즘은 (마코프 부등식을 통해) 지정된 시간 내에 완료되지 않을 경우 임의의 부정확한 답을 출력함으로써 몬테카를로 알고리즘으로 변환할 수 있음을 관찰하십시오.반대로 답이 맞는지 확인하기 위한 효율적인 검증 절차가 존재하는 경우 몬테카를로 알고리즘을 정답을 얻을 때까지 반복적으로 실행함으로써 몬테카를로 알고리즘을 라스베이거스 알고리즘으로 변환할 수 있다.

계산의 복잡성

계산 복잡도 이론은 확률론적 튜링 기계로서 무작위화된 알고리즘을 모델링합니다.라스베이거스와 몬테 카를로 알고리즘이 모두 고려되며, 몇 가지 복잡도 클래스가 연구된다.가장 기본적인 랜덤화 복잡도 클래스는 RP로, 절대 확실성으로 NO 인스턴스를 인식하고 최소 1/2 확률로 YES 인스턴스를 인식하는 효율적인(다항 시간) 랜덤화 알고리즘(또는 확률론적 튜링 머신)이 존재하는 의사결정 문제의 클래스이다.RP의 보완 클래스는 co-RP입니다.출력이 항상 올바른 다항식 시간 평균 케이스 실행 시간을 갖는 (종료되지 않을 가능성이 있는) 알고리즘을 가진 문제 클래스는 ZPP에 있다고 합니다.

YES 인스턴스와 NO 인스턴스를 모두 특정할 수 있는 문제의 클래스를 BPP라고 부릅니다.이 클래스는 P의 랜덤화 등가물로 작용한다. 즉, BPP는 효율적인 랜덤화 알고리즘의 클래스를 나타낸다.

역사

수 이론에서 랜덤화 알고리즘의 중요한 연구 행은 1917년 포클링턴의 알고리즘으로 거슬러 올라갈 수 있는데, 포클링턴 알고리즘은 제곱근 모듈로 소수를 ^[4]찾아냅니다.수 이론에서 무작위 알고리즘의 연구는 로버트 M에 의한 1977년 무작위 원시성 테스트(즉, 숫자의 원시성 결정)의 발견에 의해 촉진되었다. 솔로베이와 볼커 스트라센입니다곧이어 마이클 O. 라빈은 1976년 밀러의 원시성 테스트가 랜덤화 알고리즘으로 바뀔 수 있다는 것을 증명했다.그 당시에는 원시성에 대한 실질적인 결정론적 알고리즘이 알려져 있지 않았다.

밀러-라빈 원시성 검정은 k가 "n의 합성도에 대한 증인"이라고 표현될 수 있는 두 양의 정수 k와 n 사이의 이항 관계에 의존한다.라는 것을 알 수 있다

n의 구성도에 대한 증인이 있는 경우, n은 합성이다(즉, n은 소수가 아니다).
n이 합성인 경우 n보다 작은 자연수의 적어도 4분의 3은 그 합성성의 증명이 된다.
k와 n이 주어졌을 때 k가 n의 합성성의 증인인지 아닌지를 확인하는 빠른 알고리즘이 있다.

이는 primity 문제가 Co-RP에 있음을 시사하는 것에 주의해 주십시오.

합성수 n보다 작은 100개의 숫자를 무작위로 선택하면 그러한 "목격자"를 찾지 못할 확률은 (1/4)¹⁰⁰이므로 대부분의 실용적인 목적을 위해 이 검정이 좋은 원시성 검정입니다.n이 크면 실용적인 다른 검정이 없을 수 있습니다.충분히 독립적인 테스트를 수행함으로써 오차 확률을 임의의 정도로 줄일 수 있습니다.

따라서, 약간의 주의를 기울이면 오차 확률을 천문학적으로 줄일 수 있기 때문에, 실제로는 작은 오차 확률을 받아들이는 것과 관련된 패널티는 없습니다.실제로 결정론적 다항식 시간 우선성 테스트가 발견되었음에도 불구하고(AKS 우선성 테스트 참조), 암호 소프트웨어의 오래된 확률론적 테스트를 대체하지 않았으며 예측 가능한 미래에도 그렇게 할 것으로 예상되지 않는다.

예

퀵소트

QuickSort는 랜덤성을 유용하게 사용할 수 있는 익숙한 알고리즘입니다.이 알고리즘의 많은 결정론적 버전은 피벗 선택을 위한 프로토콜에 의해 정의된 이 동작을 생성하는 특정 입력 클래스와 함께 잘 정의된 일부 퇴화 입력 클래스(이미 정렬된 배열 등)에 대해 n개의 숫자를 정렬하는 O(n²) 시간을 필요로 한다.그러나 알고리즘이 피벗 요소를 랜덤으로 균일하게 선택한다면 입력의 특성에 관계없이 O(n log n) 시간 내에 종료할 가능성이 높아진다.

기하학에서 무작위 증분 구성

계산기하학에서 볼록한 선체나 델라우네 삼각측량 같은 구조물을 만드는 표준기술은 입력점을 무작위로 배치한 후 하나씩 기존 구조물에 삽입하는 것이다.랜덤화에 의해 삽입에 의해 발생하는 구조에 대한 예상 변경 수가 적어지기 때문에 알고리즘의 예상 실행 시간을 위에서부터 제한할 수 있습니다.이 기술은 무작위 증분 ^[5]구성이라고 알려져 있습니다.

최소 컷

입력: 그래프 G(V,E)

출력: 정점을 L과 R로 분할하고 최소 에지 수를 L과 R 사이에 둔 절단입니다.

(멀티) 그래프에서 두 개의 노드 u와 v의 수축은 u와 v를 연결하는 모든 모서리를 제외하고 u 또는 v에 입사하는 모서리를 가진 새로운 노드 u를 생성한다는 것을 기억하십시오. 그림 1은 정점 A와 B의 수축의 예를 보여줍니다.수축 후 그래프에 평행 가장자리가 있을 수 있지만 자체 루프는 포함되지 않습니다.

그림 2: 10-vertex 그래프에서의 Karger 알고리즘의 정상적인 실행.최소 절단은 크기가 3이고 정점 색상으로 표시됩니다.

그림 1: 정점 A와 B의 수축

카거의 기본^[6] 알고리즘:

begin i = 1 repeat G의 임의 에지(u,v) e E를 2개의 노드만 남아 있는 경우 해당 절단_i 결과 C₂, C, ..., C_m 끝 사이의 최소₁ 절단 값을 i = i + 1을 얻을 때까지 u'로 바꿉니다.

외부 루프의 각 실행에서 알고리즘은 2개의 노드만 남을 때까지 내부 루프를 반복하여 대응하는 컷을 얻는다.1개의 실행 실행 시간은 $O(n)$ ( $O(n)$ n $O(n)$ ) \ $displaystyle$ O ( n ) $O(n)$ n은 정점의 수를 나타냅니다.외부 루프를 m회 실행한 후 모든 결과 중 최소 컷을 출력합니다.그림 2는 알고리즘의 1회 실행 예를 나타내고 있습니다.실행 후에는 3사이즈 컷을 받습니다.

Lemma 1 — k를 최소 절단 크기로 하고 C = { $e 1, e 2$ , $...,$ $e k}$ 를 최소 절단 크기로 $합니다$ .반복 i 동안 수축에 $대해$ 에지 e $δ$ C가 선택되지 않으면 C = $C$ 입니다_i.

증명

G가 접속되어 있지 않은 경우, G는 L과 R로 분할할 수 있습니다.따라서 연결이 끊긴 그래프의 최소 절단은 0입니다.이제 G가 연결되어 있다고 가정합니다.V $= LrR$ 을 C : $C$ $=$ { $u, v} l E$ : $u$ r L,v $r$ R $}$ 에 의해 유도되는 V의 분할이라고 $하자$ (G가 연결되어 있기 때문에 잘 정의된다).C의 Edge {u,v}을(를) 고려합니다.처음에 u,v는 별개의 꼭지점입니다. $f\neq e$ 를 $선택$ 하면 $f\neq e$ $u$ 와 v는 $병합$ 되지 않습니다.따라서 알고리즘의 마지막에 그래프 전체를 커버하는 2개의 복합 노드가 있습니다.하나는 L의 정점으로 구성되어 있고 다른 하나는 R의 정점으로 구성되어 있습니다.그림 2와 같이 min cut의 사이즈는 1이며, C = {(A,B)}이다.축소는 (A, B)를 선택하지 않으면 최소 컷을 받을 수 있습니다.

Lemma 2 - G가 정점이 p개인 다중 그래프이고 최소 컷 크기가 k인 경우 G는 최소 pk/2개의 에지를 가집니다.

증명

최소 절단이 k이므로 모든 정점 v는 도(v) ≤ k를 만족해야 한다. 따라서 도 합계는 최소 pk이다.그러나 정점 도수의 합이 2E라는 것은 잘 알려져 있다. 보조항목이 그 뒤를 따른다.

알고리즘 분석

알고리즘이 성공할 확률은 1 - 모든 시도가 실패할 확률입니다.독립적으로 모든 시도가 실패할 확률은 다음과 같습니다.

\displaystyle _{i=1}^{m}\Pr(C_{i}\neq C)=\prod _{i=1}^{m}(1-\Pr(C_{i}=C)}

보조항법 1에 따르면 C = $C일 i$ 확률은 반복 i 동안 C의 가장자리가 선택되지 않을 확률입니다.내부 루프를 고려하여 G가 j 엣지 수축 후의 그래프를 나타내도록 $합니다 j$ . $여기$ 서 j { { $0,$ $1$ , $\dots,$ n - $3).$ $G$ 에는_j n - $j개$ 의 정점이 $있습니다$ .우리는 조건부 가능성의 연쇄 법칙을 사용한다.반복 j에서 선택된 가장자리가 $C$ 에 없을 가능성은 $1-{\frac {k}{|E(G_{j})|}}$ C에 있지 $1-{\frac {k}{|E(G_{j})|}}$ .C의 가장자리는 1 - $1-{\frac {k}{|E(G_{j})|}}$ ( $G$ ) { $E$ ( $G _$ { \ $frac$ { $k }$ } $1-{\frac {k}{|E(G_{j})|}}$ 。 $G$ 는_j 아직 최소 크기 k 컷을 가지고 있기 때문에 Lemma 2 ${\frac {(n-j)k}{2}}$ 에서는 최소 ${\frac {(n-j)k}{2}}$ 의 ${\frac {(n-j)k}{2}}$ j를 ${\frac {(n-j)k}{2}}$ 있습니다.

$1-{\frac {k}{|E(G_{j})|}}\geq 1-{\frac {2}{n-j}}={\frac {n-j-2}{n-j}}$ 1 $1-{\frac {k}{|E(G_{j})|}}\geq 1-{\frac {2}{n-j}}={\frac {n-j-2}{n-j}}$ - $1-{\frac {k}{|E(G_{j})|}}\geq 1-{\frac {2}{n-j}}={\frac {n-j-2}{n-j}}$ E ( $1-{\frac {k}{|E(G_{j})|}}\geq 1-{\frac {2}{n-j}}={\frac {n-j-2}{n-j}}$ ) $1-{\frac {k}{|E(G_{j})|}}\geq 1-{\frac {2}{n-j}}={\frac {n-j-2}{n-j}}$ 1 $1-{\frac {k}{|E(G_{j})|}}\geq 1-{\frac {2}{n-j}}={\frac {n-j-2}{n-j}}$ - $1-{\frac {k}{|E(G_{j})|}}\geq 1-{\frac {2}{n-j}}={\frac {n-j-2}{n-j}}$ n - $1-{\frac {k}{|E(G_{j})|}}\geq 1-{\frac {2}{n-j}}={\frac {n-j-2}{n-j}}$ - $1-{\frac {k}{|E(G_{j})|}}\geq 1-{\frac {2}{n-j}}={\frac {n-j-2}{n-j}}$ - j - $1-{\frac {k}{|E(G_{j})|}}\geq 1-{\frac {2}{n-j}}={\frac {n-j-2}{n-j}}$ ( \ $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 \leftfrac {n-2}{n}}\right)\leftflac {n-3}{n-1}\right)\leftfrac {n-4}{n-2}\right}\ldots \fright\frac {nfright}\frack {nfright}\fr}\fright}\frac {n}\fright}\fright}\fright}:\fright}}

$\Pr[C_{i}=C]\geq {\frac {2}{n(n-1)}}$ 하면 Pr $\Pr[C_{i}=C]\geq {\frac {2}{n(n-1)}}$ [ $\Pr[C_{i}=C]\geq {\frac {2}{n(n-1)}}$ i $=$ $\Pr[C_{i}=C]\geq {\frac {2}{n(n-1)}}$ ] $\Pr[C_{i}=C]\geq {\frac {2}{n(n-1)}}$ $\Pr[C_{i}=C]\geq {\frac {2}{n(n-1)}}$ $\Pr[C_{i}=C]\geq {\frac {2}{n(n-1)}}$ - $\Pr[C_{i}=C]\geq {\frac {2}{n(n-1)}}$ $){$ $displaystyle \ Pr$ [ $C$ _ { i } = $C$ ]\ $geq$ { $2$ ( n - 1 ) $\Pr[C_{i}=C]\geq {\frac {2}{n(n-1)}}$ $1-\left(1-{\frac {2}{n(n-1)}}\right)^{m}$ 따라서 알고리즘이 성공할 확률은 $적어도1$ $1-\left(1-{\frac {2}{n(n-1)}}\right)^{m}$ ( $1-\left(1-{\frac {2}{n(n-1)}}\right)^{m}$ - $1-\left(1-{\frac {2}{n(n-1)}}\right)^{m}$ - $1-\left(1-{\frac {2}{n(n-1)}}\right)^{m}$ ) $1-\left(1-{\frac {2}{n(n-1)}}\right)^{m}$ \ $frac$ - 1 \ fr - { 1 $1-\left(1-{\frac {2}{n(n-1)}}\right)^{m}$ （ n - 1 ） $。$ $^{m$ $m={\frac {n(n-1)}{2}}\ln n$ $m={\frac {n(n-1)}{2}}\ln n$ ( $m={\frac {n(n-1)}{2}}\ln n$ n - $m={\frac {n(n-1)}{2}}\ln n$ ) 2 ln $m={\frac {n(n-1)}{2}}\ln n$ $nn$ { \ $displaystyle$ m = $sn$ frac ${ n$ ( n - 1 ) } { } \ $ln$ n $m={\frac {n(n-1)}{2}}\ln n$ 의 경우 이는 $1-{\frac {1}{n}}$ - $1-{\frac {1}{n}}$ n $1-{\frac {1}{n}}$ { $displaystyle 1-{$ \ $frac$ { $1}$ { $n$ 에 해당합니다.알고리즘은 확률 $1-{\frac {1}{n}}$ - $1-{\frac {1}{n}}$ n $(\$ 의 최소 컷을 $O(mn)=O(n^{3}\log n)$ O( $O(mn)=O(n^{3}\log n)$ n $O(mn)=O(n^{3}\log n)$ $=$ $O(mn)=O(n^{3}\log n)$ $O(mn)=O(n^{3}\log n)$ log $O(mn)=O(n^{3}\log n)$ )(\ $displaystyle$ O $(mn$ )= $O(n^{3}\log$ n $O(mn)=O(n^{3}\log n)$ 에서 찾습니다.

탈난도화

무작위성은 공간이나 시간과 같은 자원으로 볼 수 있습니다.탈andomization은 랜덤성을 제거하는(또는 가능한 한 적게 사용하는) 프로세스입니다.실행 시간을 대폭 늘리지 않고 모든 알고리즘을 디랜도마이즈할 수 있을지는 현재 알려져 있지 않습니다.예를 들어, 계산 복잡도에서는 P = BPP, 즉, 작은 오류 확률로 다항 시간에 실행되는 임의 랜덤화 알고리즘을 취하여 랜덤성을 사용하지 않고 다항 시간에 실행되도록 디랜도밍할 수 있는지 여부를 알 수 없다.

특정 랜덤화 알고리즘을 디랜덤화하기 위해 사용할 수 있는 구체적인 방법이 있습니다.

조건부 확률의 방법 및 그 일반화, 비관적 추정치
불일치 이론(기하학적 알고리즘을 디랜덤화하기 위해 사용됨)
범용 해시에 사용되는 쌍별 독립성 등 알고리즘에 의해 사용되는 랜덤 변수의 제한된 독립성 이용
초기 랜덤성의 제한된 양을 증폭하기 위한 확장 그래프(또는 일반적으로 분산기)의 사용(이 마지막 접근방식은 랜덤 소스로부터 의사 난수 비트를 생성하는 것으로도 언급되며 의사 난수의 관련 토픽으로 이어진다)
알고리즘 태스크의 랜덤성 소스로 해시 함수를 사용하도록 랜덤화 알고리즘을 변경한 다음 해시 함수의 가능한 모든 파라미터(예측)를 브루트 디랜도밍하여 알고리즘을 디랜도밍합니다.이 기술은 일반적으로 샘플 공간을 철저히 탐색하고 알고리즘을 결정론적으로 만드는 데 사용됩니다(예: 무작위 그래프 알고리즘).

랜덤성이 도움이 되는 경우

계산 모델이 튜링 기계로 제한될 때, 무작위 선택을 하는 능력이 이 능력 없이는 다항 시간에 해결할 수 없는 몇몇 문제들을 다항 시간에 해결할 수 있는지는 현재 미해결 문제이다; 이것은 P = BPP의 여부이다.다만, 그 외의 컨텍스트에서는, 랜덤화가 엄격한 개선을 가져오는 문제의 구체적인 예가 있습니다.

최초의 동기 부여 예에 근거해, 2 문자의 기하급수적으로 긴 문자열(a의 절반과 b의 절반^k)이 주어졌을 경우, 랜덤 액세스 머신은 a의 인덱스를 찾기 위해서 최악의 경우 2개의 룩업을 필요로^k−1 합니다.랜덤한 선택을 할 수 있는 경우, 예상되는 다항식 룩업 수로 이 문제를 해결할 수 있습니다.
임베디드 시스템 또는 사이버 물리 시스템에서 수치 계산을 수행하는 자연스러운 방법은 높은 확률로 정확한 계산(또는 아마도 대략 정확한 계산(PACC))에 가까운 결과를 제공하는 것이다.근사 계산과 올바른 계산 사이의 불일치 손실 평가와 관련된 어려운 문제는 랜덤화에^[7] 의존함으로써 효과적으로 해결할 수 있다.
통신의 복잡성에서는 랜덤화된 프로토콜로 log $\log n$ n \ $displaystyle \log$ n 비트의 $\log n$ 통신을 $\log n$ 하여 두 문자열의 동일성을 어느 정도 확인할 수 있습니다.어떤 결정론적 프로토콜도 강력한 ^[8]상대로부터 방어하는 $\Theta (n)$ ( n ) $\ displaystyle$ \ $Theta$ ( n )비트가 $\Theta (n)$ 필요합니다.
볼록체의 부피는 다항식 ^[9]시간에 임의의 정밀도로 랜덤화된 알고리즘으로 추정할 수 있다.Barranny와 Füredi는 어떤 결정론적 알고리즘도 ^[10]같은 일을 할 수 없다는 것을 보여주었다.이것은 무조건 사실이다. 즉, 볼록한 본체가 블랙박스로만 쿼리될 수 있다고 가정할 때 복잡성-이론적인 가정에 의존하지 않는다.
랜덤성이 도움이 되는 장소의 보다 복잡한 이론적인 예는 클래스 IP입니다.IP는, 전능 프로버와 BPP 알고리즘을 실장하는 검증자 사이의 다항식으로 긴 상호 작용에 의해서 받아들여질 가능성이 높은 모든 언어로 구성됩니다.IP = PSPACE.^[11]단, 검증자가 결정론적이어야 할 경우 IP = NP입니다.
화학 반응 네트워크(A+B → 2C + D와 같은 유한한 반응 세트)에서, 초기 상태에서 주어진 목표 상태에 도달하는 능력은 결정될 수 있으며, 심지어 (반응에 대한 표준 농도 기반 확률을 사용하여) 주어진 목표 상태에 도달하는 확률도 근사할 수 있다.on will occurred next)는 판별할 수 없습니다.좀 더 구체적으로 말하면, 한정된 튜링 기계는 랜덤 화학 반응 네트워크를 사용하는 경우에만 항상 올바르게 실행될 수 있는 임의의 높은 확률로 시뮬레이션될 수 있다.단순한 비결정론적 화학 반응 네트워크(어떤 가능한 반응도 다음에 일어날 수 있음)에서 계산 능력은 원시 재귀 ^[12]함수로 제한됩니다.

「」를 참조해 주세요.

메모들

^ Hoare, C. A. R. (July 1961). "Algorithm 64: Quicksort". Commun. ACM. 4 (7): 321–. doi:10.1145/366622.366644. ISSN 0001-0782.
^ Kudelić, Robert (2016-04-01). "Monte-Carlo randomized algorithm for minimal feedback arc set problem". Applied Soft Computing. 41: 235–246. doi:10.1016/j.asoc.2015.12.018.
^ 무작위로 선택된 매우 많은 수의 소수점 테스트에서 페르마 테스트를 바보로 만드는 값을 우연히 발견할 가능성은 우주 방사선이 컴퓨터가 '올바른' 알고리즘을 실행할 때 오류를 일으킬 확률보다 낮습니다.첫 번째 이유로는 부적합하지만 두 번째 이유로는 부적합한 알고리즘을 고려하는 것은 수학과 공학의 차이를 보여줍니다."할 애벨슨과 제럴드 서스먼(1996년).컴퓨터 프로그램의 구조와 해석.MIT 프레스, 섹션 1.2
^ 윌리엄스, H.C.;Shallit, J.O(1994년),"컴퓨터 이전의 정수 Factoring", Gautschi에, 월터(교육.), 수학 계산 1943–1993:계산 수학을 반세기의;심포지엄 수치 해석에 Minisymposium 전산 번호 이론으로 서류를 밴쿠버 브리티쉬 콜럼비아, 8월 9–13, 1993년 프로에를 열었다.Symposia의 응용 수학에서 Ceedings, vol. 48, 아메르.수학. 속짱, 프로비던스, R1,를 대신하여 서명함. 481–531, doi:10.1090/psapm/048/1314885, MR1314885,"아마도 Pocklington도 임의적인 알고리즘을 개발한 것으로 믿을 만하지"페이지의 주 504.
^ 세이델 R.랜덤화 기하 알고리즘의 역방향 분석
^ A. A. Tsay, W. S. Lovejoy, David R. Karger, 컷, 플로우, 네트워크 설계의 랜덤 샘플링 문제, 연산 연구의 수학, 24(2):383-413, 1999.
^ 를 클릭합니다Alippi, Cesare (2014), Intelligence for Embedded Systems, Springer, ISBN 978-3-319-05278-6.
^ 결정론적 하한은 페이지 11을 참조하고, 로그 랜덤화 상한은 페이지 31–32를 참조한다Kushilevitz, Eyal; Nisan, Noam (2006), Communication Complexity, Cambridge University Press, ISBN 9780521029834.
^ Dyer, M.; Frieze, A.; Kannan, R. (1991), "A random polynomial-time algorithm for approximating the volume of convex bodies" (PDF), Journal of the ACM, 38 (1): 1–17, doi:10.1145/102782.102783, S2CID 13268711
^ Füredi, Z.; Bárány, I. (1986), "Computing the volume is difficult", Proc. 18th ACM Symposium on Theory of Computing (Berkeley, California, May 28–30, 1986) (PDF), New York, NY: ACM, pp. 442–447, CiteSeerX 10.1.1.726.9448, doi:10.1145/12130.12176, ISBN 0-89791-193-8, S2CID 17867291
^ Shamir, A. (1992), "IP = PSPACE", Journal of the ACM, 39 (4): 869–877, doi:10.1145/146585.146609, S2CID 315182
^ 를 클릭합니다Cook, Matthew; Soloveichik, David; Winfree, Erik; Bruck, Jehoshua (2009), "Programmability of chemical reaction networks", in Condon, Anne; Harel, David; Kok, Joost N.; Salomaa, Arto; Winfree, Erik (eds.), Algorithmic Bioprocesses (PDF), Natural Computing Series, Springer-Verlag, pp. 543–584, doi:10.1007/978-3-540-88869-7_27.

레퍼런스

토마스 H. 코먼, 찰스 E. 리저슨, 로널드 L. 리베스트, 클리포드 스타인.알고리즘 소개, 제2판MIT Press와 McGraw-Hill, 1990.ISBN 0-262-03293-7.5장: 확률론적 분석과 무작위 알고리즘, 페이지 91–122.
더크 드라하임입니다확률형 람다 계산의 의미론(마르코프 연쇄 의미론, 종단 행동 및 표현 의미론)스프링거 2017년
존 클라인버그와 에바 타도스.알고리즘 설계13장: "랜덤화 알고리즘"
Fallis, D. (2000). "The reliability of randomized algorithms". The British Journal for the Philosophy of Science. 51 (2): 255–271. doi:10.1093/bjps/51.2.255.
M. Mitzenmacher와 E. 업팔. 확률과 컴퓨팅: 랜덤 알고리즘과 확률론적 분석.케임브리지 대학 출판부, 뉴욕(NY), 2005.
라지예프 모트와니와 P.라그하반.랜덤화 알고리즘케임브리지 대학 출판부, 뉴욕(NY), 1995.
라지예프 모트와니와 P.라그하반.랜덤화 알고리즘랜덤화 알고리즘에 관한 조사.
Christos Papadimitriou (1993), Computational Complexity (1st ed.), Addison Wesley, ISBN 978-0-201-53082-7 11장: 무작위 계산, 페이지 241–278.
Rabin, Michael O. (1980). "Probabilistic algorithm for testing primality". Journal of Number Theory. 12: 128–138. doi:10.1016/0022-314X(80)90084-0.
A. A. Tsay, W. S. Lovejoy, David R. Karger, 컷, 플로우, 네트워크 설계의 랜덤 샘플링 문제, 연산 연구의 수학, 24(2):383-413, 1999.

[1] Hoare, C. A. R. (July 1961). "Algorithm 64: Quicksort". Commun. ACM. 4 (7): 321–. doi:10.1145/366622.366644. ISSN 0001-0782.

[2] Kudelić, Robert (2016-04-01). "Monte-Carlo randomized algorithm for minimal feedback arc set problem". Applied Soft Computing. 41: 235–246. doi:10.1016/j.asoc.2015.12.018.

[3] 무작위로 선택된 매우 많은 수의 소수점 테스트에서 페르마 테스트를 바보로 만드는 값을 우연히 발견할 가능성은 우주 방사선이 컴퓨터가 '올바른' 알고리즘을 실행할 때 오류를 일으킬 확률보다 낮습니다.첫 번째 이유로는 부적합하지만 두 번째 이유로는 부적합한 알고리즘을 고려하는 것은 수학과 공학의 차이를 보여줍니다."할 애벨슨과 제럴드 서스먼(1996년).컴퓨터 프로그램의 구조와 해석.MIT 프레스, 섹션 1.2

[4] 윌리엄스, H.C.;Shallit, J.O(1994년),"컴퓨터 이전의 정수 Factoring", Gautschi에, 월터(교육.), 수학 계산 1943–1993:계산 수학을 반세기의;심포지엄 수치 해석에 Minisymposium 전산 번호 이론으로 서류를 밴쿠버 브리티쉬 콜럼비아, 8월 9–13, 1993년 프로에를 열었다.Symposia의 응용 수학에서 Ceedings, vol. 48, 아메르.수학. 속짱, 프로비던스, R1,를 대신하여 서명함. 481–531, doi:10.1090/psapm/048/1314885, MR1314885,"아마도 Pocklington도 임의적인 알고리즘을 개발한 것으로 믿을 만하지"페이지의 주 504.

[5] 세이델 R.랜덤화 기하 알고리즘의 역방향 분석

[6] A. A. Tsay, W. S. Lovejoy, David R. Karger, 컷, 플로우, 네트워크 설계의 랜덤 샘플링 문제, 연산 연구의 수학, 24(2):383-413, 1999.

[7] 를 클릭합니다Alippi, Cesare (2014), Intelligence for Embedded Systems, Springer, ISBN 978-3-319-05278-6.

[8] 결정론적 하한은 페이지 11을 참조하고, 로그 랜덤화 상한은 페이지 31–32를 참조한다Kushilevitz, Eyal; Nisan, Noam (2006), Communication Complexity, Cambridge University Press, ISBN 9780521029834.

[9] Dyer, M.; Frieze, A.; Kannan, R. (1991), "A random polynomial-time algorithm for approximating the volume of convex bodies" (PDF), Journal of the ACM, 38 (1): 1–17, doi:10.1145/102782.102783, S2CID 13268711

[10] Füredi, Z.; Bárány, I. (1986), "Computing the volume is difficult", Proc. 18th ACM Symposium on Theory of Computing (Berkeley, California, May 28–30, 1986) (PDF), New York, NY: ACM, pp. 442–447, CiteSeerX 10.1.1.726.9448, doi:10.1145/12130.12176, ISBN 0-89791-193-8, S2CID 17867291

[11] Shamir, A. (1992), "IP = PSPACE", Journal of the ACM, 39 (4): 869–877, doi:10.1145/146585.146609, S2CID 315182

[12] 를 클릭합니다Cook, Matthew; Soloveichik, David; Winfree, Erik; Bruck, Jehoshua (2009), "Programmability of chemical reaction networks", in Condon, Anne; Harel, David; Kok, Joost N.; Salomaa, Arto; Winfree, Erik (eds.), Algorithmic Bioprocesses (PDF), Natural Computing Series, Springer-Verlag, pp. 543–584, doi:10.1007/978-3-540-88869-7_27.

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

Search

랜덤화 알고리즘

네임스페이스

더

목차

동기

계산의 복잡성

역사

예

퀵소트

기하학에서 무작위 증분 구성

최소 컷

알고리즘 분석

탈난도화

랜덤성이 도움이 되는 경우

「」를 참조해 주세요.

메모들

레퍼런스

Search

랜덤화 알고리즘

동기

계산의 복잡성

역사

예

퀵소트

기하학에서 무작위 증분 구성

최소 컷

알고리즘 분석

탈난도화

랜덤성이 도움이 되는 경우

「 」를 참조해 주세요.

메모들

레퍼런스

「」를 참조해 주세요.