アルゴリズム

いちばんやさしいアルゴリズムの本

みわよしこ
技術評論社

はじめに - どんなときにも無理なく登れる「アルゴリズムの階段」を目指して

序章 あなはなぜ、アルゴリズムの本が読めないのか?
0-0 アルゴリズムと小学生算数
0-1 わかりやすいから正しいわけではない
0-2 小学1年生レベルの基本的な方法は、小学6年生にも中学生にも有効とは限らない
0-3 正しさを決める要素は1つではない
0-4 アルゴリズムの理解を妨げるモヤモヤ感

第1章 アルゴリズム的価値観を理解する
1-0 「アルゴリズム的価値観」とは?

  • 本章で取り扱う話題

1-1 分かりやすいアルゴリズムは、良いアルゴリズムとは限らない

  • 「わかりやすい」「素朴」は、いけないこと?

1-2 小さい問題が解けるならば大きな問題が解けるとは限らない - 問題の大きさのパターンをどう評価するか
COLUMN 「問題の複雑さ」って、なんだろう? - ちょっとだけ、対数のおさらい
1-3 「いくつかのアルゴリズムの組み合わせ」として経営課題を解決してみよう
1-4 アルゴリズムの組み合わせを、アルゴリズム的に評価するには?
1-5 万能のアルゴリズムがあるわけではない

第2章 それは探しきれるか? - 探索と探索アルゴリズム
2-0 探索がなぜ工夫されるのか
2-1 素直な探し方(逐次検索)は、どこがいけないのか
2-2 素直な探し方(逐次探索)を改良してみる

  • 使用頻度の高い順に順序を入れ替える(その1)
  • 使用頻度の高い順に順序を入れ替える(その2)

2-3 半分の「かたまり」を捕らえる - 二分探索
2-4 まず「どこにありそうか」の当たりをつける - ハッシュ探索(チェイン法)
2-5 同じ格納位置に複数のデータがあるのはイヤ - ハッシュ探索(オープンアドレス法)
2-6 二分探索木が「とっつきにくい」と感じられる理由
2-7 二分探索木の強みを生かすには
2-8 アルゴリズム用語で「二分探索木を作る」を理解する

  • 二分探索木の生成

第3章 それは数えられるのか? - 計算時間の見積もり
3-0 「1、2、3、たくさん」?
3-1 数が増えると、いつかは「実際には数えられない」という問題が発生する
3-2 単純な計算は、単純だから繰り返せばいつか終わる?
3-3 実はありふれている「計算困難問題」

第4章 それはどういう規模か? - Order記法
4-0 計算する前に、計算に必要な時間はわからなくても、規模の見積もりはできる(Order記法)

  • 例1:整数か奇数か偶数か判断する
  • 例2:逐次検索

4-1 Order記法を理解するための最小限の数学

  • どのスケールで問題を眺めるか?
  • 掛け算と足し算を関係づける - 「対数(log)」って何だったっけ?
  • 「3 log n」と「n log n」は、なぜ違う?
  • 代表的なパターンは、直感的に理解しておこう

4-2 Order記法を使いこなすために

  • 問題の大きさをとらえる
  • 「計算量をとらえる」ことの複雑さと向き合う
  • 必要な資源の増え方からわかることは?

第5章 それは重要な問題か? - ドメインごとの優先事項
5-0 何もかもが大切だと言っていたら何も進まない

  • 一番大切なことは、何だろう?
  • 連携するもの・相反するもの・無関係なもの
  • 優先しないリスク・優先するリスク
  • 許容できるリスク・許容できないリスク

5-1 結果の数値そのものが大切な場面

  • 優先しないという選択肢はあるか
  • 優先した場合のリスク

5-2 結果の確からしさが大切な場面

  • 優先しないという選択肢はあるか
  • 優先した場合のリスク

5-3 結果がいつ得られるかが大切な場面

  • 優先しないという選択肢はあるか
  • 優先した場合のリスク

5-4 結果がどのように得られるかが大切な場面

  • 優先しないという選択肢はあるか
  • 優先した場合のリスク

5-5 組み合わせで成功する場面・失敗する場面

  • 「組み合わせの妙」が働く場面は?
  • 「似たもの同士」の落とし穴
  • 表で整理してみよう
  • バッチ処理の悲劇
  • ネット時代の「組み合わせ」に注意
  • 「問題を起こさない」「問題を最小限にする」は可能か?

第6章 それは、解かなくてはならない問題なのか? - 「割り切り」の方法
6-0 その問題は、本当に解かなくてはなりませんか?

  • 本章で取り扱う問題について

6-1 真の結果でなくてよいことにするには
6-2 解かずに済む方法を考えるには
6-3 小さな問題に分割するには
6-4 いつ解けそうかわかればよいことにするには
6-5 「誤りではなさそう」「当たるかもしれない」でよいことにするには

  • 増えるパターン
  • 減るパターン
  • 増えたり減ったりするパターン

Appendix アルゴリズム解説書を読んでみる
A-0 この章では何をするのか
A-1 初級編:結城浩「プログラマの数学」

  • 「指数的な爆発とは何か」
  • 「倍々ゲーム - 指数的な爆発が生み出す困難」
  • 「バイナリサーチ - 指数的な爆発を利用する検索」

A-2 中級編:G.T Heinemanほか「アルゴリズム・クイックリファレンス」

  • 「Order記法」そのものの説明はない
  • 「log nの振る舞い」に関する興味深い例からO(log(n))へ

A-3 上級編:D.E.Knuth「The Art of Computer Programming」

  • 「情報構造」→「木構造」→「二分木」という木構造
  • 二分木をたどってみよう
  • 二分木を最適化するには

索引