アルゴリズムとデータ構造の設計法

アルゴリズムとデータ構造の設計法

本書は,C言語プログラムを半年程経験した読者がデータ構造およびアルゴリズムの設計手法を学ぶための自習書である。大規模集積回路の物理設計など実例も取り入れられ,ハードウェアアルゴリズムについても触れている。

ジャンル
発行年月日
2003/03/10
判型
B5
ページ数
284ページ
ISBN
978-4-339-02396-1
アルゴリズムとデータ構造の設計法
品切・重版未定
当面重版の予定がございません。

定価

4,620(本体4,200円+税)

購入案内

  • 内容紹介
  • 目次
  • レビュー
  • 著者紹介

本書は,C言語プログラムを半年程経験した読者がデータ構造およびアルゴリズムの設計手法を学ぶための自習書である。大規模集積回路の物理設計など実例も取り入れられ,ハードウェアアルゴリズムについても触れている。

1.計算量
1.1 プログラムと計算時間
1.2 アルゴリズムの計算量
1.3 計算量の解析
1.4* アルゴリズムの記述方法
 1.4.1 文
 1.4.2 データ型
1.5* プログラミング
1.6* プログラミングの例
章末問題

2.基本的なデータ構造
2.1 リスト
 2.1.1 配列によるリストの実現
 2.1.2 ポインタによるリストの実現
 2.1.3 カーソルによるリストの実現
2.2 スタック
2.3 スタックによる再帰呼び出しの除去
2.4 キュー
 2.5 キューを用いたバケットソート
 2.6* 可変長キーに対する基数ソート
章末問題

3.木
3.1 木
3.2 木の実現
3.3 木の探索
3.4 木の同型性判定
3.5 2分木
3.6 2分木を用いた構造の表現
3.7* 高さを抑えた2分木への変換
章末問題

4.集合
4.1 集合の連結リストによる実現
4.2 ビットベクトルによる実現
4.3 辞書
 4.3.1 オープンハッシュ
 4.3.2 クローズドハッシュ
4.4 写像
4.5 データ構造の設計
 4.5.1 データ構造の組合せ
 4.5.2 多重リスト構造
章末問題

5.木の高度な利用
5.1 Merge-Find集合
5.2 MF木の応用
 5.2.1 オフライン最下位共通先祖
 5.2.2 オフライン最小値探索
5.3 優先度付き待ち行列
5.4 ヒープソートアルゴリズム
5.5 辞書としての2分探索木
章末問題

6.2分探索木の拡張
6.1 2分探索木に対する辞書以外の操作
6.2 平衡2分木
6.3 スプレー木
6.4 交差線分対列挙問題
6.6* 最長共通分列
章末問題

7.グラフ
7.1 グラフ
7.2 グラフを表すデータ構造
7.3 無向グラフに対する深さ優先探索
7.4 有向グラフに対する深さ優先探索
7.5* 2連結成分への分解
7.6* 強連結成分への分解
7.7 グラフに対する幅優先探索
7.8* 最短路問題
7.9* 最長路問題
章末問題

8.アルゴリズムの設計法
8.1 分割統治法
 8.1.1 クイックソートアルゴリズム
 8.1.2 交差線分対列挙問題
8.2 動的計画法
 8.2.1 0-1ナップザック問題
 8.2.2 2変量最適化
 8.2.3 全点対間最短路問題
8.3 貪欲アルゴリズム
8.4 分枝限定法
 8.4.1 0-1ナップザック問題
 8.4.2 1次元配置問題
8.5 枝狩り探索法
章末問題

9.計算量の下界とNP完全性
9.1 計算可能性
9.2 計算量の下界
 9.2.1 計算量の記法
 9.2.2 判定木を用いた計算量の下界の解析
9.3 NP完全
 9.3.1 非決定性アルゴリズムとクラスNP
 9.3.2 NP完全
 9.3.3 多項式変換の例
章末問題

10.NP困難と近似アルゴリズム
10.1 NP困難
10.2 近似アルゴリズム
 10.2.1 絶対近似アルゴリズム
 10.2.2 ε近似アルゴリズム
10.3 ε近似スキーム
 10.3.1 強多項式時間ε近似スキーム
 10.3.2 強NP困難と強多項式時間近似スキーム
10.4 逐次改良法
 10.4.1 アニーリング法
 10.4.2 遺伝的アルゴリズム
章末問題

11.ハードウェアアルゴリズム
11.1 アルゴリズムの記述とその実現
 11.1.1 逐次処理型加減算器
 11.1.2 並列処理型加減算器
11.2 整数の乗算
11.3 乗算の高速化1
11.4 乗算の高速化2
 11.4.1 ブースの符号化
 11.4.2 パイプライン処理
11.5 除算アルゴリズム
11.6 高速乗算器を用いた除算アルゴリズム
章末問題

付録
I.2項関係
II.再帰方程式の一般解
III.疑似乱数の生成
IV.クローズドハッシュの平均計算量
V.アッカーマン関数とその逆関数
VI.2分探索木の計算量
VII.AVL木の高さと点の個数の関係(定係数線形差分方程式の一般解)
VIII.クイックソートの平均計算量
IX.マトロイド

参考文献
索引

amazonレビュー

築山 修治(ツキヤマ シュウジ)