数学女孩4：随机算法ry pdf epub azw3 2024 下载

《数学女孩》系列以小说的形式展开，重点描述一群年轻人探寻数学中的美。内容由浅入深，数学讲解部分十分精妙，被称为“绝赞的数学科普书”。 《数学女孩4：随机算法》以“随机算法”为主题，从纯粹的数学和计算机程序设计两个角度对随机算法进行了细致的讲解。内容涉及排列组合、概率、期望、线性法则、矩阵、顺序查找算法、二分查找算法、冒泡排序算法和快速排序算法等。整本书一气呵成，非常适合对数学和算法感兴趣的初高中生以及成人阅读。

序言

第 1 章　绝不会输的赌博 1

1.1　掷骰子 1

1.2　抛硬币 4

1.2.1　两枚硬币 4

1.2.2　一枚硬币 7

1.2.3　的记忆 8

1.3　蒙提霍尔问题 11

1.3.1　3 个信封 11

1.3.2　上帝视角 18

第 2 章　积跬步，致千里 21

2.1　高中 21

2.1.1　泰朵拉 21

2.1.2　理纱 22

2.1.3　顺序查找 24

2.1.4　逐行调试 28

2.1.5　顺序查找算法分析 34

2.1.6　顺序查找算法分析（能找到v 的情况） 35

2.1.7　顺序查找算法分析（无法找到v 的情况） 38

2.2　算法分析 40

目 录

C O N T E N T S

2　目录

2.2.1　米尔嘉 40

2.2.2　算法分析 41

2.2.3　不同情况的归纳 42

2.2.4　思考意义 45

2.2.5　带有哨兵的顺序查找算法 48

2.2.6　创造历史 52

2.3　自己家 54

第3 章　171亿7986万9184份孤独 61

3.1　排列 61

3.1.1　书店 61

3.1.2　豁然开朗 62

3.1.3　具体示例 63

3.1.4　找规律 65

3.1.5　一般化 70

3.1.6　铺就道路 72

3.1.7　那家伙 74

3.2　组合 76

3.2.1　图书室 76

3.2.2　排列 77

3.2.3　组合 79

3.2.4　鲡鱼与绿鲤鱼 82

3.2.5　二项式定理 83

3.3　2n 的分配 88

3.3.1　帕斯卡三角形 88

3.3.2　位模式 92

目录　3

3.3.3　指数爆炸 94

3.4　幂运算的孤独 96

3.4.1　回家路上 96

3.4.2　家 96

第4 章　可能性中的不确定性 99

4.1　可能性中的确定性 99

4.2　可能性中的不确定性 106

4.2.1　相同的可能性 106

4.2.2　真正的武器 107

4.3　可能性的实验 109

4.3.1　解释程序 109

4.3.2　掷骰子比赛 112

4.3.3　轮盘比赛 113

4.4　可能性的倒塌 115

4.4.1　概率的定义 115

4.4.2　概率的意义 118

4.4.3　数学的应用 118

4.4.4　解答疑问 120

4.5　可能性的公理定义 121

4.5.1　柯尔莫哥洛夫 121

4.5.2　样本空间与概率分布函数 121

4.5.3　概率公理 125

4.5.4　子集与事件 126

4.5.5　概率公理P1 129

4.5.6　概率公理P2 130

4　目录

4.5.7　概率公理P3 131

4.5.8　还没有明白 132

4.5.9　掷出的点数为偶数的概率 134

4.5.10　质地不均匀的骰子和竖立的硬币 137

4.5.11　约定 138

4.5.12　咳嗽 139

第5 章　期望 143

5.1　随机变量 143

5.1.1　妈妈 143

5.1.2　泰朵拉 144

5.1.3　随机变量的示例 146

5.1.4　概率分布函数的示例 150

5.1.5　许多词 152

5.1.6　期望 153

5.1.7　公平的游戏 157

5.2　线性法则 159

5.2.1　米尔嘉 159

5.2.2　和的期望等于期望的和 160

5.3　二项分布 165

5.3.1　硬币的话题 165

5.3.2　二项分布的期望 168

5.3.3　划分为和的形式 171

5.3.4　指示器随机变量 172

5.3.5　快乐的作业 174

5.4　直到所有事情发生 175

目录　5

5.4.1　不知何时 175

5.4.2　能尽全力吗 176

5.4.3　运用学到的知识 180

5.4.4　尽全力 183

5.4.5　意料之外的事情 192

第6 章　难以捉摸的未来 197

6.1　约定的记忆 197

6.2　阶 199

6.2.1　更快的算法 199

6.2.2　至多为n阶 201

6.2.3　出题 204

6.2.4　至多为f(n) 阶 206

6.2.5　log n 211

6.3　查找 215

6.3.1　二分查找 215

6.3.2　实例 217

6.3.3　分析 220

6.3.4　前往排序 227

6.4　排序 228

6.4.1　冒泡排序 228

6.4.2　实例 229

6.4.3　分析 231

6.4.4　大O表示法的层级 235

6.5　动态视角、静态视角 237

6.5.1　需要比较多少次呢 237

6　目录

6.5.2　比较树 239

6.5.3　log n! 的评估 241

6.6　传递和学习 245

6.6.1　传递 245

6.6.2　学习 246

第7 章　矩阵 249

7.1　图书室 249

7.1.1　瑞谷老师 249

7.1.2　TETRALIANE 250

7.2　尤里 252

7.2.1　无解 252

7.2.2　无穷多解 254

7.2.3　唯一解 256

7.2.4　信 268

7.3　泰朵拉 269

7.3.1　图书室 269

7.3.2　行与列 269

7.3.3　矩阵与向量的积 271

7.3.4　联立方程式与矩阵 273

7.3.5　矩阵的积 274

7.3.6　逆矩阵 275

7.4　米尔嘉 280

7.4.1　看穿隐藏的谜题 280

7.4.2　线性变换 286

7.4.3　旋转 293

目录　7

7.5　回家路上 296

第8 章　孤零零的随机漫步 301

8.1　家 301

8.1.1　雨天的周六 301

8.1.2　下午茶时间 302

8.1.3　钢琴问题 302

8.1.4　旋律示例 305

8.1.5　解题方法一：毅力比拼 308

8.1.6　解题方法二：一招定胜负 310

8.1.7　一般化 314

8.1.8　摇摆不定的心 319

8.2　清晨的上学路 320

8.3　中午的教室 322

8.3.1　矩阵的练习 322

8.3.2　摇摆不定的心 325

8.4　放学后的图书室 327

8.4.1　流浪问题 327

8.4.2　A2 的意义 331

8.4.3　向着矩阵的n次方前进 332

8.4.4　上半场准备：对角矩阵 333

8.4.5　下半场准备：矩阵与逆矩阵的三明治 335

8.4.6　向着特征值前进 336

8.4.7　向着特征向量前进 342

8.4.8　求An 344

8.5　家 347

8　目录

8.5.1　摇摆不定的心 347

8.5.2　雨夜 349

第9 章　坚强、正直、美丽 351

9.1　家 351

9.2　图书室 358

9.2.1　逻辑题 358

9.2.2　可满足性问题 358

9.2.3　3-SAT 360

9.2.4　满足 363

9.2.5　分配方式的练习 364

9.2.6　NP完全问题 365

9.3　回家路上 367

9.3.1　誓言与约定 367

9.3.2　会议 368

9.4　图书室 369

9.4.1　求解3-SAT问题的随机算法 369

9.4.2　随机漫步 371

9.4.3　向着定量评估前进 376

9.4.4　另一个随机漫步 378

9.4.5　关注循环 379

9.5　家 384

9.5.1　幸运的评估 384

9.5.2　化简和式 388

9.5.3　次数的评估 390

9.6　图书室 391

目录　9

9.6.1　独立与互斥 391

9.6.2　精确的评估 392

9.6.3　斯特林公式 396

9.7　回家路上 403

9.8　家 405

第 10章　随机算法 407

10.1　休闲餐厅 407

10.2　学校 409

10.2.1　中午 409

10.2.2　快速排序算法 410

10.2.3　通过枢纽项划分数列—两只翅膀 413

10.2.4　对子数列排序—递归 417

10.2.5　运行步数的分析 418

10.2.6　分情况讨论 421

10.2.7　运行步数 425

10.2.8　平均运行步数 429

10.2.9　回家路上 434

10.3　自己家 435

10.3.1　变形 435

10.3.2　Hn 与log n 441

10.4　图书室 443

10.4.1　米尔嘉 443

10.4.2　随机快速排序 444

10.4.3　观察比较过程 447

10.4.4　期望的线性法则 452

10　目录

10.4.5　指示器随机变量的期望等于概率 453

10.5　休闲餐厅 456

10.5.1　各种各样的随机算法 456

10.5.2　准备 457

10.6　双仓图书馆 458

10.6.1　Iodine 458

10.6.2　紧张 459

10.6.3　报告 461

10.6.4　传达 462

10.6.5　Oxygen 464

10.6.6　连接 465

10.6.7　庭园 466

10.6.8　约定的印记 468

尾　声 471

后　记 477

参考文献和导读 481

结城浩（作者） 生于1963年，日本知名技术作家和程序员。在编程语言、设计模式、数学、加密技术等领域，编写了很多深受欢迎的入门书。代表作有《数学女孩》系列、《程序员的数学》《图解密码技术》等。 作者主页：http://www.hyuki.com 丛熙（译者） 2017年本科毕业于东北大学机械系，现于日本奈良先端科学技术大学院大学攻读硕士学位，研究方向为增强现实。 江志强（译者） 计算机应用软件工程师，毕业于厦门大学数学专业，目前在民航空管行业从事通信导航工作。业余时间沉迷于数学与算法。

暂无出版社相关信息，正在全力查找中！

暂无相关书籍摘录，正在全力查找中！

在线阅读地址：数学女孩4：随机算法ry在线阅读

在线听书地址：数学女孩4：随机算法ry在线收听

在线购买地址：数学女孩4：随机算法ry在线购买

我的前方本没有路，

我的身后是我踏出的路。

—高村光太郎《旅途》

我，想了解这个世界。

我，想了解我自己。

　　想了解世界的广阔。

　　想了解自己的深邃。

但实际上—我想被了解。

被世界，被她所了解。

但是我不明白。

我不明白我自己。

真的希望自己现在的样子被看到吗？

我想不明白这一点。

　　与少言寡语的红发少女，

　　邂逅在新的季节。

　　从那里诞生出新的谜题。

若要做出选择，只能有所放弃。

无限多条道路，只能选择一条。

　　过去已然确定，未来尚不可知。

　　位于它们的分界上的，是现在。

如果未来变成现在，只会留下一个时刻。

现在在前行中将不定的未来变成确定的过去。

　　选择，决定了前程。

　　选择，向未来前行。

即便无法理解，我也会选择。

即便无法理解，我也在活着。

一边选择，一边活着。

一边前行，一边开辟道路。

　　我的前方本没有路，

　　我的身后是我踏出的路。

我不知自己是否正确地了解了世界。

也不知自己是否正确地了解了自己。

但是，我今天仍在前行。

　　为了知晓无法知晓的明天。

　　为了解出未能解出的谜题。

一边期待着有你的未来—

泰朵拉重新看了看笔记本，慢慢地继续话题。

“嗯，按照村木老师的说法，先想象自己变成了计算机先生，然后再去运行代码会更好。

·大喊‘我是计算机’·想象自己被给予了算法与输入

·然后，按照流程笨拙、踏实地一步一步运行不得不说这很麻烦，但据说这样是理解算法最快的方法。”

“是吗…”

“我要试试老师说的，我特别喜欢这种毅力定胜负的比拼。接下来，人家要变成计算机了！”

回家路上。

我独自发呆，在脑海中描绘着树形图。

树形图……

如果有34段“分杈”，就能分成171亿7986万9184个树枝。经过34次分杈，就可以区分世界上每一个人了。

仅仅34次分杈就能得到171亿7986万9184种结果，那么，从过去经过无数岔路行走到现在的我们，是多少可能性中的一个啊。

仅仅1比特的不同，就能让两人的路越走越远。唉，我们的每一天都被分杈填满，我们必须在这出门无数分岔的森林里披荆斩棘。

“学长说过这样一句话吧，在面对数学公式的时候，我们每个人都是‘小数学家’。”

“嗯。”

“我会回想起那句话，这样即便时间一分一秒地过去，我也不会慌张、不会焦急。我会将注意力集中在眼前的问题上。大家都是一样的，虽然面对问题时我是一个人，可我并不孤独。学长的话语，在我的内心给予我力量。”

“……”

“我，不是独自一人。每个人都在独自面对‘自己的问题’。全世界的‘小数学’们都在忙于各自的问题。所以、所以我并不狐独。即便面对的问题不同，我也绝对、绝对不孤独。即便——

即便一个人也好，我也会认真思考。

即便一个人也好，我也会认真战斗。

只有披荆斩棘，我们才能迎来互相理解。

我发现了这样一个新世界。”

按相同的可能性发生的情况是怎样的情况？对于这一问题，数学无法做出回答。——柯尔莫哥洛夫《概率论导引》

编辑推荐

《数学女孩》系列第四弹！迷人的数学故事，好玩的数学科普书。日本数学会强力推荐！

书籍介绍

《数学女孩4：随机算法》以“随机算法”为主题，从纯粹的数学和计算机程序设计两个角度对随机算法进行了细致的讲解。内容涉及排列组合、概率、期望、线性法则、矩阵、顺序查找算法、二分查找算法、冒泡排序算法和快速排序算法等。整本书一气呵成，非常适合对数学和算法感兴趣的初高中生以及成人阅读。

• 作者： 密室行者 发布时间：2019-08-09 14:23:58

  这本不错，又回到了第一册的水准，目前四本的个人排名是1423。

• 作者： 于小鱼 发布时间：2022-02-19 00:30:35

  本册涉及概率，线性代数，和一些计算机算法，最后一章也不过是快速排序，相对比较简单

• 作者： 唐超旬 发布时间：2020-01-28 23:03:11

  可能是因为涉及的是算法的缘故，觉得比前三本简单了些。行文结构还是按照2、3两册的风格：先介绍基础知识，以此为工具，在最后一章点题，串起来讲解。我自己涉及随机算法太少，这本书算是入门指引了，今后可以多看看相关资料了。感谢结城浩！

• 作者： 林夕尘dream 发布时间：2021-04-06 14:43:42

  恩师兼兄弟剑哥的赠书

• 作者： 书蠹精 发布时间：2019-12-08 11:00:37

  获得出版社样书

• 作者： AhaEureka 发布时间：2021-10-23 15:24:35

  涉及到算法的复杂度计算还有概率论公理和矩阵的基本知识。面对基本的排序算法，脑子都转不过来可咋整。

• 数学，能够穿越时空

  作者：wdpm 发布时间：2019-11-18 18:34:58

  1 求掷出所有点数时掷骰子次数的期望。

  

  幸福的台阶：

  

  建立随机变量 Xj。它表示“假设已经出现了 j 种点数，直到掷出没出现过的点数时，掷骰子的次数”。 也就是说，Xj 表示“幸福的台阶”的第 j + 1 层的长度。

  2 大O表示法的图像含义：

  

  

  在大 O 表示法中使用对数函数时，可以不在意底。因为，所有的对数函数就算进行底的变换，其结果的差异也一定只是常数倍的。

  

  O(f(n)) 表示满足 | T(n) | 小于等于 Cf(n) 这一条件的函数 T(n) 的集合。

  用比较树证明比较排序算法的最大比较次数至少为 n log n 阶。同样，也能证明比较查找算法的最大比较次数是 Ω(log n)。

  3 联立方程式与矩阵

  

  

  

  

  矩阵的线性变换

  

  对角矩阵可以方便地计算n次方。

  

  4 可满足性问题

  将括号内的子句用 ∧(且运算符)连结，形成的整体称为逻辑公式。逻辑公式也称为合取范式，简写为CNF，取自 Conjunctive Normal Form 的首字母。

  

  假设有一个规模为 n 的问题，如果能在多项式时间内找到问题正确的解，就把这个问题称为 P 问题。‘P’是多项式时间，也就是 Polynomial time 的首字母。多项式时间指计算时间可以被 n 的常数 次方限制住，也就是 O(n^k) 的意思。P 问题可以说是‘能够高效解出的问题’。”

  与 P 问题相对应的另一类问题称为 NP 问题。是指当得到解的候选时，能够高效地判断候选是否为问题正确的解。

  P不等于NP猜想：

  已经证明了所有的 P 问题都是 NP 问题，但所有的 NP 问题都是 P 问题吗？

  随机漫步：

  

  黑 点 表 示 ‘ 分 配 方 式 ’。 一 组 分 配 方 式 确 定 了 用 到 的 变量的真假，对应 1 个黑点。因为逻辑公式有 n 种变量，所以一共有 2^n个分配方式。随机漫步就是在拥有 2^n 个元素的集合中的元素上漫步。

  汉民距离：当两个分配方式中不一致的变量个数很多时，我们认为两个分配方式距离很远;当不一致的变量个数很少时，我们认为两个分配方式距离很近。

  

  为了定量地处理远和近，我们将两个分配方式的距离定义为‘值不一致的变量的个数’，这样的距离称作汉明距离。

  5 斯特林公式

  

  6 论文

  规范正确地写下有传达价值的事情，这就是论文的本质。

  7 快速排序

  进行随机快速排序时，对于任意输入， 算法的运行步数的期望至多为 n log n 阶。随机指的是枢纽项随机选择，可以回避最坏的情况（有序情况）。

  在大于等于 j 小于等于 k 的元素中，j 或者 k 最先被选为枢纽项时，元素i和j会发生比较。元素 j 和元素 k 的比较次数为 0 次或者 1 次。

• 大学生应如何读《数女4》

  作者：層云 发布时间：2024-03-08 15:14:15

  首先，我二刷了《数女4》，是在一年来通读了更多的线性代数、算法简介、概率论和随机过程的书籍之后，回看的此书。

  不得不承认，看了几个方面的数学入门书后再看此书才看得懂，第一次看确实没太明白。不过，没关系，这里聊的“大学生应如何读《数女4》”当然指的是大学理工科学生在学习线性代数、概率论和相关的数学必修课“之余”怎么看这个“小说”的导读。

  作者在第 1 章没有上难度，延续前面几集的设定，第一章是个中学内容“接接地气”——1.2.3　彩票的记忆，说的就是老生常谈的“独立性”问题。不过，大学生可关注的是“1.3　蒙提霍尔问题 ”，写得比《普林斯顿概率论读本》还要通俗。

  第 2 章属于算法的预习，学过VB、C语言初步的中学数学那部分就够了，大学生应该重点看的是“2.2　算法分析”——使用数学去量化计算机运行效率！

  第3 章则属于“接接地气”给后面的算法分析提供数学“基础课复习”的一个内容，复习了：排列组合、二项式定理、幂和指数爆炸。因为后面的算法分析计算概率（因为“随机算法”涉及概率）的时候需要二项式定理来巧妙转化带排列组合的求和为幂的形式，这个在第9第10章反复使用得有点闷骚。

  第4 章属于概率论的前传，本科生该注意看了，特别是4.5.1柯尔莫哥洛夫公理与4.5.2概率分布函数，补充学习概率论课程中重技巧、轻理解的问题。

  接着是第5 章　期望，那真是本科生必须细读的章节！“5.1　随机变量”就把每个低年级学生必问的问题给回答了，“5.2　线性法则”和“5.3　二项分布”把概率论必考内容说透了！“5.4　直到所有事情发生”更是把几何分布（无穷项）的事件通俗化了。

  第6 章　属于算法内容的延续，开始介绍“大O表示法的层级”，其中“6.3.1　二分查找”和“6.4.1　冒泡排序”值得工科学生在学VB、C语言的时候同时玩一下（不是指编程，课内本来也有，指的是算法分析。）

  第7 章 重点！需要大学生细读——因为会考试。。。整章就是线性代数课程的考点：“7.2.1　无解到7.2.3　唯一解”是“线性空间”，“7.3.2　行与列”到“7.3.6　逆矩阵”是“矩阵乘法”。为了简单，作者只介绍二阶方阵了，这当然比mXn方阵有教学优势，因为mXn那晕乎的啊，线性代数课程难就难在晕乎在mXn了，对吧？

  第8 章 随机漫步，往后，就有点作者自嗨了，不过，可以重点看“8.1.3　钢琴问题”，这是典型的随机漫步。这是后面“9.6.2　精确的评估”的基础问题。“9.6.3　斯特林公式”更是作者自嗨回到了第一集《数学女孩》，可能是作者职业病犯了。本科生有兴趣的话可以重点关注“9.2.6　NP完全问题”、“9.4.1　求解3-SAT问题的随机算法”、“10.2.2　快速排序算法”，“10.4.2　随机快速排序”、“10.4.5　指示器随机变量的期望等于概率”等章节。

  总体而言，这一本对本科生还是很有价值的，毕竟两门必修课的考点都说了——第7 章覆盖了线性代数的主要概念，第4、5章覆盖了概率论的主要概念。