決定的アルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/09 08:27 UTC 版)
ナビゲーションに移動 検索に移動 | この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。（2022年3月） |
決定的アルゴリズム（けっていてきアルゴリズム、英: deterministic algorithm）は、計算機科学におけるアルゴリズムの種類であり、その動作が予測可能なものをいう。入力を与えられたとき、決定的アルゴリズムは常に同じ経路で計算を行い、常に同じ結果を返す。決定的アルゴリズムは最も研究の進んでいるアルゴリズムであり、その多くは実際のコンピュータで効率的に実行できる実用性を備えている。決定性アルゴリズムと言うことも多い。
決定的アルゴリズムは、同じ入力に対しては常に（ひとつの）同じ結果を返すという点で、関数の一種とみなせる。アルゴリズムはその結果の計算の具体的な手順を与えるものである。
形式的定義
形式的には、決定的アルゴリズムは有限状態機械で定義される。この場合、ある「状態」はある時点でその機械が何をしているかを表している。有限状態機械はある状態から別の状態へ厳密に遷移する。有限状態機械が決定的（決定性）であるとは、ある入力を与えられたときにその機械が通る状態遷移の経路が常に同じであることを意味する。
決定性のある計算模型の例としては、決定性チューリング機械や決定性有限状態機械がある。
非決定的なアルゴリズムを構成する要因
非決定的な振る舞いのアルゴリズムを構成する要因としては以下のようなものがある。
- 入力以外の外部の状態を使用する場合。例えば、ユーザー入力、大域変数、ハードウェアのタイマ値、ディスク上のデータなど。
- タイミングに依存した処理をする場合。例えば、複数のプロセッサが同時に同じアドレスにデータを書き込む場合、実際の正確な書き込み順序によって最終的な結果が異なる。
- ハードウェアの故障などの要因で予期しない動作をする場合。
完全に決定的なプログラムというものは実際には珍しいが、決定的であるほうが扱いやすい。このため、特に関数型言語を中心とするプログラミング言語の多くは上に挙げたようなことが偶然に起きたりしないようにしている。そのような制約によって決定性を与えているため、決定的アルゴリズムを「純関数的; purely functional」と称することもある。
決定的アルゴリズムの問題
しかし、ある種の問題では決定的アルゴリズムを発見するのが困難である。例えば、ある数が素数であるかを判定する単純で効率的な乱択アルゴリズムが存在し、判定を間違う可能性は極めて小さい（ミラー-ラビン素数判定法）。そのようなアルゴリズムは1970年代から知られているが、同様の問題についての決定的アルゴリズムはそれに比較するとあまりにも時間がかかる。
実用的にも重要な問題が多く属するNP完全問題は、非決定性チューリング機械を使えば高速に解くことができるが、効率的な決定的アルゴリズムは見つかっていない。そのため、現状では近似解を求めたり、特殊な条件を付与して解を求めるしかない。
別の問題として、予測不可能性が要求されることもあるということが挙げられる。例えば、ブラックジャックをコンピュータゲームとして実装した場合、デッキを擬似乱数を使ってシャッフルすることになる。プレイヤーがその擬似乱数の性質を知っていれば、カードがどういう順番になっているかが分かってしまう。実際、Reliable Software Technologies の Software Security Group が ASF Software, Inc. のポーカーゲームについてそのような解析を行った[1]。同様の問題は暗号理論にもあり、秘密鍵は擬似乱数を使って生成されることが多い。このような問題を防ぐものとして暗号論的擬似乱数生成器 (CSPRNG) が使われる。
脚注
- ^ 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
決定的アルゴリズム
出典: フリー百科事典『ウィキペディア（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)} であると示唆した。
※この「決定的アルゴリズム」の解説は、「ミラー–ラビン素数判定法」の解説の一部です。
「決定的アルゴリズム」を含む「ミラー–ラビン素数判定法」の記事については、「ミラー–ラビン素数判定法」の概要を参照ください。
決定的アルゴリズムと同じ種類の言葉
- 決定的アルゴリズムのページへのリンク
