いちばんやさしいアルゴリズムの本
技術評論社
著者：みわよしこ
執筆協力：永島孝
はじめに – どんなときにも無理なく登れる「アルゴリズムの階段」を目指して
目次
序章 あなはなぜ、アルゴリズムの本が読めないのか？
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」
「情報構造」→「木構造」→「二分木」という木構造
二分木をたどってみよう
二分木を最適化するには
索引