指数
#
X^A * X^B = X^(A + B)
X^A / X^B = X^(A - B)
(X^A)^B = X^(A * B)
X^N + X^N = 2X^N <> X^(2N)
2^N + 2^N = 2^(N + 1)
对数
#
约定
计算机科学中, log默认为log(2)
X^A = B, log(X)(B) = A
log(A)(B) = log(C)(B)/log(C)(A)
logAB = logA + logB
级数
#
∑(i=0)(N)2^i = 2^(N + 1) - 1
∑(i=0)(N)A^i = (A^(N + 1) - 1) / (A - 1)
如果0 < A < 1, 则 <= 1 / (1 - A)
∑(i=1)(∞)i/2^i = 2
∑(i=1)(N)i = N(N + 1) / 2 ≈ N^2 / 2
∑(i=1)(N)i^2 = N(N + 1)(2N + 1) / 6 ≈ N^3 / 3
∑(i=1)(N)i^k ≈ N^(k + 1) / |k + 1| k <> -1
k = -1时, Hn = ∑(i=1)(N)1 / i ≈ log(e)(N), Hn是调和级数
该近似式误差趋向于 λ ≈ 0.57721566, 称为欧拉常数(Euler's constant)
如果N整除A - B, 则称A与B模N同余, 记为A≡B(mod N)
81≡61≡1(mod 10)
如果A≡B(mod N), 则A + C ≡ B + C(mod N)，则AD≡BD(mod N)
证明方法
#
归纳法
基准情形(base case)
归纳假设(inductive hypothesis), k成立
证明k + 1成立
反证法
无理数
#
圆周率π，黄金分割比ψ，重力加速度g，和自然对数的底e
# e约等于2.718281828
# e表示基础增长率为1时连续增长的实际增长率
## 连续增长是自然界最广泛、增长最快的一种
## ，所以e也表示自然增长速度, 也是增长的极限速度
e=lim(x→∞)(1+1/x)^x
例子
单细胞24小时分裂一次，x天产生2^x个细胞
加条件, 一天中新生细胞产生到一半(12小时)的时候自身可以分裂
一天产生2.25个细胞, 1个原有，1个新生, 0.25个是新生细胞分裂的
改条件，每8小时细胞具有分裂能力
一天可得到2.37个细胞
改条件，新生细胞每个细微时间都有分裂能力，一天最多可以产生的细胞
一天可得到e个细胞
例子2
e或e经过一定变换得到"自然律"
例子3
螺线φkρ=αe。其中，α和k为常数，φ是极角，ρ是极径，e是自然对数的底
pi = 3.
14159 26535 89793 23846 26433
83279 50288 41971 69399 37510
58209 74944 59230 78164 06286
20899 86280 34825 34211 70679
82148 08651 32823 06647 09384
46095 50582 23172 53594 08128
48111 74502 84102 70193 85211
05559 64462 29489 54930 38196
44288 10975 66593 34461 28475
64823 37867 83165 27120 19091
45648 56692 34603 48610 45432
66482 13393 60726 02491 41273
72458 70066 06315 58817 48815
20920 96282 92540 91715 36436
78925 90360 01133 05305 48820
46652 13841 46951 94151 16094
33057 27036 57595 91953 09218
61173 81932 61179 31051 18548
07446 23799 62749 56735 18857
52724 89122 79381 83011 94912
98336 73362 44065 66430 86021
39494 63952 24737 19070 21798
60943 70277 05392 17176 29317
67523
组合数学
#
原理
鸽巢原理、ramsey定理
概率
加法原理、乘法原理
排列组合、多重集排列组合
组合恒等式
容斥原理
多重集r-组合数
mobius反演
集合
集合分划 stirling数
生成函数
组合数
指数型
catalan数列与stirling数列
分拆数
递推关系
群
置换群
burnside引理
共轭类
不动置换类
等价类
polya定理
问题
幻方
拉丁方
涂色
非降路径
正整数分拆
无序分拆
ferrers图
分配
错位排列
棋盘多项式与有禁区的排列
离散数学
#
集合
c(0)(n) + c(1)(n) + ... + c(n)(n) = 2^n
# 幂集
关系r
子关系
逆
自反
对称、反对称
传递
乘积(合成)
自反闭包
等价
部分序
映射
原像、映像
满射、单射
基数(浓度)
逻辑
联结词
∨, ∧, ￢, ←, →, ↔
=, =>
# 等价，蕴涵
原子、公式、解释
范式
析取范式
合取范式
前束范式、skolem范式
谓词
∀, ∃
谓词演算
图
权图
dijkstra算法
树
最优树
kruskal、t*
有向图
euler路、euler图
无向图
hamilton路
平面图
kuratowski判定
同胚
平面图的euler公式
plato体
着色
匹配
二部图
增广路
最大匹配
konig无限性引理
王浩定理
计算机表示
邻接矩阵
关联矩阵
弧表表示
邻接表表示
星形表示
单源最短路径
dijkstra
bellman - ford
最大流问题
增广路定理
ford - fulkerson
最大容量增广路算法
dinic、dinic改进
最短增广路算法
一般的预流推进算法
最高标号预流推进算法
数论
辗转相除
质数
合同
剩余类
一次同余式
秦九韶定理
euler函数
一元高次同余式
二次剩余
legendre符号
euler判别法
二次剩余互反律
应用
加密
群
性质
封闭性 # 运算结果还在群中
结合律 # (a·b)·c = a·(b·c)
单位元(幺元) # e·a = a·e = a
逆元 # a·b = b·a = e
代数系统
半群
封闭性
结合律
幺半群
封闭性
结合律
幺元
置换群
轮换表
奇偶性
子群
循环群
右陪集
正规子群
lagrange定理
同态映射
同构映射
核
环
整数环、矩阵环、多项式环
消去环、交换环
整区
域
子环
理想
平凡理想
单纯环
极大理想
合同关系
环同态、同构
应用
计数问题
轨道
代表元素
burnside引理
纠错码
域
素域
多项式
根
有理域多项式
eisenstein定则
分圆多项式
有限域
格
x, ⊕
对偶原理
对偶表达式
同态、同构
几个分类
有界格
有余格
分配格
模格
布尔代数
有余分配格
stone定理
化简
quine
karnaugh图
语言
语法
# 任何3型语法都是2型语法...都是1型语法...都是0型语法
g = (v, t, s, p)
# v 字母表, t是v的一个终止符子集, s是v的一个元素初始符，p是产生式集合
0型语法
# 没有任何限制
1型语法
# 产生式如 w1 -> w2, w2长度大于等于w1, 或者 w1 -> λ
# 可以写 lw1r -> lw2r , 所以上下文有关
2型语法
# w1 -> w2, w1是单个非终止符
3型语法
# w1 -> w2, w1 = a 并且w2 = ab 或者w2 = a, 其中a, b为非终止符, a是终止符，也可以是λ
# 正则语法
演绎树
有输出的fsm
mealy机
moore
没有输出的fsm
kleeme闭包
终止状态
非确定fsm
转换确定fsm
语言识别
可识别集合(stephen kleene)
正则表达式
kleene定理
其它fsm
pushdown自动机
识别到上下文无关语法
线性有界自动机
识别到上下文有关语法
turing机
识别所有语法结构产生的语言，可实现任何算法
随机数学
#
概率
古典概型
几何概型
条件概率
全概率公式
bayes公式
bernoulli概型
随机变量
离散
连续
分布函数
概率密度
分布
(0 - 1)分布
二项分布
poisson分布
几何分布
均匀分布
指数分布
正态分布
二维
联合概率密度
边缘概率分布
边缘概率密度
二维正态分布
条件分布
卷积公式
n维
数字特征
期望、方差
cauchy - schwarz不等式
标准化随机变量
协方差
矩
k阶原点矩
k阶中心矩
k + l 阶混合原点矩
k + l 阶混合中心矩
协方差矩阵
n维正态分布
大数
chebyshev不等式
chebyshev定理
bernoulli定理
中心极限定理(levy - lindberg定理)
de moivre - laplace 极限定理
liapunov 定理
样本
样本分布函数
伽玛函数
χ2分布
t 分布
f 分布
参数估计
矩估计
最大似然估计
评选标准
无偏性
有效性
一致性
区间估计
置信下限、置信上限
正态总体参数的区间估计
两个正态区间估计
u估计
t估计
f估计
假设检验
显性检验
参数检验
正态总体参数
u检验
t检验
χ2检验
f检验
...
分布拟合检验
回归分析
一元线性回归
最小二乘
可线性化的回归方程
双曲线
幂函数
指数函数
倒指数
对数
s型曲线 1 / (a + b * e ^ -x)
多元线性回归模型
方差分析
单因素
双因素
交互作用双因素
正交试验