アルゴリズムとデータ構造 (第 2 版)

●はじめての方に最適!

お店にできる行列や目的地まで行くときの道選びなど, 日常の身近な例を挙げながら, データ構造の基本から, 分割統治法, グリーディ法, バックトラック法などの設計手法までを解説していきます.具体的にイメージしながら学べるので, 初学者も無理なく理解できます.
設計手法の説明のあとには, グラフや文字列照合などの具体的なアルゴリズムについても解説します.

2006 年に初版が発行されて以来, 高専や大学など多くの学校で採用されている人気のテキストです.今回の改訂では, 表現や項目を見直し, よりわかりやすくなりました.
第 1 章 アルゴリズムの基礎
第 2 章 アルゴリズムの基本データ構造
第 3 章 アルゴリズムにおける基本概念
第 4 章 データの探索
第 5 章 ソートアルゴリズム 1
第 6 章 ソートアルゴリズム 2
第 7 章 アルゴリズムの設計手法 1
第 8 章 アルゴリズムの設計手法 2
第 9 章 アルゴリズムの設計手法 3
第 10 章 グラフアルゴリズム
第 11 章 多項式と行列
第 12 章 文字列照合アルゴリズム
第 13 章 アルゴリズムの限界

大学や高専の情報系学科で最初に出会う専門科目の一つが「アルゴリズムとデータ構造」です。『アルゴリズムとデータ構造 (第 2 版)』 (藤原 暁宏 著、森北出版、2016 年 5 月刊) は、情報工学レクチャーシリーズの一冊として、お店にできる行列や目的地まで行くときの道選びといった身近な例を挙げながら、データ構造の基本から設計手法、具体的なアルゴリズムまでを全 13 章で解説する教科書です。版元の紹介によれば初版は 2006 年の発行で、高専や大学など多くの学校で採用されてきました。第 2 版では表現や項目が見直されています。著者は刊行時点で九州工業大学の教授です。

データ構造から設計手法へ、全 13 章の並び

章立ては大きく 4 つのまとまりに分けて読めます。第 1 章「アルゴリズムの基礎」、第 2 章「アルゴリズムの基本データ構造」、第 3 章「アルゴリズムにおける基本概念」が土台で、続く第 4 章「データの探索」と、第 5 章と第 6 章の 2 章に分かれたソートアルゴリズムで、基本的な処理を一通り押さえます。第 7 章から第 9 章の 3 章は「アルゴリズムの設計手法」に充てられ、紹介文はその中身として分割統治法、グリーディ法、バックトラック法を挙げています。そのあとに第 10 章「グラフアルゴリズム」、第 11 章「多項式と行列」、第 12 章「文字列照合アルゴリズム」と具体的な問題領域が並び、最後の第 13 章「アルゴリズムの限界」で締めくくられます。

個々の解法より「設計手法」に章を割く意味

アルゴリズムの学習は、有名な解法を一つずつ覚えていく形になりがちです。しかし実際に新しい問題に向き合うときに役立つのは、問題を小さく分けて解き結果をまとめる分割統治法、その時点で最も良い選択を積み重ねるグリーディ法、候補を順に試して行き詰まったら戻るバックトラック法といった、解き方の型の引き出しです。どの型が使えるかを見極めるには、解法が入力の大きさに対してどれだけ時間を要するかを見積もる 計算量 の考え方も欠かせません。本書が個別の解法の前に 3 章を設計手法に割き、そのあとでグラフや文字列照合を扱う並びは、型を先に身につけてから具体的な問題に当てはめていく順序と読めます。第 5 章と第 6 章の ソートアルゴリズム も、比較の仕方や分け方の違いによって計算量が変わることを体感する題材として、この流れの前段に位置づけられます。

身近な例から入る教科書が合う読者

最も合うのは、講義でこの科目を履修する学生と、講義の副読本として説明の切り口を増やしたい人です。紹介文が掲げるとおり、行列や道選びといった日常の場面から入るため、抽象的な定義から始まる教科書で手が止まった人にも取り付きやすい構成です。道選びは グラフアルゴリズム の最短経路問題につながる代表的な例でもあります。一方で、特定のプログラミング言語でそのまま動く実装例を大量に読みたい人や、競技プログラミングの解法集を求める人には、講義用の教科書という本書の性格は遠回りに感じられるかもしれません。目的別の選び方は アルゴリズム本の選び方ガイド も参考になります。2016 年刊の第 2 版ですが、扱うのはデータ構造と設計手法という変わりにくい基礎です。講義の教科書に指定された人はもちろん、この科目を基礎から体系立てて学び直したい人にとって、1 冊で全体の地図を手に入れられる教科書です。