算法分析与设计试卷 - 青岛东软载波科技股份有限公司.doc

《算法分析与设计试卷 - 青岛东软载波科技股份有限公司.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法分析与设计试卷2008冬,计算机科学系姓名:学号:专业:一.翻译并解释以下专业词汇:（21分）1.Dynamicprogramming2.Candidatesolutions3.Transformation4.Greedyalgorithms5.Instances6.Intractability7.Optimizationproblems二.请回答以下问题:（32分）1.为什么说在算法的时间和空间关系上,时间是决定性因素(dominantfactor)?2.我们通常所说的有效(efficient)算法或实际可行算法是指

2、何种算法?3.字符串的子串(substring)和子序列(subsequence)有何不同?4.完整的动态规划方法由哪三部分组成？通常，我们描述一个动态规划算法只需要给出哪一部分内容？5.每一个NP问题都是难解的吗?6.如果从问题P1多项式时间归约为问题问题P2,说明问题P1比问题P2难还是简单?7.NP-hard问题一定是NP问题吗？如何证明一个问题是NP-hard？8.一个最小化问题的近似比为C的相对近似算法可以给我们什么样的保证?三.（12分）1.对于任何正整数n以下算法计算m=∑(1≤i≤n)i.其时间复杂性几何?

3、是多项式时间的吗?m=0Fori=1tondom=m+iEndforOutputm2.以下算法依据公式∑(1≤i≤n)i=n(n+1)/2计算同样的的问题，它的时间复杂性又是多少？m=n(n+1)/2Outputm一.画出字符串S=abbababb的后缀树(suffixtree).（9分）二.关于NP-Completeness：（12分）1.写出通常证明一个问题P是NP-complete的过程.2.论述使用限制（restriction）技术证明NP-completeness的合理性。3.分别用限制技术和非限制技术两种方法证

4、明如下问题的NP-completeness。HittingSetInstance:CollectionCofsubsetsofasetS,positiveintegerK.集合S上的一些子集的集合C，及正整数K。Question:isthereasubsetS’ÍSwith

5、S’

6、£KandsuchthatS’Çc¹FforeverycÎC?是否存在S的子集S’满足

7、S’

8、£K并且对C中每一个cÎC有S’Çc¹F？三.关于近似算法：（14分）1.优化形式的划分问题叙述为：将n个正整数划分k组，使得每一组的成员之和相同,要求

9、k>1且达到最小。（假设问题总有k≤n的解）(1).证明该问题是NP-hard问题(2).证明该问题不存在多项式时间近似比<3/2的近似算法。2.背包问题的优化版本可如下描述：KNAPSACKInstance:项目集U，总投资额度BÎZ+，对每个项目uÎU有所需投资s(u)ÎZ+和预计收益v(u)ÎZ+两项指标，其中s(u)£B。Objective:求U’ÍU使得åuÎU’s(u)£B并且åuÎU’v(u)达到最大。证明对于该问题不存在多项式时间绝对近似算法。3.证明以下算法是对以上背包问题的一个性能比为2的近似算法。i.

10、将U中项目按照收益/投资比率从大到小排序，设排序结果为u1,u2,…,un,满足v(u1)/s(u1)³v(u2)/s(u2)³…³v(un)/s(un).ii.U’=F,i=1，p=0，iii.Fori=1tondoa)Ifs(ui)£Btheni.U’=U’È{ui},p=p+s(ui),B=B-s(ui)b)Endif2.EndForiv.求出满足v(uj)=max{v(u1),v(u2),…,v(un)}的整数jv.IfP