内容紹介

（概要）

本書（原題：Python Algorithms: Mastering Basic Algorithms in the Python Language）はアルゴリズムの分析と設計方法について、Pythonを使って説明します。古典的なアルゴリズムに焦点を絞って解説していますが、基本的なアルゴリズムによる問題解決の方法もしっかり理解できます。

本書はプログラミングとコンピュータサイエンスの最も重要で難しい分野を非常に読みやすい形で解説しています。アルゴリズムの理論とプログラミングの実践の両方をカバーし、理論が実際のPythonプログラムにどのように反映されているかを説明します。また、Pythonに組み込まれている有名なアルゴリズムとデータ構造について説明し、実装と評価について学ぶことができます。

（こんな方におすすめ）

・Pythonの入門を終えた方

・アルゴリズムを学習したい方

・コンピュータサイエンスを専攻する学生

（目次）

第1章　どんな本なのか？

　1-1　本書の内容（つまり、何に関する本なのか？）

　1-2　本書を読む理由（なぜ、あなたはここにたどり着いたのか？）

　1-3　本書を読むにあたって（前提条件）

　1-4　本書の構成

　1-5　まとめ

　1-6　興味のある方へ

　1-7　演習問題

　1-8　参考文献

第2章　アルゴリズム解析の基礎

　2-1　計算機における重要な考え

　2-2　漸近記法

　2-3　グラフと木構造の実装

　2-4　ブラックボックスにご注意を

　2-5　まとめ

　2-6　さらに興味のある方へ

　2-7　演習問題

　2-8　参考文献

第3章　数え上げ入門

　3-1　総和をひとかじり

　3-2　トーナメントに関する2 つの物語

　3-3 部分集合と並べ替えと組み合わせ

　3-4　再帰と漸化式

　3-5　いったい何についての話だったのか？

　3-6　まとめ

　3-7　興味のある方へ

　3-8　演習問題

　3-9　参考文献

第4章　帰納と再帰と還元

　4-1　なるほど、それなら簡単だよ！

　4-2　いち、に、たくさーん

　4-3　鏡よ、鏡

　4-4　帰納法と再帰を使って設計する

　4-5　強い仮定

　4-6　不変式と正しさ

　4-7　緩和とゆっくりとした改善

　4-8　還元 + 対偶 = 困難さの証明

　4-9　問題解決のアドバイス

　4-10　まとめ

　4-11　興味のある方へ

　4-12　演習問題

　4-13　参考文献

第5章　巡回：アルゴリズムのマスターキー

　5-1　公園の中の散歩

　5-2　深く行こう！

　5-3　無限の迷路と（重みなし）最短経路

　5-4　強連結成分

　5-5　まとめ

　5-6　興味のある方へ

　5-7　演習問題

　5-8　参考文献

第6章　分割・統合・統治

　6-1　木構造型問題：バランスがすべて

　6-2　標準的なD&C アルゴリズム

　6-3　半分にしながら探索

　6-4　半分にしながらソートする

　6-5　大事な3 つの例

　6-6　木のバランスと...バランスのとり方

　6-7　まとめ

　6-8　興味のある方へ

　6-9　演習問題

　6-10　参考文献

第7章　貪欲が善って、ほんとうですか？　それなら証明してください

　7-1　一歩ずつ安全に

　7-2　ナップサック問題

　7-3　Huffmanのアルゴリズム

　7-4　最小全域木

　7-5　貪欲法は機能するが、いつ？

　7-6 まとめ

　7-7 興味のある方へ

　7-8 演習問題

　7-9 参考文献

第8章 もつれた依存関係とメモ化

　8-1 DRY（Don't Repeat Yourself）の原則

　8-2 有向非巡回グラフにおける最短経路

　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 再び還元

　11-2 カンザスはどこへ？

　11-3 その頃、カンザスでは...

　11-4 とはいえ、どこから始め、どこへ向かいましょうか？

　11-5 怪獣動物園　

　11-6 困難な状況になると、賢いものはいい加減になる

　11-7 必死に解を求めて

　11-8 物語の教訓は何だったのか

　11-9 まとめ

　11-10 興味のある方へ

　11-11 演習問題

　11-12 参考文献

付録A 全力疾走 - Pythonを最大限加速させるには

付録B 問題とアルゴリズムの一覧

付録C グラフに関する用語と表記

付録D 演習のヒント