目次

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

序章：あなたはなぜ、アルゴリズムの本が読めないのか？

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

第1章：アルゴリズム的価値観を理解する

• 1-0：「アルゴリズム的価値観」とは？
  • 本章で取り扱う話題
• 1-1：わかりやすいアルゴリズムは、良いアルゴリズムとは限らない
  • 「わかりやすい」「素朴」は、いけないこと？
• 1-2：小さい問題が解けるならば大きな問題が解けるとは限らない――問題の大きさのパターンをどう評価するか
• 【コラム】「問題の複雑さ」って、なんだろう？ ――ちょっとだけ、対数のおさらい
• 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』
  • 「情報構造」→「木構造」→「二分木」という木構造
  • 二分木をたどってみよう
  • 二分木を最適化するには