データ構造とアルゴリズム(データコウゾウトアルゴリズム)

ソフトウェアを設計するための基礎となるデータ構造とアルゴリズムについて,一般の理工系学部 1 〜 3 年生を対象として,高校の数学基礎知識のみを前提とした易しい標準的なテキストまたは入門独習書です。半期授業・ 1 年授業のどちらにも柔軟に対応できるように工夫されており,各章は 1 回の授業で扱える分量にまとめてあります。 1 〜 4 章までは必ず学ぶべき基本事項で,そのあとは講義などで使用される方や独習者の時間と興味応じて自由に選択が可能です。そのための後に,各章間の関係図・学習順序が示されているので,それぞれの事情に応じて学習するべき章を選ぶのに参考となるでしょう。
解説には図版を多用し,より深く確実な理解が得られるように配慮されています。また,すべての章末には演習問題が配置されており,巻末に略解が示されています。さらに,「カーペンターズ・アルゴリズム」というタイトルの囲み記事を設け,新しい計算原理を考えるための柔軟な発想を刺激する機会も作られています。
第 1 章 アルゴリズムと計算量
1.1 アルゴリズムとは
1.2 計算量

第 2 章 リスト構造
2.1 ポインタの効用
2.2 リスト構造

第 3 章 ヒープ
3.1 2 進木の素朴な利用
3.2 ヒープ

第 4 章 ハッシュ法とバケット法
4.1 検索問題と 2 分探索
4.2 ハッシュ法
4.3 バケット法
4.4 バケットソート

第 5 章 再帰呼出しと分割統治
5.1 再帰呼出し
5.2 分割統治

第 6 章 グラフ探索
6.1 グラフとグラフ探索
6.2 探索の基本形
6.3 キューと横型探索
6.4 スタックと縦型探索
6.5 探索のためのデータ構造

第 7 章 最短路問題
7.1 最短路の探索

第 8 章 動的計画法
8.1 最適性の原理と動的計画法
8.2 弾性マッチング

第 9 章 縮小法
9.1 問題の規模縮小化
9.2 定順位要素の抽出
9.3 2 次元線形計画法

第 10 章 最大流と割当て問題
10.1 ネットワークと流れ
10.2 最大流の逐次構成法
10.3 最大マッチング
10.4 割当て問題

第 11 章 ボロノイ図とドロネー図
11.1 ボロノイ図
11.2 最近点探索
11.3 ドロネー図
11.4 最近点対と最小全域木

第 12 章 3 次元凸包とドロネー図
12.1 3 次元凸包の分割統治構成算法
12.2 ドロネー図の構成算法
12.3 最遠点ボロノイ図
12.4 最小包含円と真円度

第 13 章 平面走査法
13.1 交点列挙問題
13.2 走査直線を用いた平面走査
13.3 2-3 木ー平面走査法のためのデータ構造

第 14 章 問題の難しさの測り方
14.1 P と NP
14.2 NP 完全
14.3 NP 困難

第 15 章 難問対策
15.1 問題の緩和
15.2 分枝限定法の例
15.3 局所改良

第 16 章 難問を利用した情報保護
16.1 秘密鍵暗号と公開鍵暗号
16.2 ナップザック問題
16.3 ナップザック問題を利用した公開鍵暗号系

演習問題の略解
参考図書
索引

情報科学科の学部課程で繰り返し採用されてきた、データ構造とアルゴリズムの古典的教科書です。著者の杉原厚吉氏は計算幾何学の研究者として知られ、本書でもスタック・キュー・木・グラフといった基本構造を、数学的な正確さを保ちつつ簡潔に展開しています。共立出版の「情報系」教科書群に位置づけられ、計算量の評価やアルゴリズムの正当性証明にも紙幅を割いている点が特徴です。

応用例やコード片を通じた直感的な学びよりも、抽象的な議論を追うことで本質を掴む構成になっています。そのため、競技プログラミング向けのレシピ集とは性格が異なり、「なぜこのデータ構造が効率的なのか」を数学的に説明できるようになりたい読者に向いています。前提知識として離散数学 (集合、論理、帰納法) の初歩があると読み進めやすいでしょう。

コードを動かしながら学びたい人には別のハンズオン寄りの本を併読する手もありますが、本書が与える「構造を抽象的に捉え、計算コストを見積もる力」は、言語やフレームワークが変わっても色褪せません。大学の講義で指定されて手に取る人が多い本ですが、実務で計算量の議論を正面から扱う必要が出てきたときに立ち戻る価値のある参照書でもあります。