非決定的なアルゴリズム
有限状態機械が決定的(決定性)であるとは、ある入力を与えられたときにその機械が通る状態遷移の経路が常に同じであることを意味する。
冪等なアルゴリズムってことかsta.icon
逆に非決定的だと冪等じゃない(同じ条件なのに違う結果返ってくるとか)
ランダム以外でそんなのあんの?
これは単に「パラメーターとして想定が漏れてた」だけじゃね?sta.icon
入力以外の外部の状態を使用する場合。例えば、ユーザー入力、大域変数、ハードウェアのタイマ値、ディスク上のデータなど。
これは「動かす機械そのものも複雑性」だからしゃーない
タイミングに依存した処理をする場合。例えば、複数のプロセッサが同時に同じアドレスにデータを書き込む場合、実際の正確な書き込み順序によって最終的な結果が異なる。
ハードウェアの故障などの要因で予期しない動作をする場合。
上記定義に従えばあらゆるアルゴリズムは(厳密に言えば)非決定的に見えるけど
何が非決定にしている?
これが絡んでそう?だが読んでもわかんね。時期尚早sta.icon