アルゴリズム
- 通常版Digital1,500 JPY
- 学生版Digital0 JPY
Jeff Erickson 著 Algorithms の翻訳です。 フォーマット: PDF ページ数: 438
この本について
この本は Jeff Erickson 著 Algorithms の翻訳です。英語版は CC-BY 4.0 ライセンスで配布されており、 http://jeffe.cs.illinois.edu/teaching/algorithms/ から無料で入手できます。 この本は CC-BY 4.0 ライセンスの許諾に基づいて販売されます。 この本の HTML 版は https://inzkyk.xyz/algorithms/ で公開されています。 扱うトピックや対象読者については HTML 版の前書き https://inzkyk.xyz/algorithms/preface/ をご覧ください。 学生版は無料です。審査などはありませんので、「自分は学生だ！」と自信を持って言える方はぜひダウンロードしてください。 学生版には表紙と奥付けに「学生版」という表示があります。それ以外は通常版と同じです。
リンク
- CC-BY 4.0 ライセンス: https://creativecommons.org/licenses/by/4.0/ - 英語版ページ: http://jeffe.cs.illinois.edu/teaching/algorithms/ - 日本語 HTML 版ページ: https://inzkyk.xyz/algorithms/
目次
前書き 第 0 章 イントロダクション 0.1 アルゴリズムとは何か？ 0.2 掛け算 0.3 議会の議席配分 0.4 悪い例 0.5 アルゴリズムの説明 0.6 アルゴリズムの解析 0.7 練習問題 第 1 章 再帰 1.1 帰着 1.2 単純にして任せる 1.3 Hanoi の塔 1.4 マージソート 1.5 クイックソート 1.6 パターン 1.7 再帰木 1.8 ♥ 線形選択 1.9 高速乗算 1.10 べき乗 1.11 練習問題 第 2 章 バックトラッキング 2.1 N クイーン 2.2 ゲーム木 2.3 部分和 2.4 共通するパターン 2.5 分かち書き (Interpunctio Verborum) 2.6 最長増加部分列 2.7 最長増加部分列 テイク 2.8 最適二分探索木 2.9 練習問題 第 3 章 動的計画法 3.1 Mātrāvṛtta 3.2 ♥ 余談 : さらに高速な Fibonacci 数 3.3 分かち書き (Interpunctio Verborum) 再訪 3.4 パターン : 賢い再帰 3.5 警告 : 貪欲は愚か 3.6 最長増加部分列 3.7 編集距離 3.8 部分和問題 3.9 最適二分探索木 3.10 木の上の動的計画法 3.11 練習問題 第 4 章 貪欲アルゴリズム 4.1 テープへのファイルの保存 4.2 講義のスケジューリング 4.3 共通するパターン 4.4 Huffman 符号 4.5 安定マッチング 4.6 練習問題 第 5 章 基本的なグラフアルゴリズム 5.1 導入と歴史 5.2 基本的な定義 5.3 グラフの表現と例 5.4 データ構造 5.5 何か優先探索 5.6 重要な変種 5.7 グラフへの帰着 5.8 練習問題 第 6 章 深さ優先探索 6.1 行きがけ順と帰りがけ順 6.2 閉路の検出 6.3 トポロジカルソート 6.4 メモ化と動的計画法 6.5 強連結性 6.6 線形時間で強連結成分を求める 6.7 練習問題 第 7 章 最小全域木 7.1 辺の重みが異なる場合 7.2 唯一の全域最小木アルゴリズム 7.3 Borůvka のアルゴリズム 7.4 Jarník の (Prim の) アルゴリズム 7.5 Kruskal のアルゴリズム 7.6 練習問題 第 8 章 最短路 8.1 最短路木 8.2 唯一の SSSP アルゴリズム 8.3 重み無しグラフ : 幅優先探索 8.4 有向非巡回グラフ : 深さ優先探索 8.5 最良優先 : Dijkstra のアルゴリズム 8.6 スベテの辺を緩和する : Bellman-Ford 8.7 練習問題 第 9 章 全組最短路 9.1 導入 9.2 たくさんの単一ソース 9.3 重みの変更 9.4 Johnson のアルゴリズム 9.5 動的計画法 9.6 分割統治 9.7 おかしな行列積 9.8 (Kleene-Roy-) Floyd-Warshall (-Ingerman) 9.9 練習問題 第 10 章最大フローと最小カット 10.1 フロー 10.2 カット 10.3 最大フロー最小カット定理 10.4 Ford と Fulkerson の増加路アルゴリズム 10.5 フローの合成と分解 10.6 Edmonds と Karp のアルゴリズム 10.7 さらなる進展 10.8 練習問題 第 11 章フローとカットの応用 11.1 辺素路 11.2 頂点容量と頂点素路 11.3 二部マッチング 11.4 タプル選択 11.5 素路被覆 11.6 ペナントレースにおける敗退 11.7 プロジェクト選択 11.8 練習問題 第 12 章 NP 困難性 12.1 勝てないゲーム 12.2 P 対 NP 12.3 NP 困難・ NP 容易・ NP 完全 12.4 ♥ きちんとした定義 (HC SVNT DRACONES) 12.5 帰着と SAT 12.6 3 SAT (CircuitSAT からの帰着) 12.7 最大独立集合 (3SAT からの帰着) 12.8 共通するパターン 12.9 クリークと頂点被覆 (最大独立集合からの帰着) 12.10 グラフの彩色 (3SAT からの帰着) 12.11 ハミルトン閉路 12.12 部分和 (最小頂点被覆からの帰着) 12.13 その他の便利な NP 困難問題 12.14 正しい問題を選ぶ 12.15 ちょっとした現実世界の例 12.16 ♥ 縞模様を超えて 12.17 練習問題
更新履歴
2019/12/08 公開 2020/03/08 誤字の修正 2024/02/02 誤字の修正