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

数学的準備拾遺 …… 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

付録A — 数表 …… 647

• 1 基本定数 (十進) …… 647
• 2 基本定数 (十六進) …… 648
• 3 調和数, Bernoulli数, Fibonacci数 …… 649