算法分析與設(shè)計試卷

1、算法分析與設(shè)計試卷算法分析與設(shè)計試卷2008冬計算機科學(xué)系計算機科學(xué)系姓名:學(xué)號:專業(yè):一.翻譯并解釋以下專業(yè)詞匯:（21分）1.Dynamicprogramming2.Cidatesolutions3.Transfmation4.Greedyalgithms5.Instances6.Intractability7.Optimizationproblems二.請回答以下問題:（32分）1.為什么說在算法的時間和空間關(guān)系上時間是決定性因素

2、(dominantfact)2.我們通常所說的有效(efficient)算法或?qū)嶋H可行算法是指何種算法3.字符串的子串(substring)和子序列(subsequence)有何不同4.完整的動態(tài)規(guī)劃方法由哪三部分組成？通常，我們描述一個動態(tài)規(guī)劃算法只需要給出哪一部分內(nèi)容？5.每一個NP問題都是難解的嗎6.如果從問題?1多項式時間歸約為問題問題?2說明問題?1比問題?2難還是簡單7.NPhard問題一定是NP問題嗎？如何證明一個問題是N

3、Phard？8.一個最小化問題的近似比為C的相對近似算法可以給我們什么樣的保證三.（12分）1.對于任何正整數(shù)n以下算法計算m=∑(1≤i≤n)i.其時間復(fù)雜性幾何是多項式時間的嗎m=0Fi=1tondom=miEndfOutputm2.以下算法依據(jù)公式∑(1≤i≤n)i=n(n1)2計算同樣的的問題，它的時間復(fù)雜性又是多少？m=n(n1)2Outputm四.畫出字符串S=abbababb的后綴樹(suffixtree).（9分）五.關(guān)

4、于NPCompleteness：（12分）1.寫出通常證明一個問題?是NPcomplete的過程.2.論述使用限制（restriction）技術(shù)證明NPcompleteness的合理性。3.分別用限制技術(shù)和非限制技術(shù)兩種方法證明如下問題的NPcompleteness。HittingSetInstance:CollectionCofsubsetsofasetSpositiveintegerK.集合S上的一些子集的集合C，及正整數(shù)K。Que

5、stion:isthereasubsetS’?Swith|S’|?KsuchthatS’?c??feveryc?C是否存在S的子集S’滿足|S’|?K并且對C中每一個c?C有S’?c??？六.關(guān)于近似算法：（14分）1.優(yōu)化形式的劃分問題敘述為：將n個正整數(shù)劃分k組，使得每一組的成員之和相同要求k1且達到最小。（假設(shè)問題總有k≤n的解）(1).證明該問題是NPhard問題(2).證明該問題不存在多項式時間近似比32的近似算法。2.背包問

6、題的優(yōu)化版本可如下描述：KNAPSACKInstance:項目集U，總投資額度B?Z，對每個項目u?U有所需投資s(u)?Z和預(yù)計收益v(u)?Z兩項指標(biāo)，其中s(u)?B。Objective:求U’?U使得?u?U’s(u)?B并且?u?U’v(u)達到最大。證明對于該問題不存在多項式時間絕對近似算法。3.證明以下算法是對以上背包問題的一個性能比為2的近似算法。i.將U中項目按照收益投資比率從大到小排序，設(shè)排序結(jié)果為u1u2…un滿足