アルゴリズムC++

部室からなんとなく借りてみたところ，気になる項目がいくつか目に付いたので目次を写経してみる．

基礎

• 1. はじめに
  • アルゴリズム
  • 話題の概要
• 2. C++(およびC)
  • 例：ユークリッドのアルゴリズム
  • データの型
  • 入出力
  • 追記
  • 練習問題
• 3. 基礎データ構造
  • 配列
  • リンクによるリスト
  • 記憶領域の割付け
  • スタック
  • スタックのリスト表現
  • キュー
  • 抽象データ型と具体データ型
  • 練習問題
• 4. 木
  • 木の定義
  • 木の性質
  • 2分木の表現
  • 森の表現
  • 木の走査
  • 練習問題
• 5. 再帰呼び出し
  • 漸化式
  • 分割統治
  • 木の再帰的走査
  • 再帰呼び出しの除去
  • まとめ
  • 練習問題
• 6. アルゴリズムの解析
  • アルゴリズム解析の進め方
  • アルゴリズムの分類
  • 計算量
  • 平均の場合の解析
  • 近似式
  • 基本漸化式
  • まとめ
  • 練習問題
• 7. アルゴリズムの実現
  • アルゴリズムの選択
  • 実験による解析
  • プログラムの最適化
  • アルゴリズムとシステム
  • 練習問題
  • 参考文献

整列

• 8. 初等的な整列法
  • ゲームのルール
  • 洗濯整列
  • 挿入整列
  • バブル整列法
  • 初等的な整列法の性能
  • 大きいレコードの整列法
  • シェルソート
  • 分配計数法
  • 練習問題
• 9. クイックソート
  • 基本アルゴリズム
  • クイックソートの性能
  • 再帰呼び出しの除去
  • 小さい部分ファイル
  • 3要素の中央値
  • 選択
  • 練習問題
• 10. 基数整列法
  • ビット
  • 基数交換法
  • 直接基数法
  • 基数整列法の性能
  • 線形時間整列法
  • 練習問題
• 11. 順位キュー
  • 素朴な実現法
  • ヒープ
  • ヒープのアルゴリズム
  • ヒープソート
  • 間接的ヒープ
  • もっと高度な実現法
  • 練習問題
• 12. マージソート
  • 併合
  • マージソート
  • リスト・マージソート
  • ボトムアップ型マージソート
  • マージソートの性能
  • プログラムの最適化
  • 再帰呼び出しの再考
  • 練習問題
• 13. 外部整列
  • 整列・併合
  • 均衡マルチウェイ併合
  • 置換え選択
  • 実用上の配慮
  • ポリフェーズ法
  • 手軽なやり方
  • 練習問題
  • 参考文献

探索

• 14.初等的な探索法
  • 逐次探索
  • 2分探索法
  • 2分探索木
  • 削除
  • 間接的2分探索木
  • 練習問題
• 15. 平衡木
  • トップダウン2-3-4木
  • 赤黒木
  • 他のアルゴリズム
  • 練習問題
• 16. ハッシュ法
  • ハッシュ関数
  • 分離連鎖法
  • 線形探索法
  • 2重ハッシュ法
  • まとめ
  • 練習問題
• 17. 基数探索
  • 離散探索木
  • トライ
  • マルチウェイ基数探索法
  • パトリシア
  • 練習問題
• 18. 外部探索
  • 索引順アクセス
  • B木
  • 拡張可能ハッシュ法
  • 仮想記憶
  • 練習問題
  • 参考文献

文字列処理

• 19. 文字列探索
  • 小史
  • 力まかせ探索法
  • クヌース・モリス・プラット法
  • ポイヤー・ムーア法
  • ラビン・カープ法
  • 多重探索
  • 練習問題
• 20. パターン照合
  • パターンの表記
  • パターン照合機会
  • 機会の表現
  • 機会のシミュレーション
  • 練習問題
• 21. 構文解析
  • 文脈自由文法
  • トップダウン構文解析法
  • ボトムアップ構文解析
  • コンパイラ
  • コンパイラ･コンパイラ
  • 練習問題
• 22. ファイル圧縮
  • ランレングス符号化
  • 可変長符号化
  • ハフマン符号
  • ハフマン符号化のプログラム
  • 練習問題
• 23. 暗号
  • ゲームのルール
  • 単純な暗号
  • 暗号化と復号の装置
  • 公開鍵暗号系
  • 練習問題
  • 参考文献

計算幾何

• 24. 初等的な計算機か手法
  • 点，線分，多角形
  • 線分の交差
  • 単純な閉路
  • 多角形による包含
  • 考察
  • 練習問題
• 25. 凸包の計算
  • ゲームのルール
  • 包装アルゴリズム
  • グラハム走査
  • 内点の消去
  • 性能
  • 練習問題
• 26. 領域探索
  • 初等的な方法
  • パケット法
  • 2D木
  • 高次元領域探索
  • 練習問題
• 27. 重なり問題
  • 水平，垂直な線分
  • 実現
  • 一般の線分の重なり問題
  • 練習問題
• 28. 最近点問題
  • 最近対問題
  • ボロノイ線図
  • 練習問題
  • 参考文献

グラフのアルゴリズム

• 29. 表現と探索
  • 用語
  • 表現
  • 深さ優先探索
  • 非再帰的な深さ優先探索
  • 幅優先探索
  • 迷路
  • 展望
  • 練習問題
• 30. 連結性
  • 連結成分
  • 2重連結性
  • 合併-発見アルゴリズム
  • 練習問題
• 31.重みつきグラフ
  • 最小木
  • 順位優先探索
  • クラスカル法
  • 最短経路
  • 密グラフの最小木と最短経路
  • 幾何学的問題
  • 練習問題
• 32. 有向グラフ
  • 深さ優先探索
  • 推移閉法
  • 最短経路の列挙
  • トポロジカル整列
  • 強連結成分
  • 練習問題
• 33. ネットワーク流
  • ネットワーク流問題
  • フォード-ファルカーソン法
  • ネットワーク探索
  • 練習問題
• 34. マッチング
  • 2部グラフ
  • 安定結婚問題
  • 高度なアルゴリズムについて
  • 練習問題
  • 参考文献

数理アルゴリズム

• 35. 乱数
  • 乱数の応用
  • 線形合同法
  • 加法的合同法
  • 乱数の検定
  • 実現上の注意
  • 練習問題
• 36. 算術
  • 多項式の算術
  • 多項式の評価と補間
  • 多項式の積
  • 大きな整数に対する算術演算
  • 行列の算術演算
  • 練習問題
• 37. ガウスの消去法
  • 簡単な例
  • 方法の概略
  • 変形と拡張
  • 練習問題
• 38. 曲線の近似
  • 多項式補間
  • スプライン補間
  • 最小2乗法
  • 練習問題
• 39. 積分
  • 記号線分
  • 簡単な求積法
  • 複合則
  • 適応型求積法
  • 練習問題
  • 参考文献

トピックス

• 40. 並列アルゴリズム
  • 一般的なアプローチ
  • 完全シャッフル
  • シストリックアレイ
  • まとめ
  • 練習問題
• 41. 高速フーリエ変換
  • 評価･乗算･補間
  • 1の複素累乗根
  • 1の複素累乗根における多項式の値の計算
  • 1の累乗根における補間
  • 実現
  • 練習問題
• 42. 動的計画法
  • ナップサック問題
  • 行列の並びの積
  • 最適2分探索木
  • 計算時間と記憶場所
  • 練習問題
• 43. 線形計画法
  • 線形計画問題
  • 幾何学的な解釈
  • シンプレックス法
  • 実現
  • 練習問題
• 44. 総当り探索
  • グラフにおける総当り探索
  • バックトラッキング
  • 寄り道：順列の発生
  • 近似アルゴリズム
  • 練習問題
• 45. NP完全問題
  • 決定性と非決定性多項式時間アルゴリズム
  • NP完全性
  • クックの定理
  • いくつかのNP完全問題
  • 練習問題
  • 参考文献

かなり長い．
夏休みくらいのまとまった時間にでも適当に読んでいくという妄想をしたけどこの膨大な量からして厳しいかもしれない．
ちなみに気になったのは 16.ハッシュ法， 17.基数探索， 19.文字列探索， 計算幾何の節全般， 33.ネットワーク流，41.高速フーリエ変換， 44.総当り探索， 45.NP完全問題 など．