contents memorandum はてな

目次とメモを置いとく場

『Cとアルゴリズムによるデータ構造』(茨木俊秀 オーム社 2014//1999)

著者:茨木 俊秀[いばらき・としひで](1940-) 計算機科学。
カバーデザイン:岡崎 善保(志岐デザイン事務所
NDC:007.64 プログラミング
備考:『Cとアルゴリズムによるデータ構造』(昭晃堂 1999年11月刊行)の再刊。おそらく内容の改定はなされていない。


Cによるアルゴリズムとデータ構造 | Ohmsha


※改訂版(2019年)
Cによるアルゴリズムとデータ構造 改訂2版 | Ohmsha


【目次】
まえがき(1999年10月 京都にて 茨木 俊秀) [1-3]
目次 [1-3]


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

1.2 アルゴリズムの例 005

ひとやすみ:アルゴリズムの起源 013

1.3 計算量の評価 013
    アルゴリズムのステップ数
    関数のオーダー記法ΟとΩとθ
    問題例の規模と計算量
    計算量の上界と下界
    多項式時間

1.4 プログラムの設計をめぐる話題 018
    プログラムの設計
    わかり易いプログラム
    図式プログラミング言語
    並列処理
    外部記憶

1.5 出典 023

演習問題 024
ひとやすみ:計算量の恐さ 025


2 基本的なデータ構造
2.1 リストとその実現 026

2.2 スタック,待ち行列など 031

2.3 グラフ,木と2分木 037

2.4 集合と辞書 049
  2.4.1 集合
  2.4.2 辞書とハッシュ表

2.5 集合族の併合 058

2.6 出典 064
演習問題 064
ひとやすみ:図形の再帰構造――フラクタル 065


3 順序つき集合の処理 
3.1 優先度つき待ち行列,ヒープ 067

3.2 2分探索木 073

3.3 平衡探索木 079

3.4 出典 084

演習問題 084
ひとやすみ:アルゴリズムと特許 085


4 整列のアルゴリズム
4.1 バブルソート 087
4.2 バケットソートと基数ソート 089
  4.2.1 バケットソート 
  4.2.2 基数ソート 

4.3 ヒープソート 094

4.4 クイックソート 096

4.5 整列アルゴリズムの計算量の下界 101

4.6 第p 要素の選択 103
  4.6.1 QUICKSELECT — SELECT 
  4.6.2 確率アルゴリズム LAZYSELECT 

4.7 出典 108
演習問題 
ひとやすみ:ハードウェア・アルゴリズム 


5 アルゴリズムの設計
5.1 整列データの処理 112
  5.1.1 整列配列の併合
  5.1.2 2分探索
  5.1.3 ニュートン法による零点の計算 

5.2 分割統治法 120
  5.2.1 マージソート 
  5.2.2 長大数の掛け算
  5.2.3 再帰方程式の漸近解 

5.3 動的計画法 123
  5.3.3 SUBSET-SUM 問題 
  5.3.2 直線上の配達スケジューリング 

5.4 出典 129

演習問題 129
ひとやすみ:確率アルゴリズム 130


6 アルゴリズムの実現 
6.1 簡単な最適化問題 132
  6.1.1 資源配分問題
  6.1.2 ナップサック問題 

6.2 グラフに関するいくつかの問題 140
  6.2.1 最小木
  6.2.2 最短路問題
  6.2.3 深さ優先探索と関節点の計算 

6.3 文字列の照合 161

6.4 計算幾何の話題から 169
  6.4.1 初等幾何学の計算
  6.4.2 ボロノイ図 

6.5 関係データベースの処理 178

6.6 出典 183

演習問題 184
ひとやすみ:Cから C++へ 187


付記:Cメモ 188
演習問題:ヒントと略解 [199-206]
文献 [207-213]
索引 [214-226]