數學女孩：隨機演算法

給讀者

序章

第1章　絕對不會輸的賭博
1.1　擲骰子
1.1.1　2個骰子
1.2　擲硬幣
1.2.1　2枚硬幣
1.2.2　1枚硬幣
1.2.3　彩券的記憶
1.3　蒙提霍爾問題
1.3.1　3封信封
1.3.2　神的觀點

第2章　累積愚直的一步
2.1　高中
2.1.1　蒂蒂
2.1.2　麗莎
2.1.3　線性搜尋
2.1.4　走查
2.1.5　線性搜尋的分析
2.1.6　線性搜尋的分析（找到v的情況）
2.1.7　線性搜尋的分析（找不到v的情況）
2.2　演算法的分析
2.2.1　米爾迦
2.2.2　演算法的分析
2.2.3　消去區分情況
2.2.4　思考意義
2.2.5　有衛兵的線性搜尋
2.2.6　建構歷史
2.3　自家
2.3.1　愚直的一步

第3章　171億7986萬9184的孤獨
3.1　排列
3.1.1　書店
3.1.2　同意感
3.1.3　具體例子
3.1.4　規則性
3.1.5　一般化
3.1.6　建造道路
3.1.7　那傢伙
3.2　組合
3.2.1　圖書室
3.2.2　排列
3.2.3　組合
3.2.4　蘆筍
3.2.5　二項式定理
3.3　2n的分配
3.3.1　帕斯卡三角形
3.3.2　位元模式
3.3.3　指數的爆發
3.4　冪乘的孤獨
3.4.1　歸途
3.4.2　家

第4章　機率的不確定性
4.1　機率的確定性
4.1.1　除法的意義
4.2　機率的不確定性
4.2.1　同樣的機率
4.2.2　真正的武器
4.3　機率的實驗
4.3.1　解譯器
4.3.2　骰子決勝負
4.3.3　輪盤決勝負
4.4　機率的崩壞
4.4.1　機率的定義
4.4.2　機率的意義
4.4.3　數學的應用
4.4.4　對疑問的解答
4.5　機率的公設定義
4.5.1　柯爾莫哥洛夫
4.5.2　樣本空間與機率分布
4.5.3　機率的公設
4.5.4　部分集合與事件
4.5.5　機率的公設P1
4.5.6　機率的公設P2
4.5.7　機率的公設P3
4.5.8　還是不懂
4.5.9　出現偶數點數的機率
4.5.10　歪斜的骰子、邊緣立起的硬幣
4.5.11　約定
4.5.12　咳嗽

第5章　期望值
5.1　隨機變數
5.1.1　媽媽
5.1.2　蒂蒂
5.1.3　隨機變數的例子
5.1.4　機率分布的例子
5.1.5　許多詞彙
5.1.6　期望值
5.1.7　公平的遊戲
5.2　線性
5.2.1　米爾迦
5.2.2　和的期望值、期望值的和
5.3　二項式分布
5.3.1　硬幣的故事
5.3.2　二項式分布的期望值
5.3.3　區分成和
5.3.4　指示隨機變數
5.3.5　愉快的作業
5.4　到全部發生為止
5.4.1　總有一天
5.4.2　能夠出盡一切嗎
5.4.3　使用學到的事
5.4.4　出盡一切
5.4.5　意想不到的事

第6章　難以捕捉的未來
6.1　約定的記憶
6.1.1　河邊
6.2　級數
6.2.1　快速演算法
6.2.2　至多n量階
6.2.3　小測驗
6.2.4　至多f(n) 量階
6.2.5　log n
6.3　搜尋
6.3.1　二元搜尋
6.3.2　實例
6.3.3　分析
6.3.4　前往排序
6.4　排序
6.4.1　泡沫排序
6.4.2　實例
6.4.3　分析
6.4.4　級數的階層
6.5　動的觀點、靜的觀點
6.5.1　需要幾次比較
6.5.2　比較樹
6.5.3　log n!的估算
6.6　傳達、學習
6.6.1　傳達
6.6.2　學習

第7章　矩陣
7.1　圖書室
7.1.1　瑞谷老師
7.1.2　四千烷
7.2　由梨
7.2.1　無解
7.2.2　無限解
7.2.3　正則
7.2.4　信
7.3　蒂蒂
7.3.1　圖書室
7.3.2　行與列
7.3.3　矩陣與向量的積
7.3.4　聯立方程式與矩陣
7.3.5　矩陣的積
7.3.6　逆矩陣
7.4　米爾迦
7.4.1　看穿隱藏的謎
7.4.2　線性變換
7.4.3　旋轉
7.5　歸途
7.5.1　對話

第8章　孤獨的隨機漫步
8.1　家
8.1.1　下雨的星期六
8.1.2　下午茶時間
8.1.3　鋼琴問題
8.1.4　旋律的例子
8.1.5　解法其一：耐性決勝負
8.1.6　解法其二：靈感決勝負
8.1.7　一般化
8.1.8　動搖的心
8.2　早晨的上學路
8.2.1　隨機漫步
8.3　中午的教室
8.3.1　矩陣的練習
8.3.2　動搖的心
8.4　放學後的圖書室
8.4.1　流浪問題
8.4.2　A2的意義
8.4.3　前往矩陣的n乘
8.4.4　準備前半部：對角矩陣
8.4.5　準備後半部：矩陣與逆矩陣的三明治
8.4.6　前往特徵值
8.4.7　前往特徵向量
8.4.8　求An
8.5　家
8.5.1　動搖的心
8.5.2　雨夜

第9章　強大、正確、美麗
9.1　家
9.1.1　下雨的星期六
9.2　圖書室
9.2.1　邏輯小測驗
9.2.2　可滿足性問題
9.2.3　3-SAT
9.2.4　滿足
9.2.5　賦值練習
9.2.6　NP完全問題
9.3　歸途
9.3.1　誓言與約定
9.3.2　會議
9.4　圖書室
9.4.1　解答3-SAT的隨機演算法
9.4.2　隨機漫步
9.4.3　朝向定量式估算
9.4.4　另一個隨機漫步
9.4.5　關注迴圈
9.5　家
9.5.1　幸運的估算
9.5.2　將和簡化
9.5.3　次數的估算
9.6　圖書室
9.6.1　獨立與互斥
9.6.2　精確的估算
9.6.3　斯特靈公式的近似
　　9.7　歸途
9.7.1　奧林匹克
9.8　家
9.8.1　邏輯

第10章　隨機演算法
10.1　家庭餐廳
10.1.1　雨
10.2　學校
10.2.1　中午
10.2.2　快速排序演算法
10.2.3　依軸分割數列──兩只翅膀
10.2.4　部分數列的排序──遞迴
10.2.5　執行步驟數的分析
10.2.6　區分情況
10.2.7　最大執行步驟數
10.2.8　平均執行步驟數
10.2.9　歸途
10.3　自家
10.3.1　改變形式
10.3.2　Hn 與 log n
10.4　圖書室
10.4.1　米爾迦
10.4.2　隨機快速排序
10.4.3　比較的觀察
10.4.4　期望值的線性
10.4.5　指示隨機變數的期望值等於機率
10.5　家庭餐廳
10.5.1　各式各樣的隨機演算法
10.5.2　準備
10.6　雙倉圖書館
10.6.1　碘
10.6.2　緊張
10.6.3　發表
10.6.4　傳達
10.6.5　氧
10.6.6　連結
10.6.7　庭園
10.6.8　約定的象徵

尾聲
後記
索引

導讀

數學女孩與隨機漫步

　　本小說是結城浩所創作的《數學女孩》系列之第四本。除了主要人物多了一位紅頭髮的美少女麗莎之外，本書敘事延續了結城浩的一貫風格，亦即，他充分運用語言、圖形、程式乃至於算式，來表現登場人物的思考脈絡。這種在故事情節中論述數學的手法，想必是本系列小說不僅吸引一般科普讀者，同時也得到數學家注意的主要原因之一。

　　明確地說，結城浩在本系列小說中的書寫，都是將構成各個主題的數學知識細節，編入故事的情節之中。因此，他的敘事往往伴隨著數學知識的開展，而達到融數學與敘事為一體的境界。一般而言，數學的這種鋪陳與開展，當然為一般科普作品所具備，不過，如果還想契合故事情節中小說人物的對話，那麼，作家的數學敘事（mathematical narrative），就非要完全融會貫通相關的數學知識不可了。

　　正是基於這種在「脈絡」（context）中「做」與「說」數學的特性，結城浩也得以細緻地分享他對相關數學主題的學習心得，因此，如果讀者有意就數學普及書籍學一點數學，那麼，這一系列小說都是上上之選。

　　本小說主題為隨機漫步（random walk）及其定量估算，但由於涉及機率、統計與矩陣，因此，作者運用了相當多的篇幅（共有四章），引進排列、組合、機率、期望值以及矩陣等高中基礎數學知識單元。在解題時，作者盯住細節但又不為其所侷限，總是提醒讀者從容出入，適時掌握「筆記」要點或「旅行地圖」，以免迷失所在位置。此外，他還進一步說明如何從結構面向切入，以連結具體例子與一般化，以及「看穿構造，需要心之眼」的知識洞察力之不可或缺。更值得注意的，在可滿足性問題（SAT）的脈絡中，作者也引進 是否成立這個千禧年百萬美元獎金難題。所謂 問題是指有效率可解的問題，至於 問題，則是給定一個可能的解時，能有效率判斷這個解是否正確的問題。目前已經證明 ，但是反過來，則仍然未知。作者從具體例子入手，說明此一難題的背景與意義，意在激發「小數學家」的豪氣，用心良苦，令人感佩。

　　另一方面，本書適時地呼應可能出自作者自己年少苦讀數學的勵志嘉言。譬如說吧，他利用書中主角深入說明數學概念或原理時，最喜歡強調「舉例是理解的試金石」，或者指出「從理所當然之處開始是好事」，還有，他在主角討論數學的場合中，也總是鼓勵讀者「能夠有自由談的對象很重要」。譬如，在反思矩陣單元（第7章）的學習時，作者主張將「矩陣的理論當武器來使用」，至於琢磨武器的方法，則是透過對話：

　　與問題的對話、與自己的對話，還有與米爾迦或蒂蒂的對話。我透過對話衡量自己的理解度，測試自己的力量。

　　還有，作者更是大聲召喚讀者：「將有傳達價值的，正確傳達地書寫 – 這是論文的本質。將過去的人類發現，再加上自己的新發現 – 這是研究的本質。將現在重疊在過去之上，看見未來 – 這是學問的本質。」這種期許年輕人的數學創新願景，在一般數學普及作品中並不多見。作者選擇了數學小說這個文類，而得以大大地凸顯此一願景，實在令數學家感到欣慰。

　　總之，結城浩在本系列的這第四本的招式並未用老，他的敘事表現或許也可以很好地解釋數學的深度與廣度，是取之不盡、用之不竭的人類知識泉源，值得我們繼承與珍惜！我在《數學女孩：哥德爾不完備定理》的推薦文中，以為該書是此一系列的終曲，沒想到結城浩又繼續發表本書以及《數學女孩：伽羅瓦定理》，真是令人驚喜！鑑於本系列對於相關數學知識普及的貢獻，我們非常期待他更多作品問世！

洪萬生