アルゴリズム設計の基礎


目次

第1章 アルゴリズムと流れ図
 1・1 問題解決とコンピュータ・アルゴリズム
 1・2 流れ図(フローチャート)
 1・3 コンピュータの動作
 1・4 アルゴリズムの正当性
 1・5 アルゴリズムの評価

第2章 制御構造T
 2・1 基本制御構造
 2・2 連接構造
  1 代入
  2 計算
  3 誤差
 2・3 選択構造
  1 単分岐型(if−then型)
  2 双分岐型(if−then−else型)
  3 論理演算子
  4 選択構造の入れ子
  5 多分岐型(case型)
 2・4 反復構造
  1 反復の意義
  2 前判定反復(do−while型)と離散範囲型反復(for型またはdo型)
  3 後判定反復(repeat−until型)
  4 無限反復(loop型)
  5 反復構造(ループ)の入れ子

第3章 データ構造T
 3・1 アルゴリズムとデータの表現
 3・2 セル
 3・3 レコード型
 3・4 配列型
  1 配列の参照
  2 挿入
  3 削除
  4 多次元配列
 3・5 リスト(ポインタ型)
  1 ポインタ
  2 挿入
  3 削除
  4 ポインタの添字表現
  5 各種のリスト
  6 リストによるグラフ表現
 3・6 プログラミング言語によるデータ構造の表現

第4章 探索T
 4・1 探索
 4・2 配列の線形探索
  1 原理
  2 計算量
  3 番兵の利用
 4・3 リストの線形探索
  1 原理
  2 自己再構成リスト
 4・4 順次ファイルの探索
 4・5 二分探索
  1 原理
  2 計算量

第5章 ソートT
 5・1 ソート
 5・2 単純選択法
  1 原理
  2 計算量
 5・3 単純交換法(バブルソート)
  1 原理
  2 計算量
 5・4 単純挿入法
  1 原理
  2 計算量

第6章 制御構造U
 6・1 モジュール
  1 モジュール化
  2 引数と関数値
 6・2 再帰
  1 再帰的定義とアルゴリズム
  2 末端再帰呼出しの除去
  3 目で見る再帰−フラクタル−
  4 再帰的定義

第7章 データ構造U(その他のポインタ型)
 7・1 スタック
  1 スタックの性質
  2 配列による表現
  3 リストによる実現
 7・2 キュー(待ち行列)
  1 キューの性質
  2 リストによる実現
  3 配列による実現
 7・3 木構造
  1 木構造
  2 木の実現
  3 木の意味づけと走査

第8章 探索U
 8・1 二分探索木
  1 二分探索木の特徴
  2 最小値の要素の参照
  3 探索
  4 挿入
  5 削除
  6 木の形状と計算量
 8・2 ハッシュ法
  1 原理
  2 ハッシュ関数
  3 外部ハッシュ法(連鎖法)
  4 内部ハッシュ法(開番地法)
  5 計算量
 8・3 グラフの深さ優先探索

第9章 ソートU
 9・1 シェルソート
  1 原理
  2 計算量
 9・2 クイックソート
  1 原理
  2 基準値の選定と分割方法
  3 部分配列の分割
  4 計算量
  5 クイックソートの改良
 9・3 ヒープソート
  1 優先順位キューとヒープ
  2 原理
  3 計算量
 9・4 マージソート
  1 原理
  2 計算量
 9・5 パケットソート
  1 原理
  2 計算量
 9・6 基数ソート
  1 原理
  2 計算量

第10章 文字列照合と関係データベース処理
 10・1 単純な文字列照合
  1 文字列照合とは
  2 原理
  3 計算量
 10・2 BM法による文字列照合
  1 原理
  2 計算量
 10・3 第要素の選択
  1 原理
  2 計算量
 10・4 関係データベース処理

第11章 アルゴリズムの複雑さ
 11・1 複雑さの階層(PとNP)
  1 クラスP
  2 クラスNP
 11・2 問題の帰着可能性
 11・3 NP完全/NP困難問題
  1 NP完全性
  2 NP困難性

第12章 アルゴリズムの設計
 12・1 分割統治法
 12・2 動的計画法
 12・3 分枝限定法
 12・4 近似解法
  1 欲張り法
  2 モンテカルロ法
 12・5 ゲームのアルゴリズム
  1 推論を表す木の探索
  2 ミニ・マックス法
  3 α−β手続きの導入
  4 探索順序の工夫による探索の効率化
  5 評価値の決定
 12・6 遺伝的アルゴリズム
  1 遺伝子
  2 遺伝的アルゴリズムの基本的操作
  3 0−1ナップサック問題への応用
  4 巡回セールスマン問題への応用

参考文献
索引


戻る