開始

• 計算とアルゴリズム
  • 1.1～1.3と演習問題1-8。計算量の話。基本。演習問題1-8は2SATがO(m+n)で解けることを示す問題。解答では最大独立集合を求める問題に帰着し、構成したグラフの特殊性から最大独立集合を求める問題はO(m+n)と言っている。しかし証明が載っていないので調べた別解をメモ。x∨y ⇔ ￢x⇒y ⇔ ￢y⇒x であることを利用しImplication graphを構成する。ある強連結成分中にあるxとその否定￢xが含まれていたら矛盾するので2SATは解けない。Implication graph中に一つもそのような強連結成分分解が無ければ良い。強連結成分分解は2回深さ優先探索をすれば解けるのでO(m+n)。

　実はきちんと学んだことの無かった、アルゴリズムのお勉強をします。
　定番のアルゴリズムイントロダクションは分厚すぎる（＆高すぎる）ので以下の本を使用します。コードは載ってないけど理論はしっかり載ってそう。必要なら自分で実装して身につけます。