‘壹’ 程序员的数学-读书笔记
计数法分为 按位计数法 和 罗马计数法
按位计数法常用的有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个概念。以下是几个小例子。
最后提到的 重复组合 里的思考问题比较有趣。
解答的思想是：
这是一种典型的将复杂问题简单化，并规律化的解答方法。
最后还是要强调下：
要 认清计数对象的本质
递归与归纳的区别
归纳（inctive） 是从个别性前提推出一般性结论。
本质上都是 将复杂问题简化 ，但方向不同。
个人理解是
递归是发现第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 的开课。
前方的路注定不好走，但是要慢慢尝试和坚持。