アルゴリズムとデータ構造岩波講座ソフトウェア科学3

2019年2月2日

岩波出版

著者：石畑清

1 アルゴリズムと計算量
1.1 アルゴリズム
アルゴリズムとは何か
アルゴリズムの正しさ
アルゴリズムの証明の方法
1.2 アルゴリズムの計算量
計算量
例題
計算量の漸近的な評価
O記法
漸近的計算量の重要性
計算量の各種の定義
データ構造
計算のメカニズム
問題の大きさの限界
アルゴリズムの選択
1.3 基本的データ構造
列
配列
リスト
配列とリストの比較
ポインターの添字表現
記憶域の割当て
各種のリスト
スタック
待ち行列
木
木の表現法
木の走査
第1章のまとめ・演習問題1

2 探索
2.1 探索とそのアルゴリズム
用語の定義
探索アルゴリズムの計算量
2.2 線形探索
配列上の線形探索
番兵
リストの線形探索
自己再構成リスト
2.3 2分探索
2分探索の原理
第1の方式
第2の方式
挿入と削除
2.4 2分探索木
2分探索木
2分探索木の挿入
計算量
2分探索木からの削除
末尾再帰呼出しの除法
2.5 平衡木
AVL木
AVL木の挿入
プログラムとしての実現
AVL木からの削除
AVL木の評価
AVL木以外の平衡木
2.6 B木
B木の定義
B木の探索
B木への挿入
プログラムとしての実現
B木からの削除
B木の効率と改良案
2次記憶装置上でのB木
2-3木
2.7 ハッシュ法
ハッシュ法の考え方
チェイン法
ハッシュ関数
チェイン法の計算量
開番地法、特に線形走査法
その他の開番地法
データの削除
開番地法の効率
ハッシュ法の評価
2.8 その他の探索アルゴリズムと集合操作
トライ
自己再構成木
集合操作
第2章のまとめ・演習問題2

3 整列
3.1 整列アルゴリズムの基礎
問題の定義
最も単純な整列アルゴリズム
選択法
挿入法
整列の計算量に関する理論的考察
3.2 シェルソート
シェルソートの原理
シェルソートの計算量
3.3 クイックソート
クイックソートの原理
クイックソートの簡単な実現法
クイックソートの計算量
補助記憶域の大きさ
分割の高速化
誤ったプログラムの例
分割の別法
基準値の選び方
挿入法の併用
再帰呼出しの除去
決定版
3.4 ヒープソート
マージ
単純マージソート
トップダウン法
自然マージソート
リストのマージソート
2次記憶上のデータの整列
マージの各種の方法
3.6 比較以外の方法による整列
ビンソート
基底法
第3章のまとめ・演習問題3

4 グラフのアルゴリズム
4.1 グラフとは何か
用語の定義
グラフアルゴリズムの計算量
4.2 グラフの表現法
行列表現
リスト表現
二つの表現法の比較
4.3 グラフの探索
深さ優先探索
無向グラフの場合
有向グラフの場合
トポロジカルソート
幅優先探索
一般的な探索アルゴリズム
4.4 各種の連結性の判定
2重連結性
関節点検出のアルゴリズム
強連結性
強連結成分への分割アルゴリズム
4.5 最短路の問題
単一出発点の問題
Dijkstraのアルゴリズムの単純な実現法
ヒープを使ったDijkstraのアルゴリズムの実現法
全頂点間の問題
最短路問題の各種の解法
グラフの推移的閉法
4.6 最小木の問題
Primのアルゴリズム
Kruskalのアルゴリズム
同値類の問題
同値類アルゴリズムの効率化
最小木アルゴリズムの計算量
4.7 グラフに関するその他のアルゴリズム
最大流問題
グラフの平面性の判定
グラフの同形性の判定
グラフのマッチング
第4章のまとめ・演習問題4

5 文字列のアルゴリズム
5.1 文字列の照合
問題の定義
素朴なアルゴリズム
Knuth-Morris-Prattのアルゴリズム
Boyer-Mooreのアルゴリズム
作戦1
作戦2
表nextの簡単な計算法
表nextの高速計算法
作戦1と作戦2の統合
5.2 正規表現とのパターン照合
正規表現
問題の定義
有限オートマトン
決定性オートマトンと非決定性オートマトン
非決定性オートマトンによるパターン照合
非決定性オートマトンから決定性オートマトンへの変換
非決定性オートマトンと決定性オートマトンの比較
型や変数の宣言
正規表現の構文解析
非決定性オートマトンの生成
決定性オートマトンの生成
テキストの照合
プログラムの改良
第5章のまとめ・演習問題5

6 難しい問題
6.1 バックトラック法
n女王問題
バックトラック法
バックトラック法の効率の改善
双方向リストを使った順列の生成
6.2 幅優先探索
8パズル
幅優先探索の手順
幅優先探索の所要記憶量
8パズルのプログラム
6.3 ゲームの木の探索
ゲームの木
ミニマックス法
評価関数
α-β法
6.4 NP完全問題
やさしい問題と難しい問題
クラスPとNP
NP完全問題
6.5 最適化問題の解法
NP完全問題の厳密解法
分岐限定法
ナップザック問題の分岐限定法による解法
動的計画法
6.6 近似アルゴリズム
Euclid的巡回セールスマン問題
単純貪欲法
大局的貪欲法
挿入法
最小木法
局所探索法
第6章のまとめ・演習問題6