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

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

B5変形判/448ページ

定価(本体3,480円+税)

ISBN 978-4-297-11686-6

電子版
  • 電子化の予定があります

→学校・法人一括購入ご検討の皆様へ

書籍の概要

この本の概要

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

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

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

こんな方におすすめ

  • 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 参考文献

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

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

  • B-1 問題
  • B-2 アルゴリズムとデータ構造

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

付録D 演習のヒント

著者プロフィール

辻真吾(つじしんご)

監訳者
現在,東京大学先端科学技術研究センターに所属。2000年東京大学大学院工学系研究科修了。創業間もないベンチャー企業に就職しJavaを用いたWebアプリ開発に従事。バイオインフォマティクスの研究を志し,退職して現在の勤務先に博士課程の学生として復学。2000年代中頃からPythonに注目し,2010年に「Pythonスタートブック(技術評論社)」を出版。その他にも「Pythonで学ぶアルゴリズムとデータ構造(講談社)」など著書多数。Start Python Clubを主宰し,2015年から月に1回「みんなのPython勉強会」を開催している。
最近は要素還元主義に立脚した科学研究や社会システムに限界を感じており,複雑系やその1分野としてのAgent-based modeling(ABM)に興味がある。
おいしい食事とお酒が好き。
Website:www.tsjshg.info


塩井宏亮(しおいひろあき)

訳者
東京大学大学院工学系研究科航空宇宙工学専攻を修了後,2014年に日本General Electric (GE) に入社。 2016年にデータサイエンティストとしてアメリカ(カリフォルニア州)のGE Digital本社へ転籍。金融,電力,製造業,ヘルスケアなどを中心に,様々な産業分野の顧客へコンサルティングサービスを提供。顧客の問題発見からアルゴリズム開発・実装,プロトタイプまでを手掛ける。現在,同じくカリフォルニア州に本社を置くスタートアップ dotData, Inc. にてデータサイエンティストとして活動中