関連サイト
本書の関連ページが用意されています。
内容紹介
Knuth先生の名著『The Art of Computer Programming』で組合せアルゴリズムを理解する!
「組合せアルゴリズムは，早い話で順列やグラフなど，組合せ対象の高速処理の技術であると定義できる．われわれはある制約を満たす最良のパターンや配置を探そうとする．そういう問題は極めて多く，わずかな優れた工夫でも数年分，数世紀分の計算時間を節約し得るので，そういうプログラムを書く技法は特に重要であり，感動である．」（本書「序」より）。
この巻では、広大な組合せアルゴリズムの分野における基本的な考え方を理解していきます。論理代数の使い方、グラフ理論、バックトラッキングなど、中核をなすアルゴリズムを取り上げます。
※ 本書は、株式会社アスキーより刊行された『The Art of Computer Programming Volume 4 日本語版』のFascicle 0 〜 4を合本し、並製本として再刊行したものです。再刊行にあたっては、旧版刊行後に発見された誤植などを修正しています。
『The Art of Computer Programming』シリーズについて
『The Art of Computer Programming』シリーズは、「コンピュータアルゴリズムの特徴についての理論」の研究を続けるドナルド・E・クヌースの集大成といえるものです。第1巻「基本アルゴリズム」、第2巻「準数値的アルゴリズム」、第3巻「ソートと探索」、第4巻「組合せアルゴリズム」、第5巻「構文アルゴリズム」、第6巻「言語理論」、第7巻「コンパイラ」という構成になっています（現在も執筆が続けられています）。
情報科学の自習、大学の授業のテキストとして利用できるように、膨大な演習問題が含まれており、その大半に解答が用意されているので、解説内容の研究、確認もできるようになっています。また、このシリーズには数学的な内容がふんだんに盛り込まれていますが、高校の代数以上の数学知識をもたない読者が数学的な色合いの濃い部分を斜め読みしても全体を理解できるような構成をとっています。
書誌情報
- 著者: Donald E.Knuth(著), 有澤誠, 和田英一(監訳), 筧一彦, 小出洋(訳)
- 発行日: 2017-03-15 (紙書籍版発行日: 2017-03-15)
- 最終更新日: 2017-03-15
- バージョン: 1.0.0
- ページ数: 888ページ(PDF版換算)
- 対応フォーマット: PDF, EPUB
- 出版社: アスキードワンゴ
対象読者
著者について
Donald E.Knuth
計算機科学者、数学者。スタンフォード大学名誉教授。アルゴリズムに関する著作The Art of Computer Programmingのシリーズはプログラミングに携わるものの間ではあまりにも有名。アルゴリズム解析の父とも呼ばれている。計算理論の発展に多大な貢献をしている。その過程で漸近記法で計算量を表すことを一般化させた。理論計算機科学への貢献とは別に、コンピュータによる組版システムTEXとフォント設計システムMETAFONTの開発者でもあり、Computer Modernという書体ファミリも開発した。作家であり学者であるクヌースは、文芸的プログラミングのコンセプトを生み出し、そのためのプログラミングシステムWEB/CWEBを開発。また、MIX/MMIX命令セットアーキテクチャを設計。(Wikipediaより)
有澤誠
1967年東京大学工学部計数工学科卒業．通産省電総研，Stanford大学大学院，山梨大学工学部等を経て，1990年から慶應義塾大学環境情報学部勤務．ソフトウエア工学，アルゴリズム論，コンテンツ工学，交通運輸情報などに関心をもつ．趣味は数理パズル．2010年慶應義塾大学名誉教授．
和田英一
1955年東京大学理学部物理学科卒業．東京大学工学部，富士通研究所を経てIIJ技術研究所．プログラム言語，操作システムなどソフトウェアシステムやインターフェースに関心があり，Happy Hacking Keyboard，和田研フォントの開発に関与，IFIP WG2.1，WIDEプロジェクトメンバー．
筧一彦
1997 年早稲田大学理工学部情報学科卒業．2002年同大学院理工学研究科博士課程修了，博士（情報科学）．1999年から2002年まで日本学術振興会特別研究員．東京大学大学院情報理工学系研究科での研究職を経て、2006年から東京大学産学連携本部にて国際面を含めた産学連携推進活動業務に従事．
小出洋
1991年電気通信大学電気通信学部計算機科学科卒業．1997年同大学院電気通信学研究科博士後期課程修了，博士（工学）．日本原子力研究所計算科学技術推進センター研究員，九州工業大学大学院工学研究科講師を経て，2003年同大学情報工学部知能情報工学科助教授．2014年同大学大学院情報創成工学研究系准教授，並列分散処理，脅威トレースに関する研究に従事．
目次
第7章 組合せ探索
- 7.1. 零と一
- 7.1.1. Boole演算の基礎
- 7.1.2. Boole関数評価
- 7.1.3. ビットごとの秘宝と技法
- 7.1.4. 二分決定図
- 7.2. すべての可能性の生成
- 7.2.1. 組合せパターンの生成
- 7.2.1.1. すべての n 項組の生成
- 7.2.1.2. すべての順列の生成
- 7.2.1.3. すべての組合せの生成
- 7.2.1.4. すべての整数分割の生成
- 7.2.1.5. すべての集合分割の生成
- 7.2.1.6. すべての木の生成
- 7.2.1.7. 歴史とより詳しい参考文献