同构：编程中的数学

图书标准信息

• 作者 刘新宇
• 出版社 机械工业出版社
• 出版时间 2022-11
• 版次 1
• ISBN 9787111725640
• 定价 89.00元
• 装帧 其他
• 开本 16开
• 纸张 胶版纸
• 页数 308页
• 字数 453千字

【内容简介】

本书从数字、递归、对称、范畴、融合、无穷、悖论七个方面介绍了计算机程序的数学基础和原理，并以“同构”概念为线索揭示出编程本质上是和数学同构的。第1章介绍皮亚诺算术公理系统,通过5条公理，构筑了计算机程序大厦的基石;通过单向链表、斐波那契数列等例子，展示了和自然数同构的计算结构。第2章介绍递归，通过欧几里得算法作为开端，最终把递归的数学原理构建在Lambda演算和Y组合子之上。第3章介绍对称群、环、域等抽象代数结构，解释了伽罗瓦理论这一抽象思维的明珠。第4章介绍范畴论，把列表、异常、多态、类型系统、复合数据结构等众多编程概念构筑在范畴论的基础上。第5章介绍融合律，它是进行算法推导和优化的有力工具。第6章介绍无穷，给出了康托尔的无穷集合论和超限数概念，介绍了编程中流的概念和无穷的关系。第7章以罗素悖论、可计算性和哥德尔不完全性定理结束本书，介绍了计算能力的边界和对编程基础哲学的影响。 本书还在各个章节中介绍相关数学家的人生经历和逸闻趣事，讲解他们如何克服困难、追求真理、创造奇迹，并穿插讲述编程、数学、艺术、音乐之间的有趣联系。

【作者简介】

刘新宇，毕业于清华大学，现任亚马逊中国研发中心物流技术团队研发经理，拥有二十余年研发经验，长期专注于函数式基础算法。

【目录】

序

前言

章数字1

1.1数的诞生1

1.2皮亚诺自然数公理2

1.3自然数和计算机程序4

1.4自然数的结构6

1.5自然数的同构10

1.6形式与结构14

第2章递归16

2.1万物皆数16

2.2欧几里得算法18

2.2.1欧几里得和《几何原本》19

2.2.2欧几里得算法概述19

2.2.3扩展欧几里得算法22

2.2.4欧几里得算法的意义26

2.3λ演算28

2.3.1表达式化简30

2.3.2λ抽象31

2.3.3λ变换规则31

2.4递归的定义35

2.5λ演算的意义36

2.6更多的递归结构38

2.7递归的形式与结构39

2.8附录：倒水趣题完整程序42

第3章对称43

3.1什么是对称43

3.2群46

3.2.1群的定义50

3.2.2幺半群与半群52

3.2.3群的质55

3.2.4置换群58

3.2.5群与对称61

3.2.6旋转对称与循环群62

3.2.7分圆方程65

3.2.8子群66

3.2.9拉格朗定理72

3.3环与域82

3.3.1环的定义84

3.3.2除环和域86

3.4伽罗瓦理论87

3.4.1扩域87

3.4.2从牛顿、拉格朗到伽罗瓦89

3.4.3自同构和伽罗瓦群95

3.4.4伽罗瓦基本定理96

3.4.5可解98

3.5附录：伽罗瓦群100

第4章范畴102

4.1范畴概述104

4.1.1范畴的例子106

4.1.2箭头≠函数110

4.2函子111

4.2.1函子的定义111

4.2.2函子的例子112

4.3积与和118

4.3.1积与和的定义120

4.3.2积与和的质122

4.3.3积与和作为函子123

4.4自然变换126

4.4.1自然变换的例子127

4.4.2自然同构130

4.5数据类型131

4.5.1起始对象和终止对象131

4.5.2幂136

4.5.3笛卡儿闭和对象算术140

4.5.4多项式函子142

4.5.5f-代数143

4.6小结156

4.7扩展阅读158

4.8附录：例子代码158

第5章融合160

5.1叠加-构建的融合161

5.1.1列表的叠加作162

5.1.2叠加-构建融合律163

5.1.3列表的构建形式164

5.1.4使用融合律化简165

5.1.5类型167

5.1.6用范畴论推导融合律168

5.2巧算100171

5.2.1穷举法171

5.2.2改进173

5.3小结和扩展阅读175

5.4附录：巧算100问题的代码175

第6章无穷177

6.1无穷概念的提出179

6.1.1无穷的哲学181

6.1.2穷竭法与微积分183

6.2潜无穷与编程186

6.3实无穷的思191

6.3.1无穷王国的花园192

6.3.2一一对应与无穷集合194

6.3.3可数无穷与不可数无穷200

6.3.4戴德金分割203

6.3.5超限数和连续统设205

6.4无穷与艺术209

6.5附录：例子代码214

6.6附录：康托尔定理的证明215

6.7附录：巴赫《音乐的奉献》无限上升的卡农216

第7章悖论218

7.1计算的边界221

7.2罗素悖论222

7.3数学基础的分歧225

7.3.1逻辑主义225

7.3.2直觉主义227

7.3.3形式主义229

7.3.4公理集合论230

7.4哥德尔不接近定理232

7.5不接近定理的证明234

7.5.1构建形式系统234

7.5.2哥德尔配数237

7.5.3构造自我指涉238

7.6的程序与对角线证明239

7.7尾声240

附录241

加法交换律的证明241

积与和的专享242

集合的笛卡儿积和不相交并集构成积与和的证明243

参246

参文献296