ストリングマッチング 単純に考えると、n文字の文字列からm文字を探索するにはO(nm)の時間がかかる。 →KMPアルゴリズム・BMアルゴリズム：O(n+m)で実行できる KMPアルゴリズム 2DPDA：2方向決定性オートマトン 前後に動く＆スタックがある。 定理：RAMは2DPD…

ハッシュ法 ハッシュ＝切り刻む ハッシュドビーフのハッシュ

証明系の健全性 ある証明系において、Φ├{PS}AならばΦ|=Aという証明系を健全であるという。 （PSの推論規則においてΦからAが導けるならばΦを満たすすべての解釈はAを満たす） 証明系の完全性 ある証明系において、Φ|=AならばΦ├{PS}Aという証明系を完全である…