大話電腦科學：生活中的計算思維

目  錄

第1篇生活中的程序設計與數據結構

第1章 遞歸：老和尚給小和尚講故事 002

1.1  “老和尚給小和尚講故事”中的遞歸 002

1.2 《盜夢空間》中的遞歸 006

1.3 生活中的遞歸 008

第2章 二進制：靠掰手指居然能數幾萬個數 009

2.1 用雙手錶示0~99的任意數字 009

2.2 用雙手錶示0~1023的任意數字 011

2.3 用雙手錶示更大的數字 013

第3章 循環與上下文切換：怎麽更有效地做重復勞動 015

3.1 按說明書組裝玩具書，重復勞動多 016

3.2 優化一：同類操作集中做，減少上下文切換 019

3.3 優化二：調整組裝順序，減少額外開銷 021

3.4 優化三：兩人合作變身“雙核CPU” 022

第4章 二分法與二叉樹：圖書館保安應該怎麽找到沒借過的書 023

4.1 用二分法在有序數組中定位數字 024

4.2 用二分法找沒有借過的書，鬧出了大烏龍 025

4.3 二叉樹可以更好地對借書問題建模 027

4.4 二叉樹的層數：需要的檢測次數 028

第5章 隊列與棧：明天該穿什麽衣服 031

5.1 把T恤衫組織成棧結構 032

5.2 把T恤衫組織成隊列結構 033

5.3 生活中的其他隊列結構 035

5.4 生活中的其他棧結構 035

第2篇生活中的算法與理論

第6章 蛋糕怎麽切才公平：多贏是可能的 038

6.1 切蛋糕是一個博弈論問題 039

6.2 A切B選算法 040

6.3 懸線切蛋糕算法 041

第7章 啟發式搜索：《最強大腦》里的那些

計算力小游戲 043

7.1 掌握正確算法，你就是最強大腦 043

7.2 啟發式搜索解數獨 044

7.3 啟發式搜索解珍瓏棋局 045

第8章 深度優先遍歷：迷宮里的右手法則 050

8.1 矩形迷宮中的右手法則 050

8.2 右手法則與深度優先搜索 052

8.3 右手法則與迷宮拓撲結構 054

8.4 右手法則在其他迷宮未必奏效 055

第9章 最短路與負環：套餐定價和外匯兌換的約束 057

9.1 合理的菜單定價與三角形不等式 058

9.2 從菜單到圖論 059

9.3 用最短路算法進行合理性檢驗 061

9.4 最短路算法與貨幣兌換中的負環 063

第10章 最佳匹配：外賣平臺是怎樣派單的 066

10.1 外賣派單與二分圖 066

10.2 二分圖匹配與運力判定問題 067

10.3 二分圖最大匹配：匈牙利算法 069

10.4 從最大匹配到最優匹配 070

第11章 旅行商問題：怎樣逛超市最省時間 073

11.1 逛超市採購是一個旅行商問題 074

11.2 生活中的其他旅行商問題 075

11.3 旅行商問題極具復雜性 076

11.4 旅行商問題的近似算法 078

第3篇生活中的數據科學

第12章 數據標註：驗證碼里的大生意 082

12.1 訓練數據通常需要人工數據標註 082

12.2 先有訓練數據，才有人工智能模型 084

12.3 訓練數據的質量與數量都很重要 085

12.4 巧妙使用驗證碼來進行數據標註 086

第13章 數據庫：搶火車票的背後發生了什麽 090

13.1 關系數據庫：最經典的數據庫 091

13.2 索引：為了更高效的數據庫查詢 092

13.3 多表單數據庫：提高整體查詢效率 093

13.4 數據庫中的並發與鎖：為什麽查到有票卻買不到 095

13.5 為什麽購物平臺往往比購票平臺更高效 096

第14章 大數據：啤酒和尿布為什麽要擺放在一起售賣 098

14.1 頻繁模式：看兩種物品同時出現的頻率 099

14.2 關聯規則：用戶購買A了，還有多大概率購買B 100

14.3 分佈式挖掘頻繁模式：高效探索關聯規則 100

第15章 最優化：為什麽肯德基、麥當勞總是開在一起 102

15.1 店鋪選址的“最優化”目標究竟是什麽 103

15.2 生活中的其他最優化問題 105

第16章 特徵工程：如何區分三個“一模一樣”的燈泡 107

16.1 區分浣熊和貓咪的特徵構建：特徵工程重要且復雜 108

16.2 提取燈泡發熱的特徵，妙解特徵工程的經典面試題 109

16.3 好的特徵工程能力處處有用 111

第4篇生活中的機器學習

第17章 最近鄰算法：孟母三遷背後的假設 114

17.1 最近鄰算法不需要“學習” 114

17.2 最近鄰算法的關鍵：如何定義相似度 116

17.3 從最近鄰到K-最近鄰：綜合考慮更穩健 117

第18章 支持向量：美國大選基本只需要看搖擺州 120

18.1 得搖擺州者，得美國大選 120

18.2 從二分類的角度看支持向量：尋找最優分界線 121

18.3 遠離最大化邊界的點對最優分界線沒有影響 124

第19章 過擬合：高考失誤真的是因為心態嗎 125

19.1 人類學習與機器學習的類比 126

19.2 高考表現得不好可能是因為過擬合 126

19.3 過擬合產生的原因 129

19.4 如何避免過擬合 131

第20章 集成學習：疑難雜症要多看幾個專家 133

20.1 集成學習與尋醫問診 133

20.2 Bagging框架：群策群力、一人一票 135

20.3 Boosting框架：考慮專家可信度加權平均 137

第21章 梯度下降：駕駛汽車和登山都用到了導數 140

21.1 一尺之棰,日取其半,萬世不竭 140

21.2 位移、速度、加速度之間的導數關系 141

21.3 梯度下降：利用導數尋找最優解 143

21.4 登山、高爾夫球中的“梯度下降” 144

第22章 樸素貝葉斯：為什麽我的郵件被識別為垃圾郵件 147

22.1 垃圾郵件中的關鍵詞 147

22.2 關鍵詞分類背後的樸素貝葉斯算法 148

22.3 元數據也是垃圾郵件分類的重要依據 150

22.4 如何避免正常郵件被誤分為垃圾郵件 151

第5篇生活中的智能系統

第23章 個體與系統的博弈：外賣騎手的困局 154

23.1 博弈論的概念 154

23.2 外賣平臺中的博弈 155

23.3 博弈的初衷是 “三贏” 156

23.4 算法的“智能”會打破博弈的平衡 157

23.5 個體之間的團結有利於博弈的平衡 159

第24章 搜索引擎：孕婦到底能不能吃螃蟹 161

24.1 早期搜索引擎：看字面相似度 162

24.2 現代搜索引擎：從字面到語義 164

24.3 搜索關鍵詞的設計 166

第25章 同溫層效應：為什麽我的App內容越來越同質化 168

25.1 協同過濾：相似的用戶喜歡相似的內容 169

25.2 現代個性化推薦系統：用戶畫像 170

25.3 用戶如何與個性化推薦系統更好地磨合 172

25.4 個性化推薦系統的弊端：同溫層現象 173

第26章 天梯匹配系統：網絡游戲如何讓玩家欲罷不能 175

26.1 天梯積分是一種Elo等級分制度 176

26.2 玩家在天梯匹配系統下的期望勝率通常是50% 178

26.3 天梯匹配系統也不僅僅是Elo等級分制度 180

26.4 如何利用天梯匹配系統科學上分 181

第27章 大語言模型：啥是ChatGPT 182

27.1 什麽是GPT 183

27.2 GPT以外的其他語言模型 185

27.3 Scaling Law：模型越大，能力越強 185

27.4 ChatGPT帶來的機遇、挑戰和風險 188

第28章 人臉識別：我的臉解鎖了媽媽的手機 190

28.1 人臉識別的常見流程 190

28.2 人臉識別常用的特徵 192

28.3 人臉識別的挑戰：如何識別偽造的人臉 193

第29章 自然語言處理：NLP is so hard 194

29.1 基於自然語言處理的應用隨處可見 195

29.2 中文的分詞極具挑戰性 196

29.3 英語的語義也常有歧義 197

29.4 歧義性也是一種魅力 198

第6篇生活中的信息安全

第30章 瀏覽器：隱私瀏覽模式到底有多隱私 200

30.1 上網沖浪的過程到底能被誰看到 201

30.2 隱私瀏覽模式到底保護了什麽隱私 203

第31章 區塊鏈：比特幣的共識 205

31.1 區塊鏈本質上是一個分佈式賬本 206

31.2 區塊鏈的獨特之處：去中心化的賬本 207

31.3 比特幣的價值在哪裡 209

第32章 哈希算法：好網站都不保存用戶的明文密碼 210

32.1 好的哈希函數是一個特級名廚 211

32.2 用戶識別：比較登錄密碼的哈希值就夠了 212

32.3 黑客如何根據哈希值反向破解密碼 213

32.4 “適量加鹽”可以讓密碼更難破解 214

32.5 靠瀏覽器記住密碼靠譜嗎 216

第33章 非對稱加密：公開的密鑰能加密卻不能解密 217

33.1 加密已經是上網沖浪的標配了 218

33.2 對稱加密的風險問題 218

33.3 非對稱加密的優勢 219

33.4 圖靈獎級別的工作：RSA算法 220

33.5 中間人攻擊：非對稱加密也沒法避免的問題 222

第7篇生活中的硬件系統

第34章 文件系統：我的聊天記錄沒有了還能找回來嗎 226

34.1 文件和文件系統 227

34.2 快捷方式與懶刪除 229

第35章 內存與存儲：為什麽手機“內存”比電腦內存還大 231

35.1 電腦存儲的分類 232

35.2 外存是一種非易失性存儲器 233

35.3 內存是一種易失性存儲器 233

35.4 手機廣告中提到的“內存”通常不是電腦科學中的

   “內存” 235

第36章 網絡：為什麽“1000M”的寬帶網絡沒有“1000M”

的運行速度 237

36.1 bit和Byte的區別 237

36.2 網速的瓶頸可能讓人意想不到 238

36.3 為什麽上傳速度通常比下載速度慢 239

36.4 網速為什麽會隨著時間波動 240

36.5 Wi-Fi里的2.4GHz和5GHz是什麽意思 241

第37章 物聯網：體感游戲的秘訣 242

37.1 體感游戲如何評分 243

37.2 體感游戲評分難免有誤差 244

37.3 記步數到底有多可靠 245

37.4 傳感器之間如何聯動提高準確度 247

第38章 分佈式計算：一小時做完年夜飯 249

38.1 鍋碗瓢盆都是烹飪過程中的“計算節點” 250

38.2 分佈式計算和烹飪共同面對的問題 251

38.3 高效烹飪與高效分佈式計算的核心都在於調度協調 252

38.4 計算資源決定了分佈式計算的上限 254

38.5 生活中的其他分佈式計算 255