・論理回路の完備性・完全性(completeness)について いまいち理解がすっきりしなかったのでうんうん考えていた。これは論理学における関数の完全性の概念と同じ。{AND∧,OR∨,NOT¬}の演算子のみで任意の数の引数をとる全ての論理関数を構成できるというもの。c…

所属判定問題 CYK法 ・Gを文脈自由文法とする。入力としてw∈T^*が与えられたとき、w∈L(G)であるかどうかを判定するアルゴリズムがある。 証明： Gについて、A⇒^*εとなるような生成規則を取り除いていけばε∈L(G)かどうかを判定できる。さらにεがあるなら、L(G…

2014computer-s1-3(4) x座標が最小であるQの要素をq0とする。q0.x - p.x 再帰させるだけなので、時間計算量はO(nlog(n))となる。 Inner loopは、lower boundの維持とbreakによるupper boundによってP2の要素それぞれに対してO(1)で動作する。OuterがO(n)だか…

回帰分析 久米・飯塚『シリーズ入門 統計的方法２ 回帰分析』岩波書店、1987年 ・回帰分析は、複数個の変数の間の関係を解析するための代表的な手法。特性と特性の量的関係をつかむ。 目的変数をy、yの挙動を説明していると考えられるn個の変数をと表す。回…

正則表現(正規表現に同じだけど、形式言語においては正則表現と呼んで、実際にプログラミングで使うようなのは正規表現と呼んだりしている)の等式における性質がわかりづらかったので解釈をメモ。以下、正則表現r,sが集合L(r),L(s)を表すとする。記号の定義…

正則言語のPumping Lemma ・L⊆Σ*を正則言語とする。このとき、ある定数N>=1が存在して、Lに属する長さがN以上の任意の記号列xに対して、xの分解x=uvwで次の条件を満たすものがある。 1. 1=NとなるLの記号列xについて、xはMによって受理されるので、xのMによ…