基础
函数的增长(估算复杂度)
大O记号:上限
- logn, n, nlogn n2, 2n, n!
- f1(x)是O(g1(x)),f2(x)是O(g2(x)),(f1+f2)(x)为O(max(g1(x),g2(x))).
大Ω记号:下限;大Θ记号:同阶
-- 多项式与最高阶同
整数和除法
简介
-- 从整除性建立的一个重要概念是素数,素数是大于1且能被1和它自己整除的整数。数论中一个重要的定理:每个正整数能都唯一地被分解为素数的乘积。把整数分解为素数因子在密码学中是很重要的。
-- 用一个整数除另一个整数得到商和余数。贯穿计算机科学的同于算法就是这些余数。本节讨论同余算法的三个应用:生成伪随机数、为文件分配内存地址和为信息加密/解密。
除法
整除:a | b 表示a整除b,可以用写为 Ec(ac=b),论域为整个整数集合(E为倒E,存在量词)
素数:素数是构造正整数的积木。
-- 证明素数的算法:如果n是合数,则n必有小于或等于根号n的一个素因子。
- 如果n是合数,则n必有小于或等于根n的一个素数因子。
- 梅森素数:2^n-1 及卢卡斯-莱默尔检验方法
- 素数定理:当X趋于无限,不超过x的素数个数约等于x/lnx。
--一个随机选择的正整数是素数的概率为1/lnx,只选奇书可以是找素数的速度加倍
证明101是素数;
求7007的素因子分解:从最小素数开始除,若整除,则余数继续用被除数素数除,否则有下一个素数。
整除算法:商与余数唯一
最大公约数与最小公倍数
-
最大公约数:利用两个整数的素因子分解。
a = p1^a1 * p2^a2 …… pn^an, b = p1^b1 * p2^b2 …… pn^bn
gcd(a, b) = p1^min(a1, b1) * p2^min(a2, b2) …… pn^min(an, bn)
-
最小公倍数
lcm(a, b) = p1^max(a1, b1) * p2^max(a2, b2) …… pn^max(an, bn)
同余算术
令m为正整数,整数a和b模m同余的充要条件是存在整数k 使得 a = b + km
同余应用
- 散列函数:h(k) = k mod m ,其中k为记录的关键字,m为内存的容量,h(k)为其分配的内存地址,用于为计算机文件分配内存地址。涉及到冲突处理。
- 伪随机数:在一定范围内随机选择的数。最常用的产生 伪随机数的过程为线性同余法。
xn+1 = a(xn + c) mod m
若其中m = 0,则称为纯乘式发生器。例如以231 - 1为模,以75 = 16807为乘数的纯乘式发生器就广为采用。
- 密码学
凯撒加密法:f(p) = (p + 3) mod 26
f-1(p) = (p - 3) mod 26
整数和算法
-- 定理:若a和b为正整数,则存在整数s和t,使得gcd(a, b) = sa + tb
数学推理、归纳与递归
证明策略
-- 一般情况下,如果命题是蕴含式,就应该首先尝试直接证明;如果这样不行,就尝试间接证明。如果这些方法都不行,就尝试归谬证明。
-- 前推、后推;分情况证明;修改现有证明;
序列与求和
数学归纳法
强归纳法
-- p(1)^p(2)……p(n-1) --> p(n)
良序性
-- 每个非空的非负数集都有最小元
递归定义与结构归纳法
-- 递归算法
-- 欧几里德最大公约数递归算法
-- 归并排序
程序的正确性
计数
计数原则
加法原则
乘法原则
排列和组合
排列
P(n, k) = n!/(n-k)!
组合
C(n, k) = n!/{(n-k)!*k!}
其他
C(n+1, k) = C(n, k) + C(n-1, k)
二项式定理
(x + y)^n = C(n, 0)x^n + C(n,1)x^(n-1)y +……+ C(n,n)y^n
2^n, 0
有重复的排列和组合
有重复的排列
有重复的组合
- n个元素的集合中允许重复的r组合是C(n+r-1, r)=C(n+r-1, n-1)个。
例如:
方程 x1 + x2 + x3 = 11
有多少个解?其中x1,x2,x3是非负数。
C(11+3-1, 11) = C(13, 11)= 78
生成排列和组合
生成排列:P138页算法1
生成组合:P138页算法2、算法3
高级计数
递推关系
生成的函数
1/(1-ax)
容斥原理
|A并B| = |A| + |B| - |A交B|
|A并B并C| = |A| + |B| + |C| - |A交B | - |A交C | - |B交C | + |A交B交C|
N(P1' P2' ... Pn') = N - |A1并A2...An|
算法例题:
1、P147 汉诺塔
2、P161 并归排序、整数的快速乘法
3、P172 使用生成函数求解递推问题
4、P181 埃拉托色筛
5、P183 错位排序
关系
关系种类与表示
-
自反
-
对称/反对称
-
传递
-
邻接矩阵 0-1构成
R R^n
关系的闭包
等价
偏序
-
定义
自反 + 反对称 + 传递 = 偏序
-
偏序集:即定义在某个集合上的关系
-
全序集:偏序集都可比,即集合上所有元素都满足关系时,称为全序集。
-
良序集:对于全序集,若其每个子集都有最小元素,则称为良序集。
-
哈塞图:对于偏序集,去除本身的一定存在的关系的最小关系的图,称为哈塞图。
即去除自反、传递关系
-
P228:拓扑排序
图
基本定义
-
度:deg(v) 定点v的度指与v连接的边的个数。
-
握手定理:2e = ∑deg(v).每个定点度数之和,为边的2倍。
-
起点/终点,入度与出度
∑deg-(v) = ∑deg+(v) = e。入度 = 出度 = 边的个数。
-
完全图 Kn,每两个顶点之间都有边。
-
圈图 Cn,完全图的外围。
-
轮图,在圈图中心加一顶点,并与其他顶点相连接。
-
偶图,分两类,类内部无边,之间有边
图的表示
连通性
通路/回路
- 欧拉通路:边不重复,dev(v) 为偶数
- 哈密顿通路:顶点不重复,dev(v) + dev(u) >= n
- P274:格雷码
最短路径
- P280,迪克斯特拉算法:将顶点分成2个集合,每次从未加的集合中,选择最短加入集合,并更新未加集合的权值。
- P283,弗洛伊德算法
可平面图
-
定义:连线不相接
-
面与顶点、边的定理: r= e - v + 2 面=边-顶点+2,证明方法:数学归纳法
-
推论:若G是带e条边,v个顶点的联通和平面简图,其中v>=3,则e<=3v-6。
-
理解:边数不能太多,太多总有连接。
-
同胚:可以从同一张图经过初等细分(在边中加一个点)来获得,则称他们为同胚。
-
定理:一个图是非可平面的,当且仅当她们包含一个同胚与K3,3或者K5的子图。
图着色
- 平面图的色数不超过4个。
- 回溯算法进行图着色。
- P294例5、例6.
树
树的应用:
- 二叉搜索树:P315 算法1 【左孩子小,右孩子大】
- 哈夫曼编码:前缀码,P318哈夫曼编码算法。叶子字节
- 决策树,每次结果都用树来表示出来。
- 博弈树,最大最小策略。决策树后,两个人都朝自己有利的方向进行。 P322例8
树的遍历
-
前序
父 -> 左子 -> 右子
P325 例1
-
中序
左子 -> 父 -> 右子
从树外面包围它。
-
后序
左子 -> 右子 -> 父
P330 算法1-3
搜索
-
深度优先搜索
P338 :算法1
-
广度优先搜索
P339 :算法2
-
回溯
图着色、N皇后问题。
最小生成树:带权最小生成树
-
P345:普林算法,例1
-
P346:布鲁斯卡尔例3
其他算法