アルゴリズムとデータ構造

実際にプログラムを作る人の立場にたって、一般的なアルゴリズムとデータ構造の基本を解説する。アルゴリズムはできるだけ高速で、実用的なものを採用した。完璧に理解できるように、それぞれのアルゴリズムは動作原理からプログラミングの際の注意点・テクニック、計算時間まで、詳細に説明する。そのため図と具体的なプログラムを豊富に盛り込んだ。プログラムは Pascal で示し、主なものは C、Common Lisp でも示した。

探索や整列、グラフ、文字列の処理といった基本的なアルゴリズムを、動作原理から実装の注意点、計算時間まで具体的なプログラムで説明した教科書が『アルゴリズムとデータ構造』 (石畑清 著、岩波書店 (岩波講座 ソフトウェア科学)、1989 年 3 月刊) です。講座全体の編者は長尾真ほかで、本書は講座の〔基礎〕3 にあたります。CiNii Books に載る BOOK データベースの内容説明は、本書を「実際にプログラムを作る人の立場にたって、一般的なアルゴリズムとデータ構造の基本を解説する」ものと紹介し、アルゴリズムは「できるだけ高速で、実用的なものを採用した」と述べています。

計算量、探索、整列から始まる全 7 章と付録

目次は 1「アルゴリズムと計算量」、2「探索」、3「整列」、4「グラフのアルゴリズム」、5「文字列のアルゴリズム」、6「難しい問題」、7「さまざまなアルゴリズム」の 7 章と、付録「C と Lisp によるプログラム」で構成されています。最初に計算量を置き、データを探す、並べるという基本の操作を経てグラフと文字列へ進み、最後の 2 章へつながる並びです。内容説明によれば、それぞれのアルゴリズムは「動作原理からプログラミングの際の注意点・テクニック、計算時間まで、詳細に説明する」方針で、そのために「図と具体的なプログラムを豊富に盛り込んだ」とされています。巻末には参考書の案内も付いています。

Pascal を主に、C と Common Lisp も添えたプログラム

内容説明は、プログラムを「Pascal で示し、主なものは C、Common Lisp でも示した」と説明しており、付録の題もこの方針に対応しています。手順を言葉や擬似コードだけで示す書き方に比べ、動くプログラムの形で示すと、配列の境界や再帰の終わり方のように実際に書いてみて初めて気づく細部まで、読者が自分の手で確かめやすくなります。国立国会図書館の書誌には、付属資料としてフロッピーディスク 1 枚 (5-2HD / 基本アルゴリズムライブラリ) と冊子の記載があります。1989 年の刊行なので、古書で手に入れる場合は付属資料の有無を確かめ、媒体を読み出す環境は別に用意する前提で考えておくのが無難です。

手間の増え方で比べる考え方は古びない

アルゴリズムの良し悪しは、特定の計算機での実測の秒数ではなく、入力の大きさに対して手間がどう増えるかを オーダー記法 で表して比べるのが基本です。n 個のデータを先頭から 1 つずつ調べる方法と、並んだデータを半分ずつ絞り込む方法では、n が 2 倍になったときの手間の伸び方がまるで違い、機械が速くなってもこの差は埋まりません。キーから格納位置を直接計算する ハッシュ表 のように、平均の手間をほぼ一定に抑える工夫が生まれたのも、同じ物差しで比べられるからです。こうした土台は言語や計算機が入れ替わっても変わらない部分であり、1989 年の教科書を読む価値がもっとも残るところでもあります。

実装と計算時間を結び付けたい人に向く理由

プログラムは Pascal が中心なので、Pascal に馴染みがなくても、C や Python のような手続き型の言語を一通り書ける人であれば構文の読み替えで追えます。競技プログラミングの解法集や、Python で書かれた入門書を探している人は別の本のほうが目的に近づきます。実装重視、理論重視といった本の型の選び分けは アルゴリズム本の選び方 にもまとめています。標準ライブラリの内側で何が起きているのかを、動くプログラムと計算時間の説明の両面から確かめたい人にとって、本書は基本のアルゴリズムを一通り手元に揃えられる一冊です。