基础
函数的增长（估算复杂度）
大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
其他算法