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

ソフトウェアを設計するための基礎となるデータ構造とアルゴリズムについて, 一般の理工系学部 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 ナップザック問題を利用した公開鍵暗号系

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

データ構造とアルゴリズムを、大学の授業 1 回分ずつにまとめた章で順に学べる教科書です。『データ構造とアルゴリズム』 (杉原 厚吉 著、共立出版、2001 年 12 月刊) は、版元の紹介によると一般の理工系学部 1〜3 年生を対象に、高校の数学基礎知識のみを前提とした易しい標準的なテキストまたは入門独習書として書かれています。半期授業と 1 年授業のどちらにも対応できるよう各章は 1 回の授業で扱える分量に収められ、すべての章末に演習問題、巻末にその略解が付きます。

全 16 章の構成、計算量と基本構造から設計の型へ

第 1 章「アルゴリズムと計算量」で、手順の良し悪しを入力の大きさに対する手間の増え方で測る 計算量 の考え方を置き、第 2 章「リスト構造」、第 3 章「ヒープ」、第 4 章「ハッシュ法とバケット法」で基本のデータ構造を扱います。版元はこの 1〜4 章を必ず学ぶべき基本事項とし、そこから先は講義で使う人や独習者が時間と興味に応じて自由に選べるとしていて、章どうしの関係図と学習順序も示されています。第 5 章「再帰呼出しと分割統治」からは、第 6 章「グラフ探索」、第 7 章「最短路問題」、第 8 章「動的計画法」、第 9 章「縮小法」、第 10 章「最大流と割当て問題」と、問題を解く設計の型が続きます。第 6 章には「キューと横型探索」「スタックと縦型探索」という節があり、キューは近い頂点から順に広げる探索、スタックは行けるところまで深く進んでから戻る探索を支える道具として登場します。データ構造を単独の部品としてではなく、探索の進み方を決める仕掛けとして学ばせる組み立てと読めます。

後半のボロノイ図、平面走査、NP 完全と公開鍵暗号

第 11 章「ボロノイ図とドロネー図」、第 12 章「3 次元凸包とドロネー図」、第 13 章「平面走査法」の 3 章は、点や図形の配置を扱う計算幾何の題材です。ボロノイ図は平面上の点の集まりに対して、どの点に最も近いかで領域を分けた図で、最寄りの施設の検索や勢力圏の計算に使われます。第 11 章には問い合わせた点に最も近い点を探す問題や、最も近い 2 点の組と最小全域木を扱う節が、第 13 章には 2-3 木を平面走査法のためのデータ構造として扱う節があり、前半で学んだ探索やデータ構造が幾何の問題でどう生きるかを追える構成です。第 14 章「問題の難しさの測り方」は P と NP、NP 完全、NP 困難を扱い、第 15 章「難問対策」で問題の緩和、分枝限定法の例、局所改良を、第 16 章「難問を利用した情報保護」で秘密鍵暗号と公開鍵暗号、ナップザック問題とそれを利用した公開鍵暗号系を取り上げます。ナップザック問題に基づく公開鍵暗号は解読法が知られていて実用には使われていない方式ですが、効率よく解けない問題を安全性の根拠にするという発想を小さな例で示す題材になります。解けない問題の理論を、守りの技術へつなげて締めくくる並びです。

高校数学から独習する理工系学部生向けの読み方

版元は解説に図版を多用したことに加え、「カーペンターズ・アルゴリズム」と題した囲み記事で、新しい計算原理を考えるための柔軟な発想を刺激する機会を設けたことを特徴に挙げています。前提が高校数学の基礎知識に限られているので、情報系の専門課程に入る前の学生や、ほかの理工系学科で グラフアルゴリズム や最適化の基礎を押さえたい人が、自分で読み進める用途に合います。一方で、紹介文と目次には特定のプログラミング言語の記載が見当たらないため、手元で実装しながら覚えたい人は、実装重視の本と組み合わせるほうが目的に近づきます。2001 年刊の本なので、言語の標準ライブラリや開発環境の使い方を期待する本でもありません。アルゴリズム本の型ごとの選び方は アルゴリズム本ガイド にまとめています。

基本のデータ構造だけで終わらず、最大流やマッチング、計算幾何、NP 完全性までを 1 冊で見通せるのが本書の強みです。講義の教科書を探している人、予習と復習を演習問題付きで進めたい学部生、情報系以外の出身で計算の難しさの理論まで一度通して学んでおきたい人にとって、章を選んで読める本書は手元に置く価値のある入門書です。まずは必修とされる 1〜4 章から始めてみてください。