アルゴリズム

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

茨木俊秀

昭晃堂

1 アルゴリズムとその計算量

  • 計算とアルゴリズム
  • アルゴリズムの例
  • 計算量の評価
  • プログラムの設計をめぐる話題
  • 文献

2 基本的なデータ量

  • リストとその実現
  • スタック,待ち行列など
  • グラフ,木と2分木
  • 集合と辞書
  • 集合族の併合
  • データ構造と抽象データ型
  • 文献

3 順序つき集合の処理と整列

  • 優先度つき待ち行列
  • 2分探索木と平衡木
  • 整列の諸アルゴリズム:バブルソート,バケットソート,基数ソート,ヒープソート
  • クイックソート
  • 整列アルゴリズムの計算量の下界
  • 第p要素の選択
  • 文献

4 アルゴリズムの実現例

  • 簡単な最適化問題
  • グラフに関するいくつかの問題
  • 関係データベースの処理
  • 文献

5 計算の複雑さ

  • 計算可能性の理論
  • 計算の複雑さの階層
  • 複雑さのクラスPとNP
  • 関連する話題と文献

6 アルゴリズムの設計

  • 分割統治法
  • 動的計画法
  • 分枝限定法
  • 近似解法
  • まとめと文献