搜索
北京工业大学2013—2014学年第二学期《算法设计与分析》期末考试试卷第1页共7页北京工业大学2014——2015学年第二学期算法设计与分析期末考试模拟试卷A卷考试说明：承诺：本人已学习了《北京工业大学考场规则》和《北京工业大学学生违纪处分条例》，承诺在考试过程中自觉遵守有关规定，服从监考教师管理，诚信考试，做到不违纪、不作弊、不替考。若有违反，愿接受相应的处分。承诺人：学号：班号：。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。注：本试卷共三大题，共6页，满分100分，考试时答案请写在试卷空白处。卷面成绩汇总表（阅卷教师填写）题号一二三总成绩满分得分一、算法时间复杂性问题（共30分）Part1.TheTimeComplexityOftheAlgorithmTest1、试证明下面的定理：[12分](1)如果f(n)=O(s(n))并且g(n)=O(r(n))，则f(n)+g(n)=O(s(n)+r(n))(2)如果f(n)=O(s(n))并且g(n)=O(r(n))，则f(n)*g(n)=O(s(n)*r(n))1.ProvethefollowingTheorem[12marks](1)iff(n)=O(s(n))andg(n)=O(r(n)),toprovef(n)+g(n)=O(s(n)+r(n))(2)iff(n)=O(s(n))andg(n)=O(r(n))，toprovef(n)*g(n)=O(s(n)*r(n))得分北京工业大学2013—2014学年第二学期《算法设计与分析》期末考试试卷第2页共7页2、已知有如下的断言：f(n)=O(s(n))并且g(n)=O(r(n))蕴含f(n)-g(n)=O(s(n)-r(n))请你举出一个反例。[8分]2.KnownasthefollowingassertionIff(n)=O(s(n))andg(n)=O(r(n))，thenf(n)-g(n)=O(s(n)-r(n))。Pleaseciteacounter-example[8marks]3、假设某算法在输入规模为n时的计算时间为：T（n）=3*2n，在A型计算机上实现并完成该算法的时间为t秒，现有更先进的B型计算机，其运算速度为A型计算机的256倍。试求出若在先进的B型机上运行同一算法则在t秒内能求解输入规模为多大的问题？[10分]3.Assumethatinthecaseoftheinputsizeisn,thecomputingtimeofthealgorithmrequiredisT（n）=3*2n.ItwouldtaketsecondstoimplementthealgorithmonComputerA.ComputerBismoreadvanced.TheoperationabilityofComputerBis256timesofComputerA.IfthesamealgorithmrunningonComputerB,pleasefindouttheinputsizesothatthealgorithmwouldsolveintseconds.[10marks]北京工业大学2013—2014学年第二学期《算法设计与分析》期末考试试卷第3页共7页二、简答题（本题共30分）Part2.BriefAnsweringQuestions.[30marks]1、对计算复杂性的研究能够使人们弄清所求解问题的固有难度，并得出评价某类算法优劣的准则，用以指导设计出更高效的算法。试用简短的语言说明“建立一个问题的复杂性的下界要比确定它的上界困难得多！”。[7分]1.Researchonthecomputingcomplexitycanmakepeopleunderstandtheinherentdifficultyofsolvingtheproblem,andgettheguidelinestoevaluatethealgorithmswithwhichcouldguidethedesignofmoreefficientalgorithms.Usebriefdescriptiontoillustrate“Itismuchmoredifficulttoestablishalowerboundforthecomplexityoftheproblemthantodetermineitsupperbound”.[7points]2、满足何种性质的问题被称为NP完全问题？请简述研究NP完全问题的意义；得分北京工业大学2013—2014学年第二学期《算法设计与分析》期末考试试卷第4页共7页[8分]IfaproblemiscalledNP-completeproblem,whatpropertiesshouldittomeet?PleasedescribethesignificanceofstudyingNP-completeproblems[8marks]3、“当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质”。问题的最优子结构性质是该问题可用动态规划算法求解的基本要素。(1)试简要阐述“论证某一问题具有最优子结构性质”时的一般方法；[8分](2)试证明0/1背包问题满足最优子结构性质；[7分]即证明：如果（x1,x2,...,xn）是所给0-1背包问题的最优解，则(x1,x2,...,xn-1)是下列子问题的最优解。3.Iftheoptimumsolutionoftheproblemcontainsitssubproblem’soptimumsolution,thenwecallthattheproblemcontainsapropertyofoptimalsubstructure.ThispropertycanbeanessentialelementofusingDynamicprogrammingalgorithmtosolvetheproblem.(1)Brieflydescribethegeneralapproachwhenwedemonstrateaproblemcontainstheoptimalsubstructure.[8marks](2)Provethatthe0/1knapsackproblemmeetsthepropertyofoptimalsubstructure.[7marks]Astoprovethatif（x1,x2,...,xn）istheoptimumsolutionofthegiven0/1knapsackproblem,then(x1,x2,...,xn-1)isthetheoptimumsolutionoffollowingquestion.北京工业大学2013—2014学年第二学期《算法设计与分析》期末考试试卷第5页共7页三、算法设计与分析问题（2题共40分）Part3.AlgorithmDesignandAnalysis[atotalof40marks]1、TSP问题的动态规划算法（20分）所谓TSP问题是指旅行商要去n个城市推销商品，其中每个城市到达且仅到达一次，并且要求所走的路程最短（该问题又称货郎担问题、邮递员问题、售货员问题等）。请用数学语言对该TSP问题加以抽象，在此基础上给出动态规划求解该问题的递归公式。要求对所给公式中的符号意义加以详细说明，并简述算法步骤。1.DynamicprogrammingalgorithmfortheTSPproblem[20marks]TSPproblemmeansthatthetravelingsalesmanwilltraveltoncitiestosellgoods,eachcitymustbearrivedandonlyonce,andalsoberequiredtotaketheshortestroute.PleaseuseabstractmathematicallanguagetodescribetheTSPproblem,andonthebasisofthis,usedynamicprogrammingmethodtogivetherecursiveformulaoftheproblem.Youshoulddescribethemeaningofthesymbolsintheformulaindetailandgiveabriefdescriptionforthealgorithmsteps.得分北京工业大学2013—2014学年第二学期《算法设计与分析》期末考试试卷第6页共7页2、广义背包问题（20分）广义背包问题的描述如下：给定载重量为M的背包和n种物品，每种物品有一定的重量和价值，现在需要设计算法，在不超过背包载重量的前提下，巧妙选择物品，使得装入背包的物品的总价值最大化。规则是，每种物品均可装入背包多次或不装入（但不能仅装入物品的一部分）。请用数学语言对上述背包问题加以抽象，在此基础上给出动态规划求解该问题的递归公式。要求对所给公式中的符号意义加以详细说明，并简述算法步骤。2.Generalizedknapsackproblem[20marks]TheDescriptionofgeneralizedknapsackproblemasfollow:Therearenkindofitemsandapackage.TheloadingweightofthepackageisM.Eachitemhasacertainweightandvalue.Nowdesignthealgorithmtomeetthefollowingrules:Inthepremiseofnotovertheloadingweight,pleasechoosetheitemscleverlysothatthetotalvalueoftheloadeditemscanbemaximum.Eachkindofitemscanbeloadedrepeatedlyornotbeloaded(buteachitemcannotbeloadedapartofit).北京工业大学2013—2014学年第二学期《算法设计与分析》期末考试试卷第7页共7页Pleaseuseabstractmathematicallanguagetodescribethisproblem,andonthebasisofthis,usedynamicprogrammingmethodtogivetherecursiveformulaoftheproblem.Youshoulddescribethemeaningofthesymbolsintheformulaindetailandgiveabriefdescriptionforthealgorithmsteps.