The Art of Computer Programming Volume 1 Fundamental Algorithms Third Edition 日本語版

Knuth 先生の名著『The Art of Computer Programming』シリーズの最初の 1 冊。
数値演算の基本アルゴリズムについて解説。独自の計算モデルである MIX の解説や、基礎的な概念、情報構造などについての話が非常に厳密に定義されながら進みます。個々の演習問題にはランク付けされていて、高校の代数以上の数学知識をもたない読者でも、数学的な色合いの濃い部分は斜め読みして、全体を把握できるように構成されています。

※本書は株式会社アスキーより刊行された『The Art of Computer Programming Volume 1 Fundamental Algorithms Third Edition 日本語版』を並製本として再刊行したものです。再刊行にあたり、旧版刊行後に発見された誤植等を修正しています。
※本書の 1.3.1、1.3.2、1.3.3 および 1.4.1、1.4.2、1.4.3 については、改訂版が『The Art of Computer Programming Volume 1 Fascicle 1 MMIX - A RISC Computer for the New Millennium 日本語版』として分冊の形で刊行されています。必要があれば、こちらをご参照ください。

◆『The Art of Computer Programming』シリーズについて
『The Art of Computer Programming』シリーズは、「コンピュータアルゴリズムの特徴についての理論」の研究を続けるドナルド・E・クヌースの集大成といえるものです。第 1 巻「基本アルゴリズム」、第 2 巻「準数値的アルゴリズム」、第 3 巻「ソートと探索」、第 4 巻「組合せアルゴリズム」、第 5 巻「構文アルゴリズム」、第 6 巻「言語理論」、第 7 巻「コンパイラ」という構成になっています (現在も執筆が続けられています)。
情報科学の自習、大学の授業のテキストとして利用できるように、膨大な演習問題が含まれており、その大半に解答が用意されているので、解説内容の研究、確認もできるようになっています。また、このシリーズには数学的な内容がふんだんに盛り込まれていますが、高校の代数以上の数学知識をもたない読者が数学的な色合いの濃い部分を斜め読みしても全体を理解できるような構成をとっています。
目次
第 1 章 基礎概念
1.1. アルゴリズム
1.2. 数学的な基礎
1.3. MIX
1.4. 基本的プログラム技法

第 2 章 情報構造
2.1. はじめに
2.2. 線形リスト
2.3. 木
2.4. 複数リンク構造
2.5. 動的メモリ配置
2.6. 歴史と参考文献

演習問題の解答

付録 A 数表
1. 基本定数 (十進)
2. 基本定数 (八進)
3. 調和数, Bernoulli 数, Fibonacci 数

付録 B 表記法索引

『The Art of Computer Programming Volume 1 Fundamental Algorithms Third Edition 日本語版』 (Donald E. Knuth 著、有澤誠、和田英一 監訳、青木孝、筧一彦、鈴木健一、長尾高弘 訳、ドワンゴ発行、KADOKAWA 発売、2015 年 6 月刊) は、クヌースのシリーズ The Art of Computer Programming (TAOCP) の第 1 巻「基本アルゴリズム」の日本語版です。原著第 3 版 (Addison-Wesley、1997 年) の翻訳で、株式会社アスキーが 2004 年に刊行した版を並製本として再刊行し、旧版刊行後に見つかった誤植などを修正しています。コンピュータプログラムの基礎概念と情報構造を、厳密な定義と膨大な演習問題で学ぶ本で、版元はシリーズを情報科学の自習や大学の授業のテキストとして使えるように組まれたものと紹介しています。著者のページによれば、第 1 巻の初版は 1968 年で、シリーズは 1999 年末に American Scientist 誌で 20 世紀の物理科学の専門書 12 点の一つに選ばれています。

第 1 章の基礎概念と MIX、第 2 章の情報構造

本文は 2 つの章で、そのあとに演習問題の解答と付録が続きます。第 1 章「基礎概念」は 1.1「アルゴリズム」、1.2「数学的な基礎」、1.3「MIX」、1.4「基本的プログラム技法」の 4 節で、版元の案内によれば、アルゴリズムの概念、必要になる数学の基礎、シリーズを理解するために必要な架空のコンピューター MIX の概要、プログラミングの基本技法を取り上げます。第 2 章「情報構造」は 2.1「はじめに」、2.2「線形リスト」、2.3「木」、2.4「複数リンク構造」、2.5「動的メモリ配置」、2.6「歴史と参考文献」の 6 節です。巻末には「演習問題の解答」と、基本定数の十進と八進、調和数、Bernoulli 数、Fibonacci 数をまとめた付録 A「数表」、付録 B「表記法索引」が置かれています。

架空の計算機で書く理由と MMIX の分冊

アルゴリズムの効率は、入力が大きくなるにつれて手間がどう増えるかという 計算量 の形で比べるのが一般的です。ただ、増え方が同じ二つの方法のどちらが速いかまでは、その表記だけでは決まりません。機械語の水準で手順を書けば、命令が何回実行されるかを数えて実行時間を定数まで含めて見積もれます。このシリーズが手順の記述に使うのが、特定の実在の機械ではない架空のコンピューター MIX です。なお版元は、本書の 1.3.1、1.3.2、1.3.3 と 1.4.1、1.4.2、1.4.3 については改訂版が『The Art of Computer Programming Volume 1 Fascicle 1 MMIX － A RISC Computer for the New Millennium 日本語版』として分冊の形で刊行されていると案内しています。著者のページによれば、原著の Fascicle 1 は 2005 年刊で、日本語版は 2006 年にアスキーから出たのち、2015 年にアスキードワンゴから並製本で再刊行されています。

ランク付きの演習問題と、数学に不安がある読者の読み方

演習問題には一つずつランクが付けられ、その大半に解答が用意されています。版元はシリーズについて、数学的な内容がふんだんに盛り込まれている一方で、高校の代数以上の数学知識をもたない読者が数学的な色合いの濃い部分を斜め読みしても全体を理解できる構成をとっていると説明しています。最初から全部の証明を追わず、まず本文の流れをつかんでから自分の力量に合ったランクの問題に取り組む読み方ができます。古い名著を読む意味については 技術書の古典を読む意味 も参考になります。

一方で、手元の言語ですぐに動くコードの書き方や、試験や面接に向けた問題の解き方を手早く知りたい場合は、目的に対して遠回りになります。そうした目的には アルゴリズム本の選び方 で紹介している実装寄りの本が向きます。データ構造やアルゴリズムの使い方は分かっていても、なぜその方法が正しく、どれだけの手間で終わるのかを自分で確かめられるようになりたい人にとって、本書は長く手元に置いて必要な節を繰り返し開く価値のある一冊です。