抽象データ型とアルゴリズム

書影

Information & Computing  73

抽象データ型とアルゴリズム

定価:
4,510
(本体:4,100円+税)
難易度:上級

発行日:1993年10月1日

発行:サイエンス社

ISBN:978-4-7819-0712-3

サイズ:並製A5

ページ数:440ページ

在庫:品切れ

内容詳細

本書はデータ構造とプログラミングの中級・上級向きに書かれており,データ構造の設計に抽象化の考えを取り入れた先駆的なものである.Pascal風言語でデータ抽象を扱っており,題材とプログラムをより構造化し,抽象データ型とその実現の関係をよりわかりやすく説明している.

目次

1 アルゴリズムの計算量
1-1 アルゴリズムの効率の比較
1-2 アルゴリズムの時間計算量と領域計算量
1-3 漸近的時間計算量−ビッグO記法とビッグΩ記法
1-4 時間計算量の増加率の重要性
1-5 Pascalプログラムの時間計算量を導く規則
1-6 練習問題
2 抽象データ型とプログラム設計
2-1 プログラム設計の要素
2-2 プログラム設計過程での抽象化機構\r
2-3 抽象データ型の厳密な定義
2-4 練習問題
3 基本的な(線形)抽象データ型
3-1 抽象データ型スタック
3-2 抽象データ型キュー
3-3 抽象データ型リスト
3-4 事例研究:算術式の評価
3-5 練習問題
4 非線形抽象データ型木
4-1 木
4-2 二分木
4-3 ひもつき二分木
4-4 二分探索木
4-5 平衡木:AVL木
4-6 平衡木:B木
4-7 練習問題
5 抽象データ型 集合-I
5-1 抽象データ型集合
5-2 ビット・ベクトルを使った集合の実現
5-3 リストによる集合の実現
5-4 木を使った集合の実現
5-5 練習問題
6 抽象データ型 集合-II
6-1 抽象データ型写像
6-2 ハッシュ法(キー変換)
6-3 優先度つきキュー
6-4 抽象データ型関係
6-5 練習問題
7 非線形抽象データ型グラフ
7-1 定義と用語
7-2 抽象データ型グラフとその実現
7-3 極大木
7-4 経路発見アルゴリズム
7-5 練習問題
8 効率のよいアルゴリズムを開発するための技法
8-1 分割統治法
8-2 動的計画法
8-3 他の技法
8-4 練習問題
9 ソーティング:抽象データ型リスト上のアルゴリズム
9-1 抽象ソーティング・アルゴリズム
9-2 分割容易/結合困難ソーティング・アルゴリズム
9-3 分割困難/結合容易ソーティング・アルゴリズム
9-4 要素の表現を利用したソーティング
9-5 分類,比較,関連問題
9-6 練習問題
10 グラフのなぞりとアルゴリズム
10-1 深さ優先探索
10-2 幅優先探索
10-3 閉路の検出
10-4 トポロジカル順序づけ
10-5 グラフの連結性
10-6 練習問題
11 文字列探索アルゴリズム
11-1 定義
11-2 文字列のデータ構造
11-3 文字列探索アルゴリズム
11-4 大きな静的文字列での文字列探索
11-5 練習問題
12 困難な問題とNP完全性
12-1 NP問題とNP完全問題
12-2 むずかしい問題を解く方法
12-3 練習問題
13 精選問題の解答

サポート情報