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

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

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

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

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

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

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