関連サイト
本書の関連ページが用意されています。
内容紹介
◆アルゴリズムのバイブル――Knuth先生の名著『The Art of Computer Programming』シリーズの第1巻!
「ディジタルコンピュータのプログラムを準備する作業は、特に魅力的な仕事だが、それは経済的な報酬や科学者としての名声のためだけでなく、詩を書いたり、作曲したりするのと同じ芸術的な経験だからである」（本書「序」より）。
著者であるドナルド・E・クヌースは、この考えを土台として、コンピュータプログラミングを学ぶために必要な基本的、かつ重要な知識を解説していきます。技術革新が激しいコンピュータ科学の世界では、最先端の知識や技術を追いかけ続けるにはたいへんな困難が伴います。そこで重要になるのは、今後数十年にわたって重要性を失わないと思われる「古典的」技術を理解することで、将来の発展に対応できる「確固たる基礎」を築くことです。
Volume 1「基本アルゴリズム」では、コンピュータプログラムの基礎概念と情報構造を学習します。第1章では、アルゴリズムの概念、必要になる数学の基礎、このシリーズを理解するために必要な架空のコンピュータMIXの概要、プログラミングの基本技法を取り上げます。第2章では、コンピュータの情報構造の概念、線形リスト、木構造を検討します。
※ 本書は、株式会社アスキーより刊行された『The Art of Computer Programming Volume 1 Fundamental Algorithms Third Edition 日本語版』を並製本として再刊行したものです。再刊行にあたっては、旧版刊行後に発見された誤植などを修正しています。
◆『The Art of Computer Programming』シリーズについて
『The Art of Computer Programming』シリーズは、「コンピュータアルゴリズムの特徴についての理論」の研究を続けるドナルド・E・クヌースの集大成といえるものです。第1巻「基本アルゴリズム」、第2巻「準数値的アルゴリズム」、第3巻「ソートと探索」、第4巻「組合せアルゴリズム」、第5巻「構文アルゴリズム」、第6巻「言語理論」、第7巻「コンパイラ」という構成になっています（現在も執筆が続けられています）。
情報科学の自習、大学の授業のテキストとして利用できるように、膨大な演習問題が含まれており、その大半に解答が用意されているので、解説内容の研究、確認もできるようになっています。また、このシリーズには数学的な内容がふんだんに盛り込まれていますが、高校の代数以上の数学知識をもたない読者が数学的な色合いの濃い部分を斜め読みしても全体を理解できるような構成をとっています。
書誌情報
- 著者: Donald E. Knuth(著), 有澤誠, 和田英一(監訳), 青木孝, 筧一彦, 鈴木健一, 長尾高弘(訳)
- 発行日: 2015-06-26 (紙書籍版発行日: 2015-06-26)
- 最終更新日: 2015-06-26
- バージョン: 1.0.0
- ページ数: 688ページ(PDF版換算)
- 対応フォーマット: PDF
- 出版社: アスキードワンゴ
対象読者
計算機科学を学ぶすべての人
著者について
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プロジェクトメンバー．
青木孝
1983年東京大学工学部計数工学科卒業．1985年東京大学大学院工学系研究科修士課程修了．機械語，プログラム言語処理系，オペレーティングシステム等のシステムソフトウェアに関心をもつ．
筧一彦
1997年早稲田大学理工学部情報学科卒業．2002年同大学院理工学研究科博士課程修了，博士（情報科学）．1999年から2002年まで日本学術振興会特別研究員．東京大学大学院情報理工学系研究科での研究職を経て、2006年から東京大学産学連携本部にて国際面を含めた産学連携推進活動業務に従事．
鈴木健一
1969年宮城県仙台市に生まれる．1997年東北大学大学院情報科学研究科博士課程修了．宮城工業高等専門学校，東北大学大学院情報科学研究科を経て，現在，東北工業大学工学部情報通信工学科に勤務．計算機アーキテクチャの研究に従事している．
長尾高弘
（株）ロングテール社長．翻訳書リチャード・M・ストールマン『フリーソフトウェアと自由な社会』，デビッド・フラナガン，まつもとゆきひろ『プログラミング言語Ruby』ほか．
目次
第1章——基礎概念
- 1.1. アルゴリズム
- 1.2. 数学的な基礎
- 1.2.1. 数学的帰納法
- 1.2.2. 整数，指数，対数
- 1.2.3. 総和と乗積
- 1.2.4. 整数関数と初等整数論
- 1.2.5. 置換と階乗
- 1.2.6. 二項係数
- 1.2.7. 調和数
- 1.2.8. Fibonacci数
- 1.2.9. 母関数
- 1.2.10. アルゴリズムの解析
- 1.2.11. 漸近的な表現
- 1.2.11.1. O記法
- 1.2.11.2. Eulerの総和公式
- 1.2.11.3. いくつかの漸近計算
- 1.3. MIX
- 1.3.1. MIXの解説
- 1.3.2. MIXアセンブリ言語
- 1.3.3. 置換への応用
- 1.4. 基本的プログラム技法
- 1.4.1. サブルーティン
- 1.4.2. コルーティン
- 1.4.3. 通訳系ルーティン
- 1.4.3.1. MIXシミュレータ
- 1.4.3.2. トレースルーティン
- 1.4.4. 入力と出力
- 1.4.5. 歴史と参考文献
第2章——情報構造
- 2.1. はじめに
- 2.2. 線形リスト
- 2.2.1. スタック，キュー，デック
- 2.2.2. 逐次割り当て
- 2.2.3. リンクによる割り当て
- 2.2.4. 循環リスト
- 2.2.5. 双方向リスト
- 2.2.6. 配列と直交リスト
- 2.3. 木
- 2.3.1. 二分木をたどる方法
- 2.3.2. 二分木による木の表現
- 2.3.3. 木のその他の表現
- 2.3.4. 木の基本的な数学的性質
- 2.3.4.1. 自由木
- 2.3.4.2. 指向木
- 2.3.4.3. 「無限グラフの補題」
- 2.3.4.4. 木の数え上げ
- 2.3.4.5. 路長
- 2.3.4.6. 研究史と参考文献
- 2.3.5. リストとごみ集め
- 2.4. 複数リンク構造
- 2.5. 動的メモリ配置
- 2.6. 歴史と参考文献
演習問題の解答
付録A——数表
- 1. 基本定数(十進)
- 2. 基本定数(八進)
- 3. 調和数, Bernoulli数, Fibonacci数