プログラミングの良書100冊！(4)

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

	定本 Cプログラマのための アルゴリズムとデータ構造 近藤 嘉雪　著 ソフトバンク パブリッシング　発行 1998年3月 414ページ 2835円（税込）
	アルゴリズムC++ Robert Sedgewick　著 野下 浩平，星 守， 佐藤 創，田口 東　訳 近代科学社　発行 1994年7月 747ページ 7980円（税込）
	C言語による 最新アルゴリズム事典 奥村 晴彦　著 技術評論社　発行 1991年2月 443ページ 2447円（税込）
	The Art of Computer Programming Volume 1 Fundamental Algorithms Third Edition 日本語版 Donald E. Knuth　著 青木 孝，筧 一彦，鈴木 健一，長尾 高弘　訳 有澤 誠，和田 英一　監訳 アスキー　発行 2004年2月 632ページ 1万290円（本体）

　データ構造とアルゴリズムについて学ぶ際に重要なのは，動的配列やリンクリストなどの各データ構造/アルゴリズムの得手不得手をしっかり理解することです。STLやJDKなどのライブラリを利用するなら，こうしたデータ構造やソートなどのアルゴリズムを自分で書く必要はあまり生じませんが，どのデータ構造/アルゴリズムを選ぶべきかは自分で判断しなければならないからです。

　ここではまず，読みやすい割にこうした点がしっかり書いてある本として「定本 Cプログラマのためのアルゴリズムとデータ構造」を紹介しておきましょう。本書は，C MAGAZINE（ソフトバンク パブリッシング発行）で1990年から2年間にわたって連載した内容をまとめたものです。最初にアルゴリズムの計算量などの概念を簡単に解説した後，スタック，キュー，リンクリスト，ツリーといったデータ構造と，2分探索やハッシュ法などの探索，クイック・ソートやマージ・ソートなどの各種ソート・アルゴリズムを紹介しています。後半では，オートマトンによる正規表現の実装，バックトラック，動的計画法なども取り上げています。比較的コンパクトにまとまっているにもかかわらず計算量などの議論をきちんとしており，取り上げているアルゴリズムにもバラエティ感があります。C言語によるソースコードもわかりやすく，誰にでも進められる良書と言えるでしょう。

　もう少し幅広いアルゴリズムを取り上げている本としては「アルゴリズムC++」があります。こちらは，「定本 Cプログラマのための…」で挙げたアルゴリズムのほかに，2次元領域やグラフの探索，乱数生成，連立方程式の解法など様々なアルゴリズムを紹介しています。論理的にものを考えることが好きな人は，こうしたアルゴリズムを知ることでプログラミングがとても楽しく感じられるようになるかもしれません。

　実際にプログラムを組む際には，N個の要素の並べ替えたもの（順列）をすべて生成するなどちょっとした問題を解く必要に迫られることもよくあります。とりあえず正しい結果を得られるコードを書くことは自体は難しくありませんが，効率のよいアルゴリズムが知られているならそれを使いたいものです。また，アルゴリズム自体は覚えていても，境界値の処理などの細かい点をどう実装すればいいかは忘れてしまった，なんてこともあるでしょう。

　こうしたときに便利なのが，「C言語による最新アルゴリズム事典」です。本書は，様々な分野のアルゴリズムを集めて「あいうえお，ABC」順に収録したもので，一つひとつのアルゴリズムについて簡単な解説とCのコードを掲載しています。辞書式順序に従うほか，索引とほかの項目への参照（リンク）をたどっていくことでも，目的とするアルゴリズムを探せるようになっています。取り上げているアルゴリズムは対数や三角関数の計算，方程式の解法，順列組み合わせなどの数学的なものが比較的多いですが，CRC値の計算や乱数生成などをちょっと拝借するのに便利なコードも含まれています。覆面算，テトロミノの箱詰め，魔方陣などのパズルを解くアルゴリズムも収録しているので，面白そうなものだけを選んで読み進めてもいいでしょう。ただし，ソースコードの解説は一切ないので，コードを読み解くだけの力は必要です。コードをJavaに書き換えた「Javaによるアルゴリズム事典」（技術評論社発行）も出版されているので，得意な言語を考えて，お好きな方を選んでください。

難しくても価値のあるアルゴリズム書籍

　データ構造とアルゴリズムには古典的な名著とされるものもたくさんあります。ここではその中から一冊，電子組版ソフトTeXの開発者としても有名な数学者Donald E. Knuthが著した「The Art of Computer Programming Volume 1 Fundamental Algorithms Third Edition 日本語版」を紹介しておきましょう。本書は全7巻を予定しているシリーズ第3版の1巻目にあたり，第1章で数学などの基礎概念を，第2章でスタック，リンクリスト，ツリーなどのデータ構造を解説しています。本誌の発売日までには，乱数と算術演算を扱った第2巻も書店に並んでいるはずです。

　演習問題の解答を含むとは言え，基礎概念とデータ構造だけで600ページを費やしていることからわかるように，説明は非常に詳細です。n個の頂点を持つ指向木が何種類あるかを母関数を利用して計算するなど，きちんと数学的な評価をしている点も見逃せません。1997年に出た原書第3版を基に新たに翻訳しているため，訳が現代的で読みやすいのもうれしいところでしょう。

　ただ，原書第1版が出たのが40年以上前である以上仕方がありませんが，アルゴリズムの実装例はCやJavaなどの言語ではなく，仮想的なアセンブリ言語MIXALを使って記述しています。加えて，数学的な部分を読みこなすには大学1～2年レベルの数学の知識が必要になります。比較的時間のある学生の方々，特にこの分野の研究者を将来目指す人にはぜひ読んでほしいと思う一方で，多忙な現場の開発者の方が読み通すにはかなりの覚悟が必要になるでしょう。