算分 2019期末回忆
by hawkey


一、选择（10）
5题，比较基础。

二、网络流（10）
旅馆里有 n个旅客，每个人有多个喜欢的菜、多个喜欢的房间，求一个能够使最多人满意的
分配菜与房间的方案。
(大概是 POJ 3281 Dining)

三、平摊分析（10）
分别给出使用下列策略的动态表的插入与删除操作的平摊复杂度以及势能函数定义。
(1) 元素满时扩大 1倍空间，元素不足 1/3时减少 1/2空间。
(2) 元素满时扩大 1/3倍空间，元素不足 4/9时减少 1/3空间。

四、随机算法（15）
已知一个问题没有 O(n^2)的有效的Monte Carlo算法，证明这个问题也不存在期望运行时间
为 O(n^2)的 Las Vegas算法。
提示：利用Markov不等式。

五、近似算法（15）
已有一个近似比为 k的求最小匹配的近似算法，设计一个近似比为(1+k/2)的求解满足三角不
等式的 TSP问题的近似算法。

六、NPC证明（15）
证明Monotone SAT是 NPC问题。
Monotone SAT：F的所有析取范式中只有 positive项（没有取否操作），问是否存在一个最
多有 k个 True的成真赋值。
(大概是 https://cs.stackexchange.com/questions/11558/prove-np-completeness-of-deciding-
satisfiability-of-monotone-boolean-formula)

七、虽然题干是 NPC证明，但其实是动归？（另一个考场勘误打印错了 TvT）（35）
题意大概是每个程序分配的缓存空间块数(整数!)与访存丢失率(Cache Miss Rate)有一个曲线，
在每个程序单位时间访存次数相同的情况下，求使得总访存丢失次数最少的每个程序分配的
最佳缓存空间块数。
(1) 两个程序，曲线规则时的分配方案。（曲线分别是直线 CMR1=1-x/10, CMR2=1-x/5）
(2) 两个程序，曲线不规则时的分配方案。（曲线随便画画）
(3) n个程序，曲线不规则时的分配方案。