出版書誌データベース

「組合せアルゴリズムは，私たちを多数の場合を含む問題に対処させる方法である．そういう技術の知識の爆発的な増加は，その記述に数巻の書を必要とする．... 本書はそのシリーズの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 解答のパズルの解

著：Ｄｏｎａｌｄ　Ｅ．Ｋｎｕｔｈ
スタンフォード大学名誉教授。アルゴリズムとプログラミング技術における先駆的な業績、コンピュータの組版に向けたTEXとMETAFONTシステムの発明、影響力のある執筆活動によって世界中で知られている。ACMチューリング賞、AMSスティール賞などを受賞している。

監：和田　英一
1955年東京大学理学部物理学科卒業。東京大学工学部、富士通研究所を経てIIJ技術研究所。プログラム言語，操作システムなどソフトウェアシステムやインターフェースに関心があり，Happy Hacking Keyboard，和田研フォントの開発に関与，WIDEプロジェクトメンバー。

他訳：岩崎　英哉
1983年東京大学工学部計数工学科卒業。1988年東京大学大学院工学系研究科情報工学専攻博士課程修了。工学博士。東京大学，東京農工大学，電気通信大学を経て，現在明治大学理工学部専任教授。専門分野は，プログラミング言語，システムソフトウェア。