Ｃによるアルゴリズムとデータ構造（改訂2版）

茨木 俊秀

株式会社 オーム社, May 30, 2019 - Computers - 258 pages

良いプログラムを書くための必須知識をまとめたテキストであり、五輪の書。

本書は、長年にわたって数多くの優秀なシステムエンジニア、プログラマーに愛読されてきた、良いプログラムを書くための必須知識をまとめたテキストです。

　うまくつくられたプログラムは、理解しやすく実行効率も高いものですが、一方、そうでないものは解読も困難なうえに、やたら時間や領域をくいます。さらに、そのようなまずいプログラムには、えてしてミスや内容的な誤りも隠されているものです。

　本書は、新たなアルゴリズムで新たなプログラミングを行うために覚えておかなくてはいけない必須知識、そしてアルゴリズムの設計、実現における基礎を、実用上の価値に重点を置いてまとめています。

　今回の改訂においては、多くの読者の声をよく参考にして、よりわかりやすく、簡明になるよう見直しを行ったほか、接尾辞木について新たな解説を加えています。

　システムエンジニア、プログラマーとして活躍される方の五輪書です。

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

   1.1　計算とアルゴリズム

   1.2　アルゴリズムの例

   1.3　計算量の評価

   1.4　プログラムの設計をめぐる話題

   演習問題

第2章　基本的なデータ構造

   2.1　リストとその実現

   2.2　スタック，待ち行列など

   2.3　グラフ，木と2分木

   2.4　集合と辞書

      2.4.1　集合

      2.4.2　辞書とハッシュ表

   2.5　集合族の併合

   演習問題

第3章　順序つき集合の処理

   3.1　順序の定義と必要な作業

   3.2　優先度つき待ち行列，ヒープ

   3.3　2分探索木

   3.4　平衡探索木

   演習問題

第4章　整列のアルゴリズム

   4.1　整列アルゴリズム概観

   4.2　バブルソート

   4.3　バケットソートと基数ソート

      4.3.1　バケットソート

      4.3.2　基数ソート

   4.4　ヒープソート

   4.5　クイックソート

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

   4.7 第p要素の選択

      4.7.1　QUICKSELECTとSELECT

      4.7.2　確率アルゴリズムLAZYSELECT

   演習問題

第5章　アルゴリズムの設計

   5.1　整列データの処理

      5.1.1　整列配列の併合

      5.1.2　2分探索

      5.1.3　ニュートン法による零点の計算

   5.2　分割統治法

      5.2.1　マージソート

      5.2.2　長大数の掛け算

      5.2.3　再帰方程式の漸近解

   5.3　動的計画法

      5.3.1　SUBSET-SUM問題

      5.3.2　直線上の配達スケジューリング

   演習問題

第6章　アルゴリズムの実現

   6.1　簡単な最適化問題

      6.1.1　資源配分問題

      6.1.2　ナップサック問題

   6.2　グラフに関するいくつかの問題

      6.2.1　最小木

      6.2.2　最短路問題

      6.2.3　深さ優先探索と関節点の計算

   6.3　文字列の照合

   6.4　計算幾何の話題から

      6.4.1　初等幾何学の計算

      6.4.2　ボロノイ図

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

   演習問題

付記：Cメモ

演習問題：ヒントと略解

Contents

• 1 アルゴリズムとその計算量: 1
• 12 アルゴリズムの例: 5
• アルゴリズムの起源: 13
• 13 計算量の評価: 14
• 14 プログラムの設計をめぐる話題: 20
• 出典: 25
• 計算量の恐さ: 26
• 2 基本的なデータ構造: 29
• 22 スタック待ち行列など: 35
• 23 グラフ木と2分木: 42
• 24 集合と辞書: 53
• 242 辞書とハッシュ表: 55
• 25 集合族の併合: 63
• 出典: 69
• 図形の再帰構造フラクタル: 70
• 3 順序つき集合の処理: 71
• 32 優先度つき待ち行列ヒープ: 72
• 33 2分探索木: 78
• 34 平衡探索木: 84
• 出典: 90
• アルゴリズムと特許: 91
• 4 整列のアルゴリズム: 93
• 42 バブルソート: 94
• 43 バケットソートと基数ソート: 96
• 431 バケットソート: 97
• 432 基数ソート: 98
• 44 ヒープソート: 101
• 45 クイックソート: 103
• 46 整列アルゴリズムの計算量の下界: 109
• 47 第p要素の選択: 111
• 471 QUICKSELECTとSELECT: 112
• 472 確率アルゴリズムLAZYSELECT: 116
• 出典: 117
• 演習問題: 118
• ハードウェアアルゴリズム: 120
• 5 アルゴリズムの設計: 123
• 512 2分探索: 125
• 513 ニュートン法による零点の計算: 129
• 52 分割統治法: 131
• 521 マージソート: 132
• 522 長大数の掛け算: 134
• 523 再帰方程式の漸近解: 135
• 531 SUBSETSUM問題: 136
• 532 直線上の配達スケジューリング: 138
• 出典: 142
• 確率アルゴリズム: 143
• 6 アルゴリズムの実現: 145
• 612 ナップサック問題: 152
• 62 グラフに関するいくつかの問題: 154
• 621 最小木: 157
• 622 最短路問題: 163
• 623 深さ優先探索と関節点の計算: 171
• 63 文字列の照合: 177
• 64 計算幾何の話題から: 182
• 642 ボロノイ図: 184
• 65 関係データベースの処理: 191
• 出典: 197
• 演習問題: 198
• CからC++へ: 200
• Cメモ: 203
• ヒントと略解: 217
• 文献: 226
• 索引: 233
• 奥付: 247

Bibliographic information

• Title: Ｃによるアルゴリズムとデータ構造（改訂2版）
• Author: 茨木 俊秀
• Publisher: 株式会社 オーム社, 2019
• ISBN: 4274223914, 9784274223914
• Length: 258 pages
• Subjects: Computers / General; Computers / Programming / Algorithms