1、算法分析与设计试卷 2008 冬, 计算机科学系姓名: 学号: 专业:一. 翻译并解释以下专业词汇: （21 分） 1. Dynamic programming2. Candidate solutions3. Transformation4. Greedy algorithms5. Instances6. Intractability7. Optimization problems二. 请回答以下问题: （32 分）1. 为什么说在算法的时间和空间关系上, 时间是决定性因素(dominant factor)?2. 我们通常所说的有效 (efficient) 算法或实际可行算法是指何种算法?3.
2、 字符串的子串 (substring) 和 子序列 (subsequence) 有何不同?4. 完整的动态规划方法由哪三部分组成？通常，我们描述一个动态规划算法只需要给出哪一部分内容？5. 每一个 NP 问题都是难解的吗?6. 如果从问题 1 多项式时间归约为问题问题 2, 说明问题 1 比问题 2 难还是简单?7. NP-hard 问题一定是 NP 问题吗？ 如何证明一个问题是 NP-hard？8. 一个最小化问题的近似比为 C 的相对近似算法可以给我们什么样的保证?三. （12 分）1. 对于任何正整数 n 以下算法计算 m= (1in )i. 其时间复杂性几何? 是多项式时间的吗?m=0
3、For i=1 to n do m=m+iEndfor Output m2. 以下算法依据公式 (1in )i=n(n+1)/2 计算同样的的问题，它的时间复杂性又是多少？m= n(n+1)/2Output m四. 画出字符串 S=abbababb 的后缀树(suffix tree).（9 分）五. 关于 NP-Completeness： （12 分）1. 写出通常证明一个问题 是 NP-complete 的过程 .2. 论述使用限制（restriction）技术证明 NP-completeness 的合理性。3. 分别用限制技术和非限制技术两种方法证明如下问题的 NP-completenes
4、s。Hitting SetInstance: Collection C of subsets of a set S, positive integer K. 集合 S 上的一些子集的集合 C， 及正整数 K。Question: is there a subset SS with |S|K and such that S c for every cC?是否存在 S 的子集 S满足| S|K 并且对 C 中每一个 cC 有 S c ？六. 关于近似算法： （14 分）1. 优化形式的划分问题叙述为：将 n 个正整数划分 k 组，使得每一组的成员之和相同,要求 k1 且达到最小。 （假设问题总有 k
5、n 的解）(1). 证明该问题是 NP-hard 问题(2). 证明该问题不存在多项式时间近似比3/2 的近似算法。2. 背包问题的优化版本可如下描述：KNAPSACKInstance: 项目集 U，总投资额度 BZ+，对每个项目 uU 有所需投资 s(u)Z+ 和预计收益 v(u) Z+ 两项指标， 其中 s(u) B。Objective: 求 UU 使得 uU s(u) B 并且 uU v(u) 达到最大。证明对于该问题不存在多项式时间绝对近似算法。3. 证明以下算法是对以上背包问题的一个性能比为 2 的近似算法。i. 将 U 中项目按照收益/投资比率从大到小排序，设排序结果为 u1, u2, un, 满足 v(u1)/ s(u1) v(u2)/ s(u2) v(un)/ s(un).ii. U=, i=1，p=0，iii. For i=1 to n doa) If s(ui) B theni. U= Uui, p=p + s(ui), B=B - s(ui)b) Endif2. EndForiv. 求出满足 v(uj)=max v(u1), v(u2), v(un) 的整数 jv. If P v(uj) then U=ujvi. Output U
