还 行 吧,是最后一门考试了。

选择题回来了,不像上个学期全是大题。


选择题

不少选择题都是几年前考过的原题,下面只给印象比较深刻的几道

  1. n 为大于 4 的素数 ⇒ B(n) = [2, n-2] 的等价命题是?
  2. 给了四个环,问经过了两个主动轮之后状态相同的是哪一对。不知道主动轮是啥的话,这题答对的概率就是 25%。
    1. 巧合的是,我也忘了主动轮到底是什么。所以复习的时候,分布式那两个下界证明就算看不下去,没见过的概念也得拿出来确认一下。

简答题

  1. 把同步环上 O(n) 的非均匀算法改成均匀的(假设每 phase 可以处理 k 条消息)。证明你的算法的正确性、时间复杂度、消息复杂度。
  2. 环上选举
    1. 匿名环上有选举算法吗?为什么?
    2. 异步环,用向左邻居发 msg 然后等右邻居发回来的算法消息复杂度是多少?Leader 的 ID 有什么特征?
    3. 异步环上改进 b 的算法(k-邻居),给出算法描述(伪代码/文字描述/流程图均可),以及证明消息复杂度。
  3. MC 算法执行多少次能把 55%-正确 偏 y0 的算法搞成 95% 正确的?给出详细的论证。
  4. 团问题怎么把优化问题变成判定问题?怎么规约?规约的时间复杂度?

算法题

  1. Sherwood 算法,给定 A 的伪代码,写出 B 的。并且给出期望运行时间。
  2. 最小顶点覆盖问题,要求给出近似比不超过 2 的算法,并证明这一点。给出你的算法的时间复杂度。
    1. 和某同学复习的时候他考前押到了这题
    2. 第一眼看过去,似乎应该先按照度数排序,然后依次选择顶点度数最大的点,但是怎么证明近似比呢?事实上,有简单到不需要排序的方法可以解这个问题。