Python計算機科学新教本

―新定番問題を解決する探索アルゴリズム、k平均法、ニューラルネットワーク

[cover photo]
TOPICS
Programming , Math , Python
発行年月日
PRINT LENGTH
280
ISBN
978-4-87311-881-9
原書
Classic Computer Science Problems in Python
FORMAT
Print PDF EPUB
Ebook
3,300円
Ebookを購入する
Print
3,300円

探索、制約充足、グラフといった、コンピュータサイエンスにおける定番問題だけでなく、機械学習や深層学習で使われるk平均クラスタリング、ニューラルネットワークに関する問題を通して、アルゴリズムの知識を深め、解決方法を学び、本物の問題解決能力とプログラミングスキルを身につけます。ハノイの塔、8クイーン問題、経路探索といったおなじみの例題だけでなく、線形探索や二分探索といった定番の探索アルゴリズムを使ってDNAを探し出したり、遺伝的アルゴリズムを使って覆面算を解く、敵対探索を使って三目並べを解くなど、ユニークな例題を通じて、コンピュータサイエンスの知識を広げます。Python 3.7対応。

目次

日本語版へのまえがき 
謝 辞
はじめに

1章 簡単な問題
    1.1 フィボナッチ数列 [問題1 フィボナッチ数列]
        1.1.1 最初の再帰解
        1.1.2 基底部を用意する
        1.1.3 メモ化で救う
        1.1.4 自動メモ化
        1.1.5 単純なフィボナッチ
        1.1.6 フィボナッチ数列をジェネレーターで作る
    1.2 簡単な圧縮 [問題2 遺伝子コードの圧縮]
    1.3 破られない暗号 [問題3 ワンタイムパッドを使った暗号化と復号]
        1.3.1 データを順に取り出す
        1.3.2 暗号化と復号
    1.4 円周率πの計算 [問題4 級数によるπの計算]
    1.5 ハノイの塔 [問題5 ハノイの塔]
        1.5.1 塔のモデル 
        1.5.2 ハノイの塔を解く
    1.6 実世界での応用
    1.7 練習問題

2章 探索問題
    2.1 DNA探索 [問題6 DNAのコドン探索]
        2.1.1 DNAの格納
        2.1.2 線形探索
        2.1.3 二分探索
        2.1.4 ジェネリックな例
    2.2 迷路の解法 [問題7 迷路を解く]
        2.2.1 ランダムな迷路の生成
        2.2.2 迷路の細部
        2.2.3 深さ優先探索
        2.2.4 幅優先探索
        2.2.5 A*探索
    2.3 宣教師と食人種(川渡り問題) [問題8 宣教師と食人種(川渡り問題)]
        2.3.1 問題の表現
        2.3.2 解
    2.4 実世界での応用
    2.5 練習問題

3章 制約充足問題
    3.1 制約充足問題フレームワークの構築 [問題9 制約充足問題フレームワーク]
    3.2 オーストラリアの地図の塗り分け問題 [問題10 地図の塗り分け]
    3.3 8クイーン問題 [問題11 8クイーン]
    3.4 単語探し [問題12 単語探し]
    3.5 SEND+MORE=MONEY [問題13 覆面算]
    3.6 回路レイアウト [問題14 回路レイアウト]
    3.7 実世界での応用
    3.8 練習問題

4章 グラフ問題
    4.1 グラフとしての地図
    4.2 グラフのフレームワークを作る [問題15 グラフのフレームワーク]
        4.2.1 辺とグラフの処理
    4.3 最短経路の発見 [問題16 グラフの最短経路]
        4.3.1 再び幅優先探索(BFS)
    4.4 ネットワーク構築コストの最小化 [問題17 最小被覆木]
        4.4.1 重みの処理
        4.4.2 最小被覆木
    4.5 重み付きグラフの最短経路 [問題18 重み付きグラフの最短経路]
        4.5.1 ダイクストラのアルゴリズム
    4.6 実世界での応用
    4.7 練習問題

5章 遺伝的アルゴリズム
    5.1 生物学的な背景
    5.2 ジェネリックな遺伝的アルゴリズム [問題19 ジェネリックな遺伝的アルゴリズム]
    5.3 簡単なテスト [問題20 式の最大値]
    5.4 再びSEND+MORE=MONEY [問題21 遺伝的アルゴリズムによるSEND+MORE=MONEY]
    5.5 リスト圧縮の最適化 [問題22 リストの最適圧縮]
    5.6 遺伝的アルゴリズムの課題
    5.7 実世界での応用
    5.8 練習問題

6章 k平均クラスタリング
    6.1 準備
    6.2 k平均クラスタリングアルゴリズム [問題23 k平均クラスタリング]
    6.3 米国の州知事を年齢と経度でクラスタリング [問題24 州知事のクラスタリング]
    6.4 マイケル・ジャクソンのアルバムを演奏時間でクラスタリング [問題25 音楽アルバムのクラスタリング]
    6.5 k平均クラスタ問題とその拡張
    6.6 実世界での応用
    6.7 練習問題

7章 簡単なニューラルネットワーク
    7.1 生物学的基盤
    7.2 人工ニューラルネットワーク [問題26 ニューラルネットワーク構築]
        7.2.1 ニューロン
        7.2.2 層(レイヤー)
        7.2.3 バックプロパゲーション
        7.2.4 全体像
    7.3 準備作業
        7.3.1 ドット積
        7.3.2 活性化関数
    7.4 ネットワークの構築
        7.4.1 ニューロンの実装
        7.4.2 層の実装
        7.4.3 ネットワークの実装
    7.5 分類問題
        7.5.1 データの正規化
        7.5.2 クラシックなirisデータセット [問題27 アヤメの分類]
        7.5.3 ワインの分類 [問題28 ワインの分類]
    7.6 ニューラルネットワークの高速化
    7.7 ニューラルネットワーク問題とその拡張
    7.8 実世界での応用
    7.9 練習問題

8章 敵対探索
    8.1 ボードゲームの基本要素
    8.2 三目並べ [問題29 三目並べ]
        8.2.1 三目並べの状態管理
        8.2.2 ミニマックス
        8.2.3 ミニマックスを三目並べでテスト
        8.2.4 三目並べAIの開発
    8.3 コネクトフォー [問題30 コネクトフォー]
        8.3.1 コネクトフォーゲームのメカニズム
        8.3.2 コネクトフォーAI
        8.3.3 アルファベータ法でミニマックスを改善 [問題31 アルファベータ法]
    8.4 アルファベータ法の先のミニマックスの改善
    8.5 実世界での応用
    8.6 練習問題

9章 その他さまざまな問題
    9.1 ナップサック問題 [問題32 ナップサック問題]
    9.2 巡回セールスマン問題 [問題33 巡回セールスマン問題]
        9.2.1 素朴な方式
        9.2.2 次のレベルに移行
    9.3 電話番号記憶術 [問題34 電話番号記憶術]
    9.4 実世界での応用
    9.5 練習問題

付録A 用語集

付録B 参考文献
    B.1 Python
    B.2 アルゴリズムとデータ構造
    B.3 人工知能
    B.4 関数型プログラミング
    B.5 本書で述べたオープンソースプロジェクト

付録C 型ヒントの簡単な紹介
    C.1 型ヒントとは何か
    C.2 型ヒントはどのようなものか
    C.3 なぜ型ヒントが役立つか
    C.4 型ヒントの問題点は何か
    C.5 さらに学ぶために

訳者あとがき
索引