eecs376 mid term

分治算法 divide and conquer

正确性证明 Correctness

使用 数学归纳法 (尤其是 强归纳法进行证明)

1. base case 证明: 用一个 trivial 的方法证明 base case 是正确的
2. recursive step: 首先假设前几步返回的都是真的 (也就是在 分治算法里面本层的返回值有效) 然后利用 conquer 步骤的特性证明最终输出是正确的

搜索类算法的正确性分析

如果要用分治算法进行搜索，我们很难直接用归纳法证明递推性质 (因为其他都不符合，并不能说该算法很好的证明了前面的部分) 所以用 invariant 来进行说明 某一部分查找的特性已经被前几层 递归保存了 (即为什么会到这一层递归？一定是前几层没有满足某一个原因，但是由于递归是具有方向选择性的，因此我们会确保某一个部分的 inveriant 能被保证成立) 那么只要证明 本层筛选针对其他没有 被保证的角度也会通过筛选证明即可

时间分析 Runtime Analysis

一般要用到一个递归表达式以及一个时间表达式，然后利用 master theorem 进行证明

2D 平面最近的点查找

动态规划算法 dynamic programming

解决了分治算法中的子分治覆盖问题
全局最优往往是由多个局部最优解组合而成的

算法定义

1. 将目标 定量化, 即将目标变成值
2. 将分析过程变成 递归关系 (包括可以从尾向头思考，每次只思考一层而不是多层协作的问题) 并且分析 base case
3. 明确动态规划的填表方向以及表格尺寸，以及在递归关系下的初始值 (这也要明确填表方向)，以及最终返回值处于表格的位置
4. 看看如何优化本算法到解决相关的其他问题

常见思路

将过程分析反过来，从结果向头进行分析，看最后一步有哪几种可能 (或者最后一个取或者不取) 用递归来说就是到倒数几步的结果 + 最后一步的价值
注意递归函数输入值和 value 不一定有相同的单位, 例如输入值可以是 target 的值而返回的可能是 满足的集合数量
不选取最后一步的 case 下, 可能也会有多种情况进行取最好 (这里也涉及了分类讨论的情况)

最大递增子串

图的最短路径 - SSSP 类问题

引理

1. 从节点 s 到节点 t 的最短路径经过了 v 那么 这里 s 到 v 和 v 到 t 的路径也是最短路径 (从长推导短)
2. 假设没有负 cycle 存在

思路

$\text{dist}^{(i)}(s,v) = \min_{(u,v)}\{\text{dist}^{(i-1)}(s,u) + w(u,v)\}$

即利用最后一步选择角度完成了动态规划

i 的作用

如果没有这个 potential value i, 那么会存在 dist(s,v) 需要 dist(s,t) 而后者并没有计算，从而也可能会需要 dist(s,v) 进行转算，也就是说二者可能对称, 那么我们需要设计一个额外量 $i$ 来逐步减少防止无尽循环, 表现在图中就是中间步骤长.

base case

如果 i == 0, 那么如果 s!=v, 说明 0 步能够到达，trivially 是错误的，我们这里设value 结果为 $\infty$; 如果 s == v, 说明 本身就在，那么结果是 0

dp 表格 (Bellman-Ford, BF)

用一个 2d 表格来存储，一个维度存 i, 一个维度存 s 到 v 的最短路径权值
base: table[0],[0] = 0, table[0],[v] = $\infty$ for all v != 0
那么对于每一个 i 从 0 到 n-1 (n 为总点数量) 进行遍历, 各自遍历每一个节点 v, 来存储从出发点 s 到 v 经过对应 i 步的最短路径，从这个逻辑出发，我们对最后一步的选取为上一步加上路径权值中的最小值，即
table[i],[v] = min{table[i-1],[u] + w(u,v)} for all u,v in E
当然从这一步我们也可以看出 i 需要对 i-1 的所有值
时间复杂度是 $O(mn)$, 其中 m 为边数，n 为点数
注意这个表格有可能不会填满，因此时间复杂度并不是简单的 $O(n^2)$, 由于每一步遍历的可能性数量取决于边的数量，即 $O(m)$ 再加上重复 i 次，因此是 $O(mn)$
最终的结果是 table[n],[v] 即为 s 到 v 的最短路径

APSP 问题

查找任意两个节点之间的最近距离
由于相较于 SSSP 问题，我们这里的出发点并不固定，所以我们需要用一个 3d 数组存储，新增的维度用来记录出发节点, 那么时间复杂度从简单方向想就是 $O(mn^2)$

Floyd-Warshall 算法

贪心算法

算法思路

1. 用贪心算法求局部最优解并且标记为 $ALG := \{s_1, s_2, \cdots s_n\}$ 这里顺序要和最优解集的结果保持一致
2. 对比 ALG 解与最优解 OPT 之间的区别, 找到第一个不同的元素 $s_{diff}\in ALG, f\in OPT$ 并判断二者能不能交换, 即构建新解 $OPT' :=OPT \cup s_{diff} \backslash f$
3. 证明新解是 valid 且 no worse than OPT
4. 递推将剩下所有不同的解都换成 OPT 从而证明整个 ALG 的解是最优解
5. 最后一步往往要说明 ALG 会等于最优解 (因为 ALG 每一步都大于等于 OPT 且 OPT 本身是最优解，那么对比之下 ALG 也是最优解)

计算理论定义

语言

• alphabet: 一个非空的有限符号集合
• string: 通过某个 alphabet 组成的有限个元素的集合
  • all string 集合 $\Sigma^*$
• language: 一个 string 的集合

Deterministic Finite Automaton

• 5 tuple: $(Q, \Sigma, \delta, q_0, F)$
  • Q: 状态
  • $\Sigma$: alphabet
  • $\delta$: transition function, 从一个状态到另一个状态的转移
    • $\delta: Q \times \Sigma \to Q$
    • 可以表述为一个矩阵
  • $q_0$: 初始状态
  • F: 终止状态集合
• DFA 的语言: 表示接受的语言集合，我们也称 DFA M decides this language, M accept strings in L(M), reject strings not in L(M)

Turing Machine 图灵机

图灵机是一个 7 tuple 的定义

• 7 tuple: $(Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$
  • Q: 状态
  • $\Sigma$: 输入 alphabet
  • $\Gamma$: tape alphabet, $\Sigma \subseteq \Gamma$
  • $\delta$: transition function, $\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$
  • $q_0$: 初始状态
  • $q_{accept}$: 接受状态
  • $q_{reject}$: 拒绝状态
    图灵机对于一个 string 的处理结果有三种可能: accept, reject 或者 loops

Church-Turing Thesis

一个函数可以被高效的计算当且仅当其可以被图灵机decide

语言

L(M) 表示 $L(M) = \{w | M \text{ accepts w}\}$

图灵机的可决定性

定义1

如果我们称一个图灵机可以 decides a language L 那么 1. M accept $x\in L$ 2. M reject $x\notin L$

等价定理

1. M halts on all inputs
2. $x\in L$ 且 M(x) accept

图灵机的可识别性

我们称一个图灵机 recognize 一个语言，当且仅当

1. M accept $x\in L$
2. M reject or loop $x\notin L$

等价定理

$x\in L$ 当且仅当 $M(x)$ accept

可数性

单射

函数 $f: A\to B$ 是单射当且仅当对于任意 $a_1, a_2 \in A$ 如果 $f(a_1) = f(a_2)$ 那么 $a_1 = a_2$
一般用 one-to-one map 来表示单射关系

可数集

一个集合是可数的当且仅当它可以和自然数集一一对应 (one-to-one)
也就是说集合可数等价于存在一个从 该集合 S 到自然数集合 $\mathbb{N}$ 的单射关系 且有 $|S| \le |\mathbb{N}|$

引理1

集合 S 可数当且仅当 存在一个 枚举 enumeration $S:=\{s_1, s_2, \cdots\}$ 使得 S 中的每个元素至少出现一次
这个引理可以帮我们免去定义从 S 到 $\mathbb{N}$ 的映射，因为我们可以直接用枚举来表示

引理2

在任意一个 alphabet $\Sigma$ 下有限集合 $\Sigma^*$ 是可数的 (即所有 string 可以被 enumerated)

引理3

图灵机集合是可数的

不可数的证明 diagonalization

我们可以用对角线方法来证明 $\mathbb{N}$ 和 $(0,1)$ 之间的不等势性
这将用到上述的引理1: 我们假设存在一个 (0,1) 的枚举 $\{r_1,r_2\cdots\}$，那么每个实数必然都会出现在这个枚举中，那么我们令一个集合 $S$ 的每个元素 $s_i$ 的第 i 个元素不等于现有的排列 $r_i$ 的第 i 个元素，那么这个集合必然不在枚举中但是在 (0,1) 的空间中，因此我们有问题

用对角线法则证明 不可决定语言

引理1

所有语言的集合是不可数的

引理2

对于每个 alphabet 都会存在一个 不可决定的 language

language集合(包括图灵机集合) 不可决定的对角线证明方法

定义一个 2d 表格，横坐标表示当前 alphabet 组成的 string 枚举 (注意我们已经在引理说明了 alphabet 的 $\Sigma^*$ 集合是可数的), 纵坐标表示语言的枚举 (这里是假设可以数用于归谬)
关注表格的对角线，我们令 $b_{ii}$ 表示第 i 个 string $s_i$ 是否在第 i 个 language $L_i$ 中，那么我们可以构建一个新的 string $s$ 使得 $s_i = 1 - b_{ii}$ 那么这个 string 一定不在表格中，或者说构建语言 $L':=\{s_j: b_{jj} = 0\}$ 那么这个语言一定不在表格中，这个语言不可数 (对于图灵机问题而言这个语言是无法决定的, 因为对于任意一个 图灵机其对应坐标的字符串的识别结果是反的)

自然不可决定语言

Barber language

定义一个语言 $L_{barber}:=\{\langle M\rangle: M \text{ is a TM that does not accept itself}\}$ 那么我们可以证明这个语言是不可决定的

Acceptance language

定义一个语言 $L_{accept}:=\{(\langle M\rangle, x): M \text{ is a TM that accepts w}\}$ 那么我们可以证明这个语言是不可决定的

Halting language

定义一个语言 $L_{halt}:=\{(\langle M\rangle ,w): M \text{ is a TM that halts on w}\}$ 那么我们可以证明这个语言是不可决定的

图灵归约 Turing Reduction

定义

对于一个语言 $A$ 和 $B$ 如果存在一个图灵机 $M$ 可以解决 $A$ 当且仅当 $M$ 可以解决 $B$ 那么我们称 $A$ 可以归约到 $B$ 也就是 $A \le_T B$

逻辑推导方向

• 如果 $A \le_T B$ 那么 $B$ 是可决定的那么 $A$ 也是可决定的
• 如果 $A \le_T B$ 那么 $A$ 是不可决定的那么 $B$ 也是不可决定的

可识别性 Recognizability

定理1

语言 $L_{Halt}$ 是可识别的

定理2

对于语言 $L_1,L_2$ 可识别，那么 $L_1 \cup L_2$ 也是可识别的；$L_1 \cap L_2$ 也是可识别的

定理3

语言 $L$ decidable 当且仅当 $L$ 可识别且 $\overline{L}$ 可识别

定理4

如果一个语言undecidable, 且 $\overline L$ recognizable 那么 $L$ 是不可识别的; 如果 L undecidable 那么至少 $L$ 或者 $\overline{L}$ 是不可识别的

corecognizable

如果一个语言的补集是可识别的，那么这个语言是 corecognizable

Dovetailing 鸽尾法

我们可以用 dovetailing 方法来证明一个语言是可识别的，即同时运行所有可能的图灵机，如果有一个图灵机接受了那么我们就接受 (以防止某些 loop 的问题出现)