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

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