関連サイト
本書の関連ページが用意されています。
内容紹介
◆Knuth先生の名著『The Art of Computer Programming』でソートと探索を極める!
「この巻のタイトル「ソートと探索」から，まるで汎用のソートルーティンや情報検索を行う応用プログラムを調べることに関心があるシステムプログラマ対象の書のように思われるかもしれない．しかし，実際にソートと探索の分野は，多様で重要な一般的問題を議論する理想的な枠組を提供している」（本書「序」より）。
この巻では、第5章でものを順にソートすることに関して、第6章で表やファイル中の特定の要素を探索する問題について学びます。
※ 本書は、株式会社アスキーより刊行された『The Art of Computer Programming Volume 3 Sorting and Searching Second Edition 日本語版』を並製本として再刊行したものです。再刊行にあたっては、旧版刊行後に発見された誤植などを修正しています。
◆『The Art of Computer Programming』シリーズについて
『The Art of Computer Programming』シリーズは、「コンピュータアルゴリズムの特徴についての理論」の研究を続けるドナルド・E・クヌースの集大成といえるものです。第1巻「基本アルゴリズム」、第2巻「準数値的アルゴリズム」、第3巻「ソートと探索」、第4巻「組合せアルゴリズム」、第5巻「構文アルゴリズム」、第6巻「言語理論」、第7巻「コンパイラ」という構成になっています（現在も執筆が続けられています）。
情報科学の自習、大学の授業のテキストとして利用できるように、膨大な演習問題が含まれており、その大半に解答が用意されているので、解説内容の研究、確認もできるようになっています。また、このシリーズには数学的な内容がふんだんに盛り込まれていますが、高校の代数以上の数学知識をもたない読者が数学的な色合いの濃い部分を斜め読みしても全体を理解できるような構成をとっています。
書誌情報
- 著者: Donald E. Knuth(著), 有澤誠, 和田英一(監訳), 石井裕一郎, 伊知地宏, 小出洋, 高岡詠子, 田中久美子, 長尾高弘(訳)
- 発行日: 2015-10-30 (紙書籍版発行日: 2015-10-30)
- 最終更新日: 2015-11-10
- バージョン: 1.0.1
- ページ数: 769ページ(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プロジェクトメンバー．
石井裕一郎
弁理士（特定侵害訴訟代理業務可能），芦田・木村国際特許事務所にて活動中．1990年東京大学工学部航空工学科宇宙工学卒業．和田研フォントの開発に関与の後，1997年同大学院工学系研究科情報工学博士課程満期退学，1998年同博士（工学）．1997年弁理士登録，2004年-2006年日本大学商学部非常勤講師．プログラミングと知的財産権の関わりに興味を持つ．
伊知地宏
1982年千葉大学理学部数学科卒業，1984年千葉大学大学院理学研究科数学専攻修了．富士ゼロックス（株）を経て，2001年ラムダ数学教育研究所設立．東京大学，東京工業大学，早稲田大学，千葉大学非常勤講師．プログラムの数学，プログラミング言語，整数論（特に不定方程式論），パズルの数理に興味を持つ．
小出洋
1991年電気通信大学電気通信学部計算機科学科卒業．1997年同大学院電気通信学研究科博士後期課程修了，博士（工学）．日本原子力研究所計算科学技術推進センター研究員，九州工業大学大学院工学研究科講師を経て，2003年同大学情報工学部知能情報工学科助教授．2014年同大学大学院情報創成工学研究系准教授，並列分散処理，脅威トレースに関する研究に従事．
高岡詠子
慶應義塾大学理工学部数理科学科卒業，同大学大学院理工学研究科計算機科学専攻博士課程修了，博士（工学）．現在，上智大学理工学部教授．専門分野はデータベースとWebアプリケーション，コンピュータと社会（医療・教育・環境・福祉）．2007年情報処理学会山下記念研究賞受賞，2013年度情報処理学会学会活動貢献賞受賞，主な著書：『チューリングの計算理論入門』，『シャノンの情報理論入門』（講談社ブルーバックス），『計算事始め（'13）』および『情報科学の基礎（'07）』（放送大学教科書）．
田中久美子
九州大学システム情報科学研究院教授。東京大学大学院工学系研究科情報工学専攻博士課程修了、博士（工学）。工業技術院電子技術総合研究所、東京大学大学院情報学環講師を経て、2005年より東京大学大学院情報理工学系研究科准教授、2012年より現職。自然言語や記号系に普遍に内在する数理構造に興味を持つ。
長尾高弘
（株）ロングテール社長．翻訳書リチャード・M・ストールマン『フリーソフトウェアと自由な社会』，デビッド・フラナガン，まつもとゆきひろ『プログラミング言語Ruby』ほか．
目次
第5章——ソート
- 5.1. 順列の組合せ論の性質
- 5.1.1. 逆転
- 5.1.2. 多重集合の順列
- 5.1.3. 連
- 5.1.4. タブローと対合
- 5.2. 内部ソート
- 5.2.1. 挿入ソート
- 5.2.2. 交換ソート
- 5.2.3. 選択ソート
- 5.2.4. マージによるソート
- 5.2.5. 分配によるソート
- 5.3. 最適なソート
- 5.3.1. 最小比較回数ソート
- 5.3.2. 最小比較マージ
- 5.3.3. 比較最小選択
- 5.3.4. ソートのためのネットワーク
- 5.4. 外部ソート
- 5.4.1. 多系列マージおよび置換選択法
- 5.4.2. 多段階マージ
- 5.4.3. 縦列マージ
- 5.4.4. テープの逆読み
- 5.4.5. 振動ソート
- 5.4.6. テープマージに関する実用上の考察
- 5.4.7. 外部基数ソート
- 5.4.8. テープ2 本でのソート
- 5.4.9. ディスクとドラム
- 5.5. 要約，歴史，文献
第6章——探索
- 6.1. 逐次探索
- 6.2. キーの比較による探索
- 6.2.1. 整列されている表の探索
- 6.2.2. 二分木探索
- 6.2.3. バランス木
- 6.2.4. 多分木
- 6.3. ディジタル探索
- 6.4. ハッシュ法
- 6.5. 副キーによる検索
演習問題の解答
付録A——数表
- 1. 基本定数(十進)
- 2. 基本定数(八進)
- 3. 調和数, Bernoulli数, Fibonacci数