The Art of Computer Programming Volume 4B Combinatorial Algorithms Part 2 日本語版

発売日 : 2023年12月18日

著者／編集 : Donald　E．Knuth/和田　英一/岩崎　英哉/田村　直之/寺田　実

出版社 : ドワンゴ

発行形態 : 単行本

ページ数 : 728p

「組合せアルゴリズムは，私たちを多数の場合を含む問題に対処させる方法である．そういう技術の知識の爆発的な増加は，その記述に数巻の書を必要とする．... 本書はそのシリーズの2番手であり，第4A巻の後継である．」(本書「序」より)。この巻では，組合せアルゴリズムの重要な部分となる「バックトラック」を解説します。バックトラックの概論に続いて，厳密被覆問題などの解決に有効な手法となる「ダンシングリンク」を取り上げます。後半では、計算機科学の全分野で基本的な問題の1つとなる「充足可能性(Satisfiability：SAT)」について詳解します。バックトラックアルゴリズムを理解するために必要となる確率論の概論について，「数学的準備拾遺」が特別に用意されています。この巻には1,000問を超える演習問題があり，アルゴリズムの本格的な理解に役立てることができるでしょう。

数学的準備拾遺
第7章 組合せ探索
7.2. すべての可能性の生成
7.2.2. BacktrackProgramming
7.2.2.1. ダンシングリンクス
7.2.2.2. 充足可能性(Satisfiability)
演習問題の解答
付録A 数表
付録B 表記法索引
付録C アルゴリズムと定理の索引
付録D 組合せ問題の索引
付録E 解答のパズルの解

Ｄｏｎａｌｄ　Ｅ．Ｋｎｕｔｈ

和田　英一

岩崎　英哉

田村　直之

寺田　実