算法
- 有限条指令的序列
- 输出个数大于0
对所有的有效输入停机的Turing机，RAM机等
算法A解问题P：把问题P的任何实例作为算法A的输入，A能够在有限步 停机，并输出该实例的正确的解
平均复杂度：►在指定输入的概率分布下，算法求解输入规模为 $n$ 的实例所需要的平均时间 $A(n)$
规范分析 关注渐进复杂度
实证分析 benchmark
并行算法 与通信开销有关，Amdahl法则 $S=\frac{1}{f+\frac{1-f}{p}}$ ，大多数算法并行加速比与处理器不能达到线性关系。
如果0.5的话，10台处理器都不能加速两倍。
并行计算模型：PRAM，原子GRAM，格网，超立方体；块GRAM，BSP，CGM，LogP
近似算法 近似比反映近似解与最优解之间的差距，是描述近似算法质量的重要指标
常是贪心和随机策略
Basis
O() 为渐进上界，$o$ 取不到
$\Omega()$ 为渐进下界，$\omega$ 取不到
$\Theta$ 为渐进紧确定界
$n! = \sqrt{2\pi n}(n/e)^n (1+\Theta(1/n))=o(n^n)=\Omega(2^n)$
- $\log n! = \Theta(n \log n)$
递归方程求解
- 奇怪的尝试法（猜测+归纳）
- 积分作为近似
- 归纳过程不能用 O，可以尝试加低阶项
- 可以尝试换元
- $T(n)=2T(\sqrt n)+\log n$
- 主定理：$a\ge 1,b>1$ 为常数，$f(n)$ 为函数，$T(n)$ 为非负整数。
若 $f(n) = O(n^{\log _ba - \epsilon}),\epsilon>0$ ，则 $T(n)=\Theta(n^{\log_b a})$
若 $f(n)=\Theta(n ^{\log _b a})$ ，则 $T(n)=\Theta(n^{\log_b a} \log n)$
若 $f(n) = \Omega(n^{\log _ba+\epsilon}),\epsilon>0$ ，且对于常数 $c$ 和充分大的 $n$ 有 $a f(n/b)<c\ f(n)$ ，则 $T(n)=\Theta(f(n))$
但是比如 $n \log n$ 不能用主定理。
生成函数解递推式
- 部分分式分解之类的算法
分治算法
- 数逆序对
- 芯片测试
- SELECT算法 BFPRT算法
- 每次选 5 个一组，每组找中位数
- 最近点对算法【只有最近11个是有价值的】
- 整数乘法
- 多项式乘法（卷积计算）
动态规划
- 受控制的暴力，强大而简洁的算法设计技术和运筹学方法
- 最优子结构 问题的最优解蕴含着 子问题的最优解
- 背包问题的判定是 NP 完全的，但存在近似解法，最优值相差不超过 $0.01\%$
树分解
- 把图分解成树
- ►对于每个顶点 v∈V，存在节点 i∈N 使得 v∈χ(i)。
- ►对于每一条边 (v, w) ∈ E，存在一个 i∈N 且 v∈χ(i) 且 w∈χ(i)。
- ►对于每个 i, j, k∈N：如果 j 位于 i 和 k 之间的路径上，则 χ(i) ∩ χ(k) ⊆ χ(j)。
- 等价地，任意 v∈V 在 T 中对应的节点形成一棵子
- 树宽是最大节点的节点个数。
可以用状态压缩进行DP，从而求最大独立集（如果是弦图，可以记录整个块云云）
Reinforcement Learning which in fact is sometimes called approximate dynamic programming.
贪心算法
- 活动选择问题
- 证明：归纳
- 归纳基础：证明存在包含活动 1 的最优解
- 归纳步骤：假设按照算法前 k 步选择都存在对应的最优解， 证明第k+1步选择也存在对应的最优解
- 最优装载
- 最小延迟调度（最大延时最小）
- 直接交换论证
- 解没有逆序，那么最大延迟就是相同时间最后一个被调度的。
- 如果最优调度存在逆序，那么交换逆序之后还是最优。
- 最优缓存调度
- FF算法：最远访问替换。
- 证明考虑，最优调度策略，和 FF 算法的出来的调度策略。
- 假设这两个算法的前 $j$ 步相同，第 $j+1$ 步为 $d$，最优策略收回 $f$，FF算法收回 $e$
- 考虑最优策略，构造策略S’，这一步收回e，证明S’不比S劣
- 由于 $S’$ 和 $S$ 第一个不一样的地方
- 如果是访问 $f$，考虑现在收回的元素，通过构造，把两个调度算法的内存变得一样
- 如果是访问 $g$ ，并且不是 $e,f$，注意到 $S’$ 此前收回了 $e$，保留了 $f$，而 $S$ 此前保留了 $e$
- 那么 $S$ 收回了 $e$，留下了 $g$ 。
- 只需要让 $S’$ 是收回 $f$，并且保留 $g$，就能让两个一样了。
- 也就是最优缓存调度。
- 【LRU算法的竞争比是 $k$】
- 找零钱问题
- 虽然贪心法是不对的，但是什么时候贪心法的正确性能够得到保证？
- 如果 $w{k+1} + G_k(\delta) \le pw_k , \delta = pv_k-v{k+1}$ 即最小余量。
- Huffman，Prim，Kruskal，Dijkstra
- Huffman证明：
- 一定是最小的两个先合并。
- 然后可以归纳成子问题。
- Kruskal证明
- 如果有最优解，考虑最小权值的边，如果不是全局最小的，可以通过替换达到更优解
拟阵理论
- 矩阵的所有行组成集合 $S$
- 集合 $ℓ$ 的每个元素都是 $S$ 的一个非空子集合，包含若干线性无关（独立）的行
- $M = (S, ℓ )$ 是拟阵，由于它满足
- $S$ 是一个有穷集合
- 遗传性：如果 $B\in ℓ,A\subseteq B$ 则 $A\in ℓ$。
- 交换性：如果 $A\in ℓ , B \in ℓ , |A| < |B|$ ，则存在 $x\in B-A$，$A\cup \set x \in ℓ$
- 扩张：保持独立性
- 极大独立子集
- theorem：拟阵中所有极大的独立子集的大小都相同
- 加权拟阵：如果有加权函数 $w$，$w(x) \to R^+,x \in S$
- 单位时间任务调度问题：关键是考虑如何证明交换性。
分支限界
- 搜索空间：一棵树，每个节点对应了部分解向量，可达的树叶对应了可行解。
- 必要条件：多米诺性质【只要不合法了，接下来就一定不合法】
- 平均效率估算：Mente Carlo方法
- 随机找一条路径，假设其它分支与随机选出的路径一样。
- 计数搜索树的点数。
物品无限的背包问题
求解非凸优化
凸优化几乎总有全局最优解的高效算法，分支限界是非凸优化的一种全局优化方式。
非启发式方法：维护目标函数全局的可证明的上界和下届，当能确认 $\epsilon$ 次优性时终止运行。
- EE364b：运气好的时候效果还不错。
求上界方法：任取一个点求目标函数值，局部优化方法
求下界方法：凸松弛 (convex relaxation)，对偶性，Lipschitz界或其他下界
基本思路
- 可行集划分成凸的子集，分别求上下界，形成全局上下界
- 两者足够接近时终止算法；或者细化划分
最大团问题
- 圆排列问题
- 连续邮资问题
- SAT && CDCL (Conflict Driven Clause Learning)
Amortized analysis
- aggregate method
- accounting method
- potential method
- 平摊代价i = 实际代价i + $\phi(Di) - \phi(D{i-1})$
- 要求任意的i , $\phi(D_i) \ge \phi(D_0)$，可以思考成记账法。
move-first-front算法- 不会比最优策略的四倍还要差。
- 定义势函数为：相对于最优策略的两倍逆序对数。
- 考虑 A 交换元素前，势的变化，以及交换元素后势的变化。
Linear Programming
单纯形不考
标准型：最小化目标函数，等式约束，常数非负，变量非负。
如果标准形有可行解，则必有基本可行解
- 否则，考虑一个可行解，存在线性相关的一些列
- 把这些列根据线性无关的那个系数使劲往非零元素上加，等式约束会一直满足
- 但是大于等于零的约束可以差不多减少一个。
- 一直减少，就出现基本可行解了
如果有最优解，则存在基本可行解是最优解
- 因为是最优解，所以周围不比他大
- 由此可以推出 $\sum c_j \lambda_j = 0$
- 从而另一个也是最优解（过于抽象，此处忽略，但是不考）
构造初始基本可行解
- 引入 $m$ 个松弛变量，初值设为 $b_i$
使用bland规则，不会出现循环。
对偶：拉格朗日乘子法推导即可