ぱらぱらめくる『クヌース本4.0』

The Art of Computer Programming,Volume 4, Fascicle 0 Introduction to Combinatorial Algorithms and Boolean Functions 日本語版 (ASCII Addison Wesley Programming Se)

• 組合せ問題
  • パターンを考えて、次の５つのことを問題にする(ことが多い)
    • (1)存在：そのパターンに合う配置Xはあるか(Satisfiability(SAT),Boolean Satisfiability)
    • (2)構成：あるなら、Xはすぐに見つかるか
    • (3)数え上げ：配置Xは何通りあるか
    • (4)生成：配置X1,X2,...を規則的にたどれるか
    • (5)最適化：目的関数fが与えられたとき、f(X)を最大または最小にする配置は何か
  • 実用世界では、このほかに
    • (6)制約充足問題(Constraint satisfaction problem(CSP))も大事
• グラフ代数
  • こちらでまとめ直し
• ハイパーグラフへの拡張
  • ハイパーエッジを複数のノードの組(複数のノードをつなぐもの)とする。また、このつなぐノードの個数をr個にそろえたようなハイパーグラフをr-uniformハイパーグラフを称することとする。このとき、普通のグラフはそのハイパーエッジのすべてが２個のノードをつないでいるから、r-uniform ハイパーエッジである
  • Hypergraph visualization
  • ハイパーグラフとネットワーク解析
• 被覆と独立はグラフ・ハイパーグラフで考えられる
• 0と1
  • ２変数の作る４通りに関する真偽は通りのこと
  • n変数の作るに関する真偽は通りに対応する
    • 多重線形表現(multilinear representation)とか排他的標準形(exclusive normal form)というような一意的表現を持つ
      • のような式
• PLA: Programmable logic array は計算機チップが持つ、１つ以上の加法標準形を計算する構造的単位
• 充足可能性問題というのがあるそうだ(こちら)
  • この問題を解くのは確かに大変そうだ
  • だけれど、この問題の答を「予測」するという作業は日々(外れている可能性が高いかもしれないが)やっているように思う。さて、どうやっている？
  • 場合分けで解くのが不適当なパズルを「解けた！」という感じで解いているときのようなことに(不正確だが)対応しているようにも思える
  • 囲碁の「手筋」の選び方もこんな感じか
• 中央値判定という三項演算(Median_algebra(中央値演算)
• ブール関数評価
  • 真理値表があるときに、通りをしらみつぶしにしないでもよいだろうけれど、その効率って…と言う話
  • 個の評価を逐次してやって、(該当しない場合分けはやらずに)判断するのも、一つの「効率のよいブール関数評価」
  • BDDもZDDもそう
• 多重出力
  • 複数のブール関数に対して、同一の入力をして、複数の関数の結果をそろえてみたいときに、複数のブール関数を使うことで、複数のブール関数を直列に処理するより、効率がよくならない？という話
  • 部分関数化・関数の分解・部分関数の分解