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

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