決定的アルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』
決定的アルゴリズム（けっていてきアルゴリズム、英: 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
Une fenêtre (pop-into) d'information (contenu principal de Sensagent) est invoquée un double-clic sur n'importe quel mot de votre page web. LA fenêtre fournit des explications et des traductions contextuelles, c'est-à-dire sans obliger votre visiteur à quitter votre page web !