決定性とは？ わかりやすく解説

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/02 09:30 UTC 版)

「ハッシュ関数」の記事における「決定性」の解説

ハッシュを使った手法は決定的でなければならない。つまり、ある入力が与えられたとき、生成するハッシュ値は常に同じでなければならない。言い換えれば、数学的な意味で関数になっていなければならない。したがってハッシュ関数は、時刻などに基づいた擬似乱数のような外部パラメータに依存してはならない。また、ハッシュ対象オブジェクトのメモリアドレスが処理中に変化する可能性があるなら（ガベージコレクションが行われるシステムでは変化する可能性がある）、それもパラメータとして利用することはできないが、時にはアドレス変更と同時にハッシュのやり直しを行うこともある。

※この「決定性」の解説は、「ハッシュ関数」の解説の一部です。
「決定性」を含む「ハッシュ関数」の記事については、「ハッシュ関数」の概要を参照ください。

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/14 04:59 UTC 版)

「有限オートマトン」の記事における「決定性」の解説

さらなる分類方法として、決定性有限オートマトン (DFA) と非決定性有限オートマトン (NFA, GNFA) がある。決定性有限オートマトンでは、各状態の考えられる全ての入力について一意に次の状態が決定される。非決定性有限オートマトンでは、ある状態にある入力があったとき遷移がどうなるかが決定されない（遷移がないかもしれないし、複数の遷移が対応しているかもしれない）。このような区別は実行時間などの観点では重要だが、ふるまいに関する観点ではそれほど重要ではない。それぞれのオートマトンで表現可能なふるまいは同じであり、任意のNFAを等価な（しかしより大きな）DFAに変換するアルゴリズムが存在する（冪集合構築（英語版））。 ひとつしか状態を持たない有限オートマトンは結合有限オートマトンと呼ばれ、入力動作のみを持つ。これは複数の有限オートマトンが協調動作する場合に便利であり、結合有限オートマトンとして表せる部分を抽出して設計に活用する。

※この「決定性」の解説は、「有限オートマトン」の解説の一部です。
「決定性」を含む「有限オートマトン」の記事については、「有限オートマトン」の概要を参照ください。