関連サイト
本書の関連ページが用意されています。
内容紹介
「組合せアルゴリズムは，私たちを多数の場合を含む問題に対処させる方法である．そういう技術の知識の爆発的な増加は，その記述に数巻の書を必要とする．… 本書はそのシリーズの2番手であり，第4A 巻の後継である．」(本書「序」より)。
この巻では，組合せアルゴリズムの重要な部分となる「バックトラック」を解説します。バックトラックの概論に続いて，厳密被覆問題などの解決に有効な手法となる「ダンシングリンク」を取り上げます。後半では、計算機科学の全分野で基本的な問題の1つとなる「充足可能性(Satisfiability：SAT)」について詳解します。バックトラックアルゴリズムを理解するために必要となる確率論の概論について，「数学的準備拾遺」が特別に用意されています。
この巻には1,000問を超える演習問題があり，アルゴリズムの本格的な理解に役立てることができるでしょう。
書誌情報
- 著者: Donald E. Knuth(著), 和田 英一(監訳・訳), 岩崎 英哉, 田村 直之(訳)
- 発行日: 2023-12-18 (紙書籍版発行日: 2023-12-18)
- 最終更新日: 2023-12-18
- バージョン: 1.0.0
- ページ数: 728ページ(PDF換算)
- 対応フォーマット: PDF, EPUB
- 出版社: アスキードワンゴ
対象読者
著者について
Donald E. Knuth
計算機科学者、数学者。スタンフォード大学名誉教授。アルゴリズムに関する著作The Art of Computer Programmingのシリーズはプログラミングに携わるものの間ではあまりにも有名。アルゴリズム解析の父とも呼ばれている。計算理論の発展に多大な貢献をしている。その過程で漸近記法で計算量を表すことを一般化させた。理論計算機科学への貢献とは別に、コンピュータによる組版システムTEXとフォント設計システムMETAFONTの開発者でもあり、Computer Modernという書体ファミリも開発した。作家であり学者であるクヌースは、文芸的プログラミングのコンセプトを生み出し、そのためのプログラミングシステムWEB/CWEBを開発。また、MIX/MMIX命令セットアーキテクチャを設計。(Wikipediaより)
和田 英一
1955年東京大学理学部物理学科卒業．東京大学工学部，富士通研究所を経てIIJ技術研究所．プログラム言語，操作システムなどソフトウェアシステムやインターフェースに関心があり，Happy Hacking Keyboard，和田研フォントの開発に関与，WIDEプロジェクトメンバー．
岩崎 英哉
1983年東京大学工学部計数工学科卒業．1988年東京大学大学院工学系研究科情報工学専攻博士課程修了．工学博士．東京大学，東京農工大学，電気通信大学を経て，現在明治大学理工学部専任教授．専門分野は，プログラミング言語，システムソフトウェア．
田村 直之
1980年神戸大学理学部物理学科卒業．1985年同大学大学院自然科学研究科修了（学術博士）．日本IBMを経て1988年より神戸大学に所属．論理プログラミング，制約プログラミング，SATソルバー，パズルなどに興味がある．
目次
数学的準備拾遺
第7章 組合せ探索
- 7.2. すべての可能性の生成
- 7.2.2. BacktrackProgramming
- 7.2.2.1. ダンシングリンクス
- 7.2.2.2. 充足可能性(Satisfiability)