LYNX

Links

Tags

Categories

问求复习

线性规划

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}$
oj复习

模拟退火

poj2069

#include <stdio.h>
#include <assert.h>
#include <math.h>

const int MAXN = 31;

struct fuck {
double x, y, z;
} p[MAXN], ans;

int n;
double radius;

void SA();
double dis(fuck a, fuck b);

int main()
{
int i = 0;
while (~scanf("%d", &n)) {
if (n == 0) break;
for (i = 0; i < n; i ++) {
scanf("%lf%lf%lf", &p[i].x, &p[i].y, &p[i].z);
}
SA();
printf("%.5lf\n", radius);
}
return 0;
}

void SA()
{
ans.x = ans.y = ans.z = 0;
int max_p = -1;
int i = 0;
for (double t = 100; t > 0.0000001; t *= 0.99) {
radius = 0;
for (i = 0; i < n; i ++) {
double tmp_dis = dis(ans, p[i]);
if (tmp_dis > radius) {
max_p = i;
radius = tmp_dis;
}
}
ans.x -= (ans.x - p[max_p].x) / radius * t;
ans.y -= (ans.y - p[max_p].y) / radius * t;
ans.z -= (ans.z - p[max_p].z) / radius * t;
}
}

double dis(fuck a, fuck b)
{
return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y) + (a.z - b.z)*(a.z - b.z));
}

p4035

#include <stdio.h>
#include <assert.h>
#include <math.h>

const int MAXN = 12;

struct fuck {
double num[MAXN];
} point[MAXN], center, delta;

int n;

void SA();
double dis(fuck a, fuck b);

int main()
{
int i = 0, j = 0;
scanf("%d", &n);
for (i = 0; i < n + 1; i ++) {
for (j = 0; j < n; j ++) {
scanf("%lf", &point[i].num[j]);
}
}
SA();
for (i = 0; i < n; i ++) {
printf("%.3lf%c", center.num[i], i == n - 1 ? '\n' : ' ');
}
return 0;
}

void SA()
{
int i = 0, j = 0;
for (i = 0; i < n; i ++) {
center.num[i] = 0;
}

for (double t = 10000; t > 0.0001; t *= 0.99995) {
double ave = 0;
double each_dis[MAXN];
for (i = 0; i < n + 1; i ++) {
each_dis[i] = dis(center, point[i]);
ave += each_dis[i];
}
ave /= n + 1;

for (i = 0; i < n; i ++) {
delta.num[i] = 0;
}
for (i = 0; i < n + 1; i ++) {
for (j = 0; j < n; j ++) {
delta.num[j] += (ave - each_dis[i]) / (ave) * (center.num[j] - point[i].num[j]);
}
}
for (i = 0; i < n; i ++) {
center.num[i] += t * delta.num[i];
}
}
}

double dis(fuck a, fuck b)
{
int i = 0;
double ans = 0;
for (i = 0; i < n; i ++) {
ans += (a.num[i] - b.num[i]) * (a.num[i] - b.num[i]);
}
return sqrt(ans);
}

素数判定

p3383

  • 增大步长
#include <stdio.h>
#include <assert.h>

int n;

int is_prime(int a);

int main()
{
scanf("%d%d", &n, &n);
while (n --) {
int test = 0;
scanf("%d", &test);
printf("%s\n", is_prime(test) ? "Yes" : "No");
}
return 0;
}

int is_prime(int a)
{
if (a == 1) return 0;
if (a == 2 || a == 3) return 1;
if ((a % 6 != 1) && (a % 6 != 5)) return 0;
for (int i = 5; i * i <= a; i += 6) {
if (a % i == 0) return 0;
if (a % (i + 2) == 0) return 0;
}
return 1;
}
  • Miller-Rabin
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

int my_exp(long long a, int b, int m);
int MR(int a);

int n;
int num[] = {2, 3, 5, 7, 11, 13, 17, 19};

int main()
{
scanf("%d%d", &n, &n);
while (n --) {
int test = 0;
scanf("%d", &test);
printf("%s\n", MR(test) ? "Yes" : "No");
}
return 0;
}

int my_exp(long long a, int b, int m)
{// a^b % m
long long ans = 1;
while (b) {
if (b & 1) {
ans = ans * a % m;
}
a = (long long)a * a % m;
b >>= 1;
}
return (int)ans;
}

int MR(int a)
{
if (a == 1) return 0;// 特判
// 计算 a - 1 == 2^t * u
int u = a - 1;
int t = 0;
while (u % 2 == 0) {
u >>= 1;

t ++;
}
assert(u % 2 == 1);
// witness
for (int i = 0; i < (int)(sizeof(num) / sizeof(int)); i ++)
{
if (a == num[i]) return 1;// 特判
int x = my_exp(num[i], u, a);
for (int j = 1; j <= t; j ++) {
int last = x;
x = (int)((long long)last * last % a);
if ((x == 1) && (last != 1) && (last != a - 1)) return 0;
}
if (x != 1) return 0;
}
return 1;
}

poj3641

#include <stdio.h>
#include <assert.h>

long long my_exp(long long a, long long b, long long m);
int MR(long long a);

int p, a;
int num[] = {2, 3, 5, 7, 11, 13, 17, 19};

int main()
{
while (~scanf("%d%d", &p, &a)) {
if ((p == 0) && (a == 0)) break;
if (my_exp(a, p, p) == a && MR(p) == 0) {
printf("yes\n");
} else {
printf("no\n");
}
}
return 0;
}

long long my_exp(long long a, long long b, long long m)
{
long long ans = 1;
while (b) {
if (b & 1) {
ans = ans * a % m;
}
a = a * a % m;
b >>= 1;
}
return ans;
}

int MR(long long a)
{
if (a == 1) return 0;
// a - 1 = 2^t * u
long long u = a - 1;
int t = 0;
while (u % 2 == 0) {
u /= 2;
t ++;
}
assert(u % 2 == 1);
// witness
for (int i = 0; i < (int)(sizeof(num)/sizeof(int)); i ++) {
if (a == num[i]) return 1;
long long x = my_exp(num[i], u, a);
for (int j = 0; j < t; j ++) {
long long last = x;
x = x * x % a;
if (x == 1 && last != 1 && last != a - 1) return 0;
}
if (x != 1) return 0;
}
return 1;
}

hdoj2138

多组cases

KMP

p3375

#include <stdio.h>
#include <string.h>
#include <assert.h>

const int MAXN = 1000001;
const int MAXM = 1000001;

int next[MAXM];
char s1[MAXN];
char s2[MAXM];
int s1_len, s2_len;

void pre();
void kmp();

int main()
{
scanf("%s%s", s1, s2);
pre();
kmp();
for (int i = 0; i < s2_len; i ++) {
printf("%d%c", next[i], i == s2_len - 1 ? '\n' : ' ');
}
return 0;
}

void pre()
{
s2_len = strlen(s2);
int len = 0;
int i = 1;
next[0] = 0;
while (i < s2_len) {
if (s2[i] == s2[len]) {// 增加长度
len ++;
next[i] = len;
i ++;
} else {
while (len > 0) {
len = next[len - 1];
if (s2[i] == s2[len]) {
len ++;
next[i] = len;
i ++;
break;
}
}
if (len == 0) {// 没有找到匹配
next[i] = len;
i ++;
}
}
}
}

void kmp()
{
s1_len = strlen(s1);
int i = 0, j = 0;
while (i < s1_len) {
if (s1[i] == s2[j]) {
i ++;
j ++;
if (j == s2_len) {// 找到匹配
printf("%d\n", i + 1 - s2_len);
j = next[j - 1];
}
} else {
int found = 0;
while (j > 0) {
j = next[j - 1];
if (s1[i] == s2[j]) {
i ++;
j ++;
if (j == s2_len) {// 找到匹配
printf("%d\n", i);
j = next[j - 1];
found = 1;
}
break;
}
}
if (j == 0 && found == 0) {
i ++;
}
}
}
}

poj3461

#include <string.h>
#include <stdio.h>
#include <assert.h>

const int MAXN = 1000010;

char W[MAXN];
char T[MAXN];
int next[MAXN];
int n;
int wlen, tlen;

void prefix();
void kmp();

int main()
{
scanf("%d", &n);
while (n --) {
scanf("%s%s", W, T);
prefix();
kmp();
}
}

void prefix()
{
wlen = strlen(W);
int i = 1, j = 0;
next[0] = 0;
while (i < wlen) {
while (j > 0 && W[j] != W[i]) j = next[j - 1];
if (W[j] == W[i]) {
j ++;
next[i] = j;
} else {
next[i] = 0;
}
i ++;
}
}

void kmp()
{
tlen = strlen(T);
int i = 0, j = 0;
int ans = 0;
while (i < tlen) {
while (j > 0 && W[j] != T[i]) {
j = next[j - 1];
}
if (W[j] == T[i]) j ++;
if (j == wlen) {
ans ++;
j = next[j - 1];
}
i ++;
}
printf("%d\n", ans);
}
Algorithmics-for-Hard-Problems

2

2.3

Definition 2.3.1.2

Let $\Sigma$ be an alphabet. A word over $\Sigma$ is any finite sequence of symbols of $\Sigma$. The empty word $\lambda$ is the only word consisting of zero symbols. The set of all words over the alphabet $\Sigma$ is denoted by $\Sigma^{*}$

Definition 2.3.1.3

The length of a word $w$ over an alphabet $\Sigma$, denoted by $|w|$, is the number of symbols in $w$. For every word $w\in\Sigma^{*}$, and every symbal $a\in\Sigma$, $\sharp_{a}(w)$ is the number of occurrences of the symbol $a$ in the word $w$

Definition 2.3.1.4

Let $\Sigma$ be an alphabet. Then, for any $n\in\mathbb{N}$
$$ \Sigma^n=\{x\in\Sigma^{*}||x|=n\} $$
We define $\Sigma^+=\Sigma^{*}-\{\lambda\}$

Definition 2.3.1.5 (concatenation)

For every word $w\in\Sigma^{*}$, we define

  • $w^0=\lambda$, and
  • $w^{n + 1}=w\cdot w^n=ww^n$ for every positive integer $n$

Definition 2.3.1.9 (language)

Let $\Sigma$ be an alphabet, Every set $L\subseteq\Sigma^{*}$ is called a language over $\Sigma$. The complement of the language $L$ according to $\Sigma$ is $L^C=\Sigma^{*}-L$

Let $\Sigma_1$ and $\Sigma_2$ be alphabets, and let $L_1\subseteq\Sigma_1^{*}$ and $L_2\subseteq\Sigma_2^{*}$ be languages. The concatenation of $L_1$ and $L_2$ is
$$ L_1L_2=L_1\circ L_2=\{uv\in(\Sigma_1\cup\Sigma_2)^{*}|u\in L_1 and\ v\in L_2\} $$

Definition 2.3.1.10

Let $\Sigma=\{s_1,s_2…s_m\},m\ge1$, be an alphabet, and let $s_1 < s_2 < … < s_m$ be a linear ordering on $\Sigma$. We define the canonical ordering on $\Sigma^{*}$ as follows. For all $u,v\in\Sigma^{*}$
$$u < v\mbox{ if }|u| < |v|$$
$$\mbox{or }|u|=|v|,u=xs_iu’,\mbox{ and }v=xs_jv’$$
$$\mbox{for some }x,u’,v’\in\Sigma^{*},\mbox{ and }i < j$$

2.3.2

Definition 2.3.2.1

A decision problem is a triple $(L, U, \Sigma)$ where $\Sigma$ is an alphabet and $L\subseteq U\subseteq\Sigma^{*}$. An algorithm $A$ solves(decides) the decision problem $(L, U, \Sigma^{*}$ if, for every $x\in U$

  • $A(x)=1$ if $x\in L$, and
  • $A(x)=0$ if $x\in U-L(x\not\in L)$

Definition 2.3.2.2

An optimization problem is a 7-tuple $U=(\Sigma_I,\Sigma_O,L,L_I,M,cost,goal)$, where

  • $\Sigma_I$ is an alphabet, called the input alphabet of $U$
  • $\Sigma_O$ is an alphabet, called the output alphabet of $U$
  • $L\subseteq\Sigma_I^{*}$ is the language of feasible problem instances
  • $L_I\subseteq L$ is the language of the(actual) problem instances of $U$
  • $M$ is a function from $L$ to (power set)$Pot(\Sigma_O^{*})$, and for every $x\in L$, $M(x)$ is some $x\in L$, assigns a positive real number cost($u,x$)
  • cost is the cost function that, for every pair $(u,x)$, where $u\in M(x)$ for some $x\in L$, assigns a positive real number cost($u,x$)
  • goal$\in${minimum,maximum}

For every $x\in L_I$, a feasible solution $y\in M(x)$ is called optimal for $x$ and $U$ if
$$ cost(y,x)=goal\{cost(z,x)|z\in M(x)\} $$
For an optimal solution $y\in M(x)$, we denote cost($u,x$) by Opt$_U(x)$ ,$U$ is called maxmization problem if goal=maximum, and $U$ is a minimization problem if goal=minimum. In what follows Output$_U(x)\subseteq M(x)$ denotes the set of all optimal solutions for the instance $x$ of $U$

An algorithm $A$ is consistent for $U$ if, for every $x\in L_I$, the output $A(x)\in M(x)$. We say that an algorithm $B$ solves the optimization problem $U$ if

  • $B$ is consistent for $U$, and
  • for every $x\in L_1, B(x)$ is an optimal solution for $x$ and $U$

Definition 2.3.2.3

Let $U_1=(\Sigma_I,\Sigma_O,L,L_{I,1},M,cost,goal)$ and $U_2=(\Sigma_I,\Sigma_O,L,L_{I,2},M,cost,goal)$ be two optimization problems. We say that $U_1$ is a subproblem of $U_2$ if $L_{I,1}\subseteq L_{I,2}$

Theorem 2.3.3.3

There is a decision problem $(L,\Sigma_{bool})$ such that, for every algorithm $A$ deciding $L$, there exists another algorithm $B$ deciding $L$, such that
$$ Time_B(n)=\log_2(Time_A(n)) $$
for infinitely many positive integers $n$

Definition 2.3.3.5

We define the complexity class $P$ of languages decidable in polynomial-time by
$$ P=\{L=L(M)|M\mbox{ is a TM(an algorithm) with }Time_M(n)\in O(n^c)\mbox{ for some positive integer c}\} $$

A language (decision problem) $L$ is called tractable(practially solvable) if $L\in P$. A language $L$ is called intractable if $L\not\in P$

Definition 2.3.3.6

Let $M$ be a nondeterministic TM(algorithm). We say that $M$ accepts a language $L, L = L(M)$, if

  • for every $x\in L$, there exists at least one computation of $M$ that accepts $x$, and
  • for every $y\not\in L$, all computations of $M$ reject $y$

For every input $w\in L$, the ** time complexity Time$_M(w)$ of $M$ on $w$ ** is the time complexity of the shortest accepting computation of $M$ on $w$. The time complexity of $M$ is the function Time$_M$ from $\mathbb{N}$ to $\mathbb{N}$ defined by
$$ Time_M(n)=\max\{Time_M(x)|x\in L(M)\cap\Sigma^n\} $$

Definition 2.3.3.7

Let $L\subseteq\Sigma^{*}$ be a language. An algorithm $A$ working on inputs from $\Sigma^{*}\times\{0,1\}$ is called a verifier for $L$, denoted $L=V(A)$, if
$$ L=\{w\in\Sigma^{*}|A\mbox{ accepts }(w,c)\mbox{ for some }c\in\{0,1\}^{*}\} $$
If $A$ accepts $(w,c)\in\Sigma^{*}\times\{0,1\}$, we say that $c$ is a proof(certificate) of the fact $w\in L$

A verifier $A$ for $L$ is called a polynomial-time verifier if there exists a positive integer $d$ such that, for every $w\in L$, Time$_A(w,c)\in O(|w|^d)$ for a proof $c$ of $w\in L$

We define the class of polynomially verifiable languages as
$$ VP=\{V(A)|A\mbox{ is a polynomial-time verifier}\} $$

Definition 2.3.3.10

Let $L_1\subseteq\Sigma_1^{*}$ and $L_2\subseteq\Sigma_2^{*}$ be two languages. We say that $L_1$ is polynomial-time reducible to $L_2, L_1\le_pL_2$, if there exists a polynomial-time algorithm $A$ that computes a mapping from $\Sigma_1^{*}$ to $\Sigma_2^{*}$ such that, for every $x\in\Sigma_1^{*}$
$$ x\in L_1\Leftrightarrow A(x)\in L_2 $$
A is called the polynomial-time reduction from $L_1$ to $L_2$

  • A language $L$ is called NP-hard if, for every $U\in NP,U\le_pL$
  • A language $L$ is called NP-complete if
    • $L\in NP$, and
    • $L$ is NP-hard

Lemma 2.3.3.11

If $L$ is NP-hard and $L\in P$, then P=NP

Lemma 2.3.3.15

Sat$\le_{p}$Clique

Lemma 2.3.3.16

Clique$\le_{p}$VC

Lemma 2.3.3.19

3Sat$\le_{p}$Sol-0/1-LP

Definition 2.3.3.21

NPO is the class of optimization problems, where $U=(\Sigma_I,\Sigma_O,L,L_I,M,cost,goal)\in$NPO if the following conditions hold

  • $L_I\in$P

  • there exists a polynomial $p_U$ such that

    • for every $x\in L_I$, and every $y\in M(x),|y|\le p_U(|x|)$, and
    • there exists a polynomial-time algorithm that, for every $y\in\Sigma_O^{*}$ and every $x\in L_I$ such that $|y|\le p_U(|x|)$, decides whether $y\in M(x)$, and
  • the function cost is computable in polynomial time

Definition 2.3.3.23

PO is the class of optimization problems $U=(\Sigma_I,\Sigma_O,L,L_I,M,cost,goal)$ such that

  • $U\in$NPO, and
  • there is a polynomial-time algorithm that, for every $x\in L_1$, computes an optimal solution for $x$

Definition 2.3.3.24

Let $U=(\Sigma_1,\Sigma_O,L,L_1,M,cost,goal)$ be an optimization problem from NPO, We define the threshold language of $U$ as
$$ Lang_U=\{(x,a)\in L_1\times\Sigma_{bool}^{*}|Opt_U(x)\le Number(a)\} $$
if goal=minimum, and as
$$ Lang_U=\{(x,a)\in L_1\times\Sigma_{bool}^{*}|Opt_U(x)\ge Number(a)\} $$
if goal=maximum

We say that $U$ is NP-hard if Lang$_U$ is NP-hard

Lemma 2.3.3.25

If an optimization problem $U\in$PO, then Lang$_U\in$P

4

4.2

Definition 4.2.1.1

Let $U=(\Sigma_I,\Sigma_O,L,L_I,M,cost,goal)$ be an optimization problem, and let $A$ be a consistent algorithm for $U$. For every $x\in L_I$, the relative error $\varepsilon_A(x)$ of $A$ on $x$ is defined as
$$ \varepsilon_A=\dfrac{|cost(A(x))-Opt_U(x)|}{Opt_U(x)} $$

  • For any $n\in\mathbb{N}$, we define the relative error of $A$ as
    $$ \varepsilon_A(n)=\max\{\varepsilon_A(x)|x\in L_I\cap(\Sigma_I)^n\} $$

  • For every $s\in L_I$, the approximation ratio $R_A(x)$ of $A$ on $x$ is defined as
    $$ R_A(x)=\max\{\dfrac{cst(A(x))}{Opt_U(x)},\dfrac{Opt_U(x)}{cost(A(x))}\} $$

  • For any $n\in\mathbb{N}$, we define the approximation ratio of $A$ as
    $$ R_A(n)=\max\{R_A(x)|x\in L_I\cap(\Sigma_I)^n\} $$

  • For any positive real $\delta > 1$, we say that $A$ is a $\delta$-approximation algorithm for $U$ if $R_A(x)\le\delta$ for every $x\in L_I$

  • For every function $f:\mathbb{N}\to\mathbb{R}^+$, we say that $A$ si an $f(n)$-approximation algorithm for $U$ if $R_A(n)\le f(n)$ for every $n\in\mathbb{N}$

Definition 4.2.1.6

Let $U=(\Sigma_I,\Sigma_O,L,L_I,M,cost,goal)$ be an optimization problem. An algorithm $A$ is called a polynomial-time approximation scheme (PTAS) for $U$ if for every input pair $(x,\varepsilon)\in L_I\times\mathbb{R}^+, A$ computes a feasible solution $A(x)$ with a relative error at most $\varepsilon$, and $Time_A(x,\varepsilon^{-1})$ can be bounded by a function that is polynomial in $|x|$.

If $Time_A(x,\varepsilon^{-1})$ can be bounded by a function that is polynomial in both $|x|$ and $\varepsilon^{-1}$, then we say that $A$ is a fully polynomial-time approximation scheme (FPTAS) for $U$

Definition 4.2.3.1

Let $U=(\Sigma_I,\Sigma_O,L,L_I,M,cost,goal)$ and $\bar{U}=(\Sigma_I,\Sigma_O,L,L,M,cost,goal)$ be two optimization problems with $L_I\subset L$. A distance function for $\bar{U}$ according to $L_I$ is any function $h_L:L\to\mathbb{R}^{\ge0}$ satisfying the properties

  1. $h_L(x)=0$ for every $x\in L_I$, and
  2. $h$ is polynomial-time computable

Let $h$ be a distance function for $\bar{U}$ accoring to $L_I$. We define, for any $r\in\mathbb{R}^+$
$$ Ball_{r,h}(L_I)=\{w\in L|h(w)\le r\} $$
Let $A$ be a consistent algorithm for $\bar{U}$, and let $A$ be an $\varepsilon$-approximation algorithm for $U$ for some $\varepsilon\in\mathbb{R}^{-1}$. Let $p$ be a positive real. We say that $A$ is p-stable according to $h$ if, for every real $0 < r \le p$, there exists a $\delta_{r,\varepsilon}\in\mathbb{R}^{> 1}$ such that $A$ is a $\delta_{r,\varepsilon}$-approximation for $U_r=(\Sigma_I,\Sigma_O,L,Ball_{r,h}(L_I),M,cost,goal)$

$A$ is stable according to $h$ if $A$ is $p$-stable according to $h$ for every $p\in\mathbb{R}^+$. We say that $A$ is unstable according to h if $A$ is not $p$-stable for any $p\in\mathbb{R}^+$

For every positive integer $r$, and every function $f_r:\mathbb{N}\to\mathbb{R}^{> 1}$ we say that $A$ is $(r,f_r(n))$-quasistable according to $h$ if $A$ is an $f_r(n)$-approximation algorithm for $U_r=(\Sigma_I,\Sigma_O,L,Ball_{r,h}(L_I),M,cost,goal)$

Definition 4.2.3.6

Let $U=(\Sigma_I,\Sigma_O,L,Ball_{r,h}(L_I),M,cost,goal)$ and $\bar{U}=(\Sigma_I,\Sigma_O,L,L,M,cost,goal)$ be two optimization problems with $L_I\subset L$. Let $h$ be a distance function for $\bar{U}$ according to $L_I$, and let $U_r=(\Sigma_I,\Sigma_O,L,Ball_{r,h}(L_I),M,cost,goal)$ for every $r\in\mathbb{R}^+$. Let $A=\{A_{\varepsilon}\}_{\varepsilon > 0}$ be a PTAS for $U$

If for every $r > 0$ and every $\varepsilon > 0, A_{\varepsilon}$ is a $\delta_{r,\varepsilon}$-approximation algorithm for $U_r$, we say that the PTAS $A$ is stable according to $h$

If $\delta_{r,\varepsilon}\le f(\varepsilon)\cdot g(r)$, where

  • $f$ and $g$ are some functions from $\mathbb{R}^{\ge0}$ to $\mathbb{R}^+$, and
  • $\lim_{\varepsilon\to0}f(\varepsilon)=0$
    then we say that the PTAS $A$ is superstable according to $h$

5

5.2

Definition 5.2.2.10

Let $U=(\Sigma_I,\Sigma_O,L,L_I,M,cost,goal)$ be an optimization problem. For any positive real $\delta > 1$ a randomized algorithm $A$ is called a randomized $\delta$-approximation algorithm for $U$ if

  1. $Prob(A(x)\in M(x))=1$, and
  2. $Prob(R_A(x)\le\delta)\ge1/2

for every $x\in L_I

For every function $f:\mathbb{N}\to\mathbb{R}^+$, we say that $A$ is a randomized $f(n)$-approximation algorithm for $U$ if
$$ Prob(A(x)\in M(x))=1\ and\ Prob(R_A(x)\le f(|x|))\ge1/2 $$
for every $x\in L_I$

A randomized algorithm $A$ is called a randomized polynomial-time approximation scheme (RPTAS) for $U$ if there exists a function $p:L_I\times\mathbb{R}^+\to\mathbb{N}$ such that for every input $(x,\delta)\in L_I\times\mathbb{R}^+$:

  1. $Prob(A(x,\delta)\in M(x))=1$ for every random choice $A$ computes a feasible solution of $U$
  2. $Prob(\varepsilon_A(x,\delta)\le\delta)\ge1/2$ a feasible solution, whose relative error is at most $\delta$, is produced with the probability at least 1/2
  3. $Time_A(x,\delta^{-1})\le p(|x|,\delta^{-1})$ and $p$ is a polynomial in $|x|$

If $p(|x|,\delta^{-1})$ is polynomial in both its arguments $|x|$ and $\delta^{-1}$, then we say that $A$ is a randomized fully polynomial-time approximation scheme (RFPTAS) for $U$

Definition 5.2.2.11

Let $U=(\Sigma_I,\Sigma_O,L,L_I,M,cost,goal)$ be an approximation problem. For any positive real $\delta > 1$, a randomized algorithm $A$ is called a randomized $\delta$-expected approximation algorithm for $U$ if

  1. $Prob(A(x)\in M(x))=1$
  2. $E[R_A(x)]\le\delta$

for every $x\in L_I$

Discrete Mathematics for CS

2.2 Inverses and Greatest Common Divisors

Lemma 2.8

The equation
$$ a{\cdot}_nx = 1 $$
has a solution in $\mathbb{Z}_{n}$ if and only there exist integers $x$ and $y$ such that
$$ ax + ny = 1 $$

Corollary 2.10

If $a\in\mathbb{Z}_{n}$ and $x$ and $y$ are integers such that $ax + ny = 1$, then the multiplicative inverse of $a$ in $\mathbb{Z}_{n}$ is $x$ mod $n$

Lemma 2.11

Given $a$ and $n$, if there exist integers $x$ and $y$ such that $ax+ny=1$, then $\gcd(a,n)=1$

Lemma 2.13

If $j,k,q$, and $r$ are positive integers such that $k=jq+r$, then
$$ \gcd(j,k) = \gcd(r,j) $$

Euclid’s extended GCD algorithm

  • 本书版
void gcd_cs(int j, int k, int ans[3])// j < k(为什么?)且j, k为正数
{
int i = 0;
int q[MAXI], j_arr[MAXI];
int r = 0;
if (j == k)
{
ans[0] = j, ans[1] = 1, ans[2] = 0;
return;
}
else
j_arr[i] = j;
do
{
q[i] = k / j_arr[i];// low(k / j[i])
r = k % j_arr[i];
k = j_arr[i];
j_arr[i + 1] = r;
i ++;
}
while (r != 0);
i --;
int gcd = j_arr[i];// 已经找到gcd(j, k),现找x, y
int y[MAXI], x[MAXI];
y[i] = 0, x[i] = 1;
i --;
while (i >= 0)
{
y[i] = x[i + 1];
x[i] = y[i + 1] - q[i] * x[i + 1];
i --;
}
ans[0] = gcd, ans[1] = x[0], ans[2] = y[0];
return;
}
  • 算法导论版
void gcd_tc(int a, int b, int ans[3])
{
if (b == 0)
{
ans[0] = a, ans[1] = 1, ans[2] = 0;
return;
}
else
{
gcd_tc(b, a % b, ans);
int temp = ans[1];
ans[1] = ans[2], ans[2] = temp - (a / b) * ans[2];
return;
}
}

Theorem 2.15

Two positive integers $j$ and $k$ have greatest common divisor 1 iff there are integers $x$ and $y$ such that $hx+ky=1$

Algorithms

31 数论算法

31.3 模运算

欧拉函数

$\mathbb{Z}_n^*$的规模表示为$\phi(n)$,称为欧拉phi函数,满足下式
$$\phi(n)=n\prod_{\text{$p:p$是素数且$p|n$}}(1-\dfrac{1}{p})$$

31.4 求解模线性方程

定理 31.20

对任意正整数$a$和$n$,如果$d=\gcd(a,n)$,则在$\mathbb{Z}_n$中
$$\langle a\rangle=\langle d\rangle=\{0,d,2d,…,((n/d)-1)d\}$$
因此$|\langle a\rangle|=n/d$

推论 31.21

当且仅当$d|b$时,方程$ax\equiv b(\mod n)$对于未知量$x$有解,这里$d=\gcd(a,n)$

推论 31.22

方程$ax\equiv b(\mod n)$

  • 或者对模$n$有$d$个不同的解
  • 或者无解
    这里$d=\gcd(a,n)$

定理 31.23

令$d=\gcd(a,n)$,假设对某些整数$x’$和$y’$,有$d=ax’+ny’$(例如Extended-Euclid所计算出的结果).如果$d|b$,则方程$ax\equiv b(\mod n)$有一个解的值为$x_0$,这里
$$x_0=x’(b/d)\mod n$$

定理 31.24

假设方程$ax\equiv b(\mod n)$有解(即$d|b$,这里$d=\gcd(a,n)$),且$x_0$是该方程的任意一个解.因此,该方程对模$n$恰有$d$个不同的解,分别为$x_i=x_0+i(n/d),i=0,1,…,d-1$

推论 31.25

对任意$n>1$,如果$\gcd(a,n)=1$,则方程$ax\equiv b(\mod n)$对模$n$有唯一解

推论 31.26

对任意$n>1$,如果$\gcd(a,n)=1$,则方程$ax\equiv1(\mod n)$对模$n$有唯一解;否则方程无解

31.5 中国余数定理

定理 31.27 中国余数定理

令$n=n_1n_2…n_k$,其中因子$n_i$两两互质.考虑以下对应关系
$$a\leftrightarrow(a_1,a_2,…,a_k)\qquad(31.27)$$
这里$a\in\mathbb{Z}_n,a_i\in\mathbb{Z}_{n_i}$,而且对$i=1,2,…,k$
$$a_i=a\mod n_i$$
因此映射(31.27)是一个在$\mathbb{Z}_n$与笛卡尔积$\mathbb{Z}_{n_1}\times\mathbb{Z}_{n_2}\times…\times\mathbb{Z}_{n_k}$之间的双射.通过在合适的系统中对每个坐标位置独立地执行操作,对$\mathbb{Z}_n$中元素所执行的运算可以等价地作用于对应的$k$元组.也就是说,如果
$$a\leftrightarrow(a_1,a_2,…,a_k)$$
$$b\leftrightarrow(b_1,b_2,…,b_k)$$
那么
$$(a+b)\mod n\leftrightarrow((a_1+b_1)\mod n_1,…,(a_k+b_k)\mod n_k)$$
$$(a-b)\mod n\leftrightarrow((a_1-b_1)\mod n_1,…,(a_k-b_k)\mod n_k)$$
$$(ab)\mod n\leftrightarrow((a_1b_1)\mod n_1,…,(a_kb_k)\mod n_k)$$

推论 31.28

如果$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$有唯一解

推论 31.29

如果$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)$$

31.6 元素的幂

定理 31.30 欧拉定理

对于任意整数$n>1,a^{\phi(n)}\equiv1(\mod n)$对所有$a\in\mathbb{Z}_n^*$都成立

定理 31.31 费马定理

如果$p$是素数,则$a^{p-1}\equiv1(\mod p)$对所有$a\in\mathbb{Z}_p^*$都成立

定理 31.32

如果ord$_n(g)=|\mathbb{Z}_n^*|$,则对模$n,\mathbb{Z}_n^*$中的每个元素都是$g$的一个幂,且$g$是$\mathbb{Z}_n^*$的一个原根生成元.如果$\mathbb{Z}_n^*$包含一个原根,就称$\mathbb{Z}_n^*$是循环的

对所有的素数$p>2$和所有正整数$e$,使得$\mathbb{Z}_n^*$是循环群的$n>1$的值为$2,4,p^e,2p^e$

定理 31.33 离散对数定理

如果$g$是$\mathbb{Z}_n^*$的一个原根,则当且仅当等式$x\equiv y(\mod\phi(n))$成立时,有等式$g^x\equiv g^y(\mod n)$成立

定理 31.34

如果$p$是一个奇素数且$e\ge1$,则方程
$$x^2\equiv1(\mod p^e)$$
仅有两个解,即$x=1,x=-1$

推论 31.35

如果对模$n$存在1的非平凡平方根,则$n$是合数

34 NP完全性

34.4 NP完全性的证明

引理 34.8

如果语言$L$是一种满足对任意$L\in$NPC都有$L’\le_PL$的语言,则$L$是NP难度的.此外,如果$L\in$NP,则$L\in$NPC

公式可满足性

$$ SAT=\{\langle\varphi\rangle: \text{$\varphi$是一个可满足的布尔公式}\} $$

3-CNF-SAT 3-CNF可满足性

布尔公式中的一个文字(literal)是指一个变量或变量的非.如果一个布尔公式可以表示为所有子句的与,并且每个子句都是一个或多个文字的或,则该布尔公式为合取范式,CNF(conjunctive normal form).如果公式中每个子句恰好都有三个不同的文字,则称该布尔公式为3合取范式,3-CNF,例如
$$ (x_1\vee\lnot x_1\vee\lnot x_2)\wedge(x_3\vee x_2\vee x_4)\wedge(\lnot x_1\vee\lnot x_3\vee\lnot x_4) $$
就是一个3合取范式,第一个子句包含3个文字$x_1,\lnot x_1$和$\lnot x_2$

Abstract Algebra(人话版)

Sage准备

  • mac
    1. 开启共享
    2. Applications/SageMath-8.6.app/Contents/Resources/sage/sage

模$n$整数$Z_n$

Z8 = Integers(8)
Z8.list()
# [0, 1, 2, 3, 4, 5, 6, 7]

a = Z8.an_element(); a
# 0

a = Z8(7); a
# 7

Z8.addition_table(names = 'elements')
# + 0 1 2 3 4 5 6 7
# +----------------
# 0| 0 1 2 3 4 5 6 7
# 1| 1 2 3 4 5 6 7 0
# 2| 2 3 4 5 6 7 0 1
# 3| 3 4 5 6 7 0 1 2
# 4| 4 5 6 7 0 1 2 3
# 5| 5 6 7 0 1 2 3 4
# 6| 6 7 0 1 2 3 4 5
# 7| 7 0 1 2 3 4 5 6

子群subgroups

    • 结合律
    • 单位元存在
    • 逆元存在
  • 子群

    • 封闭性
    • 单位元存在性
    • 逆元存在性
S8 = SymmetricGroup(8)
Q = QuaternionGroup()
Q.is_subgroup(S8)
# True

a = S8.random_element()
[a (x) for x in S8.domain()]
# [5, 2, 6, 4, 1, 8, 3, 7]

一般线性群

  • $\mathbb{M}_2(\mathbb{R})$:所有$2\times2$矩阵
  • $GL_2(\mathbb{R})$:$\mathbb{M}_2$中可逆矩阵.可逆矩阵构成一般线性群
  • $A\in GL_2(\mathbb{R}),A^{-1}=\dfrac{1}{ad-bc}
    \begin{pmatrix}
    d & -b \\
  • c & a \\
    \end{pmatrix}
    $
matrix([[1,0],[3,4]])
# [1 0]
# [3 4]

循环群

  • 存在一些$a\in G$使得$G=\langle a\rangle$
  • $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$
G = 3*ZZ
-12 in G
# True
G.gen()
# 3

四元群$Q_8$

  • $Q_8={\pm1,\pm I,\pm J,\pm K}$,其中

$$
1=
\begin{pmatrix}
1 & 0 \\
0 & 1 \\
\end{pmatrix}
I=
\begin{pmatrix}
0 & 1 \\
-1 & 0 \\
\end{pmatrix}
J=
\begin{pmatrix}
0 & i \\
i & 0 \\
\end{pmatrix}
K=\begin{pmatrix}
i & 0 \\
0 & -i \\
\end{pmatrix}
$$

Q = QuaternionGroup()
Q.order()
# 8
Q.is_abelian()
# False

Sage中复数用CC表示,可用i/I

H = [CC(1), CC(-1), CC(i), CC(-i)]
sage: CC.multiplication_table(elements = H, names = ['1', '-1', 'i', '-i'])
# * 1 -1 i -i
# +------------
# 1| 1 -1 i -i
# -1| -1 1 -i i
# i| i -i -1 1
# -i| -i i 1 -1

二面体群(Dihedral Group)$D_n$

D100 = DihedralGroup(100)
D50 = DihedralGroup(50)
Z2 = Integers(2)
D100.is_abelian()
# False
D100.is_cyclic()
# False

置换群$S_n$:

  • 秩:$|S_n|=n!$
S3 = SymmetricGroup(3)
rho1 = S3([3, 2, 1]); rho1
# (1,3)

S3.domain()
# {1, 2, 3}

[rho1(x) for x in S3.domain()]
# [3, 2, 1]

[[a(x) for x in S3.domain()] for a in S3]
# [[1, 2, 3], [3, 1, 2], [2, 3, 1], [1, 3, 2], [3, 2, 1], [2, 1, 3]]

S3.cayley_table(names='elements')
# * () (2,3) (1,2) (1,2,3) (1,3,2) (1,3)
# +------------------------------------------------
# ()| () (2,3) (1,2) (1,2,3) (1,3,2) (1,3)
# (2,3)| (2,3) () (1,2,3) (1,2) (1,3) (1,3,2)
# (1,2)| (1,2) (1,3,2) () (1,3) (2,3) (1,2,3)
# (1,2,3)| (1,2,3) (1,3) (2,3) (1,3,2) () (1,2)
# (1,3,2)| (1,3,2) (1,2) (1,3) () (1,2,3) (2,3)
# (1,3)| (1,3) (1,2,3) (1,3,2) (2,3) (1,2) ()
S5 = SymmetricGroup(5)
sigma = S5("(1,3)(2,5,4)")
sigma**2
# (2,4,5)

循环置换群

C3 = CyclicPermutationGroup(3)

交代群$A_n$

  • $S_n$的子群,偶排列,$|A_n|=\dfrac{n!}{2}$

如果排列为偶.sign()输出1,为奇输出-1

A4 = AlternatingGroup(4)
rho = A4.random_element()
rho
# (1,4,2)

rho.sign()
# 1

S4 = SymmetricGroup(4)
rho = S4.random_element()
rho; rho.sign()
# (1,4,2,3)
# -1

A4.order()' S4.order()
# 12
# 24

通过给定generators来生成一个群的子群

sigma = (1,4,2)
sg = A4.subgroup([sigma])
sg.list()
# [(), (1,2,4), (1,4,2)]

穷举所有子群(注意s)

A4.subgroups()

陪集

  • $H$是$G$的子群,$H$的左陪集:$gH=\{gh:h\in H\}$
S3 = SymmetricGroup(3)
a = S3("(1,2)")
H = S3.subgroup([a])
rc = S3.cosets(H, side = 'right'); rc
# [[(), (1,2)], [(2,3), (1,3,2)], [(1,2,3), (1,3)]]

lc = S3.cosets(H, side = 'left'); lc
# [[(), (1,2)], [(2,3), (1,2,3)], [(1,3,2), (1,3)]]

乱序的list比较结果为False,可通过排序再进行比较

b = S3("(1,2,3)")
H = S3.subgroup([b])
rc = S3.cosets(H, side = 'right');
lc = S3.cosets(H, side = 'left');
rc == lc
# False

rc_sorted = sorted([sorted(coset) for coset in rc])
lc_sorted = sorted([sorted(coset) for coset in lc])
rc_sorted == lc_sorted
# True
  • $H$是$G$的子群,index of $H=H$在$G$中左陪集的个数$=H$右陪集的个数,记作$[G:H]$

正规子群(Normal Subgroups)

  • $H$是$G$的子群,$gH=Hg,\forall g\in G$
  • 等价条件,设$N$是$G$的子群
    • $N$是$G$的正规子群
    • $\forall g\in G,gNg^{-1}\subset N$
    • $\forall g\in G,gNg^{-1}=N$
A4.is_normal(S4)
# True

商群(factor/quotient group)

  • $N$是$G$的正规子群,商群$G/N$是$N$在$G$中左陪集的集合
  • $aN,bN\in G/N,(aN)(bN)=abN$
  • $G/N$的阶为$[G:N]$
Q = S4.quotient(A4)

同构 同态

  • 同构:$(G,\cdot),(H,\circ)$单射且满射$\phi:G\to H$

$$\phi(a\cdot b)=\phi(a)\circ\phi(b),\forall a,b\in G$$

  • 同态:$(G,\cdot),(H,\circ)$映射$\phi:G\to H$

$$\phi(a\cdot b)=\phi(a)\circ\phi(b),\forall a,b\in G$$

  • 核(kernel):群同态$\phi:G\to H$,$e$是$H$的单位元,$G$的子群$\phi^{-1}({e})$是$\phi$的kernel
A4.is_isomorphic(S4)
# False

x = S4.gen(0)
phi = PermutationGroupMorphism(A4, S4, x)
phi
# Permutation group morphism:
# From: Alternating group of order 4!/2 as a permutation group
# To: Symmetric group of order 4! as a permutation group
# Defn: [(2,3,4), (1,2,3)] -> [(1,2,3,4)]

phi = PermutationGroupMorphism(A4, S4, A4.gens()); phi
# Permutation group morphism:
# From: Alternating group of order 4!/2 as a permutation group
# To: Symmetric group of order 4! as a permutation group
# Defn: [(2,3,4), (1,2,3)] -> [(2,3,4), (1,2,3)]

a = A4.random_element(); print(a, "->", phi(a))
# ((2,3,4), '->', (2,3,4))

phi.kernel()
# Subgroup of (Alternating group of order 4!/2 as a permutation group) generated by [()]

null space

sage中null space使用kernel代替

Z = Integers(2)
Z
# Ring of integers modulo 2
M = matrix(Z,[[0,1,0,0,0],[1,0,1,0,1],[1,0,0,1,0]])
M
# [0 1 0 0 0]
# [1 0 1 0 1]
# [1 0 0 1 0]
H = M.right_kernel_matrix()
H
# [1 0 0 1 1]
# [0 0 1 0 1]
Abstract Algebra

2. The Integers

Theorem 2.10

Let $a$ and $b$ be nonzero integers. Then there exist integers $r$ and $s$ such that
$$ \gcd(a,b)=ar+bs $$
Furthermore, the greatest common divisor of $a$ and $b$ is unique

3.Groups

Theorem 3.23

In a group, the usual laws of exponents hold; that is, for all $g, h\in G$

  1. $g^mg^n=g^{m+n}$ for all $m, n\in\mathbb{Z}$

  2. $(g^m)^n=g^{mn}$ for all $m, n\in\mathbb{Z}$

  3. $(gh)^n=(g^{-1}h^{-1})^{-n}$ for all $n\in\mathbb{Z}$. Furthermore, if $G$ is abelian, then $(gh)^n=g^nh^n$

Proposition 3.30

A subset $H$ of $G$ is a subgroup if and only if it satisfies the following conditions

  1. The identity $e$ of $G$ is in $H$

  2. If $h_1, h_2\in H$, then $h_1h_2\in H$

  3. If $h\in H$, then $h^{-1}\in H$

Proposition 3.31

Let $H$ be a subset of a group $G$. Then $H$ is a subgroup of $G$ if and only if $H\not=\emptyset$, and whenever $g, h\in H$ then $gh^{-1}$ is in $H$

4.Cyclic Groups

Remark 4.4

If we are using the “+” notations, as in the case of the integers under addition, we write $\langle a\rangle={na:a\in\mathbb{Z}}$

For $a\in G$, we call $\langle a\rangle$ the cyclic subgroup generated by $a$. If $G$ contains some element $a$ such that $G=\langle a\rangle$, then $G$ is a cyclic group. In this case $a$ is a generator of $G$.

If $a$ is an element of a group $G$, we define the order of $a$ to be the smallest positive integer $n$ such that $a^n=e$, and we write $|a|=n$. If there is no such integer $n$, we say that the order of $a$ is infinite and write $|a|=\infty$ to denote the order of $a$

Corollary 4.14

The generators of $\mathbb{Z}_n$ are the integers r subch that $1\le r<n$ and gcd$(r, n)=1$

$\text{cis}(x)=\cos(x)+$i$\sin(x)$

Proposition 4.20

Let $z=r\text{cis}\theta$ and $w=s\text{cis}\phi$ be two nozero compler numbers. Then $$zw=rs\text{cis}(\theta+\phi)$$

5. Permutation Groups

Proposition 5.8

Let $\sigma$ and $\tau$ be two disjoint cycles in $S_X$. Then $\sigma\tau=\tau\sigma$

Theorem 5.9

Every permutation in $S_n$ can be written as the product of disjpint cycles

Lemma 5.14

If the identity is written is written as the product of r transpositions $$id=\tau_1\tau_2…\tau_r$$ then $r$ is an even number

The Alternating Groups

One of the most important subgroups of $S_n$ is the set of all even permutations, $A_n$. The group $A_n$ is called the alternating group on n letters

Theorem 5.16

The set $A_n$ is a subgroup of $S_n$

Proposition 5.17

The number of even permutations in $S_n, n\ge2$, is equal to the number of odd permutations; hence, the order of $A_n$ is $\dfrac{n!}{2}$

Dihedral Groups

We define the nth dihedral group to be the group of rigid motions of a regular n-gon. $D_n$ consists of all finite products of $r$ and $s$

$$D_n={1, r, r^2…r^{n-1}, s, sr, sr^2…sr^{n-1}}$$

6.Cosets and Lagrange’s Theorem

Cosets

Let $G$ be a group and $H$ a subgroup of $G$. Define a left coset of $H$ with representative $g\in G$ to be the set $$gH={gh:h\in H}$$

Lemma 6.3

Let $H$ be a subgroup of a group $G$ and suppose that $g_1,g_2\in G$. The following conditions are equivalent

  1. $g_1H=g_2H$
  2. $Hg_1^{-1}=Hg_2^{-1}$
  3. $g_1H\subset g_2H$
  4. $g_2\in g_1 H$
  5. $g_1^{-1}g_2\in H$

Theorem 6.4

Let $H$ be a subgroup of a group $G$. Then the left cosets of $H$ in $G$ partition $G$. That is, the group $G$ is the disjoint union of the left cosets of $H$ in $G$

Remark 6.5

Let $G$ be a group and $H$ be a subgroup of $G$. Define the index of $H$ in $G$ to be the number of left cosets of $H$ in $G$. We will denote the index by $[G:H]$

Theorem 6.10 Lagrange

Let $G$ be a finite group and let $H$ be a subgroup of $G$. Then $G/H=[G:H]$ is the number of distinct left cosets of $H$ in $G$. In particular, the number of elements in $H$ must divide the number of elements in $G$

Corollary 6.11

Suppose that $G$ is a finite group and $g\in G$. Then the order of $g$ must divide the number of elements in $G$

Corollary 6.12

Let $|G|=p$ with $p$ a prime number. Then $G$ is cyclic and any $g\in G$ such that $g\not=e$ is a generator

Corollary 6.13

Let $H$ and $K$ be subgroups of a finite group $G$ such that $K\subset H\subset G$. Then $$[G:K]=[G:H][H:K]$$

Proposition 6.15

The group $A_4$ has no subgroup of order 6

Theorem 6.16

Two cycles $\tau$ and $\mu$ in $S_n$ have the same length if and only if there exists a $\sigma\in S_n$ such that $\mu=\sigma\tau\sigma^{-1}$

Euler $\phi$-function

The Euler $\phi$-function is the map $\phi:\mathbb{N}\to\mathbb{N}$ defined by $\phi(n)=1$ for $n=1$, and, for $n>1$, $\phi(n)$ is the number of positive integers $m$ with $1\le m < n$ and $\gcd(m,n)=1$

Theorem 6.18 Euler’s Theorem

Let $a$ and $n$ be integers such that $n>0$ and $\gcd(a,n)=1$. Then $a^{\phi(n)}\equiv1(\mod n)$

Theorem 6.19 Fermat’s Little Theorem

Let $p$ be any prime number and suppise that $p\not|a(p$ does not divide $a$). Then $$a^{p-1}\equiv1(\mod p)$$

Furthermore, for any integer $b, b^p\equiv b(\mod p)$

Algebraic Coding Theory

weight

The weight $w(x)$ of a binary code word $x$ is the number of 1s in $x$, $w(x)=d(x,0)$

Theorem 8.17

Let $x$ and $y$ be binary n-tuples. Then $w(x + y) = d(x, y)$

Theorem 8.18

Let $d_{\min}$ be the minimum distance for a group code $C$. Then $d_{\min}$ is the minimum of all the nonzero weights of the nonzero codewords in $C$. That is
$$d_{\min}=\min{w(x):x\not=0}$$

Theorem 8.21

Let $\mathbb{M}_{m\times n}$ denote the set fo all $m\times n$ matrices with entries in $\mathbb{Z}_2$. We do matrix operations as usual except that all our addition and multiplication operations occur in $\mathbb{Z}_2$. Define the null sppace of a matrix $H\in\mathbb{M}_{m\times n}(\mathbb{Z}_2)$ to be the set of all binary n-tuples $x$ such that $Hx=0$. We denote the null space of a matrix $H$ by Null$(H)$

Let $H$ be in $\mathbb{M}_{m\times n}(\mathbb{Z}_2)$. Then the null space of $H$ is a group code.

Theorem 8.25

If $H\in\mathbb{M}_{m\times n}(\mathbb{Z}_2)$ is a canonical parity-check matrix, then Null$(H)$ consists of all $x\in\mathbb{Z}_2^n$ whose first $n-m$ bits are arbitrary but whose last $m$ bits are determined by $Hx=0$. Each of the last $m$ bits serves as an even parity check bit for some of the first $n-m$ bits. Hence, $H$ gives rise to an $(n,n-m)$-block code

Theorem 8.26

Suppose that $G$ is an $n\times k$ standard generator matrix. Then $C={y:Gx=y for x\in\mathbb{Z}_2^k}$ is an $(n,k)$-block code. More specifically, $C$ is a group code

Lemma 8.27

Let $H=(A|I_m)$ be an $m\times n$ canonical parity-check matrix and $G=(\dfrac{I_{n-m}}{A})$ be the corresponding $n\times(n-m)$ standard generator matrix. Then $HG=0$

Theorem 8.28

Let $H=(A|I_m)$ be an $m\times n$ canonical parity-check matrix and let $G=(\dfrac{I_{n-m}}{A})$ be the $n\times(n-m)$ standard generator matrix associated with $H$. Let $C$ be the code generated by $G$. Then $y$ is in $C$ if and only if $Hy=0$. In particular, $C$ is a linear code with canonical parity-check matrix $H$

Proposition 8.30

Let $e_i$ be the binary n-tuple with a 1 in the ith coordinate and 0’s elsewhere and suppose that $H\in\mathbb{M}_{m\times n}(\mathbb{Z}_2)$. Then $He_i$ is the ith column of the matrix $H$

Theorem 8.31

Let $H$ be an $m\times n$ binary matrix. Then the null space of $H$ is a single error-detecting code if and only if no column of $H$ consists entirely of zeros

Theorem 8.34

Let $H$ be a binary matrix. The null space of $H$ is a single error-correcting code if and only if $H$ does not contain any zero columns and no two columns of $H$ are identical

Proposition 8.36

If $H$ is an $m\times n$ matrix and $x\in\mathbb{Z}_2^n$, then we say that the syndrome of $x$ is $Hx$

Let the $m\times n$ binary matrix $H$ determine a linear code and let $x$ be the received n-tuple. Write $x$ as $x=c+e$, where $c$ is the transmitted codeword and $e$ is the transmission error. The the syndrome $Hx$ of the received codeword $x$ is also the syndrome of the error $e$

Proposition 8.43

Let $C$ be an $(n,k)$-linear code given by the matrix $H$ and suppose that $x$ and $y$ are in $\mathbb{Z}_2^n$. Then $x$ and $y$ are in the same coset of $C$ if and only if $Hx=Hy$. That is, two n-tuples are in the same coset if and only if their syndromes are the same

Isomorphisms

Isomorphism

If $G$ is isomorphic to $H$, we write $G\cong H$. The map $\phi$ is called an isomorphism

Theorem 9.7

All cyclic groups of infinite order are isomorphic to $\mathbb{Z}$

Theorem 9.8

If $G$ is a cylic group of order $n$, then $G$ is isomorphic to $\mathbb{Z}$

Corollary 9.9

If $G$ is a group of order $p$, where $p$ is a prime number, then $G$ is isomorphic to $\mathbb{Z}_p$

Theorem 9.12

Every group is isomorphic to a group of permutations

Proposition 9.13

Let $G$ and $H$ be groups. The set $G\times H$ is a group under the operation $(g_1,h_1)(g_2,h_2)=(g_1g_1,h_1h_2)$ where $g_1,g_2\in G$ and $h_1,h_2\in H$

External Direct Product

The group $G\times H$ is called the external direct product of $G$ and $H$. Notice that there is nothing special about the fact that we have used only two groups to build a new group. The direct product $$\prod^n_{i=1}G_i=G_1\times G_2…G_n$$ of the groups $G_1,G_2…G_n$ is defined in exactly the same manner. If $G=G_1=G_2…G_n$, we often write $G^n$ instead of $G_1\times G_2…G_n$

9.17

Let $(g,h)\in G\times H$, If $g$ and $h$ have finite orders $r$ and $s$ respectively, then the order of $(g,h)$ in $G\times H$ is the least common multiple of $r$ and $s$

Corollary 9.18

Let $(g_1,…,g_n)\in\prod G_i$. If $g_i$ has finite order $r_i$ in $G_i$, then the order of $(g_1,…,g_n)$ in $\prod G_i$ is the least common multiple of $r_1,…,r_n$

Theorem 9.21

The group $\mathbb{Z}_m\times\mathbb{Z}_n$ is isomorphic to $\mathbb{Z}_{mn}$ if and only if $\gcd(m,n)=1$

Corollary 9.22

Let $n_1,…,n_k$ be positive integers. Then $$\prod^k_{i=1}\mathbb{Z}_{n_i}\cong\mathbb{Z}_{n_1…n_k}$$ if and only if $\gcd(n_i,n_j)=1$ for $i\not=j$

Corollary 9.23

If $$m=p_1^{e_1},…,p_k^{e_k}$$ where the $p_is$ are distinct primes, then

$$\mathbb{Z}_{m_{}}\cong\mathbb{Z}_{p_1^{e_1}}\times…\times\mathbb{Z}_{p_k^{e_k}}$$

Internal Direct Products

Internal Direct Product

Let $G$ be a group with subgroups $H$ and $K$ satisfying the following conditions

  • $G=HK={hk:h\in H,k\in K}$
  • $H\cap K={e}$
  • $hk=kh$ for all $k\in K$ and $h\in H$

then $G$ is the internal direct product of $H$ and $K$

Theorem 9.27

Let $G$ be the internal direct product of subgroups $H$ and $K$. Then $G$ is isomorphic to $H\times K$

Theorem 9.28

The group $\mathbb{Z}_6$ is an internal direct product of subgroups $H_i$, where $i=1,2…n$. Then $G$ is isomorphic to $\prod_iH_i$

10 Normal Subgroups and Factor Groups

Normal Subgroups

A subgroup $H$ of a group G is normal in $G$ if $gH=Hg$ for all $g\in G$. That is,a normal subgroup of a group $G$ is one in which the right and left cosets are precisely the same

Theorem 10.3

Let $G$ be a group and $N$ be a subgroup of $G$. Then the following statements are equivalent

  1. The subgroup $N$ is normal in G
  2. Forall $g\in G, gNg^{-1}\subset N$
  3. For all $g\in G, gNg^{-1}=N$

Factor Groups

If $N$ is a normal subgroup of a group $G$, then the cosets of $N$ in $G$ form a group $G/N$ under the operation $(aN)(bN)=abN$. The group is called the factor or quotient group of $G$ and $N$

Theorem 10.4

Let $N$ be a normal subgroup of a group $G$. The cosets of $N$ in $G$ form a group $G/N$ of order $G/N$

Simple Groups

Groups with nontrivial normal subgroups are called simple groups

Lemma 10.8

The alternating group $A_n$ is generated by 3-cycles for $n\ge3$

Lemma 10.9

Let $N$ be a normal subgroup of $A_n$, where $n\ge3$. If $N$ contains a 3-cycle, then $N=A$

Lemma 10.10

For $n\ge5$, every nontrivial normal subgroup $N$ of $A_n$ contains a 3-cycle

Theorem 10.11

The alternating group $A_n$ is simple for $n\ge5$

11 Group Homomorphisms

Homomorphisms

A homomorphism between groups $(G,\cdot)$ and $(H,\circ)$ is a map $\phi:G\to H$ such that $$\phi(g_1\cdot g_2)=\phi(g_1)\circ\phi(g_2)$$ for $g_1,g_2\in G$. The range of $\phi$ in $H$ is called the homomorphic image of $\phi$

Proposition 11.4

Let $\phi:G_1\to G_2$ be a homomorphism of groups. Then

  1. If $e$ is the identity of $G_1$, then $\phi(e)$ is the identity of $G_2$
  2. For any element $g\in G_1, \phi(g^{-1})=[\phi(g)]^{-1}$
  3. If $H_1$ is a subgroup of $G_1$, then $\phi(H_1)$ is a subgroup of $G_2$
  4. If $H_2$ is a subgroup of $G_2$, then $\phi^{-1}(H_2)-{g\in G_1:\phi(g)\in H_2}$ is a subgroup of $G_1$. Furthermore, if $H_2$ is normal in $G_2$, then $\phi^{-1}(H_2)$ is normal in $G_1$

Kernel

Let $\phi:G\to H$ be a group homomorphism and suppose that $e$ is the identity of $H$. By Proposition 11.4, $\phi^{-1}({e})$ is a subgroup of $G$. This subgroup is called the kernel of $\phi$ and will be denoted by $\ker\phi$

Theorem 11.5

Let $\phi:G\to H$ be a group homomorphism. Then the kernel of $\phi$ is a normal subgroup of $G$

Canonical Homomorphism

Let $H$ be a normal subgroup of $G$. Define the natural or canonical homomorphism $$\phi:G\to G/H$$ by $$\phi(g)=gH$$ This is indeed a homomorphism since $$\phi(g_1g_2)=g_1g_2H=g_1Hg_2H=\phi(g_1)\phi(g_2)$$ The kernel of this homomorphism is $H$

Theorem 11.10 First Isomorphism Theorem

If $\phi:G\to H$ is a group homomorphism with $K=\ker\psi$, then $K$ is normal in $G$. Let $\phi:G\to G/K$ be the canonical homomorphism. Then there exists a unique isomorphism $\eta:G/K\to\psi(G)$ such that $\psi=\eta\phi$

Theorem 11.12 Second Isomorphism Theorem

Let $H$ be a subgroup of a group $G$ (not necessarily normal in $G$) and $N$ a normal subgroup of $G$. Then $HN$ is a subgroup of $G, H\cap N$ is a normal subgroup of $H$, and $$H/N\cap N\cong HN/N$$

Theorem 11.13 Correspondence Theorem

Let $N$ be a normal subgroup of a group $G$. Then $H\mapsto H/N$ is a one-to-one correspondence between the set of subgroups $H$ containing $N$ and the set of subgroups of $G/N$. Furthermore, the normal subgroups of $G$ containing $N$ correspond to normal subgroups of $G/N$

Third Isomorphism Theorem

Let $G$ be a group and $N$ and $H$ be normal subgroups of $G$ with $N\subset H$. Then $$G/H\cong\dfrac{G/N}{H/N}$$

1 / 1