アルゴリズム

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

杉原厚吉
共立出版

第1章 アルゴリズムと計算量

  • 1.1 アルゴリズムとは
  • 1.2 計算量

第2章 リスト構造

  • 2.1 ポインタの効用
  • 2.2 リスト構造

第3章 ヒープ

  • 3.1 2進木の素朴な利用
  • 3.2 ヒープ

第4章 ハッシュ法とバケット法

  • 4.1 検索問題と2分探索
  • 4.2 ハッシュ法
  • 4.3 バケット法
  • 4.4 バケットソート

第5章 再帰呼出しと分割統治

  • 5.1 再帰呼出し
  • 5.2 分割統治

第6章 グラフ探索

  • 6.1 グラフとグラフ探索
  • 6.2 探索の基本形
  • 6.3 キューと横型探索
  • 6.4 スタックと縦型探索
  • 6.5 探索のためのデータ構造

第7章 最短路問題

  • 7.1 最短路の探索

第8章 動的計画法

  • 8.1 最適性の原理と動的計画法
  • 8.2 弾性マッチング

第9章 縮小法

  • 9.1 問題の規模縮小化
  • 9.2 定順位要素の抽出
  • 9.3 2次元線形計画法

第10章 最大流と割当て問題

  • 10.1 ネットワークと流れ
  • 10.2 最大流の逐次構成法
  • 10.3 最大マッチング
  • 10.4 割当て問題

第11章 ボロノイ図とドロネー図

  • 11.1 ボロノイ図
  • 11.2 最近点探索
  • 11.3 ドロネー図
  • 11.4 最近点対と最小全域木

第12章 3次元凸包とドロネー図

  • 12.1 3次元凸包の分割統治構成算法
  • 12.2 ドロネー図の構成算法
  • 12.3 最遠点ボロノイ図
  • 12.4 最小包含円と真円度

第13章 平面走査法

  • 13.1 交点列挙問題
  • 13.2 走査直線を用いた平面走査
  • 13.3 2-3木―平面走査法のためのデータ構造

第14章 問題の難しさの測り方

  • 14.1 PとNP
  • 14.2 NP完全
  • 14.3 NP困難

第15章 難問対策

  • 15.1 問題の緩和
  • 15.2 分枝限定法の例
  • 15.3 局所改良

第16章 難問を利用した情報保護

  • 16.1 秘密鍵暗号と公開鍵暗号
  • 16.2 ナップザック問題
  • 16.3 ナップザック問題を利用した公開鍵暗号系

演習問題の略解
参考図書
索引