线性规划

TODO

群论

群

• 封闭
• 结合律
• 单位元
• 逆元

阿贝尔群(abelian or commutative)

$a\circ b=b\circ a$

子群

• 封闭
• 单位元
• 逆元

cyclic group(循环群)

• 存在一些$a\in G$使得$G=\langle a\rangle$
• order of $a$:满足$a^n=e$的最小正整数$n$
• 循环群是阿贝尔群
• 循环群的子群是循环群
• $C_{\infty}\cong\mathbb{Z}(\mathbb{Z},+),C_n\cong\mathbb{Z}_n$
• 无限循环群$C_{\infty}$
  • $|g^k|=\infty$
  • 生成元:$g,g^{-1}$
  • 子群:$\langle g^k\rangle,k\in\mathbb{N}$
• 有限循环群$C_n$
  • 生成元:$g^k,\gcd(k,n)=1$

symmetric group(对称群)

$|S_n|=n!$

permutation group

• $S_n$的子群是permutation group

cycle

• cycle of length $k$:$\sigma(a_k)=a_1$
• $\sigma,\tau$是$S_X$中不相交的cycles,那么$\sigma\tau=\tau\sigma$
• transpositions:长度为2的cycle
  • $(a_1,a_2,…,a_n)=(a_1a_n)(a_1a_{n-1})…(a_1a_3)(a_1a_2)$

alternating group(交代群)

• even permutations

dihedral group(二面体群)

• $D_n$是$S_n$的一个阶为$2n$的子群

cosets(陪集)

• $g\in G$
  • 左陪集:$gH=\{gh:h\in H\}$
  • 右陪集:$Hg=\{hg:h\in H\}$
• 令$H$是$G$的子群,$g_1,g_2\in G$,以下条件等价:
  1. $g_1H=g_2H$
  2. $Hg_1^{-1}=Hg_2^{-1}$
  3. $g_1H\subset g_2H$
  4. $g_2\in g_1H$
  5. $g_1^{-1}g_2\in H$
• index of $H$ in $G$:$H$在$G$中左陪集数$[G:H]$

拉格朗日定理

TODO

isomorphism(同构)

单射,满射$G\to H:\forall a,b\in G,\phi(a\cdot b)=\phi(a)\circ\phi(b)$

• 无限循环群同构于$\mathbb{Z}$
• $n$阶有限循环群同构于$\mathbb{Z}_n$
• $p$阶($p$为质数)群同构于$\mathbb{Z}_p$

external direct products(外直积)

$G\times H:(g_1,h_1)(g_2,h_2)=(g_1\cdot g_2,h_1\circ h_2)$

• 令$(g,h)\in G\times H$,$g,h$的阶各为$r,s$,那么$(g,h)$在$G\times H$中的阶为$s,r$的最小公倍数

internal direct products(内直积)

• $G$是$H$和$K$的内直积:
  • $G=HK=\{hk:h\in H,k\in K\}$
  • $H\cap K=\{e\}$
  • $hk=kh$
• 若$G$是$H$和$K$的内直积,$G\cong H\times K$

正规子群

$H$是$G$的子群,$H$ is normal:$\forall g\in G,gH=Hg$

• 令$N$是$G$子群,以下等价
  1. $N$ normal in $G$
  2. $\forall g\in G,gNg^{-1}\subset N$
  3. $\forall g\in G,gNg^{-1}=N$

商群(factor or quotient group)

若$N$是$G$的正规子群,那么$N$的陪集在运算$(aN)(bN)=abN$下构成群$G/N$(阶为$[G:N]$)

the simplicity of the alternating group

TODO

Homomorphisms(同态)

映射$G\to H:\forall a,b\in G,\phi(a\cdot b)=\phi(a)\circ\phi(b)$

• 令同态映射$\phi:G\to H$,kernel:$\phi(\{e\})^{-1}$($G$的正规子群)

同构定理

• natural/canonical homomorphism:
  • $H$是$G$的正规子群,定义$\phi:G\to G/H$ by $\phi(g)=gH$
• 第一同构定理
  • 如果$\psi:G\to H$是同态映射且$K=\ker\psi$,那么$K$ is normal in $G$
  • 令$\phi:G\to G/K$为canonical homomorphism,那么存在唯一的同构映射$\eta:G/K\to\phi(G)$ such that $\psi=\eta\phi$
• 第二同构定理
  • $H$是$G$的子群,且$N$是$G$的正则子群,那么:
    • $HN$是$G$的子群
    • $H\cap N$是$H$的正规子群
    • $H/H\cap N\cong HN/N$

串匹配

TODO

数论

欧几里得算法

int euclid(int a, int b)
{
  if (b == 0) {
    return a;
  }
  return euclid(b, a % b);
}

struct fuck {
  int d, x, y;
};

fuck extended_euclid(int a, int b)// gcd(a, b) = d = a * x + b * y
{
  if (b == 0) {
    return (a, 1, 0);
  }
  (d_, x_, y_) = extended_euclid(b, a % b);
  (d, x, y) = (d_, y_, x_ - (a / b) * y_);
  return (d, x, y);
}

欧拉函数

$\phi(n):\le n$正整数中与$n$互质的数的个数

• $\phi(n)=n\prod(1-\dfrac{1}{p}),p$是$n$的质因子,不重复
• 若$m,n$互质,$\phi(mn)=\phi(m)\phi(n)$
• 若$n$为质数,$\phi(n)=n-1$

求解模线性方程

• 当且仅当$d|b$时,$ax\equiv b(\mod n)$有解,$d=\gcd(a,n)$
• 对任意正整数$a,n$,如果$d=\gcd(a,n)$,则在$\mathbb{Z}_n$中
  1. $\langle a\rangle=\langle d\rangle=\{0,d,2d,…,((n/d)-1)d\}$
  2. $|\langle a\rangle|=n/d$

中国余数定理

• $n_1,n_2…n_k$两两互质,且$n=n_1n_2…n_k$,则对任意整数$a_1,a_2…a_k$,关于$x$的方程组$x\equiv a_i(\mod n_i),i=1,2…k$有唯一解
• $n_1,n_2…n_k$两两互质,且$n=n_1n_2…n_k$,则对所有整数$x,a$:$x\equiv a(\mod n_i),i=1,2…k$当且仅当$x\equiv a(\mod n_i)$

元素的幂

• 欧拉定理:$\forall n > 1,a^{\phi(n)}\equiv1(\mod n),a\in\mathbb{Z}_n^{*}$
• 费马定理:$p$是素数,则$a^{p-1}\equiv1(\mod p),a\in\mathbb{Z}_n^{*}$

Mille-Rabin

int num[] = {2, 3, 5, 7, 11, 13, 17, 19};
int MR(long long a)
{
  if (a == 1) return 0;
  2^t * u = a - 1;
  for (i = 0; i < num.length; i ++) {
    x = num[i]^u % a;
    for (j = 0; j < t; j ++) {
      last = x;
      x = x * x % a;
      if (x == 1 && last != 1 && last != a - 1) return 0;
    }
    if (x != 1) return 0;
  }
  return 1;
}

RSA

1. 选两个素数$p\not=q$
2. $n=pq$
3. 选与$\phi(n)$互质的小奇数$e$
4. 计算模$\phi(n)$下$e$的乘法逆元$d$
5. 公开$e,n$

代数编码

• $(n,m)$-block code:$m$位编码成$n$位
• 矩阵$H\in\mathbb{M}_{m\times n}(\mathbb{Z}_2)的$null space($Null(H)$):使得$Hx=0$的$x$集合
• canonical parity-check matrix:$H=(A|I_m)$
• standard generator matrix:$G=(\dfrac{I_{n-m}}{A})$
• $\{y:Gx=y,x\in\mathbb{Z}_2^k\}=C=Null(H),((n,k)$-block code)
• $HG=0$
• $y\in C$当且仅当$Hy=0$
• $C$是single error-correcting code当且仅当$H$没有全0的column且$H$任意两columns都不相同
• syndrome of $x$(校验子):$Hx$
• 对$r$行(校验位长度)的汉明奇偶校验矩阵,其列数至多$2^r-1$(除去0),设信息位长度为$k$,则$2^r-1\ge k+r$

NPC理论

判定问题$(L,U,\Sigma)$

• input: An $x\in U$
• output: ‘yes’ if $x\in L$, ‘no’ otherwise

最优化问题$(\Sigma_I,\Sigma_O,L,L_I,M,cost,goal)$

• input: $L_I$的问题实例
• constraints: 对于$x\in L_I$的约束条件$M(x)$
• costs: cost函数
• goal: maximum/minimun

NP完全性

• co-NP:{$L|L^C\in$NP}
• $L_1\le_PL_2$:$x\in L_1$当且仅当$f(x)\in L_2$
• NP-hard:
  1. 不一定是NP
  2. 所有NP可以约化到它
• $L_2\in P,L_1\le_PL_2$则$L_1\in P$
• $L’\in$NPC,$L’\le_PL$则$L$是NP难度的

3-CNF可满足性$\le_P$团问题

• 建图:
  1. 对每个子句$C=(x\vee y\vee z)$,将$x,y,z$以3元组的形式加入到点集$V$
  2. 对所有$V$中来自不同3元组的两个点$u,v$,若$u$不是$v$的非,则建边$(u,v)$
• 3-CNF可满足$\to$规模为$k$的团:
  • 每个3元组中至少会有一个文字为真,在每个3元组中选一个这样的顶点,组成规模为$k$的集合$V’$
  • 因为$k$个顶点对应的文字不可能互补,所以两两之间有边,所以$V’$是团
• 规模为$k$的团$\to$3-CNF可满足
  • $k$个顶点对应的文字两两互不为补,令这些顶点对应的文字为真

团问题$\le_P$顶点覆盖问题

• 建图:
  • 根据输入$G$建立补图$\bar{G}$
• $G$有规模为$k$的团$\to\bar{G}$有规模为$|V|-k$的顶点覆盖:
  • 设$G$包含规模为$k$的团$V’$
  • 对$\bar{G}$中任意一条边$(u,v)$,$(u,v)\not\in G$,所以$u,v$至少一个不在团$V’$中,即$u,v$至少一个在$V-V’$中,即$u,v$两点被点集$V-V’$覆盖,所以$V-V’$能覆盖$\bar{G}$中的所有顶点
• $\bar{G}$有规模为$|V|-k$的顶点覆盖$\to G$有规模为$k$的团:
  • 设$\bar{G}$包含规模为$|V|-k$的顶点覆盖$V’$
  • 对$G$中任意2个顶点$u,v$,若$u\not\in V’$且$v\not\in V’$,那么$G$中一定有边$(u,v)$,所以任意$u,v\in V-V’$存在边$(u,v)$,所以$V-V’$是团

哈密顿回路问题$\le_P$旅行商问题

• 建图:
  • 对于输入$G$,建立完全图$G’$,定义费用$c(i,j)=\begin{cases}
    0\quad(i,j)\in E\\
    1\quad(i,j)\not\in E\\
    \end{cases}$
• $G$有哈密顿回路$\to G’$中有费用至多为0的回路:
• $G’$中有费用至多为0的回路$\to G$有哈密顿回路:

3-CNF可满足性$\le_P$子集和问题

• 建模:
  1. 输入含$n$个变量,$k$个子句
  2. 集合$S$为$2k+2n$个$k+n$位10进制数的集合(高$n$位对应$n$个变量,低$k$为对应$k$个子句):
     1. 对于每个变量$x$,在$S$中构建2个数$v,v’$:
        1. $v,v’$对应$x$的那一位为1
        2. 对所有子句$C$,若$C$包含$x$,则$v$对应的$C$那一位为1,若$C$包含$\lnot x$,则$v’$对应$C$的那一位为1
     2. 对于每个子句$C$,在$S$中构建两个数$s,s’$:
        1. $s$对应$C$的那一位为1
        2. $s’$对应$C$的那一位为2
  3. 目标:选取$S’\subseteq S$,其中所有数之和$t$高$n$位全为1,低$k$位全为$4$
• 3-CNF可满足$\to$存在$S’\subseteq S$和为$t$:
  1. 若变量$x_i=1$则将$v_i$包含进$S’$,否则将$v_i’$包含进$S’$:$t$的高$n$位为全1
  2. 现在$t$的低$k$位每一位可能为$1,2,3$,再对每一个集合$\{s_j,s_j’\}$选取一个非空集合,使得$t$在对应子句$C_i$的位置为4
• 存在$S’\subseteq S’$和为$t\to$3-CNF可满足:
  1. 因为$t$的高$n$位全为1,那么每对$v_i,v_i’$,$S’$都只包含2者之1
  2. 若$v_i\in S’$,$x_i$置1,否则置0
  3. TODO

随机化算法

拉斯维加斯算法

• $Prob(A(x)=F(x))=1$
• $Prob(A(x)=?)=1-Prob(A(x)=F(x))\le\dfrac{1}{2}$

蒙特卡洛算法

• one-sided-error:
  1. $x\in L,Prob(A(x)=1)\ge1/2$
  2. $x\not\in L,Prob(A(x)=0)=1$
• two-sided-error:
  1. $Prob(A(x)=F(x))\ge1/2+\varepsilon$
• unbounded-error:
  1. $Prob(A(x)=F(x)) > \dfrac{1}{2}$