The Art of Computer Programming Volume 4B の日本語訳

序 …… vii

演習問題についての注意 …… xiii

数学的準備拾遺 …… 1

• さまざまな不等式 …… 3

• マルチンゲール …… 6

• マルチンゲールからの末尾不等式 …… 8

• 応用 …… 9

• ほとんど確かあるいは極めて確かなこと …… 11

• 演習問題 …… 12

第7章 — 組合せ探索 …… [4A.1]

• 7.2. すべての可能性の生成 …… [4A.275]

  • 7.2.1. 組合せパターンの生成 …… [4A.275]

  • 7.2.2. Backtrack Programming …… 32

    • • データ構造 …… 34

      • Walkerの方式 …… 35

      • 順列とLangford対 …… 36

      • ことばの四角 …… 38

      • コンマフリー符号 …… 39

      • 選択肢の動的な並べ替え …… 40

      • 逐次割当て再訪 …… 41

      • コンマフリー問題のためのリスト …… 42

      • 更新と復元の一般的なしくみ …… 43

      • コンマフリー符号でのバックトラック …… 46

      • 実行時間の見積もり …… 47

      • *解の数の見積もり …… 50

      • 問題の分割 …… 52

      • 歴史的注 …… 54

      • 演習問題 …… 55

    • 7.2.2.1. ダンシングリンクス …… 66

      • 厳密被覆問題 …… 67

      • 二次アイテム …… 71

      • 進捗報告 …… 73

      • 数独 …… 74

      • ポリオミノ …… 79

      • ポリキューブ …… 82

      • 厳密被覆問題の分解 …… 83

      • 色制御の被覆 …… 87

      • 多重性を取り入れる …… 91

      • *新しいダンスステップ …… 95

      • *アルゴリズムXの解析 …… 98

      • *マッチング問題の解析 …… 102

      • *まともな注目点を維持する …… 104

      • 局所的等価性の開発 …… 106

      • *オプションの前処理 …… 108

      • 最小コスト解 …… 111

      • *最小コスト切断の実装 …… 115

      • *ZDDとダンス …… 118

      • 要約 …… 121

      • 歴史的注記 …… 121

      • 演習問題 — 第1部 …… 122

      • 演習問題 — 第2部 …… 155

      • 演習問題 — 第3部 …… 173

    • 7.2.2.2. 充足可能性 (Satisfiability) …… 185

      • 単純な例 …… 188

      • SATに対するバックトラック法 …… 210

      • ランダムな充足可能性 …… 230

      • 導出 …… 238

      • 導出によるSAT解法 …… 243

      • Monte Carlo法 …… 260

      • 局所補題 …… 264

      • *メッセージパッシング …… 273

      • *節の前処理 …… 277

      • 制約の節への符号化 …… 279

      • 単位伝播と強制 …… 285

      • 対称性除去 …… 287

      • 充足可能性を保つ写像 …… 289

      • 100個のテストケース …… 295

      • パラメータを調整する …… 305

      • 並列性の開拓 …… 309

      • 簡単な歴史 …… 310

      • 演習問題 …… 313

演習問題の解答 …… 368

付録A — 数表 …… 647

• 1 基本定数 (十進) …… 647

• 2 基本定数 (十六進) …… 648

• 3 調和数, Bernoulli数, Fibonacci数 …… 649

付録B — 表記法索引 …… 651

付録C — アルゴリズムと定理の索引 …… 657

付録D — 組合せ問題の索引 …… 658

付録E — 解答のパズルの解 …… 661

索引 …… 664