概要

プログラマにとって，アルゴリズムをきちんと理解することは，実際にプログラミングや情報処理技術者試験を受験する際に必須と言えます。ただし，数学の苦手な人にとっては「探索」「ソート」「選択」「マージ」などは，小難しく感じています。そこで，本書は「小学校の算数を基礎知識として，これから本格的にアルゴリズムを学ぶための基盤を作る」ことを目的に，とことんやさしく解説します。

こんな方におすすめ

• アルゴリズム解説本やパズル本などに出てくる数式を理解したい人
• 「基本情報処理試験」の「大分類1：基礎理論」を勉強している人

目次

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

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

• 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』
  • 「情報構造」→「木構造」→「二分木」という木構造
  • 二分木をたどってみよう
  • 二分木を最適化するには

サポート

正誤表

本書の以下の部分に誤りがありました。ここに訂正するとともに，ご迷惑をおかけしたことを深くお詫び申し上げます。

P.85の下から3行目

（以下2015年1月5日更新）

P.21　図1（上から3つ目の図の説明）

P.72　本文中の図（1回目）

P.72　本文中の図（3回目）

P.95　本文中の図（二分木構造の右下）

P.111の下から3行目
P.112の図3中の「2×2」の経路数

P.123　図1（グラフ中の凡例）

P.123　図2（グラフ中の凡例）