アルゴリズム

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

浪平博人
オーム社

I章 データ構造
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 ハッシュの解析

データ構造まとめ

II章 ソートとマージ
1 内部ソート(データのすべてがメモリに入るとき)

  • 1.1 よく使われる方法
    • 1.1.1 最小を選ぶことを繰り返す方法
    • 1.1.2 シェルソート
    • 1.1.3 ヒープソート
      • 補足1:再帰法を用いたヒープソート
      • 補足2:C言語によるプログラミング例
    • 1.1.14 クイックソート
  • 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 カスケードマージ

ソートとマージまとめ

III章 検索
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 ハッシングの特徴

検索まとめ

IV章 アルゴリズム構成のパターン
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 分割表現の工夫

4 繰返し法

  • 4.1 ニュートン法
  • 4.2 ガウス - ザイデル法

5 経験則(ヒューリスティックアプローチ)

  • ヒューリスティックアプローチによる問題解決例

アルゴリズム構成のパターンまとめ

参考文献
索引