アルゴリズム入門データ表現と処理技術

2020年5月31日

アルゴリズム入門―データ表現と処理技術

オーム社

著者：浪平博人

はしがき

Ⅰ章データ構造
1 データ構造とは何か

2 配列
2.1 基本説明
2.2 配列表現例
【例1 マトリクス】
【例2 マルコフ過程】
補足：マルコフ過程

3 スタック
3.1 基本説明
3.2 スタック使用例(サブルーチン制御)

4 キュー

5 リンクドリスト
5.1 基本説明
5.2 ダブルリンクドリスト
5.3 リスト構造の使用例
【例1 多項式の表現】
【例2 疎なマトリクの表現】
【例3 リストソート】

6 木
6.1 基本説明
6.2 2分木の意味づけ(走査)および使用例
6.2.1 走査法
6.2.2 2分木使用例
6.3 2分木のデータ操作
6.4 2分木の解析
補足：探索回数の一般解析
6.5 2分木のバランシング
6.6 整列2分木(ヒープ：山積み)

7 Bトリー
7.1 m次のBトリー
7.2 2-3-4トリー

8 ハッシュ
8.1 基本説明
8.2 ハッシュ関数
8.3 ハッシュの解析

データ構造まとめ

Ⅱ章ソートとマージ
1 内部ソート(データのすべてがメモリに入るとき)
1.1 よく使われる方法
1.1.1 最小を選ぶことを繰り返す方法
1.1.2 シェルソート
1.1.3 ヒープソート
補足1：再帰法を用いたヒープソート
補足2：C言語によるプログラミング例
1.1.4 クイックソート
1.2 考えがおもしろい方法
1.2.1 大小関係を数える方法
1.2.2 バブルソート
1.2.3 差し込みによるソート
1.2.4 マージソート
補足：BASICによるプログラム例
1.2.5 ラディックスソート
1.2.6 キーが整数値に対応づけできるとき
1.3 トポロジカルソート
1.4 ソートの形態
1.5 ソートの効率解析

2 マージ，外部ソート
2.1 基本的マージ手順
2.2 データ数が非常に異なるときのマージの工夫
2.3 外部ソート2.4
補足：昔デープを用いたころの工夫
2.4.1 2ウェイマージ
2.4.2 マルチウェイマージ
2.4.3 ポリフェーズマージ
補足：フィナボチ数列
2.4.4 カスケードマージ

ソートとマージまとめ

Ⅲ章検索
1 順次比較による検索

2データがソート順に並んでいるとき
2.1 2分探索
2.2 フィボナチ探索

3 データの追加，削除が多いとき：2分木探索
補足：平均比較回数を最小にするトリーの構成法

4 データがディスクにあるとき
4.1 デンスインデックス
4.2 スパースインデックス
4.3 Bトリーによるインデックス

5 範囲で検索する場合：範囲検索
5.1 全データをチェック：シーケンシャルサーチ
5.2 2次インデックス
5.3 グリッド法
5.4 2次元トリーによるデータ分割

6 ハシング
6.1 メモリ内にデータをストアする場合
6.1.1 オープンアドレス方式
6.1.2 2重ハッシュのオープンアドレス方式
6.2 データがディスクにあるとき
6.3 複合ハッシュ
補足：ハッシュにおける2次キーへのビットの最適配分
6.4 ハッシングの特徴

検索まとめ

Ⅳ章アルゴリズム構成のパターン
1 直接的方法
1.1 解析的に手順が定まるとき
1.2 起こりうるすべての場合を調べることが可能なとき

2 起こりうるすべての場合を調べることが不可能なとき
2.1 ダイナミックプログラミング
補足1：DPの一般形式
補足2：ラグランジェの方法
補足3：最適性原理2.2 バックトラッキング
2.2.1 バックトラッキングとは
2.2.2 割当て問題
補足：割当て問題のOR的解法

3 分割法
3.1 再帰法
3.1.1 再帰法とデータ構造
3.1.2 再帰法とフラクタルとの関連
3.1.3 再帰法の実行プロセス
3.1.4 再帰表現例
【例1 整数nのプリント】
【例2 n個のなかよりの最大最小要素の選択問題】
【例3 2分探索】
【例4 クイックソート】
【例5 コッホ曲線】
補足：BASICによる非再帰的表現手法
3.2 漸化式
【例1 ガウスの掃出法】
【例2 コンボルーション】
3.3 分割効率の解析
3.3.1 分割のバランス
補足：漸化式の一般解
3.3.2 分割表現の工夫