情報
世界標準MIT教科書 アルゴリズムイントロダクション 第3版 総合版
原著は，計算機科学の基礎分野で世界的に著名な4人の専門家がMITでの教育用に著した計算機アルゴリズム論の包括的テキストであり，その第3版．前版までで既にアルゴリズムとデータ構造に関する世界標準教科書としての地位を確立しているが，より良い教科書を目指して再び全面的な記述の見直しがなされ，それを基に新たな章や節の追加なども含めて，大幅な改訂がなされている．
単にアルゴリズムをわかりやすく解説するだけでなく，最終的なアルゴリズム設計に至るまでに，どのような概念が必要で，それがどのように解析に裏打ちされているのかを科学的に詳述している．
さらに各節末には練習問題（全957題）が，また章末にも多様なレベルの問題が多数配置されており（全158題），学部や大学院の講義用教科書として，また技術系専門家のハンドブックあるいはアルゴリズム大事典としても活用できる．
本書は，原著の第1～35章，および付録A～Dまでの完訳総合版である．また巻末の索引も圧巻で，和（英）‐英（和）という構成により，「数理用語辞典」としてもまことに有用である．
電子書籍¥15,400 小売希望価格（税込）
紙の書籍¥15,400定価（税込）
基本情報
| 発売日 | 2013年12月17日 |
|---|---|
| 本体価格 | 14,000円 |
| ページ数 | 1120 ページ ※印刷物 |
| サイズ | B5 |
| ISBN | 9784764904088 |
| ジャンル | 情報 |
| タグ | アルゴリズム |
| 電子書籍形式 | 固定型 |
主要目次
まえがき
I 基 礎
序 論
1 計算におけるアルゴリズムの役割
1.1 アルゴリズム
1.2 科学技術としてのアルゴリズム
2 さあ，始めよう
2.1 挿入ソート
2.2 アルゴリズムの解析
2.3 アルゴリズムの設計
3 関数の増加
3.1 漸近記法
3.2 標準的な記法と一般的な関数
4 分割統治
4.1 最大部分配列問題
4.2 行列積のための Strassen のアルゴリズム
4.3 漸化式を解くための置換え法
4.4 漸化式を解くための再帰木法
4.5 漸化式を解くためのマスター法
★4.6 マスター定理の証明
5 確率的解析と乱択アルゴリズム
5.1 雇用問題
5.2 指標確率変数
5.3 乱択アルゴリズム
★5.4 確率的解析と指標確率変数のさらなる利用
II ソートと順序統計量
序 論
6 ヒープソート
6.1 ヒープ
6.2 ヒープ条件の維持
6.3 ヒープの構築
6.4 ヒープソートアルゴリズム
6.5 優先度付きキュー
7 クイックソート
7.1 クイックソートの記述
7.2 クイックソートの性能
7.3 乱択版クイックソート
7.4 クイックソートの解析
8 線形時間ソート
8.1 ソートの下界
8.2 計数ソート
8.3 基数ソート
8.4 バケツソート
9 中央値と順序統計量
9.1 最大値と最小値
9.2 線形期待時間選択アルゴリズム
9.3 線形最悪時間選択アルゴリズム
III データ構造
序 論
10 基本データ構造
10.1 スタックとキュー
10.2 連結リスト
10.3 ポインタとオブジェクトの実現
10.4 根付き木の表現
11 ハッシュ表
11.1 直接アドレス表
11.2 ハッシュ表
11.3 ハッシュ関数
11.4 オープンアドレス指定法
★11.5 完全ハッシュ法
12 2 分探索木
12.1 2 分探索木
12.2 2 分探索木に対する質問
12.3 挿入と削除
★12.4 ランダムに構成した 2 分探索木
13 2 色木
13.1 2 色木の性質
13.2 回 転
13.3 挿 入
13.4 削 除
14 データ構造の補強
14.1 動的順序統計量
14.2 データ構造補強法
14.3 区間木
IV 高度な設計と解析の手法
序 論
15 動的計画法
15.1 ロッド切出し
15.2 連鎖行列積
15.3 動的計画法の基本要素
15.4 最長共通部分列
15.5 最適 2 分探索木
16 貪欲アルゴリズム
16.1 活動選択問題
16.2 貪欲戦略の基本要素
16.3 ハフマン符号
★16.4 マトロイドと貪欲法
★16.5 マトロイドとしてのタスクスケジューリング問題
17 ならし解析
17.1 集計法
17.2 出納法
17.3 ポテンシャル法
17.4 動的な表
V 高度なデータ構造
序 論
18 B 木
18.1 B 木の定義
18.2 B 木上の基本操作
18.3 B 木からのキーの削除
19 フィボナッチヒープ
19.1 フィボナッチヒープの構造
19.2 マージ可能ヒープ操作
19.3 キー値の下方修正と節点の削除
19.4 最大次数の上界
20 van Emde Boas 木
20.1 設計方針の予備的考察
20.2 再帰構造
20.3 van Emde Boas 木
21 互いに素な集合族のためのデータ構造
21.1 互いに素な集合族の操作
21.2 連結リストによる互いに素な集合族の表現
21.3 互いに素な集合の森
★21.4 経路圧縮を用いるランクによる合併の解析
VI グラフアルゴリズム
序 論
22 基本的グラフアルゴリズム
22.1 グラフの表現
22.2 幅優先探索
22.3 深さ優先探索
22.4 トポロジカルソート
22.5 強連結成分
23 最小全域木
23.1 成長法による最小全域木の生成
23.2 Kruskal と Prim のアルゴリズム
24 単一始点最短路問題
24.1 Bellman–Ford アルゴリズム
24.2 有向非巡回グラフにおける単一始点最短路
24.3 Dijkstra のアルゴリズム
24.4 差分制約と最短路
24.5 最短路の性質の証明
25 全点対最短路
25.1 最短路と行列積
25.2 Floyd–Warshall アルゴリズム
25.3 疎グラフに対する Johnson のアルゴリズム
26 最大フロー
26.1 フローネットワーク
26.2 Ford–Fulkerson 法
26.3 2 部グラフの最大マッチング
★26.4 プッシュ再ラベルアルゴリズム
★26.5 再ラベルフロント移動アルゴリズム
VII 精選トピックス
序 論
27 マルチスレッドアルゴリズム
27.1 動的マルチスレッドの基礎
27.2 行列乗算のためのマルチスレッドアルゴリズム
27.3 マージソートのマルチスレッド化
28 行列演算
28.1 連立 1 次方程式の解法
28.2 逆行列の計算
28.3 対称正定値行列と最小 2 乗近似
29 線形計画法
29.1 標準形とスラック形
29.2 線形計画としての問題の定式化
29.3 シンプレックスアルゴリズム
29.4 双対性
29.5 初期実行可能基底解
30 多項式と FFT
30.1 多項式の表現
30.2 DFT と FFT
30.3 効率の良い FFT の実現
31 整数論的アルゴリズム
31.1 整数論の基本概念
31.2 最大公約数
31.3 剰余演算
31.4 1 次合同式の解法
31.5 中国人剰余定理
31.6 要素のベキ乗
31.7 RSA 公開鍵暗号系
★31.8 素数判定
★31.9 整数の素因数分解
32 文字列照合
32.1 素朴な文字列照合アルゴリズム
32.2 Rabin–Karp アルゴリズム
32.3 有限オートマトンを用いる文字列照合
★32.4 Knuth–Morris–Pratt アルゴリズム
33 計算幾何学
33.1 線分の性質
33.2 線分交差判定
33.3 凸包の構成
33.4 最近点対の発見
34 NP 完全性
34.1 多項式時間
34.2 多項式時間検証
34.3 NP 完全性と帰着可能性
34.4 NP 完全性の証明
34.5 NP 完全問題
35 近似アルゴリズム
35.1 頂点被覆問題
35.2 巡回セールスマン問題
35.3 集合被覆問題
35.4 乱択化と線形計画法
35.5 部分和問題
VIII 付録：数学的基礎
序 論
A 和
A.1 和の公式と性質
A.2 和の上界と下界
B 集合など
B.1 集 合
B.2 関 係
B.3 関 数
B.4 グラフ
B.5 木
C 数え上げと確率
C.1 数え上げ
C.2 確 率
C.3 離散確率変数
C.4 幾何分布と 2 項分布
★C.5 2 項分布の裾
D 行 列
D.1 行列と行列演算
D.2 行列の基礎的性質
参考文献
訳者あとがき
教授の名前
索 引
人名読み方ガイド
I 基 礎
序 論
1 計算におけるアルゴリズムの役割
1.1 アルゴリズム
1.2 科学技術としてのアルゴリズム
2 さあ，始めよう
2.1 挿入ソート
2.2 アルゴリズムの解析
2.3 アルゴリズムの設計
3 関数の増加
3.1 漸近記法
3.2 標準的な記法と一般的な関数
4 分割統治
4.1 最大部分配列問題
4.2 行列積のための Strassen のアルゴリズム
4.3 漸化式を解くための置換え法
4.4 漸化式を解くための再帰木法
4.5 漸化式を解くためのマスター法
★4.6 マスター定理の証明
5 確率的解析と乱択アルゴリズム
5.1 雇用問題
5.2 指標確率変数
5.3 乱択アルゴリズム
★5.4 確率的解析と指標確率変数のさらなる利用
II ソートと順序統計量
序 論
6 ヒープソート
6.1 ヒープ
6.2 ヒープ条件の維持
6.3 ヒープの構築
6.4 ヒープソートアルゴリズム
6.5 優先度付きキュー
7 クイックソート
7.1 クイックソートの記述
7.2 クイックソートの性能
7.3 乱択版クイックソート
7.4 クイックソートの解析
8 線形時間ソート
8.1 ソートの下界
8.2 計数ソート
8.3 基数ソート
8.4 バケツソート
9 中央値と順序統計量
9.1 最大値と最小値
9.2 線形期待時間選択アルゴリズム
9.3 線形最悪時間選択アルゴリズム
III データ構造
序 論
10 基本データ構造
10.1 スタックとキュー
10.2 連結リスト
10.3 ポインタとオブジェクトの実現
10.4 根付き木の表現
11 ハッシュ表
11.1 直接アドレス表
11.2 ハッシュ表
11.3 ハッシュ関数
11.4 オープンアドレス指定法
★11.5 完全ハッシュ法
12 2 分探索木
12.1 2 分探索木
12.2 2 分探索木に対する質問
12.3 挿入と削除
★12.4 ランダムに構成した 2 分探索木
13 2 色木
13.1 2 色木の性質
13.2 回 転
13.3 挿 入
13.4 削 除
14 データ構造の補強
14.1 動的順序統計量
14.2 データ構造補強法
14.3 区間木
IV 高度な設計と解析の手法
序 論
15 動的計画法
15.1 ロッド切出し
15.2 連鎖行列積
15.3 動的計画法の基本要素
15.4 最長共通部分列
15.5 最適 2 分探索木
16 貪欲アルゴリズム
16.1 活動選択問題
16.2 貪欲戦略の基本要素
16.3 ハフマン符号
★16.4 マトロイドと貪欲法
★16.5 マトロイドとしてのタスクスケジューリング問題
17 ならし解析
17.1 集計法
17.2 出納法
17.3 ポテンシャル法
17.4 動的な表
V 高度なデータ構造
序 論
18 B 木
18.1 B 木の定義
18.2 B 木上の基本操作
18.3 B 木からのキーの削除
19 フィボナッチヒープ
19.1 フィボナッチヒープの構造
19.2 マージ可能ヒープ操作
19.3 キー値の下方修正と節点の削除
19.4 最大次数の上界
20 van Emde Boas 木
20.1 設計方針の予備的考察
20.2 再帰構造
20.3 van Emde Boas 木
21 互いに素な集合族のためのデータ構造
21.1 互いに素な集合族の操作
21.2 連結リストによる互いに素な集合族の表現
21.3 互いに素な集合の森
★21.4 経路圧縮を用いるランクによる合併の解析
VI グラフアルゴリズム
序 論
22 基本的グラフアルゴリズム
22.1 グラフの表現
22.2 幅優先探索
22.3 深さ優先探索
22.4 トポロジカルソート
22.5 強連結成分
23 最小全域木
23.1 成長法による最小全域木の生成
23.2 Kruskal と Prim のアルゴリズム
24 単一始点最短路問題
24.1 Bellman–Ford アルゴリズム
24.2 有向非巡回グラフにおける単一始点最短路
24.3 Dijkstra のアルゴリズム
24.4 差分制約と最短路
24.5 最短路の性質の証明
25 全点対最短路
25.1 最短路と行列積
25.2 Floyd–Warshall アルゴリズム
25.3 疎グラフに対する Johnson のアルゴリズム
26 最大フロー
26.1 フローネットワーク
26.2 Ford–Fulkerson 法
26.3 2 部グラフの最大マッチング
★26.4 プッシュ再ラベルアルゴリズム
★26.5 再ラベルフロント移動アルゴリズム
VII 精選トピックス
序 論
27 マルチスレッドアルゴリズム
27.1 動的マルチスレッドの基礎
27.2 行列乗算のためのマルチスレッドアルゴリズム
27.3 マージソートのマルチスレッド化
28 行列演算
28.1 連立 1 次方程式の解法
28.2 逆行列の計算
28.3 対称正定値行列と最小 2 乗近似
29 線形計画法
29.1 標準形とスラック形
29.2 線形計画としての問題の定式化
29.3 シンプレックスアルゴリズム
29.4 双対性
29.5 初期実行可能基底解
30 多項式と FFT
30.1 多項式の表現
30.2 DFT と FFT
30.3 効率の良い FFT の実現
31 整数論的アルゴリズム
31.1 整数論の基本概念
31.2 最大公約数
31.3 剰余演算
31.4 1 次合同式の解法
31.5 中国人剰余定理
31.6 要素のベキ乗
31.7 RSA 公開鍵暗号系
★31.8 素数判定
★31.9 整数の素因数分解
32 文字列照合
32.1 素朴な文字列照合アルゴリズム
32.2 Rabin–Karp アルゴリズム
32.3 有限オートマトンを用いる文字列照合
★32.4 Knuth–Morris–Pratt アルゴリズム
33 計算幾何学
33.1 線分の性質
33.2 線分交差判定
33.3 凸包の構成
33.4 最近点対の発見
34 NP 完全性
34.1 多項式時間
34.2 多項式時間検証
34.3 NP 完全性と帰着可能性
34.4 NP 完全性の証明
34.5 NP 完全問題
35 近似アルゴリズム
35.1 頂点被覆問題
35.2 巡回セールスマン問題
35.3 集合被覆問題
35.4 乱択化と線形計画法
35.5 部分和問題
VIII 付録：数学的基礎
序 論
A 和
A.1 和の公式と性質
A.2 和の上界と下界
B 集合など
B.1 集 合
B.2 関 係
B.3 関 数
B.4 グラフ
B.5 木
C 数え上げと確率
C.1 数え上げ
C.2 確 率
C.3 離散確率変数
C.4 幾何分布と 2 項分布
★C.5 2 項分布の裾
D 行 列
D.1 行列と行列演算
D.2 行列の基礎的性質
参考文献
訳者あとがき
教授の名前
索 引
人名読み方ガイド