Pythonによる問題解決のためのアルゴリズム設計技法
書籍情報
発売日 : 2020年11月13日
著者／編集 : Magnus Lie Hetland/辻 真吾/塩井 宏亮
出版社 : 技術評論社
発行形態 : 単行本
書籍説明
内容紹介
プログラミングとコンピュータサイエンスの最も重要で難しい分野を非常に読みやすい形で解説。アルゴリズムの理論とプログラミングの実践の両方をカバーし、理論が実際のＰｙｔｈｏｎプログラムにどのように反映されているかを説明。Ｐｙｔｈｏｎに組み込まれている有名なアルゴリズムとデータ構造について説明している。
目次
第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 参考文献
付録A 全力疾走 - Pythonを最大限加速させるには
付録B 問題とアルゴリズムの一覧
B-1 問題
B-2 アルゴリズムとデータ構造
付録C グラフに関する用語と表記
付録D 演習のヒント
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 参考文献
付録A 全力疾走 - Pythonを最大限加速させるには
付録B 問題とアルゴリズムの一覧
B-1 問題
B-2 アルゴリズムとデータ構造
付録C グラフに関する用語と表記
付録D 演習のヒント
著者情報
Hetland, Magnus Lie
magnus lie hetland
辻 真吾
監訳者 辻 真吾（つじしんご） 現在、東京大学先端科学技術研究センターに所属。2000年東京大学大学院工学系研究科修了。創業間もないベンチャー企業に就職しJavaを用いたWebアプリ開発に従事。バイオインフォマティクスの研究を志し、退職して現在の勤務先に博士課程の学生として復学。2000年代中頃からPythonに注目し、2010年に「Pythonスタートブック（技術評論社）」を出版。その他にも「Pythonで学ぶアルゴリズムとデータ構造（講談社）」など著書多数。Start Python Clubを主宰し、2015年から月に1回「みんなのPython勉強会」を開催している。 最近は要素還元主義に立脚した科学研究や社会システムに限界を感じており、複雑系やその1分野としてのAgent-based modeling（ABM）に興味がある。 おいしい食事とお酒が好き。
辻, 真吾
塩井 宏亮
訳者 塩井宏亮（しおいひろあき） 東京大学大学院工学系研究科航空宇宙工学専攻を修了後、2014年に日本General Electric (GE) に入社。 2016年にデータサイエンティストとしてアメリカ（カリフォルニア州）のGE Digital本社へ転籍。金融、電力、製造業、ヘルスケアなどを中心に、様々な産業分野の顧客へコンサルティングサービスを提供。顧客の問題発見からアルゴリズム開発・実装、プロトタイプまでを手掛ける。現在、同じくカリフォルニア州に本社を置くスタートアップ dotData, Inc. にてデータサイエンティストとして活動中
塩井, 宏亮
