程序员的数学-读书笔记

~

计数法分为 按位计数法 和 罗马计数法
按位计数法常用的有2进制、8进制、10进制、16进制等几种。

理论上多少进制在数学上都可以存在，玛雅人用20进制，巴比伦人用10进制和60进制的混合计数法。玛雅人20进制可能是和手脚趾加起来的数量有关。巴比伦人采用60进制也可能是因为记录数字的黏土版比较难记录文字记号，为了在大数的书写上少占位便采用了60进制。
从这一点来看，环境对文明和文化的形成真的是有决定性的影响。假如巴比伦人掌握了造纸术或者在竹子上书写文字的话，60进制这种违反人类天性的计数方法一定不会出现。话说，汉莫拉比法典就是写在黑色的玄武岩上的。能够记录的文字也就屈指可数吧。

作者提到了其实人也是可以采用2进制计数法的，可是同样大小的数字用2进制书写起来位数太多，一来书写不方便，二来计算时易发生马虎出现错误。而10进制的数天生就是顺应人类人性的，即使是幼儿也可以通过数手指头的方式来计数。
相反对于计算机的物理构造来讲，0代表开关断开，1代表开关连接，这种二极管的物理限制正好决定了计算机较为适用2进制。不过如果你想做出一个10进制的计算机也不是没有可能的。

这一章比较有趣的是罗马计数法，我以前也没有接触过超过20的罗马数字，也不知道罗马数字各个数位上的数字相加之和为数字本身所代表的量。例如：

反观阿拉伯数字

由此引发作者在两个程序领域上的思考：

关键词：真值表、文氏图、逻辑表达式、卡诺图、三值逻辑、完整性、排他性

- 能够判断对错的陈述句叫做命题（proposition）

逻辑非 --不是A

逆命题

逆否命题

德摩根定律

卡诺图 （二灯游戏、三灯游戏引出）

未定义逻辑（undefined）

三值逻辑的德摩根定律

本章探讨的是通过余数来解决存在规律、周期性的问题。通过规律和周期性的重复，将大问题简化成容易解决的小问题。

首先作者通过解决星期几问题，引入了余数的思考概念。

上面的问题在 大问题通过余数规律简化为小问题 这个方法上表现的还不明显，于是引入了第三个问题：1234567^7654321的个位数是多少。

以上三个问题是小学奥赛便涉及到的问题，然而其思想在解决真实面对的复杂问题或具象的实际问题时却很好用。

将一个数字除以2，他的余数应该为0或者1二者之一。我们也可以叫 奇偶问题 。
书中有几个案例：

这样分析过来就很好解决七桥问题，确定每个点所连接的桥的点数，与上述结论做对比。
A点为3，B点为，C点为3，D点为3.
由此可以得出七桥问题不可能实现。这个问题的解决也是通过奇偶性来解决的。

作者举了高斯求和的故事来讲如何用数学归纳法来解决无穷数列的求和问题。
两个小例子便是从0开始到N的和，以及1开始的奇数和。

数学归纳法 是证明[ 有关整数的断言对于0以上的所有整数（0,1,2...）是否成立 ]所用的方法。
证明方法归结为两歩：

根据上述方法，假若某个假设成立，那么P(0)成立，因为P(0)成立，所以P(0+1)即P(1)也成立。反复如此，对于无穷数列遵守这个规律的证明，就像多米诺骨牌，推到第一个，后面的都会按照第一个的规则倒下去。

然而要避免整个证明出错，就要重视第二个步骤，也就是归纳。归纳在证明时一定要考虑 是否在所有定义条件下均成立 ，尤其要注意的是在P(0)的条件下是否实现。

课后对话很有意思：

计数是人类每天生活都要运用的方法。
计数的关键就在于 注意“遗漏”和“重复”
例如：

综上，在计数时要发现事物的规则。
要 认清计数对象的本质
要 认清计数对象的本质
要 认清计数对象的本质
重要的事情说三遍。

将计数对象进行 归纳总结 ，使其作为普通规则来掌握。这样一般不容易出错。

接下来，作者在 加法法则 里写到：

乘法法则 的概念比较有意思。

接下来，本章提到了置换、排列、组合3个概念。以下是几个小例子。

最后提到的 重复组合 里的思考问题比较有趣。

解答的思想是：

这是一种典型的将复杂问题简单化，并规律化的解答方法。

最后还是要强调下：
要 认清计数对象的本质

递归与归纳的区别

归纳（inductive） 是从个别性前提推出一般性结论。

本质上都是 将复杂问题简化 ，但方向不同。
个人理解是

递归是发现第n项和前一两项之间的关系，实证确定后，往回不断递推的一种个别性结论。
即这个结论不是在n为任何自然数时都成立的。需要注意n为0和1的两项。

通过递归解决问题的线路是： 找到递归结构——建立递推公式——找到解析式（只带n的式子） ，如果不能以解析式的方式描述递归结构，也可以用递推公式的方法描述。如下图所示的汉诺塔的递推公式：（它也可以描述成解析式的方式）

归纳所谓的个别性前提是指

斐波那契数列就是运用了递归的思想。通过研究和思考复杂问题，抓住事务本质，得到f(n)=f(n-1)+f(n-2)

所以当我们想要用递归的方法解决问题时，注意思考第n元素与前后元素的关系。由一个点推开，成一条贯穿始终的线。

利用帕斯卡三角形来研究Cnk=Cn-1(k-1) + Cn-1k的思考方式另辟蹊径。将两个加数假设成组合问题里含一个元素和不含那个元素的两个情况。从而证明了式子。利用的便是组合的数学分析法。（这句话组合的意思不是数学意义上的）。

所以以上将复杂问题简化的方法是递归解法之一，是为了在复杂问题中找到隐含的递归结构。其思路是：

通过思考一张1mm的纸，折多少次能够有地月距离那么厚，作者引出指数的概念。

这一章的内容比较简单，对于 指数爆炸 大家应该都不陌生。而 对数 估计也很熟悉。之前接触到的汉诺塔问题的解析式和斐波那契数列都属于指数的范畴。

然而在解决 测试所有设定选项的程序时，检查次数也是一个指数问题 。所以我们应该如何轻松的解决这类问题呢？

利用二分法查找

利用二分法，先询问最中间的人，如果在左边，就继续在左边的范围内重复此项方法，直到找到罪犯。这便被称为 2分法 。他和汉诺塔的解析式如出一辙，可以利用指数原理经过很少的步骤便可找到目标。

二分法本身也是 递归结构 ，经过n次询问，可以在2^n-1人中确定目标。每判断一次就可以查找近一半的对象。
二分法需要注意的是，所有元素一定要 按顺序排列 ，这点至关重要。

指数思想也被用于加密的实现中。因为每多加密一位，暴力破解就需要指数次的运算能力的提升。原则上有限时间里根本不可能破解。指数以其数字的巨大增长能力在加密领域有基本性的作用。

对于指数问题的解决方法，主要有4种，但均不太容易应付规模大的数字。

作为指数函数的逆函数，文章涉及了对数。同时也简单介绍了古代科学家用过的计算尺。

无穷可以分为 可数无穷 和 不可数无穷 。
所谓 可数无穷 是指 可以按照一定的规律或者表达方式来表达 。
即集合中所有元素都与正整数一一对应。如果每一个元素都可以与1.2.3....等数字对应，也就是说可以按规律表达出来就是可数无穷。
例如：

所以有不可数的集合吗？
此时运用到了 对角论证法 和 反证法（也叫归谬法）
假设我们要证明 所有整数数列的集合是不可数的 ，那么反证就是 假设所有整数数列的集合是可数的 ，此处是运用的反证法。
现在我们按下图的方式来列出所有整数数列，编号为k的整数列在表的k行。

如果按照图中第k行的第k个元素ak单独组出一组数列{a1,a2,a3......}的话，他也是应该包含在所有整数数列里的，然而并没有，他是游离在所有整数数列之外的。此处得出矛盾，说明命题错误，命题 所有整数数列的集合是不可数的 为真。此方法被称为 对角论证法
除此之外
-所有实数的集合是不可数的
-所有函数的集合也是不可数的

随后书中讨论到了不可解的问题
对于不可解的问题的定义是

事实上，不能写成程序的函数是存在的。
有些函数不能用文字表达，而且要写成程序的函数必须 严谨定义确切和文字表达 两个概念。

停机问题
不可解问题的一例。定义是

有限时间并不指时间长短，而是指无论耗时多长，只要能有终止的一刻就好。
事实上，程序本身并不能判断某一程序是否可以在有限时间内结束运行
所以停机问题也是 不可解问题 之一。

这一章是对之前8章的回顾和总结。

前几章作者分别对 0的意义、逻辑、余数、数学归纳、排列组合、递归、指数爆炸、不可解问题 进行了简单的介绍和探讨。其实所有的章节最后都是在引领读者产生如何解决问题的思考。

1.认清模式，进行抽象化

2.由不擅长催生出的智慧

3.幻想法则

本书比较适合作为第一本接触算法的书籍。目前开始在上 Khan的Algorithms ，9月份跟上 coursera的Algorithms Part I 的开课。

前方的路注定不好走，但是要慢慢尝试和坚持。

---

奈曼旗13271679543： 程序员的数学怎么样 - ？
潜霞达菲： 首先,这是本好书.本书有相当不错的易读性和趣味性,可以作为最入门级别的启蒙教材.我认为数学和编程是很重要的两个东西,而这本书可以当成这两门学问的基础读物......

奈曼旗13271679543： 软件开发的程序员需要掌握多的数学知识? - ？
潜霞达菲： 需要数学,但是这个数学不是说你现在学的数学这点知识,而是你是逻辑思维,如果你仅仅是想成为一个程序员,只是一个写代码的人,那你数学不需要太好,但是,如果你真想好好从事计算机这方面,尤其是想软件开发,你必须得学好数学,...

奈曼旗13271679543： 《程序员的数学》这本书程序员获益多吗 - ？
潜霞达菲： 还不错,不能指望通过它直接得到在工作中立刻用上的东西,但很多思想还是值得学习的,就好像在计算机课程中的数据结构,讲解了很多基本类型的数据结构,在编程中不见得每一个项目都用得上每一种数据结构,但是有了这个训练,知道什么时候该用什么了.

奈曼旗13271679543： 作为一名合格的程序员,请问需要掌握哪些数学知识,学到什么样的水平 - ？
潜霞达菲： 程序员的知识是多方面的, 数学方面至少高等数学大专以上文化程度,概率统计,数字逻辑运算方面的知识,主要就是做哪一方面的程序设计,有些学过的可能长期也不用,搞科学研究的、游戏、智能软件开发、安全方面的要求就高一些,没有一定数学基础有些算法书就读不懂,搞社会一般应用的要求相对较低一些,这些只是常识,程序员关键一点把一门课及相关知识精通,可以把用户提出的问题很快的自己能够理解,转换成计算机处理方式,成为软件或网站,而且和用户的需求基本一致.当然有些人的数学水平并不高,设计出的软件人人爱用,水平很高,程序员的知识包括数学方面的知识也在不断充实更新中.

奈曼旗13271679543： 推荐给程序员看的数学方面的书籍、资料 - ？
潜霞达菲： 离散数学 高等教育出版社 屈婉玲,耿素云,张立昂 著 数据结构 清华大学出版社 严蔚敏 著 计算机算法设计与分析 电子工业出版社 王晓东 著 这些都是对程序员很有用的课程,参考书.其他还有 王晓东的编程珠玑 组合数学 计算理论 等等

奈曼旗13271679543： 想当一名出色的程序员数学必须要很好吗 - ？
潜霞达菲： 做程序员需要数学知识的,从事开创性的工作的都是数学很好的.比如谷歌的搜索系统,那就是从一个数学模式中推导出来的.

奈曼旗13271679543： 程序员的数学 什么是数学 从一到无穷大 - ？
潜霞达菲： 程序员不是考出来的,是要有真才实学,考那东西没有用的,等你面试的时候人家什么证书都不要,就问你几个问题,看看你的编程基础怎么样,至于数学,我个人觉得只是在初中级阶段用处不大,如果想有更高更好的发展,数学一定要好,总之数学好点没坏处,至于考程序员,真的没什么用处,还不如把那些时间用来学习别的.....思维的方法要求比较高.另外对数学的基本常识理论要懂,比如计算2010年是否闰年,则要对闰年的判断方法用数学建模来表示.比如水仙数等,这些基本的数学方法.另外写个程序得出某个事件处理的结果,首先就要求你了解这个事件的整个过程(这样才可以知道原理并建立数学模型),其次是这个事件的处理方法(就是如何得出该结论),最后就是反复调试直到没有漏洞.

奈曼旗13271679543： 程序员的数学功底要达到什么程度,算是一名好的程序员 - ？
潜霞达菲： 这个不好定义,数学好不一定逻辑好,否则相反,比如你去写一个逻辑面向对象的程序那可能非常简单,如果让你去写一个流水灯那就有难度了!难在这个逻辑上面了,电梯程序大家肯定都做过,不是很简单但是关键要素很重要要有“变量锁!”否则就成了一个大bug程序了

奈曼旗13271679543： 一本数学科普书的读书笔记300字左右 - ？
潜霞达菲： 书名:《离散数学(上)》清华大学计算机系的教材 离散数学(discrete mathematics)是计算机科学基础理论的核心课程.它包括数理逻辑、集合论、代数结构、图论、形式语言、自动机和计算集合等.第一章 命题逻辑的基本概念 第一节 命...