続・アルゴリズムを学ぼう
KADOKAWA／アスキー・メディアワークス
著者：川中真耶、杵渕朋彦、椎名俊輔
はじめに
目次
第0講 はじまり
明日木大学、入学式！
キャラクター紹介
伯方涼子（はかたりょうこ）
澤戸うい（さわどうい）
高橋メイ（たかはしめい）
日比野萌来（ひびのめぐる）
倉科莉紗（くらしなりさ）
第1講 計算量の計算
1.1 期待の新入部員！？
1.2 マージソートの計算量（おさらい）
1.2.1 計算量
1.3 クイックソート
1.3.1 平均計算量
1.3.2 最悪計算量
1.4 ようこそ！ 技育部へ！
第2講 ライツアウトの数学
2.1 温泉合宿、開始！
2.2 ライツアウトのルール
2.3 ライツアウトと数学
2.4 数学の準備
2.5 ライツアウトの方程式
2.6 行列の話
2.6.1 線型空間
2.6.2 線型写像
2.6.3 ライツアウトの行列
2.7 掃き出し法による逆行列の計算
2.7.1 掃き出し法の実装
2.7.2 掃き出し法の計算量
2.7.3 解けないライツアウト
2.8 温泉の夜は更けて
第3講 続・ライツアウトの数学
3.1 早く起きた朝は
3.2 解けないライツアウト
3.2.1 ライツアウトの方程式を観察
3.2.2 解けない理由
3.3 数学に翻訳
3.3.1 行列の基本変形
3.3.2 同じもので分類
3.3.3 群の作用・軌道
3.3.4 休憩：有限オートマトン
3.3.5 次元と階数
3.4 倉科、ダウン
第4講 文字列のアルゴリズム
4.1 急ぐ2 人
4.2 文字列検索
4.3 ナイーブな方法
4.4 ラビン・カープ法
4.4.1 ローリングハッシュ
4.4.2 ラビン・カープ法の実装
4.5 クヌース・モリス・プラット法（KMP法）
4.6 ボイヤー・ムーア法（BM法）
4.7 接尾辞配列(SuffixArray)
4.7.1 ターナリークイックソート
4.8 伯方と澤戸が狙うモノは？
第5講 正規表現とオートマトン
5.1 メイの悩み
5.2 正規はregularの訳語
5.3 正規表現とは
5.3.1 簡易版正規表現の定義
5.4 簡易版正規表現の構文解析
5.4.1 データ構造の定義
5.4.2 構文解析
5.5 正規表現とオートマトン
5.5.1 決定性有限オートマトン
5.5.2 DFA の実装とDFA上での文字列の受理
5.5.3 非決定性有限オートマトン
5.5.4 NFA の実装とNFA上での文字列の受理
5.6 正規表現からNFAへの変換
5.6.1 RegexTermAlnumの場合
5.6.2 RegexTermOptionの場合
5.6.3 RegexTermStarの場合
5.6.4 RegexTermSequenceの場合
5.6.5 RegexTermSelectionの場合
5.6.6 構文木からNFAへの変換
5.6.7 NFA からDFAへの変換
5.7 DFAの状態数最小化
5.8 正規表現と反復補題
5.8.1 反復補題
5.9 チケットの代償
第6講 山登り法と焼きなまし法
6.1 謎の予算争奪戦！
6.2 トラベリングセールスマン問題（TSP）
6.3 全探索による厳密解法
6.4 動的計画法による厳密解法
6.5 山登り法
6.6 山登り法のトラベリングセールスマン問題への適用
6.7 焼きなまし法
6.8 伯方の大計画！
第7講 リバーシの実装とミニマックス法
7.1 壮絶！ リバーシ100 番勝負！
7.2 リバーシのルール
7.3 二人零和有限確定完全情報ゲーム
7.4 リバーシの実装
7.4.1 石の実装
7.4.2 位置の実装
7.4.3 盤の実装
7.4.4 石を置く部分の実装
7.4.5 手番の実装
7.4.6 Player の実装
7.4.7 メインループの実装
7.5 簡単な思考ルーチン
7.6 深く読む
7.6.1 ミニマックス法
7.6.2 ミニマックス法の実装
7.6.3 ネガマックス法
7.7 日比野へのおみやげは・・・・・・
第8講 よりよい評価関数の設計とより高速なゲーム木探索
8.1 インターネットのなかの戦場！
8.2 コードのリファクタリング
8.3 評価関数を改善する
8.3.1 開放度を計算する
8.3.2 確定石の個数を数える
8.3.3 評価関数の実装
8.4 さらに高速化する
8.4.1 アルファベータ枝刈り
アルファベータ枝刈りの実装
8.4.2 スカウト法
8.4.3 ムーブオーダリング
8.4.4 さらなる方法
8.5 終盤を完全に読み切る
8.6 伯方謹製ロンドンマップ！
第9講 教師つき学習
9.1 イギリス旅行の想い出
9.2 教師つき学習の概要
9.2.1 特徴量
9.2.2 重みベクトル
9.3 問題の定式化
9.3.1 最急降下法
9.3.2 過学習の抑制
9.3.3 実際の学習
9.4 学習の実装
9.4.1 リバーシの棋譜
9.4.2 重みベクトルの実装
9.4.3 特徴ベクトルの実装
9.4.4 学習部分の実装
9.5 さらばイギリス！
第10講 乱数とシミュレーション
10.1 フラグマスター伯方！
10.2 乱数
10.2.1 乱数生成
合同法
10.2.2 乱数の品質・検定
10.2.3 頻度検定
系列相関検定
10.2.4 モンテカルロアルゴリズム
10.3 シミュレーションを使ったリバーシAI
10.3.1 ランダムに打つAI
10.3.2 シミュレーションの舞台
10.3.3 単純なモンテカルロ法AI
10.4 勉強の成果！
第11講 エンディング
11.1 メイからの重大発表？
索引
著者プロフィール