「数学ガール/乱択アルゴリズム：結城浩」（Kindle版）
この第３巻で学べるのは、まず確率論の基礎、二項定理、コンピュータ・プログラムによるサーチ（検索）やソート（並べ替え）などのアルゴリズムとプログラムの実行時間の見積り（解析）方法、線形代数の基礎（行列、行列の対角化、固有値、固有ベクトル）、ランダムウォークだ。これらは第１章から第８章までの内容。第９章と第１０章で本書の到達点である「乱択アルゴリズム」が紹介されている。
確率論や二項定理は高校で学ぶ内容だけでなく、確率というものの本質を深く掘り下げ、コルモゴロフの確率の公理まで取り上げているところが素晴らしい。二項定理にしてもパスカルの三角形や、順列と組み合せを使う問題との関係を上手に説明し自然な形で確率論の二項分布の説明に導いている。
アルゴリズムというのは与えられた問題をコンピュータが解くための手順のことだ。どれだけ手際よく効率的な手順で解かせるかといことに焦点があてられる。第８章までで取り上げられているのは、リニアサーチ、バイナリサーチ、バブルソートなどアルゴリズムを学ぶ上で基本的なものばかりだ。処理するデータの数が増えるに従い、結果が出るまでの時間がかかるのは当然のことだが、データの増加がどのように処理時間の増加に結びついているかを、これまで学んだ数学を駆使して具体的に見積計算をしているところが本書の優れている点。
行列について解説している箇所は、高校や大学で教えられている対角化、固有値、固有ベクトルに加えてランダムウォークを例にとり確率論を行列にあてはめ、読者に行列のもつ可能性の広がりを紹介している。
第８章までで紹介されるアルゴリズムは、どれも時間さえかければ確実に答が得られるものばかりである。同じ結果が出るのであれば処理時間が短いほうが優れたアルゴリズムだということになる。実際、バブルソートよりはクイックソートのほうが短い時間で結果が得られる。クイックソートは第１０章で紹介される。それではもっと処理時間を短くすることはできないか？そのひとつが確率論をアルゴリズム理論に取り込んだ「乱択アルゴリズム」なのである。
乱択アルゴリズムでは、その中で乱数を使ってピボット（並べ替えの軸）を選択していて、決められた実行時間で必ず答が出ることは保証されていない。平均的なデータに対し答えが得られるまでの時間の期待値が最小になるのが特徴だ。決められた時間内に答えに辿りつけない場合は、通常のアルゴリズムに切り替えて答を求めることになる。
本書では第１０章で普通のクイックソートと乱択アルゴリズムを使ったクイックソートを紹介し、それらの実行ステップの比較を数学的に解析している。いちばん難しくて面白いのはこの部分だろう。
ところでコンピュータ・サイエンスの分野には「Ｐ≠ＮＰ予想」という「ミレニアム懸賞問題」のひとつがある。「予想」と呼ばれていることからわかるとおり、まだ解決されておらず、映画「容疑者Xの献身」の中でも取り上げられた。
仮にＰ＝ＮＰであると示された場合、多項式時間で検証可能な問題は全て多項式時間で判定可能であることを意味し、未だ効率の悪い指数時間アルゴリズムしかない様々な分野の問題に効率的な計算アルゴリズムが与えられる可能性が示される。しかし、多くの研究者が長年に渡って多項式時間オーダーのアルゴリズムの開発に取り組んでいるにも関わらず、そのような効率的なアルゴリズムは見つかっていない。このことがＰ≠ＮＰ予想の根拠の一つとなっている。
この予想を解く鍵となるのが「ＮＰ問題」であり、その中に「ＮＰ完全問題」がある。そして「充足可能性問題（SAT)」という一見シンプルな問題が「ＮＰ完全問題」であることが判明した。
つまり「充足可能性問題（SAT)」が間接的に「Ｐ≠ＮＰ予想」を解く鍵となっていることがわかったのである。そして「充足可能性問題（SAT)」を解くアルゴリズムはそもそも存在しないのか、それとも存在するけれどもまだ見つかっていないのかということも証明されていない。
ただ「充足可能性問題（SAT)」を解くためのステップのオーダー（回数の増加傾向）を下げるために「乱択アルゴリズムの一種」が１９８２年にチューリング賞を受けることになった論文で使われていたという経緯がある。ふぅ、これでやっとつながった。これらの超難問の意味は本書の中でくわしく解説されているので安心していただきたい。
このように「数学ガール」シリーズでは、本書がそうであるように最後の章で素人には絶対理解するのが無理と思われるような難問をとりあげている。これが数学初心者から理数系の大学生まで楽しめる理由のひとつだと思う。初心者は最後の難しい部分を理解できなくても数学の奥深さを知ることができるし、理数系の大学生にとっても十分チャレンジするのに値するテーマだからだ。大学で数学を専攻し、自然言語処理（機械翻訳）系のプログラマとして社会人をスタートした僕にとっても第９章と第１０章は十分興味を持って読むことができた。
登場人物は双倉図書館のお嬢さんであるプログラミングが得意な「リサ」という中学生の女の子が加わり女の子４人と「僕」になる。青春ストーリーの箇所も、甘くほろ苦い物語が展開し作家としての著者の才能をうかがわせる。巻を重ねるごとに腕を上げていると思った。第１巻のレビューで少しばかり批判してしまったテトラちゃんの「あちゃちゃ。」という言葉遣いについても「テトラ語」として考えれば自然に受け入れられるようになった。慣れてしまったのかもしれないが。（笑）
４６０ページにおよぶ大著であるが、一気に読めると思う。著者がツイッターでリツイートする読者のつぶやきを見ると、「数学ガール」シリーズは文系の人でも楽しめているようだ。理数系の高校生以上向けだと思っていた僕の想定は若干ゆるくしたほうがよかったかもしれない。特に数学に苦手意識を持っている人や、数学の楽しみを味わったことのない人が本シリーズと出会い、多くの数学ファンが生まれることを僕は願っている。
第１巻のレビュー記事にも書いたが、「数学ガール」シリーズはぜひ英訳して世界に向けて発信してほしいという気持をますます強く持つようになった。
これで４巻全部のレビュー記事を書き終えることができた！
次は数理物理学系の本に取り組むことにした。今後は物理と数学、数理物理学の本をローテーションしながら紹介し、物理学としての「超ひも理論・M理論」と、それを数学的に定式化する「非可換幾何学」の理解という目標に向かって進んでいこう。
ちなみに数理物理学というのは物理学の法則の正当性を数学的に定式化したり、物理学の結果から新しい数学分野を切り開いたりする、物理学と数学の境界をなす分野のことだ。
『数学ガール』シリーズの内容の一部は（草稿として）著者のホームページから読むことができる。本書の正誤表もある。
『数学ガール』シリーズ：《理系にとって最強の萌え》をあなたに。
http://www.hyuki.com/girl/
また著者の結城浩さんのWikiはこちら。
http://www.hyuki.com/index.html
「数学ガール：結城浩」（Kindle版）
「数学ガール/フェルマーの最終定理：結城浩」（Kindle版）
「数学ガール/ゲーデルの不完全性定理：結城浩」（Kindle版）
「数学ガール/乱択アルゴリズム：結城浩」（Kindle版）
「数学ガール/ガロア理論：結城浩」（Kindle版）
「数学ガール/ポアンカレ予想：結城浩」（Kindle版）
関連記事：
数学ガール：結城浩
https://blog.goo.ne.jp/ktonegaw/e/bb4f1447d41afcc8b46b85229296dd7a
数学ガール/フェルマーの最終定理：結城浩
https://blog.goo.ne.jp/ktonegaw/e/4bf119bf3842421f8916c787c51216ae
数学ガール/ゲーデルの不完全性定理：結城浩
https://blog.goo.ne.jp/ktonegaw/e/f9b0b9264e35a680ce974fcbf17c62c0
数学ガール/ガロア理論：結城浩
https://blog.goo.ne.jp/ktonegaw/e/a5450818389e0220779e363617332a76
数学ガール/ポアンカレ予想 : 結城浩
https://blog.goo.ne.jp/ktonegaw/e/769e2639898b351545e7ad8a8eba89d7
Kindle版発売：「数学ガール：結城浩」シリーズ
https://blog.goo.ne.jp/ktonegaw/e/9d9037d14ed9ffcc98c7b2569fba7c39
応援クリックをお願いします！このブログのランキングはこれらのサイトで確認できます。
「数学ガール/乱択アルゴリズム：結城浩」（Kindle版）
あなたへ
プロローグ
第１章：絶対に負けないギャンブル
- サイコロ投げ（2個のサイコロ）
- コイン投げ（2枚のコイン、1枚のコイン、宝くじの記憶）
- モンティ・ホールの問題（3通の封筒、神の視点）
第２章：愚直な一歩の積み重ね
- 高校（テトラちゃん、リサ、リニアサーチ、ウォークスルー、リニアサーチの解析、リニアサーチの解析（νが見つかる場合）、リニアサーチの解析（νが見つからない場合））
- アルゴリズムの解析（ミルカさん、アルゴリズムの解析、場合分けの消去、意味を考える、番兵付きリニアサーチ、歴史を作る）
- 自宅（愚直な一歩）
第３章：171億7986万9184の孤独
- 順列（書店、納得感、具体例、規則性、一般化、道を作る、あいつ）
- 組み合せ（図書室、順列、組み合せ、アスパラガス、二項定理）
- 2^nの分配（パスカルの三角形、ビットパターン、指数的爆発）
- 冪乗の孤独（帰路、家）
第４章：確からしさの不確かさ
- 確からしさの確かさ（割り算の意味）
- 確からしさの不確かさ（同じ確からしさ、ほんとうの武器）
- 確からしさの実験（インタプリタ、サイコロ勝負、ルーレット勝負）
- 確からしさの崩壊（確率の定義、確率の意味、数学の適用、疑問への答え）
- 確からしさの公理的定義（コルモゴロフ、標本空間と確率分布、確率の公理、部分集合と事象、確率の公理 P1、確率の公理 P2、確率の公理 P3、まだわかりません、偶数の目が出る確率、ゆがんだサイコロ、縁で立つコイン、約束、咳）
第５章：期待値
- 確率変数（母、テトラちゃん、確率変数の例、確率分布の例、たくさんの言葉、期待値、公平なゲーム）
- 線型性（ミルカさん、和の期待値は期待値の和）
- 二項分布（コインの話、二項分布の期待値、和に分ける、インディケータ確率変数、楽しい宿題）
- すべてが起きるまで（いつの日か、すべてを尽くせるかどうか、学んだことを使う、すべてを尽くす、思いがけないこと）
第６章：とらえがたい未来
- 約束の記憶（川のほとり）
- オーダー（速いアルゴリズム、たかだかnのオーダー、クイズ、たかだかf(n)のオーダー、log n）
- サーチ（バイナリサーチ、実例、解析、ソートへ）
- ソート（バブルソート、実例、解析、オーダーの階層）
- 動的な視点、静的な視点（比較は何回必要か、比較木、log n!の評価）
- 伝えること、学ぶこと（伝えること、学ぶこと）
第７章：行列
- 図書室（瑞谷先生、テトラリアン）
- ユーリ（不能、不定、正則、手紙）
- テトラちゃん（図書室、行と列、行列とベクトルの積、連立方程式と行列、行列の積、逆行列）
- ミルカさん（隠れた謎を見抜く、線型変換、回転）
- 帰路（対話）
第８章：ひとりぼっちのランダムウォーク
- 家（雨の土曜日、お茶タイム、ピアノ問題、メロディの例、解き方その一：根気勝負、解き方その二：閃き勝負、一般化、揺れる心）
- 朝の通学路（ランダムウォーク）
- 昼の教室（行列の練習、揺れる心）
- 放課後の図書室（放浪問題、A^2の意味、行列のn乗へ、準備前半：対角行列、準備後半：行列と逆行列のサンドイッチ、固有値へ、固有ベクトルへ、A^nを求め用）
- 家（揺れる心、雨の夜）
第９章：強く、正しく、美しく
- 家（雨の土曜日）
- 図書室（論理クイズ、充足可能性問題、3-SAT、充足する、割り当て練習、NP完全問題）
- 帰路（誓いと約束、カンファレンス）
- 図書室（3-SATを解く乱択アルゴリズム、ランダムウォーク、定量的評価へ向けて、もう一つのランダムウォーク、ラウンドに注目）
- 家（ラッキーの評価、和を簡単に、回数の評価）
- 図書室（独立と排反、精密な評価、スターリングの近似）
- 帰路（オリンピック）
- 家（論理）
第１０章：乱択アルゴリズム
- ファミリーレストラン（雨）
- 学校（お昼、クイックソート・アルゴリズム、ピボットによる数列の分割 - 二つの翼、部分数列のソート - 再帰、実行ステップ数の解析、場合分け、最大実行ステップ数、平均実行ステップ数、帰路）
- 自宅（形を変えて、Hnとlog n）
- 図書室（ミルカさん、乱択クイックソート、比較の観察、期待値の線型性、インディケータ確率変数の期待値は確率に等しい）
- ファミリーレストラン（さまざまな乱択アルゴリズム、準備）
- 双倉図書館（アイアダイン、緊張、発表、伝える、オキシジェン、つなぐ、庭、約束のしるし）
エピローグ
あとがき
参考文献と読書案内
索引
この第３巻で学べるのは、まず確率論の基礎、二項定理、コンピュータ・プログラムによるサーチ（検索）やソート（並べ替え）などのアルゴリズムとプログラムの実行時間の見積り（解析）方法、線形代数の基礎（行列、行列の対角化、固有値、固有ベクトル）、ランダムウォークだ。これらは第１章から第８章までの内容。第９章と第１０章で本書の到達点である「乱択アルゴリズム」が紹介されている。
確率論や二項定理は高校で学ぶ内容だけでなく、確率というものの本質を深く掘り下げ、コルモゴロフの確率の公理まで取り上げているところが素晴らしい。二項定理にしてもパスカルの三角形や、順列と組み合せを使う問題との関係を上手に説明し自然な形で確率論の二項分布の説明に導いている。
アルゴリズムというのは与えられた問題をコンピュータが解くための手順のことだ。どれだけ手際よく効率的な手順で解かせるかといことに焦点があてられる。第８章までで取り上げられているのは、リニアサーチ、バイナリサーチ、バブルソートなどアルゴリズムを学ぶ上で基本的なものばかりだ。処理するデータの数が増えるに従い、結果が出るまでの時間がかかるのは当然のことだが、データの増加がどのように処理時間の増加に結びついているかを、これまで学んだ数学を駆使して具体的に見積計算をしているところが本書の優れている点。
行列について解説している箇所は、高校や大学で教えられている対角化、固有値、固有ベクトルに加えてランダムウォークを例にとり確率論を行列にあてはめ、読者に行列のもつ可能性の広がりを紹介している。
第８章までで紹介されるアルゴリズムは、どれも時間さえかければ確実に答が得られるものばかりである。同じ結果が出るのであれば処理時間が短いほうが優れたアルゴリズムだということになる。実際、バブルソートよりはクイックソートのほうが短い時間で結果が得られる。クイックソートは第１０章で紹介される。それではもっと処理時間を短くすることはできないか？そのひとつが確率論をアルゴリズム理論に取り込んだ「乱択アルゴリズム」なのである。
乱択アルゴリズムでは、その中で乱数を使ってピボット（並べ替えの軸）を選択していて、決められた実行時間で必ず答が出ることは保証されていない。平均的なデータに対し答えが得られるまでの時間の期待値が最小になるのが特徴だ。決められた時間内に答えに辿りつけない場合は、通常のアルゴリズムに切り替えて答を求めることになる。
本書では第１０章で普通のクイックソートと乱択アルゴリズムを使ったクイックソートを紹介し、それらの実行ステップの比較を数学的に解析している。いちばん難しくて面白いのはこの部分だろう。
ところでコンピュータ・サイエンスの分野には「Ｐ≠ＮＰ予想」という「ミレニアム懸賞問題」のひとつがある。「予想」と呼ばれていることからわかるとおり、まだ解決されておらず、映画「容疑者Xの献身」の中でも取り上げられた。
仮にＰ＝ＮＰであると示された場合、多項式時間で検証可能な問題は全て多項式時間で判定可能であることを意味し、未だ効率の悪い指数時間アルゴリズムしかない様々な分野の問題に効率的な計算アルゴリズムが与えられる可能性が示される。しかし、多くの研究者が長年に渡って多項式時間オーダーのアルゴリズムの開発に取り組んでいるにも関わらず、そのような効率的なアルゴリズムは見つかっていない。このことがＰ≠ＮＰ予想の根拠の一つとなっている。
この予想を解く鍵となるのが「ＮＰ問題」であり、その中に「ＮＰ完全問題」がある。そして「充足可能性問題（SAT)」という一見シンプルな問題が「ＮＰ完全問題」であることが判明した。
つまり「充足可能性問題（SAT)」が間接的に「Ｐ≠ＮＰ予想」を解く鍵となっていることがわかったのである。そして「充足可能性問題（SAT)」を解くアルゴリズムはそもそも存在しないのか、それとも存在するけれどもまだ見つかっていないのかということも証明されていない。
ただ「充足可能性問題（SAT)」を解くためのステップのオーダー（回数の増加傾向）を下げるために「乱択アルゴリズムの一種」が１９８２年にチューリング賞を受けることになった論文で使われていたという経緯がある。ふぅ、これでやっとつながった。これらの超難問の意味は本書の中でくわしく解説されているので安心していただきたい。
このように「数学ガール」シリーズでは、本書がそうであるように最後の章で素人には絶対理解するのが無理と思われるような難問をとりあげている。これが数学初心者から理数系の大学生まで楽しめる理由のひとつだと思う。初心者は最後の難しい部分を理解できなくても数学の奥深さを知ることができるし、理数系の大学生にとっても十分チャレンジするのに値するテーマだからだ。大学で数学を専攻し、自然言語処理（機械翻訳）系のプログラマとして社会人をスタートした僕にとっても第９章と第１０章は十分興味を持って読むことができた。
登場人物は双倉図書館のお嬢さんであるプログラミングが得意な「リサ」という中学生の女の子が加わり女の子４人と「僕」になる。青春ストーリーの箇所も、甘くほろ苦い物語が展開し作家としての著者の才能をうかがわせる。巻を重ねるごとに腕を上げていると思った。第１巻のレビューで少しばかり批判してしまったテトラちゃんの「あちゃちゃ。」という言葉遣いについても「テトラ語」として考えれば自然に受け入れられるようになった。慣れてしまったのかもしれないが。（笑）
４６０ページにおよぶ大著であるが、一気に読めると思う。著者がツイッターでリツイートする読者のつぶやきを見ると、「数学ガール」シリーズは文系の人でも楽しめているようだ。理数系の高校生以上向けだと思っていた僕の想定は若干ゆるくしたほうがよかったかもしれない。特に数学に苦手意識を持っている人や、数学の楽しみを味わったことのない人が本シリーズと出会い、多くの数学ファンが生まれることを僕は願っている。
第１巻のレビュー記事にも書いたが、「数学ガール」シリーズはぜひ英訳して世界に向けて発信してほしいという気持をますます強く持つようになった。
これで４巻全部のレビュー記事を書き終えることができた！
次は数理物理学系の本に取り組むことにした。今後は物理と数学、数理物理学の本をローテーションしながら紹介し、物理学としての「超ひも理論・M理論」と、それを数学的に定式化する「非可換幾何学」の理解という目標に向かって進んでいこう。
ちなみに数理物理学というのは物理学の法則の正当性を数学的に定式化したり、物理学の結果から新しい数学分野を切り開いたりする、物理学と数学の境界をなす分野のことだ。
『数学ガール』シリーズの内容の一部は（草稿として）著者のホームページから読むことができる。本書の正誤表もある。
『数学ガール』シリーズ：《理系にとって最強の萌え》をあなたに。
http://www.hyuki.com/girl/
また著者の結城浩さんのWikiはこちら。
http://www.hyuki.com/index.html
「数学ガール：結城浩」（Kindle版）
「数学ガール/フェルマーの最終定理：結城浩」（Kindle版）
「数学ガール/ゲーデルの不完全性定理：結城浩」（Kindle版）
「数学ガール/乱択アルゴリズム：結城浩」（Kindle版）
「数学ガール/ガロア理論：結城浩」（Kindle版）
「数学ガール/ポアンカレ予想：結城浩」（Kindle版）
関連記事：
数学ガール：結城浩
https://blog.goo.ne.jp/ktonegaw/e/bb4f1447d41afcc8b46b85229296dd7a
数学ガール/フェルマーの最終定理：結城浩
https://blog.goo.ne.jp/ktonegaw/e/4bf119bf3842421f8916c787c51216ae
数学ガール/ゲーデルの不完全性定理：結城浩
https://blog.goo.ne.jp/ktonegaw/e/f9b0b9264e35a680ce974fcbf17c62c0
数学ガール/ガロア理論：結城浩
https://blog.goo.ne.jp/ktonegaw/e/a5450818389e0220779e363617332a76
数学ガール/ポアンカレ予想 : 結城浩
https://blog.goo.ne.jp/ktonegaw/e/769e2639898b351545e7ad8a8eba89d7
Kindle版発売：「数学ガール：結城浩」シリーズ
https://blog.goo.ne.jp/ktonegaw/e/9d9037d14ed9ffcc98c7b2569fba7c39
応援クリックをお願いします！このブログのランキングはこれらのサイトで確認できます。
「数学ガール/乱択アルゴリズム：結城浩」（Kindle版）
あなたへ
プロローグ
第１章：絶対に負けないギャンブル
- サイコロ投げ（2個のサイコロ）
- コイン投げ（2枚のコイン、1枚のコイン、宝くじの記憶）
- モンティ・ホールの問題（3通の封筒、神の視点）
第２章：愚直な一歩の積み重ね
- 高校（テトラちゃん、リサ、リニアサーチ、ウォークスルー、リニアサーチの解析、リニアサーチの解析（νが見つかる場合）、リニアサーチの解析（νが見つからない場合））
- アルゴリズムの解析（ミルカさん、アルゴリズムの解析、場合分けの消去、意味を考える、番兵付きリニアサーチ、歴史を作る）
- 自宅（愚直な一歩）
第３章：171億7986万9184の孤独
- 順列（書店、納得感、具体例、規則性、一般化、道を作る、あいつ）
- 組み合せ（図書室、順列、組み合せ、アスパラガス、二項定理）
- 2^nの分配（パスカルの三角形、ビットパターン、指数的爆発）
- 冪乗の孤独（帰路、家）
第４章：確からしさの不確かさ
- 確からしさの確かさ（割り算の意味）
- 確からしさの不確かさ（同じ確からしさ、ほんとうの武器）
- 確からしさの実験（インタプリタ、サイコロ勝負、ルーレット勝負）
- 確からしさの崩壊（確率の定義、確率の意味、数学の適用、疑問への答え）
- 確からしさの公理的定義（コルモゴロフ、標本空間と確率分布、確率の公理、部分集合と事象、確率の公理 P1、確率の公理 P2、確率の公理 P3、まだわかりません、偶数の目が出る確率、ゆがんだサイコロ、縁で立つコイン、約束、咳）
第５章：期待値
- 確率変数（母、テトラちゃん、確率変数の例、確率分布の例、たくさんの言葉、期待値、公平なゲーム）
- 線型性（ミルカさん、和の期待値は期待値の和）
- 二項分布（コインの話、二項分布の期待値、和に分ける、インディケータ確率変数、楽しい宿題）
- すべてが起きるまで（いつの日か、すべてを尽くせるかどうか、学んだことを使う、すべてを尽くす、思いがけないこと）
第６章：とらえがたい未来
- 約束の記憶（川のほとり）
- オーダー（速いアルゴリズム、たかだかnのオーダー、クイズ、たかだかf(n)のオーダー、log n）
- サーチ（バイナリサーチ、実例、解析、ソートへ）
- ソート（バブルソート、実例、解析、オーダーの階層）
- 動的な視点、静的な視点（比較は何回必要か、比較木、log n!の評価）
- 伝えること、学ぶこと（伝えること、学ぶこと）
第７章：行列
- 図書室（瑞谷先生、テトラリアン）
- ユーリ（不能、不定、正則、手紙）
- テトラちゃん（図書室、行と列、行列とベクトルの積、連立方程式と行列、行列の積、逆行列）
- ミルカさん（隠れた謎を見抜く、線型変換、回転）
- 帰路（対話）
第８章：ひとりぼっちのランダムウォーク
- 家（雨の土曜日、お茶タイム、ピアノ問題、メロディの例、解き方その一：根気勝負、解き方その二：閃き勝負、一般化、揺れる心）
- 朝の通学路（ランダムウォーク）
- 昼の教室（行列の練習、揺れる心）
- 放課後の図書室（放浪問題、A^2の意味、行列のn乗へ、準備前半：対角行列、準備後半：行列と逆行列のサンドイッチ、固有値へ、固有ベクトルへ、A^nを求め用）
- 家（揺れる心、雨の夜）
第９章：強く、正しく、美しく
- 家（雨の土曜日）
- 図書室（論理クイズ、充足可能性問題、3-SAT、充足する、割り当て練習、NP完全問題）
- 帰路（誓いと約束、カンファレンス）
- 図書室（3-SATを解く乱択アルゴリズム、ランダムウォーク、定量的評価へ向けて、もう一つのランダムウォーク、ラウンドに注目）
- 家（ラッキーの評価、和を簡単に、回数の評価）
- 図書室（独立と排反、精密な評価、スターリングの近似）
- 帰路（オリンピック）
- 家（論理）
第１０章：乱択アルゴリズム
- ファミリーレストラン（雨）
- 学校（お昼、クイックソート・アルゴリズム、ピボットによる数列の分割 - 二つの翼、部分数列のソート - 再帰、実行ステップ数の解析、場合分け、最大実行ステップ数、平均実行ステップ数、帰路）
- 自宅（形を変えて、Hnとlog n）
- 図書室（ミルカさん、乱択クイックソート、比較の観察、期待値の線型性、インディケータ確率変数の期待値は確率に等しい）
- ファミリーレストラン（さまざまな乱択アルゴリズム、準備）
- 双倉図書館（アイアダイン、緊張、発表、伝える、オキシジェン、つなぐ、庭、約束のしるし）
エピローグ
あとがき
参考文献と読書案内
索引
アクセス
トータル
ランキング
