计算理论——公式汇总

作者: 闭门造折 | 来源:发表于2019-11-25 21:00 被阅读0次

真的蛋疼，明明是很简单的公式和理论，课件非要全英文，给阅读增添了很多的难度不说，有的地方还由于英文水平欠佳导致理解有误。
X-Y表示第X个课件第Y页内容

1-10 欧几里得算法

就是辗转相除法。
GCD(A, B) = GCD(B, A%B)

1-13 香农熵

假设有n个可选项1,2,...,N，选中概率为p = (p₁， p₂,...,p_n)
则香农熵为 $-\sum_{i=1}^{n}p_{i}\cdot log_{2} p_{i}$

1-24 递归

给个递归的例子：斐波那契数列
$\left\{\begin{matrix} f_{0} = 0,f_{1}=1 \\ f_{n}=f_{n-1} + f_{n-2} \end{matrix}\right.$

1-30 特征函数

对任意集合 $X\subset N$ 有特征函数
$\chi\left ( x \right )=\left\{\begin{matrix} 1 & if\: \: x \in X\\ 0 & otherwise \end{matrix}\right.$

1-32 基础函数

f(x) = c；f(x) = x+1；Ui(x1,x2,...,xn)=xi
假设f和g都是基础函数，则f(g)和g(f)仍为基础函数

1-92 作业1

$f(n)满足f\left ( n \right )=a\cdot f\left ( \frac{n}{b} \right )+cn^{d}$ 试证明 $f\left ( n \right )=\left\{\begin{matrix} O\left ( n^{d} \right ) & \left ( a< b^{d} \right )\\ O\left ( n^{d}logn \right ) & \left ( a= b^{d} \right )\\ O\left ( n^{log_{b}a} \right ) & \left ( a> b^{d} \right ) \end{matrix}\right.$

证明：
f(0)=a·f(0)+0 => f(0) = 0
$\\f(n)=a\cdot f\left ( \frac{n}{b} \right )+cn^{d} \\=a\cdot \left ( a\cdot f\left ( \frac{n}{b^{2}}\right ) + \frac{cn^{d}}{b^{d}} \right )+cn^{d} \\=a^{2}\cdot f\left ( \frac{n}{b^{2}} \right )+\left ( 1+\frac{a}{b^{d}} \right )\cdot cn^{d} \\=a^{log_{b}n}f(0)+\left ( 1+\frac{a}{b^{d}}+...+\frac{a^{log_{b}n}}{n} \right )\cdot cn^{d} \\=\left ( 1+q+...+q^{t} \right )\cdot cn^{d}$
其中 $t=log_{b}n，q=\frac{a}{b^{d}}$
则 $a<b^{d}$ 时， $1+q+...+q^t→C$
$a=b^d$ 时， $1+q+...+q^t=t=log_bn$
$a>b^d$ 时， $1+q+...+q^t=\frac{b^{d}-a\cdot \left ( \frac{a}{b^{d}} \right )^{log_{b}n}}{b^{d}-a} =\frac{c1-a\cdot \frac{a^{log_{b}n}}{n^{d}}}{c2}$

1-93 欧几里得距离

N维空间直线距离，题目用的似乎是分治，但是具体不是特别懂

2-4 divisible

对于d，可be divisible by d的为d的倍数。

2-13 ≡符号

$a\equiv b\left ( mod\: \: m \right )\Leftrightarrow a\:mod\:m\:=\:b\:mod\:m$

2-29 复杂性界限

$f\left ( n \right )=O\left ( g\left ( n \right ) \right )$ ，当存在c使得任意n有 $f(n)≤c·g(n)$
$f\left ( n \right )=o\left ( g\left ( n \right ) \right )$ ，当n趋向∞时有 $\frac{f\left ( n \right )}{g\left ( n \right )}=0$
$f\left ( n \right )=\Omega \left ( g\left ( n \right ) \right )$ ，当存在c使得任意n有 $f(n)≥c·g(n)$
$f\left ( n \right )=\Theta \left ( g\left ( n \right ) \right )$ ，同时又g为f的上界及下界
$f\left ( n \right )=\omega \left ( g\left ( n \right ) \right )$ ，当n趋向∞时有 $\frac{g\left ( n \right )}{f\left ( n \right )}=0$
$f\left ( n \right )=\widetilde{O} \left ( g\left ( n \right ) \right )$ ，当 $f(n)=O(g(n)·poly(log_2g(n)))$

2-58 ≤x的质数个数

x→∞时，≤x的质数个数趋向于 $\frac{x}{lnx}$

2-77 邻居

使用 $N(v)$ 或 $\Gamma (v)$ 来表示v的邻居集

2-79 容积

容积 $vol(S)={\sum_{u\in S}^{}}d(u)$
即点集S中所有点的度数之和

2-107 最大流

见这篇博客《网络流——最大流问题例题》

2-122 作业题3

100!的末尾0的数量 = 1~100中5的倍数数量+25的倍数数量

2-122 作业题4

证明 $log_23$ 为无理数
反证法证明即可。
假设 $log_23$ 为有理数，则存在p,q有
$log_23=\frac{p}{q}$
进而 $2^{\frac{p}{q}}=3$
$2^p=3^q$ ，当q不为0时，等式右侧为奇数，当p不为0时，等式左侧为偶数，显然不成立

2-122 作业题5

证明若 $2^n-1$ 为质数，则n为质数
同样反证法证明
假设 $2^n-1$ 为质数，但n为合数
则存在p，q有 $n=p·q$
则 $2^n-1=2^{p·q}-1可拆分$
即假设不成立

2-122 作业题6

对于6个点简单图，必存在全连接或全不连接的3个点。
任选1个点，对于剩下5个点，至少有3个不相连，或至少有3个相连。假设是有3个相连
对于这3个点，若之间存在连线，则与第一个点可形成全连接三角形。若均不存在连线，则构成全不连接三角形。

4-12 条件概率

$Pr[E|F]=\frac{Pr[E\cap F]}{Pr[F]}$

4-13 独立变量

$Pr[E \cap F]=Pr[E]·Pr[F]$

4-17 二项分布定理

p的可能性为1，则n次中发生k次概率为 $\binom{n}{k}p^k(1-p)^{n-k}$

4-21 贝叶斯定理

$Pr[F|E]=\frac{Pr[E|F]·Pr[F]}{Pr[E|F]·Pr[F]+Pr[E|\overline F]·Pr[\overline F]}$
$Pr[F_j|E]=\frac{Pr[E|F_j]·Pr[F_j]}{\sum_{i=1}^{n} Pr[E|F_i]·Pr[F_i]}$