概要

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

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

本書で学べること

• 新しい問題を効率的なアルゴリズムで解ける問題に変換する方法。もしくは，効率的に解けない問題であると示す方法
• 数学と基本的な実験やベンチマークを使ってアルゴリズムとPythonのプログラムを分析する方法
• 古典的なアルゴリズムとデータ構造を深く理解し，Pythonでこれらを効率的に実装する方法
• 新しい問題を解くために新しいアルゴリズムを設計し，実績のある設計原理・設計技法を使って実装する方法
• Pythonのハイパフォーマンスコンピューティングを実現する豊富なツールを使って実装を高速化する方法

こんな方におすすめ

• Pythonの入門を終えた方
• アルゴリズムを学習したい方
• コンピュータサイエンスを専攻する学生

日本語版監訳者より

現代社会はアルゴリズムに支えられています。コンピュータとアルゴリズムの登場が世界を変えたと言っても過言ではありません。アルゴリズムに関する話題は，コンピュータ科学と数学の両方に広がりを持っています。ある問題Aがあるときに，それを解くためのアルゴリズムを思いついたとしましょう。アルゴリズムをプログラミングしていくつか問題Aの具体例に適用したところ，答えがきちんと返ってきたとします。得られた答えが役に立てば，それで良いこともあるでしょう。しかし，そのアルゴリズムですべての問題Aが解けるかどうかは分かりません。アルゴリズムが途中で止まったり，間違った答えを返したりしないということを証明する必要があります。これには数学的な考え方が必要です。多くのアルゴリズムの入門書は，こうした数学的な側面についてふれていません。一方，アルゴリズムに関する専門的な書籍では，数学記号をふんだんに使った説明を目にします。この本はこれらのちょうど間に位置します。原著ではかなり複雑で難しい議論が軽妙な語り口で解説されています。もしアルゴリズムに関してまったく知識がない場合は，まず入門書を手に取ることをおすすめします。また本書を読み進めるためには，Pythonプログラミングの知識も必要です。

アルゴリズムで問題が解けるということは，簡単な計算の積み重ねで最終的に正しい答えが得られるということです。各ステップの計算は本当に単純です。2つの値の比較や，グラフであればあるノードに隣接するすべてのノードを順番に取得するような計算です。こうした単純な計算の繰り返しでどうして問題が解けるのか，本書の2〜4章ではこの一般的な課題に真正面から取り組みます。これらの章で扱われる話題は，アルゴリズムを設計し数学的に正しいことを証明できるようになるための知識です。このため，抽象度が高い議論も含まれます。続く5〜8章では多種多様なアルゴリズムを例に，それらを支える設計思想を解説しています。個別のアルゴリズムとコードを理解するところからはじめ，一見違う問題に対して，同じ設計思想のアルゴリズムが適用できる仕組みがわかるようになればかなりの上級者です。9章と10章はグラフに関する話題がまとまっています。グラフは応用範囲が広いため，本書の前半でもたびたび話題に上ります。最後の11章は計算理論の話です。P≠NP問題の理解の助けになりますが，ほとんどが抽象的な話題なので少し毛色が違った章になります。各章で中心になるトピックには，必ずPythonのコードが提示されます。コードを読むことで，アルゴリズムの動作が分かります。ダウンロードしたコードを自分で変更して繰り返し実行すれば，さらに理解が深まるはずです。

原著者のMagnus Lie Hetlandさんは，経験豊かなPythonプログラマであり，大学でアルゴリズムを教えている専門家です。幅広く深い知識の持ち主であるため，この本にはさまざまな話題が含まれます。比較的難しいトピックをその概要の説明だけにとどめている部分もあります。こうした話題を完全に理解したいと思う場合は，本書で提示されている参考資料にあたる必要があるでしょう。最近はWebを探せば関連情報をすぐに見つけることもできます。本書が広大なアルゴリズムの世界へ旅立つきっかけを与えてくれます。

日本語，英語に関わらず，言葉は曖昧さを持ちます。書き手の意図が読み手に正しく伝わらないこともあるでしょう。しかしコードは違います。正しく動くコードは，作り手の意図が受け手に正確に伝わります。プログラミングができれば，コードを読むことでアルゴリズムを理解できるわけです。本書のコードは簡潔で，丁寧なコメントも付いています。短いコードから想像を超える計算結果が生み出される様子は，まさに世界を変えたアルゴリズムの威力そのものです。

複雑さを増す一方の現代社会にはさまざまな課題があります。すべてが計算で解決できるわけではありませんが，アルゴリズムが役立つ場面は多くあるでしょう。例えば，物流の配送ルートを最適化すれば燃料を削減できます。これは既存のアルゴリズムを少し変更するだけで解決できそうです。膨大な数の化合物から効率良く薬の候補を見つけられれば，患者さんが少ない希少疾患の治療方法を確立できるかもしれません。こうした複雑で難しそうな課題は，冷静に分析して部分的に解ける問題へ変換する必要があります。これはまさに本書で解説されているアルゴリズムの設計技法です。読者のみなさんの頭の中で再構築された知識が，現実のさまざまな課題に適用され1つでも多く解決につながれば，監訳者としてこの上ない喜びです。

目次

第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 演習のヒント

サポート

補足情報

本書掲載のコードについて

本書に掲載しているコードを下記Webサイトにまとめています。

• https://github.com/ghmagazine/python_algorithms