決定的アルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/09 08:27 UTC 版)
決定的アルゴリズム（けっていてきアルゴリズム、英: deterministic algorithm）は、計算機科学におけるアルゴリズムの種類であり、その動作が予測可能なものをいう。入力を与えられたとき、決定的アルゴリズムは常に同じ経路で計算を行い、常に同じ結果を返す。決定的アルゴリズムは最も研究の進んでいるアルゴリズムであり、その多くは実際のコンピュータで効率的に実行できる実用性を備えている。決定性アルゴリズムと言うことも多い。
- ^ Gary McGraw and John Viega. Make your software behave: Playing the numbers: How to cheat in online gambling. http://www.ibm.com/developerworks/library/s-playing/#h4
- 1 決定的アルゴリズムとは
- 2 決定的アルゴリズムの概要
決定的アルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/10 15:53 UTC 版)
「ミラー–ラビン素数判定法」の記事における「決定的アルゴリズム」の解説
ミラー-ラビン素数判定法は、Gary L. Miller が最初に開発したMillerテストをマイケル・ラビンが無条件の確率的アルゴリズムに修正したものである。元となったMillerテストはある限度以下の全ての a を調べるという、未だ証明されていない拡張リーマン予想に基づいた決定的アルゴリズムである。とはいえ拡張リーマン予想全体を必要とするわけではなく、平方ディリクレ指標について拡張リーマン予想が成り立てばよい。 Millerテストは未証明の拡張リーマン予想を必要としていることや、それを修正したミラー-ラビン素数判定法が許容出来る誤判定確率から判定時間を調整でき速度面で有利であることから実際には使われていない。また同じく決定的アルゴリズムであるAKS素数判定法の方が、証明されていない予想に依存していないぶんだけMillerテストよりも強い。 Millerテストには、判定を信頼できるものにするには限度をどう決めたらよいかという問題がある。 判定対象の数 n が合成数なら、n と互いに素な「強い嘘つき」の a は群 ( Z / n Z ) ∗ {\displaystyle \left(\mathbb {Z} /n\mathbb {Z} \right)^{*}} の真の部分群に含まれる。つまり ( Z / n Z ) ∗ {\displaystyle \left(\mathbb {Z} /n\mathbb {Z} \right)^{*}} の生成元集合の全 a について判定するとき、その中には必ず n の合成性の証拠となる数が含まれる。拡張リーマン予想が真であると仮定すると、ミラーが既に指摘したように O((ln n)2) より小さい元から、この集合が生成されることがわかっている。big O記法の定数は Eric Bach によって 2 まで減らされた（1990年）。このことから、次のような素数判定アルゴリズムが導かれる: 入力: n > 1; 判定対象の奇数 出力: n が合成数なら composite、さもなくば prime を返す。 n − 1 {\displaystyle n-1} を 2 のべき乗で割って、 2 s ⋅ d {\displaystyle 2^{s}\cdot d} の形式にする。 以下を [ 2 , min ( n − 1 , ⌊ 2 ( ln n ) 2 ⌋ ) ] {\displaystyle [2,\min(n-1,\lfloor 2(\ln n)^{2}\rfloor )]} の範囲の全ての a について繰り返す:ad mod n ≠ 1 かつ [0, s − 1] の範囲の全ての r について a d ⋅ 2 r {\displaystyle a^{d\cdot 2^{r}}} mod n ≠ −1 なら、composite を返す。 prime を返す。 このアルゴリズムの実行時間は Õ((log n)4) である。 判定対象の数 n が十分小さければ、全ての a < 2(ln n)2 を調べる必要はなく、もっと小さい証拠の可能性のある数の集合で十分である。例えば、Jaeschke (1993) は以下を検証した。 もし n < 4,759,123,141 なら、a = 2, 7, 61 について調べればよい。 もし n < 341,550,071,728,321 なら、a = 2, 3, 5, 7, 11, 13, 17 について調べれば十分である。 もちろん、a < n の場合だけ調べる。この種の基準については を参照されたい。このような結果を活用することで、ある範囲の数については非常に高速で決定的な素数判定が可能である。 しかし、全ての合成数についてはこのような有限の集合では不十分である。Alford、Granville、Pomerance は、合成数 n について合成性の証拠となる最小の数が ( ln n ) 1 / ( 3 ln ln ln n ) {\displaystyle (\ln n)^{1/(3\ln \ln \ln n)}\;} より大きい合成数が無数に存在する、 X が十分大きいときには X 以下のそのような合成数の個数は少なくとも X 1 / ( 35 ln ln ln X ) {\displaystyle X^{1/(35\ln \ln \ln X)}} であることを示した。また彼らはヒューリスティック的に、w 以下の合成性の証拠となる数のある n 以下の合成数について w のオーダーを Θ ( ln n ln ln n ) {\displaystyle \Theta (\ln n\,\ln \ln n)} であると示唆した。
※この「決定的アルゴリズム」の解説は、「ミラー–ラビン素数判定法」の解説の一部です。
「決定的アルゴリズム」を含む「ミラー–ラビン素数判定法」の記事については、「ミラー–ラビン素数判定法」の概要を参照ください。
決定的アルゴリズムと同じ種類の言葉
- 決定的アルゴリズムのページへのリンク
