読者です 読者をやめる 読者になる 読者になる

計算理論

計算理論の基礎(チューリング機械)part2

[計算理論]チューリン機械part2 停止問題 停止問題(halting problem)とは、チューリング機械の結果が「受理・拒否」か「ループ」を 判定できるかという問題。 一般的に「停止性をアルゴリズム的に決定する方法は存在しない」。 万能チューリング機械 万能チ…

計算理論の基礎(チューリング機械)

[計算理論]チューリング機械 チューリング機械の特徴 ・チューリング機械はテープに大使、書き出しも読み出しもどちらもできる。 ・読み書きヘッドは左右どちらでも動く。 ・テープは無限長である。 ・チューリング機械は拒否や受理に対応する状態に入るとす…

計算理論の基礎(正規言語) part3

[計算理論]正規言語 決定性・非決定性 ・決定性(deterministic):次の入力文字を読み出すと、次の状態が何であるか決まる ・非決定性(nondeterministic):どの時点においても次の状態としての複数の選択肢が存在する 決定性有限オートマトン(DFA) ・すべての…

計算理論の基礎(正規言語) part2

[計算理論]正規言語 正規演算 正規演算とはAとBを言語とした場合に、以下で定義する3つの演算のいずれかを指す。 ・和集合演算(union) \[ A \cup B = \{ x | x \in A または x \in B \} \] ・連結演算(conncatenation) \[A \circ B = \{xy | x \in A かつ y…

計算理論の基礎(正規言語) part1

[計算理論]正規言語 計算モデルの導入 理想的な計算モデルとして有限状態機械「有限オートマトン」を導入する。・有限オートマトンの正式な定義 有限オートマトンは以下の要素を持つ。 状態の集合 入力アルファベット 動作規則(δ:遷移関数 によって定義され…

計算理論の基礎(関数と関係)

[計算理論]計算理論の導入3(関数と関係について) 計算理論を学ぶ為に関数と関係についてまとめる。 語句 ・関数(function):入力と出力の関係を決める。 ・写像(mapping):関数と同意。f(a) = bは「fはaをbに写す」と言う。 ・定義域(domain):入力となりえ…

計算理論の基礎(列と組)

[計算理論]計算理論の導入2(列と組について) 計算理論を学ぶ為に列と組についてまとめる。 語句 ・列(sequence):ものをある順序で並べたもの Example (5, 21, 4) ・組(tuple):有限な列 k個組(k-tuple);k個の要素からなる列 ・対(pair):2個組 ・冪(べき)…

計算理論の基礎(集合)

[計算理論]計算理論の導入(集合について) 計算理論を学ぶ為に、集合理論についてまとめておく 語句 ・集合(set):「もの」の集まり ・元(element):集合に属するもの ・要素(member):集合に属するもの(元と同意) 記法 \[ A \in a \] aはAの要素である。 \[ …