读书笔记 - 程序员的数学

2013-01-06 22:22

为了写好程序,要努力学习数学,从基础学起~

第1章 0的故事

十进制逢十进一,二进制逢二进一

将十进制转化为二进制
12/2 = 6..0
6/2 = 3..0
3.2 = 1..1
1/2 = 0..1

所以十进制的12等于二进制的1100
235/2 = 117..1
117/2 = 58..1
58/2 = 29..0
29/2 = 14..1
14/2 = 7..0
7/2 = 3..1
3/2 = 1..1
1/2 = 0..1

计算机采用二进制的原因是,二进制的加法表更简单,容易用计算机实现。

按位计数法如二进制,十进制,八进制等,不按位计数法如罗马数字等。

10的1次方是10的2次方的十分之一,等于10;
10的0次方是10的1次方的十分之一,等于1;
10的-1次方是10的0次方的十分之一,等于1/10。

0的作用:占位符,统一标准,简化规则

日常生活中用0表示没有可以起到简化规则的作用。

第2章 逻辑

逻辑是消除歧义的工具,计算机正确的执行逻辑判断来解决人类的问题。

能够判断对错的陈述句叫做命题,命题正确时为真命题,命题错误时为假命题。命题要么为真,要么为假,同时满足true和false的不能称之为命题。既不为true也不为false的也不能称之为命题。

处理逻辑问题时,需要保证不能有遗漏,不能有重复,小心边界值,兼顾完整性和排他性。

非 ^A (!)
A为true时,A为false
A为false时,A为true
双重否定等于肯定。

与 A ^ B (&& and)
A和B同时为true时,A ^ B才为true

或 A V B (|| or)
A和B有一个为true,A V B就是true

异或 A (+) B
A和B不相等时,A (+) B才为true。

相等 A = B (可以理解为同或)
A和B相等时,A = B为true。

蕴含 A => B
A为true时,仅当B为true时,A => B才为true。
A为false时,A => B恒为true。

逆否命题
若A => B 等于 (^B) => (^A)

德摩根定律
(^A) V (^B) => ^(A V B)
(^A) ^ (^B) => ^(A ^ B)

可以用文氏图来描述命题的真假,用卡诺图来简化复杂逻辑表达式。

第3章 余数

余数就是做除法运算时剩下的数。

今天是星期天,那么100天后是星期几?
今天是星期天,7天后还是星期天,14天后还是星期天,...,98天后还是星期天,所以100天后是星期二。

1234567的987654321次方的个位数是几?
7的0次方的个位 = 1
7的1次方的个位= 7
7的2次方的个位 = 9
7的3次方的个位 = 3
7的4次方的个位 = 1
7的5次方的个位 = 7
。。。

个位在1 7 9 3 之间循环
987654321 % 4 = 1
所以答案为7

运用余数,大数字的问题就可以转化为小数字的问题。

一笔画问题
可以一笔画成 => 所有的顶点都是偶点,或者有2个奇点。

第4章 数学归纳法

n * 2为偶数
n * 2 -1 为奇数
0到n的整数之和为(n*(n+1))/2

数学归纳法步骤
步骤1: 证明p(0)成立
步骤2:证明无论k为0以上的哪个整数,若p(k)成立,则p(k+1)成立

第5章 排列组合

计数需要注意重复和遗漏。

加法法则只在集合中没有重复元素的条件下成立。
乘法法则,将集合A中的所有元素与集合B的所有元素组合起来,组合的总数就是两个集合的元素数相乘。
置换,将n个事物按顺序进行排列称之为置换。

排列 permutation
P(n,k) = n(n-1)(n-2)(n-k+1)
或者
P(n,k) = (n!)/(n-k)!

组合 combination
C(n,k) = P(n,k)/P(k,k)
C(n,k) = (n!)/((n-k)! * k!)
C(n,k) = C(k-1, n-1) + C(k, n-1)

置换、排列、组合的关系
置换表示3张牌的交替排列方法
组合表示3张牌的取法
排列表示取出3张牌,进行交替排列
3张的置换 * 从5张中取3张的组合 = 从5张中取3张的排列

第6章 递归

GNU是什么意思?
'GNU is Not UNIX的缩写'。

汉诺塔问题
将n个圆盘,从x柱,经由z柱,转移到y柱的步骤:
当n=0时,什么也不做
当n>0时,
首先,将n-1个圆盘从x柱,经由y柱,转移到z柱(解出n-1层汉诺塔)
然后,将1个圆盘从x柱转移到y柱
最后,将n-1个圆盘从z柱,经由x柱,转移到y柱
H(n) = 2的n次方 - 1

递归和归纳都是将复杂问题简单化,递归(recursive)是从一般性前提推出个别性结论,而归纳(inductive)是从个别性前提推出一般性结论。

第7章 指数爆炸

二分法查找,n次就可以从2的n-1次方减1中找到目标数据
10次可以从2047个目标中查找到目标数据
20次可以从2097151个目标中查找到到目标是数据
30次可以从2147483647个目标中查找到目标数据

求数字10000中0的个数4,就称作求10000的对数。

处理涉及指数爆炸问题的4中方法:
极力求解,转换成简单问题求解,近似求解,概率求解

第8章 不可解问题

反证法:
1. 首先,假设命题的否定形式成立
2. 根据假设进行论证,推导出矛盾的结果。
即 '先假设命题的否定形式成立,然后再进行推理,引出矛盾'的论证方法。

集合的元素是有限的,或者集合中的所有元素都与正整数一一对应时,这个集合就被定义为可数(countable)。
可数的意思是'元素可按一定规律既无遗漏,也无重复地数出来'。

有限集合是可数的。
0以上的所有偶数的集合是可数的。
所有整数的集合是可数的。
所有有理数的集合是可数的。

所有整数数列的集合是不可数的。
所有实数的集合是不可数的。
所有函数的集合也是不可数的。

不可解问题:
原则上不能用程序来解决的问题。

停机问题:
判断'某程序在给定的数据下,是否会在有限时间内结束运行'的问题。