Mengzelev's Blog

Mengzelev's Blog

Do not touch fish!

难问题求解学习笔记-随机算法
前言输出为随机变量的算法称为蒙特卡洛算法(Monte Carlo)输出总是正确的但时间复杂度为随机变量的算法称为拉斯维加斯算法(Las Vegas) 概率论理论引入了随机算法$A$与确定输入$x$构成的随机试验。试验可以被描述为概率空间$(S_{A,x},Prob)$,其中$S_{A,x}={C\mid C \text{is a computation (radom run) of } A \text{ on } x}$,$Prob$是$S_{A,x}$上的概率分布。 基础一种新的复杂度度量$Random_A(x)$: 对于所有$A$在$x$上的随机计算中使用的random bits的最...
难问题求解学习笔记-近似算法
概念近似算法是能提供最优化问题的可行解的算法,所提供的解的质量不会与最优解相差太多 形式化定义:$U={\Sigma_I, \Sigma_O, L, L_I, \mathcal{M}, cost, goal}$是一个最优化问题,$A$是$U$的consistent algorithm. 对任意$x\in L_I$, $A$在$x$上的相对误差(relative error)$\varepsilon_A(x)$定义为$$\varepsilon_A(x)=\frac{|cost(A(x))-Opt_U(x)|}{Opt_U(x)}$$对任意$x\in\mathbb{N}$,定义$A$的相对误...
自己看得惯的板子整理
动态规划状态压缩dpdfs版1234567891011121314151617int dfs(int i, int rnd, int status) { int j; if (status == two[num] - 1) return 0; if (f[i][status] > 0) return f[i][status]; int q = 1e9; for (j = num; j > 0; --j) { int temp = 1 << (j - 1); if (j != i &...
os期中复习
应用眼中的OS 操作系统一方面需要提供程序的执行的环境和相应的资源,还要提供和操作系统世界中其他对象交互的方法和约定 并发共享内存多线程 并发定义:一个程序、算法或问题的不同部分乱序或偏序执行而不影响最终结果的能力 程序经历了什么? 编译器优化$\to$顺序丧失 操作系统中断,多处理器、缓存(硬件)$\to$原子性)(all or nothing)丧失 缓存,乱序(硬件)$\to$可见性丧失 互斥评估一把锁的基本准则 所能够完成基本任务:提供互斥性质 锁的分配是公平的:不会有现成想要上锁却永远得不到它 锁的高效的:无等待时性能?多线程同时等待时性能?多CPU每个核的线程都要上锁...
问题求解学习笔记-密码算法
RSA公钥加密系统每个参与者都有一把公钥($P$)和密钥($S$) $\mathcal{D}$表示允许信息的集合,要求公钥与密钥指定一种从$\mathcal{D}$到自身的一一对应的函数。Alice的公钥函数$P_A()$和密钥函数$S_A()$都是$\mathcal{D}$的排列 系统中任何参与者的公钥与密钥都是匹配对,指定函数互为反函数,对任何消息$M\in \mathcal{D}$,有$$M=S_A(P_A(M))$$$$M=P_A(S_A(M))$$ 加密过程 Bob取得Alice的公钥$P_A$ Bob计算出相应与$M$的密文$C=P_A(M)$,并把$C$发送给Alice 当...
算法导论学习笔记-数论算法
输入规模和算数计算的代价给定$k$个整数输入$a_1,a_2,\cdots ,a_k$,如果算法可以在关于$\lg~a_1,\lg~a_2,\cdots ,\lg~a_k$的多项式时间内完成,即算法在关于二进制编码后的输入长度的多项式时间内完成,则称该算法为多项式时间算法 当输入很大时,基本运算也会变得耗时。两个$\beta$位整数相乘需要耗时$\Theta(\beta^2)$.一个$\beta$为整数除以另一个较短整数的商或余数需要耗时$\Theta(\beta^2)$ 基础数论概念整除性与约数你懂的 素数与合数你也懂的 除法定理、余数和等模定理31.1(除法定理): 对于任何整数$a...
问题求解学习笔记-数论基础
数学归纳法你都懂的 辗转相除法(Division Algorithm)定理2.9(辗转相除法): $a,b$为整数,满足$b>0$,则存在唯一的整数$q$和$r$使得$a=bq+r$,此处$0\le r<b$ $a\mid b$: $a$能整除$b$,$b$能被$a$整除 定理2.10: $a,b$为非零整数,则存在整数$r,s$使得gcd($a,b)=ar+bs$. $gcd(a,b)$是唯一的。但$r,s$不唯一 推论2.11: $a,b$为互质的整数,则存在整数$r,s$使得$ar+bs=1$【事实上是当且仅当的关系】 欧几里得算法(The Euclidean Algo...
算法导论学习笔记-字符串匹配
基本知识问题的形式化定义 文本是一个长度为$n$的数组$T[1,…n]$ 模式是一个长度为$m$的数组$P1,…m$ $P$和$T$的元素都是来自一个有限字母集$\Sigma$的字符 若$0\le s\le n-m$,且$T[s+1,…s+m]=P[1,…m]$,则称模式$P$在文本$T$中出现,且偏移为$s$(模式$P$在文本$T$中出现的位置是$s+1$开始的) 如果$P$在$T$中以偏移$s$出现,那么称$s$是有效偏移,否则是无效偏移 字符串匹配问题:找到所有的有效偏移 算法总运行时间=预处理时间+匹配时间 符号和术语 $\Sigma^*$: 包含所有有限长度的字符串的集合 ...
问求学习笔记-群同构基本定理与正规子群
同构(Isomorphisms)定义对两个群$(G,\cdot)$和$(H,\circ)$,若存在一个保群运算的双射$\phi:G\to H$,即对于任意$a,b\in G$$$\phi(a\cdot b)=\phi(a)\circ\phi(b)$$则称$G$和$H$同构(isomorphic),记作$G\cong H$. $\phi$称为同构函数(isomorphism)。 基本定理定理9.6: Let $\phi: G\to H$ be an isomorphism of two groups. Then the following statements are true. $\p...
问求学习笔记-置换群与拉格朗日定理
置换群(Permutation Group)定理5.1:The symmetric group on $n$ letters, $S_n$, is a group with $n!$ elements, wherethe binary operation is the composition of maps. 置换群(permutation group):所有排列的集合$S_n$的一个子集 Cycle NotationA permutation $\sigma\in S_X$ is a cycle of length $k$ if there exite elements $a_1,a_...
Mengzelev
Mengzelev
FRIENDS
Click here