算法考试题

1.什么是数问题？给定判定问题，若不存在某个定义在Z+上的多项式P(·),使得对任意的都有MAX[I]≤P(length[I])成立.则称问题为数问题[即最大数值不受约束的问题]。2.什么是强NPC问题？假设判定问题属于NP类，且存在多项式函数P(·)。若受P(·)限制的的子问题属于NPC类,则问题为强NP-完全的，简称为强NPC问题。证明题：3.证明多任务排工属于NPC类证：对多任务问题的实例施加如下限制4.证明X3C问题属于NPC类证明：容易验证X3C∈NP。∵猜测一个3元素子集C’，判定是否C’∈C,并且X中的元素出现在C’中一次且仅一次。这显然可在多项式时间内完成。下面将3DM实例多项式时间归约到X3C的相应实例。给出背包问题优化方式1）当p不等于NP证明背包问题没有多项式时间绝对近似算式12{()|1}...,,1,iaAmijAaALaZmZDZAMAXLaimDAAAAAAAijm实例：有限任务集合，任务的加工时间为()，加工任务的机器数为,所有任务完成的最后期限为。询问：是否存在的划分使得。的划分为。3,,,3,333DMWXYMWXYXCSWXYCMDMiffXCXCNPC设的实例为：。由此构造问题的相应实例：。实例中存在完美对集实例中存在严格覆盖。。12()=()2aAaAmLaDLaPAR设，为偶数；取。则变成问题的实例。1111,...,max,{0,1},1(),|()()|nnnjjjjnjjjIPPWWBPxxjnIWxBAKIAIOPTIK:优化形式的背包问题的实例可描述为如下整数规划,其中,...,,为实例中元素的价值与重量,为背包的容量。假设背包问题有多项式时间绝对近似算法,则存在常数使对背包问题的任意实例，都有证明。11'(1),1,':max',{0,1},1(')'|(')(')|{'|1}(')':iiniiiiniiiiPKPinIIPxxinIWxBAIAIOPTIKxinAIIAA令则将变换为另一背包问题实例当算法应用于实例时，也应该有。设为对应于解值的解.显然,这个解也必然是实例的一组可行解。这样，由算法可设计出另一算法2）设计背包问题Ra小于等于2的多项式时间近似算法，并证明之。证明：满足三角不等式化廓设计Ra小于等于2多项式时间近似算法，满足三角不等式化廓问题并证明之证明：设货郎问的题实例I为无向完全图G和距离d(vi,vj)，由G求得最小生成树T。则d(T)OPT(I),其中d(T)为树T中所有边的长度和。∴欧拉回路E的总长度d(E)2OPT(I),由抄近路得到的TSP回路长度不超过d(E)。[∵距离满足三角不等式，∴超近路不会增加回路的长度]∴MST(I)2OPT(I),即RMST21(,),''IGVEGTTGG.对货郎问题任意实例相应的赋权完全图调用最小生成树算法，求出的最小生成树；2.复制最小生成树的每条边,形成欧拉图；3.在中求欧拉回路；4.采用抄近路方法,将欧拉回路变成货郎旅游回路。+1'',{'|1},{'|1}iiIKIIAxinxinI对给定的背包问题的任意实例,将每个元素的价值放大倍,变换成实例；对实例调用算法得到一组解输出作为解答实例的解。(')(')'()=,()=+1+11|'()()|[(')(')]1+1+11'()()'()=()'iiAIOPTIAIOPTIKKKAIOPTIAIOPTIKKPWinAIOPTIAIOPTIAPNP显然有由于背包问题限定，，，均为整数[即，为整数值]，所以。注意到算法为多项式时间算法，由此推出背包问题有多项式时间精确算法，这与矛盾。112211221{(,),(,),...,(,)}//.../211,0()3()=max{()mnnnniinLPWPWPWPwPwPwGALnixxGAIAIGAI算法：求解背包问题将个元素排序得，满足：采用贪心算法，在主次表中，自编号为到编号为的元素,逐个试装入背包,若编号为的元素能装入背包,则取否则取。直到不能装入为止。得到一个可行解,其解值为。取，iax}iPI1n对应的元素装入背包,得到实例的可行解。+111+1111()max2(),()()2()()inf{()|}2rriiiirriiiiiinAAArWBWBOPTIPPPAIOPTIRIAIRIRII设正整数满足,。于是有：，即为背包问题任意实例。画图说明DTM结构写出判断二进制数1010奇偶性过程Q01bq0(q0,0,r)(q0,1,r)(q1,b,l)q1(q2,0,s)(q2,1,s)(q2,b,s)q2(qy,0,s)(qn,1,s)(q2,b,s)①={0,1,b},∑={0,1};②Q={q0,q1,q2,qy,qn}，停机为qy时，回答为偶数，停机为qn时，回答为奇数;③状态转换规则[即DTM程序M]