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

関連サイト

本書の詳細ページが用意されています。

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

関連書籍

本書の前著『アルゴリズムを学ぼう』も好評発売中です。

アルゴリズムを学ぼう【電子書籍】

川中真耶, 杵渕朋彦, 椎名俊輔
KADOKAWA/アスキー・メディアワークス
発行日: 2012-06-01
対応フォーマット: PDF,EPUB

詳細を見る

内容紹介

前著「アルゴリズムを学ぼう」では、答が1つに決まる問題というのが多かったのですが、今回は数学、文字列、正規表現とオートマトン、ゲームのAIなど、プログラマーなら知っておくべき基礎的な知識を、多岐にわたって集めました。

数学の分野では、基礎的な線形代数や群の知識を、ライツアウトを解くという題材を用いて説明しています。ライツアウトという具体例を用いることで、抽象的な線形代数や群の問題が、具体的なイメージを持って理解できるのではないかと思います。ライツアウトを完璧に解くという問題だけでも、さまざまな数学的知識が学べるということに、ちょっとびっくりしますね。

文字列の分野では、基礎的な文字列の検索アルゴリズムを集めました。検索は読者のみなさまもふだんから利用していることと思いますが、それがどのように動作しているのかを、実際のコードを使って解説します。ここには、さまざまなアルゴリズムの定石が詰まっているので、ぜひ学んでほしい問題です。また、高速な検索に欠かせない技術の1つである、接尾辞配列（SuffixArray）にも少し触れています。

正規表現とオートマトンでは、プログラムでもよく使われる正規表現が、実際にどのように動作しているのかを解説します。正規表現は読者のみなさまもよく使っていると思いますが、実際に構築されるオートマトンの具体的なイメージを持つことで、より正規表現に親しみを持ってもらえるのではないかと思います。正規表現で書くことができない文字列というのも存在するので、それを理解するための理論的背景にも、少しだけですが触れています。

ゲームのAIでは、リバーシを題材に、評価関数の作り方、深く読む方法などを説明します。評価関数では、マスに点をつけるという単純な方法からはじまり、リバーシの上級者が実際に使っているテクニックを使った方法を取り上げます。そして、最終的に人が打った棋譜を参考に、評価関数を学習するところまで解説しました。深く読む方法では、ミニマックス探索からはじめて、アルファベータ枝刈り、ネガスカウト法など、読みを高速にする方法を解説しています。また、乱数を使ったAIも取り上げました。ゲームのAIは奥が深く、本書で解説しているのはほんの入口だけですが、それでもAIが実際にどのように考えているのかを知る助けになると思います。

(「はじめに」より抜粋)

書誌情報

• 著者: 川中真耶, 杵渕朋彦, 椎名俊輔
• 発行日: 2013-08-02
• 最終更新日: 2013-08-02
• バージョン: 1.0.0
• ページ数: 329ページ
• 対応フォーマット: PDF, EPUB
• 出版社: KADOKAWA/アスキー・メディアワークス

対象読者

アルゴリズムを学びたい人、『アルゴリズムを学ぼう』の読者の方

著者について

川中真耶

某大手検索会社勤務。最近は、Web ブラウザーのビルドを高速化するような仕事をしている。プログラミングを本格的にはじめたのは大学に入ってからだが、その楽しさにはまる。もう少し硬い学問をやろうと思っていたのに、結局情報科学科へ進学するまでになった。大学でやってたのはツリーオートマトンとか、そのあたり。このころ関数型言語の美しさに惚れ、以来愛用するようになる。
就職してからは、Web というプラットフォームのおもしろさにはまり、趣味方面でもWeb サービスを作るのに手をだした。そのうち自分の作ったサービスで、世界を征服したいと思っている。

杵渕朋彦

某潜水艦っぽい名前の会社勤務。業務システムの開発やリリースの仕事をしている。数学大好きっ子で、その一部としてプログラミングの本も読んでいた。実際にソースコードを書いたのは大学に入ってからだが、思考をプログラムで表現・実行できるおもしろさにはまる。プログラミング言語そのものへの興味が強い。
いろいろなことに興味を持つが、その知的好奇心に従って手をだしていたら、人生1 回ぶんでは時間が足りなくなってきたのが悩みどころ。それでも、死ぬまでに多くのことを知りたいと思っている。

椎名俊輔

某パッケージソフトウェア開発会社の技術研究部門に所属。プログラミングやアルゴリズムの勉強は就職してからはじめた。共同執筆者の2 人と比べるのがもうしわけないほどに、まだまだエレガントなコードは書けていない。多数の部署を経たあとに、現在の研究職へ。おもに、NoSQL やクラウドまわりの技術調査と運用を行なっている。最近リリースしたクラウドを活用したサービスでは、おもに運用自動化のためのツール類の開発と、それらツールの運用を担当している。

目次

はじめに

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

索引

著者プロフィール