Pythonによる問題解決のためのアルゴリズム設計技法

2020年11月14日

技術評論社

著者：Magnus Lie Hetland
監訳：辻真吾
訳者：塩井宏亮

著者について
テクニカルレビュアーについて
謝辞
序文
訳者まえがき
Pythonバージョンとサンプルコードについて
実行環境について
演習問題について
謝辞
日本語版監訳者より

第1章どんな本なのか？
1-1 本書の内容（つまり，何に関する本なのか？）
1-2 本書を読む理由（なぜ，あなたはここにたどり着いたのか？）
1-3 本書を読むにあたって（前提条件）
　Column 必要なものを手に入れよう
1-4 本書の構成
1-5 まとめ
1-6 興味のある方へ
1-7 演習問題
1-8 参考文献

第2章アルゴリズム解析の基礎
2-1 計算機における重要な考え
2-2 漸近記法
　ブラックボックス list
　ギリシャ語はちんぷんかんぷん！
　交通ルール
　漸近法の試し乗り
　3つの大事なケース
　実験に基づいたアルゴリズムの評価
　ヒント1 できるかぎり，心配しない
　ヒント2 時間測定にはtimeit を使おう
　ヒント3 ボトルネックを見つけるために，プロファイラを使おう
　ヒント4 結果を可視化しよう
　ヒント5 時間の比較によって結論を導き出すときは要注意
　ヒント6 実験によって漸近性について結論を出すときは要注意
2-3 グラフと木構造の実装
　ブラックボックス dictとset
　隣接リストなど
　隣接行列
　Column 特殊な目的のNumPy配列
　木構造の実装
　Column Bunchパターン
　多様な表現
　Column グラフライブラリ
2-4 ブラックボックスにご注意を
　隠れた二乗項
　浮動小数点を使うときの問題
　Column 数学のちょっとした復習
2-5 まとめ
2-6 さらに興味のある方へ
2-7 演習問題
2-8 参考文献

第3章数え上げ入門
3-1 総和をひとかじり
　ギリシャ語をまた少し
　総和を使ってみる
3-2 トーナメントに関する2 つの物語
　握手問題
　ウサギとカメ
　Column なぜ二進数が使えるのか
3-3 部分集合と並べ替えと組み合わせ
　Column 擬似多項式時間
3-4 再帰と漸化式
　自分の手で計算してみよう
　いくつかの大事な例
　推定と確認
　Column ウサギの穴へ−変数を変えてみる
　マスター定理：クッキー型解法
3-5 いったい何についての話だったのか？
3-6 まとめ
3-7 興味のある方へ
3-8 演習問題
3-9 参考文献

第4章帰納と再帰と還元
4-1 なるほど，それなら簡単だよ！
4-2 いち，に，たくさーん
4-3 鏡よ，鏡
　Column チェッカーボード問題の実装
　Column 還元はどこに使われていたのか？
4-4 帰納法と再帰を使って設計する
　最大置換問題
　セレブ問題
　トポロジカルソート
　ブラックボックストポロジカルソートとPython MRO
4-5 強い仮定
　Column 逆帰納法と2のべき乗
4-6 不変式と正しさ
4-7 緩和とゆっくりとした改善
4-8 還元 + 対偶 = 困難さの証明
4-9 問題解決のアドバイス
4-10 まとめ
4-11 興味のある方へ
4-12 演習問題
4-13 参考文献

第5章巡回：アルゴリズムのマスターキー
　Column Kaliningradの島巡り
5-1 公園の中の散歩
　サイクル禁止
　無限ループから抜け出す方法
5-2 深く行こう！
　深さ優先時刻と（ふたたび）トポロジカルソート
　Column ノードの色とエッジの型
5-3 無限の迷路と（重みなし）最短経路
　ブラックボックス deque
5-4 強連結成分
　Column ゴールと枝刈り
5-5 まとめ
5-6 興味のある方へ
5-7 演習問題
5-8 参考文献

第6章分割・統合・統治
6-1 木構造型問題：バランスがすべて
6-2 標準的なD&C アルゴリズム
6-3 半分にしながら探索
　ブラックボックス bisect
　枝刈りを使った探索木の横断的走査
　Column 二分法・二分探索木・ハッシュテーブルのどれを選ぶ？
　選択アルゴリズム
　Column 線形時間で選択，保証付き！
6-4 半分にしながらソートする
　ブラックボックス TIMSORT
　どうやってソートを速くするか？
6-5 大事な3 つの例
　最近傍ペア問題
　凸包問題
　Column どれくらい早く凸包を見つけ出せるか？
　最大スライス問題
　Column 本当に仕事を分割するマルチプロセシング
6-6 木のバランスと…バランスのとり方
　ブラックボックス Binary Heaps, Heapq, Heapsort
6-7 まとめ
6-8 興味のある方へ
6-9 演習問題
6-10 参考文献

第7章貪欲が善って，ほんとうですか？それなら証明してください
7-1 一歩ずつ安全に
　Column 熱心な求婚者と安定した結婚
7-2 ナップサック問題
　有理ナップサック問題
　整数ナップサック問題
7-3 Huffmanのアルゴリズム
　アルゴリズム
　最初の貪欲な選択
　残りの道を行く
　最適なマージ
7-4 最小全域木
　最短エッジ
　残りはどうなるでしょうか？
　Kruskal のアルゴリズム
　Primのアルゴリズム
　Column 少し異なる観点
7-5 貪欲法は機能するが，いつ？
　ベストを残せ
　完璧より悪いものはない
　安全には気を付けて
7-6 まとめ
7-7 興味のある方へ
7-8 演習問題
7-9 参考文献

第8章もつれた依存関係とメモ化
8-1 DRY（Don’t Repeat Yourself）の原則
8-2 有向非巡回グラフにおける最短経路
　Column さまざまなDAG 最短経路問題
8-3 最長増加部分列（LIS）
8-4 列の比較
8-5 ナップサック問題の反撃
8-6 二値列分割
8-7 まとめ
8-8 興味のある方へ
8-9 演習問題
8-10 参考文献

第9章 A地点からB地点へEdsger Dijkstraとその仲間たちとともに
9-1 知識の伝播
9-2 狂ったように緩和する
9-3 隠れたDAG を見つける
9-4 万人対万人
9-5 突拍子もない部分問題
9-6 中間で会う
9-7 どこに向かっているのかを知る
9-8 まとめ
9-9 興味のある方へ
9-10 演習問題
9-11 参考文献

第10章マッチング・カット・フロー
10-1 二部マッチング
10-2 辺素な道
10-3 最大フロー
　残余ネットワーク
10-4 最小カット
　双対性
10-5 最小コストフローと割り当て問題
10-6 応用例
　野球の優勝チーム推定問題
　代表者の選択問題
　長期休暇中の医師の出勤シフト
　需要と供給
　一貫性のある行列の丸め
10-7 まとめ
10-8 興味のある方へ
10-9 演習問題
10-10 参考文献

第11章困難な問題と適度ないい加減さ
11-1 再び還元
　Column 部分問題による還元
11-2 カンザスはどこへ？
11-3 その頃，カンザスでは…
　Column Co-NPとAlgorithmicaの不思議の国の非対称性
11-4 とはいえ，どこから始め，どこへ向かいましょうか？
　Column 2-SATはNP完全？
　終わりのない物語
11-5 怪獣動物園
　ナップサック問題再び
　クリークと色塗り
　経路と回路
11-6 困難な状況になると，賢いものはいい加減になる
11-7 必死に解を求めて
11-8 物語の教訓は何だったのか
11-9 まとめ
11-10 興味のある方へ
11-11 演習問題
11-12 参考文献