下列每对问题, 一个是可用多项式时间算法解决的, 一个是NP完全问题 最短和最长简单路径 欧拉回路和哈密顿圈 2-CNF可满足性问题和3-CNF可满足性问题 证书: 如哈密顿圈问题中的|V|个顶点序列, 3-CNF可满足性问题中的一组变量的赋值 可被证明: 已知一个问题的证书, 可以证明此问题 ...

代数编码检错码和纠错码奇偶校验 校验位 parity check bit 不检验多错, 不纠错 最大似然编码 Maximum-Likelihood Decoding 假设收到的n元组被解码成最接近的编码 Block Codes (n, m)-block code: 编码函数$E: \mathb ...

RSA公钥加密系统 公钥$P_A$, 私钥$S_A$ 对于Bob给Alice的加密消息M: 发送方式: Bob取得Alice公钥$P_A$ Bob计算出相应于M的密文$C=P_A(M)$ 接收过程: Alice收到密文C后, 她用自己的密钥$S_A$恢复原始信息: $S_A(C) = S_A ...

整数 第一/第二数学归纳法 良序公理: 每个自然数集的子集都是良定义的, 即有最小元素 数学归纳法可推出良序公理 对于整数a和b, b > 0, 存在唯一的整数q和r, 满足$a=bq+r$, 其中$0\le e<b$. 对于非0整数a和b, 存在整数r和s, 满足 \gcd(a, b) ...

串匹配朴素字符串匹配算法 检测每一个位置开始的字符串是否符合要求. 最坏$\Theta((n-m+1)m)$ Rabin-Karp算法123456789101112131415RABIN-KARP-MATCHER(T, P, d, q)n = T.lengthm = P.lengthh = d^& ...

问题求解3算法导论整理动态规划动态规划方法通常用来求解最优化问题。这类问题可以有很多可行解，每个解都有一个值，我们希望寻找具有最优值（最小值或最大值）的解。我们成这样的解为问题的一个最优解，而不是最优解。 最优子结构：问题的最优解由相关子问题的最优解构成，而这些子问题可以独立求解。 实现： 自顶向下 ...

图论部分整理注：本部分源自ytr和hw的整理，我就加了一点 图的基本定理一、引言图与图模型 图(graph)G是由有限非空集合V及其二元子集E构成,其中V中元素称为顶点(vertex), E中元素称为边(edge)；集合V和E分别称为G的顶点集(vertex set)和边集(edge set)。 如 ...

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in ...