大话计算机科学：生活中的计算思维

目 录

第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

......(更多)