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

構成数 : 1

1. はじめに
1.1 アルゴリズムとデータ構造の重要性
1.2 計算モデルと計算量
1.2.1 問題と問題例
1.2.2 計算機モデル
1.2.3 アルゴリズムのオーダー表記
1.2.4 指数関数と多項式関数の比較
1.2.5 計算量とアルゴリズムの種類
1.3 NP完全性
1.3.1 PとNP
1.3.2 NPの定義
1.3.3 多項式時間帰着とNP完全
演習問題

2. 基本的データ構造
2.1 配列
2.2 線形データ構造
2.2.1 配列を使う方法
2.2.2 リスト
2.2.3 スタック
2.2.4 キュー(待ち行列)
2.3 木
2.3.1 一般的木構造
2.3.2 完全二分木
2.4 グラフ
2.4.1 グラフの基本
2.4.2 次数とカット
2.4.3 部分グラフと路と連結性
2.4.4 木と森とDAGと二部グラフと完全グラフ
2.4.5 グラフのデータ構造
2.4.6 グラフの探索-幅優先探索と深さ優先探索
演習問題
プログラム演習

3. 整列
3.1 整列とはなにか
3.2 バブルソート
3.2.1 バブルソートのアルゴリズム
3.2.2 バブルソートの計算時間
3.3 マージソート
3.3.1 マージソートのアルゴリズム
3.3.2 マージソートの計算時間
3.4 クイックソート
3.4.1 クイックソートのアルゴリズム
3.4.2 クイックソートの計算時間
3.5 バケットソート
3.5.1 バケットソートのアルゴリズム
3.5.2 バケットソートの計算時間
3.6 基数ソート
3.6.1 基数ソートのアルゴリズム
3.6.2 基数ソートの計算時間
3.7 ヒープソート
3.7.1 ヒープとはなにか
3.7.2 ヒープの構造
3.7.3 Insertの方法
3.7.4 DeleteMinの方法
3.7.5 Deleteの方法
3.7.6 ヒープソートのアルゴリズム
3.7.7 ヒープの線形時間作成法
3.8 整列計算時間の下界値
演習問題
プログラム演習

4. 集合に関する操作
4.1 主な操作とデータ構造
4.2 辞書
4.2.1 ハッシュ表
4.2.2 外部ハッシュ法
4.2.3 内部ハッシュ法
4.3 カッコウハッシュ
4.3.1 カッコウハッシュとはなにか
4.3.2 カッコウハッシュの詳細
4.3.3 格納列の閉路と単純格納列
4.3.4 カッコウハッシュの解析*
4.4 ユニオン・ファインド
4.4.1 問題設定
4.4.2 配列による実現
4.4.3 ポインタでの実現
4.4.4 木による実現-ほぼ線形時間のユニオン・ファインド
4.4.5 木構造上に限定された場合の線形時間ユニオン・ファインド
演習問題
プログラム演習

5. 平衡二分探索木
5.1 平衡二分探索木の基本
5.1.1 二分探索
5.1.2 二分探索木の構造とMember
5.1.3 最大値・最小値の発見と整列
5.1.4 データの挿入と削除
5.1.5 回転操作
5.2 二色木
5.2.1 二色木の基本
5.2.2 二色木における挿入
5.2.3 二色木における削除
5.2.4 二色木の合併と分割
5.2.5 別のデータの管理
5.3 スプレー木
5.3.1 オンラインアルゴリズムと動的最適性予想
5.3.2 スプレー木のアルゴリズム
5.3.3 スプレー木のO(logn)競合化*
5.4 タンゴ木
5.4.1 タンゴ木の基本思想とインターリーブ限界
5.4.2 タンゴ木の構造
5.4.3 補助木のつくり替え
5.4.4 タンゴ木の計算時間の解析*
演習問題
プログラム演習

6. 古典的アルゴリズム
6.1 最小木問題
6.1.1 問題の定義
6.1.2 貪欲算法とクラスカルのアルゴリズム
...