# 決定的アルゴリズム [決定的アルゴリズム - Wikipedia](https://ja.wikipedia.org/wiki/決定的アルゴリズム) **決定的アルゴリズム**（けっていてきアルゴリズム、[英](https://ja.wikipedia.org/wiki/%E8%8B%B1%E8%AA%9E "英語"): deterministic algorithm）は、[計算機科学](https://ja.wikipedia.org/wiki/%E8%A8%88%E7%AE%97%E6%A9%9F%E7%A7%91%E5%AD%A6 "計算機科学")における[アルゴリズム](https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0 "アルゴリズム")の種類であり、その動作が予測可能なものをいう。入力を与えられたとき、決定的アルゴリズムは常に同じ経路で計算を行い、常に同じ結果を返す。決定的アルゴリズムは最も研究の進んでいるアルゴリズムであり、その多くは実際のコンピュータで効率的に実行できる実用性を備えている。**決定性アルゴリズム**と言うことも多い。 決定的アルゴリズムは、同じ入力に対しては常に（ひとつの）同じ結果を返すという点で、[関数](https://ja.wikipedia.org/wiki/%E9%96%A2%E6%95%B0_(%E6%95%B0%E5%AD%A6) "関数 (数学)")の一種とみなせる。アルゴリズムはその結果の計算の具体的な手順を与えるものである。 ## 非決定的なアルゴリズムを構成する要因 - 入力以外の外部の状態を使用する場合。例えば、ユーザー入力、大域変数、ハードウェアのタイマ値、ディスク上のデータなど。 - タイミングに依存した処理をする場合。例えば、複数のプロセッサが同時に同じアドレスにデータを書き込む場合、実際の正確な書き込み順序によって最終的な結果が異なる。 - ハードウェアの故障などの要因で予期しない動作をする場合。 完全に決定的なプログラムというものは実際には珍しいが、決定的であるほうが扱いやすい。このため、特に[関数型言語](https://ja.wikipedia.org/wiki/%E9%96%A2%E6%95%B0%E5%9E%8B%E8%A8%80%E8%AA%9E "関数型言語")を中心とする[プログラミング言語](https://ja.wikipedia.org/wiki/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E8%A8%80%E8%AA%9E "プログラミング言語")の多くは上に挙げたようなことが偶然に起きたりしないようにしている。そのような制約によって決定性を与えているため、決定的アルゴリズムを「純関数的; purely functional」と称することもある。 ## 決定的アルゴリズムの問題 実用的にも重要な問題が多く属する[NP完全問題](https://ja.wikipedia.org/wiki/NP%E5%AE%8C%E5%85%A8%E5%95%8F%E9%A1%8C "NP完全問題")は、[非決定性チューリング機械](https://ja.wikipedia.org/wiki/%E9%9D%9E%E6%B1%BA%E5%AE%9A%E6%80%A7%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E6%A9%9F%E6%A2%B0 "非決定性チューリング機械")を使えば高速に解くことができるが、効率的な決定的アルゴリズムは見つかっていない。そのため、現状では近似解を求めたり、特殊な条件を付与して解を求めるしかない。 ## Deterministic algorithm [Deterministic algorithm - Wikipedia](https://en.wikipedia.org/wiki/Deterministic_algorithm) ### Haskell [Haskell](https://en.wikipedia.org/wiki/Haskell) provides several mechanisms: - Non-determinism or notion of Fail - the _Maybe_ and _Either_ types include the notion of success in the result. - the _fail_ method of the class Monad, may be used to signal _fail_ as exception. - the Maybe [monad](https://en.wikipedia.org/wiki/Monad_(functional_programming) "Monad (functional programming)") and MaybeT monad transformer provide for failed computations (stop the computation sequence and return Nothing)[[10]](https://en.wikipedia.org/wiki/Deterministic_algorithm#cite_note-10) - Neterminism/non-det with multiple solutions - you may retrieve all possible outcomes of a multiple result computation, by wrapping its result type in a MonadPlus [monad](https://en.wikipedia.org/wiki/Monad_(functional_programming) "Monad (functional programming)"). (its method _mzero_ makes an outcome fail and _mplus_ collects the successful results).[[11]](https://en.wikipedia.org/wiki/Deterministic_algorithm#cite_note-monad-plus-11)