アルゴリズム

続・アルゴリズムを学ぼう

川中真耶
杵渕朋彦
椎名俊輔

アスキー・メディアワークス

はじめに

第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 メイからの重大発表?

索引
著者プロフィール