还 行 吧,是最后一门考试了。
选择题回来了,不像上个学期全是大题。
选择题
不少选择题都是几年前考过的原题,下面只给印象比较深刻的几道
- n 为大于 4 的素数 ⇒ B(n) = [2, n-2] 的等价命题是?
- 给了四个环,问经过了两个主动轮之后状态相同的是哪一对。不知道主动轮是啥的话,这题答对的概率就是 25%。
- 巧合的是,我也忘了主动轮到底是什么。所以复习的时候,分布式那两个下界证明就算看不下去,没见过的概念也得拿出来确认一下。
简答题
- 把同步环上 O(n) 的非均匀算法改成均匀的(假设每 phase 可以处理 k 条消息)。证明你的算法的正确性、时间复杂度、消息复杂度。
- 环上选举
- 匿名环上有选举算法吗?为什么?
- 异步环,用向左邻居发 msg 然后等右邻居发回来的算法消息复杂度是多少?Leader 的 ID 有什么特征?
- 异步环上改进 b 的算法(k-邻居),给出算法描述(伪代码/文字描述/流程图均可),以及证明消息复杂度。
- MC 算法执行多少次能把 55%-正确 偏 y0 的算法搞成 95% 正确的?给出详细的论证。
- 团问题怎么把优化问题变成判定问题?怎么规约?规约的时间复杂度?
算法题
- Sherwood 算法,给定 A 的伪代码,写出 B 的。并且给出期望运行时间。
- 最小顶点覆盖问题,要求给出近似比不超过 2 的算法,并证明这一点。给出你的算法的时间复杂度。
- 和某同学复习的时候他考前押到了这题
- 第一眼看过去,似乎应该先按照度数排序,然后依次选择顶点度数最大的点,但是怎么证明近似比呢?事实上,有简单到不需要排序的方法可以解这个问题。