算法习题PPT课件

教材:1王王晓东,计算机算法设计与分析(第4版),电子工业.2S唐常杰等译,Sipser著,计算理论导引,机械工业.参考资料:3C潘金贵等译,Cormen等著,算法导论,机械工业.4M黄林鹏等译,Manber著,算法引论-一种创造性方法,电子.5刘刘汝佳等,算法艺术与信息学竞赛,清华大学.6LLewis等著,计算理论基础,清华大学.,计算理论与算法分析设计,第一章算法分析题1-1,1-2,1-4,第1章概论,1-1求下列函数的渐近表达式:3n2+10n;n2/10+2n;21+1/n;logn3;10log3n.解:3n2+10n=(n2);n2/10+2n=(2n);21+1/n=(1);logn3=(logn);10log3n=(n);1-2试论O(1)与O(2)的区别.答:没有区别,因为根据定义1=O(2),2=O(1),第1章概论,1-4(1)假设某算法在输入规模为n时的计算时间为T(n)=32n.在某台计算机上实现并完成该算法的时间为t秒.现有另一台计算机,其运行速度是第一台的64倍,那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题?(2)若上述算法的计算时间改进为T(n)=n2,其余条件不变,则在新机器上用t秒时间能解输入规模为多大的问题?(3)若上述算法的计算时间改进为T(n)=8,其余条件不变,那么在新机器上用t秒时间能解输入规模为多大的问题?解:设机器1上t秒能解的问题规模为n1,机器2上t秒能解的问题规模为n2.(1)由t=32n1=32n2/64知,n2=n1+6,所以规模增大6.(2)由t=n12=n22/64知,n2=8n1,所以规模增大7倍.(3)若t8则n1可以任意大,若t1/8则n2可以任意大.,第2章分治,2-8设n个不同的整数排好序后存于T1:n中.若存在一个下标i，1in,使得Ti=i.设计一个有效算法找到这个下标.要求算法在最坏情况下的计算时间O(logn).解:不同整数意味着要么严格递增,要么严格递减若T1:n严格递减,则Tii(Tji蕴含jj)满足二分法条件,可用二分搜索若T1:n严格递增,Tii蕴含ji(Tjj),Tii0蕴含jn时,指跨过第n堆到第(i+len-1)%n堆,仅sum函数需要修改milen=minmik+mi+klen-k+sumi:i+len-1|0kt,则milen=t;silen=k;,输出minmin|1in类似可以打印合并次序由加速原理加速,第3章动态规划,3.数字三角形问题问题描述:给定一个有n行数字组成的数字三角形,如下图所示.试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字和最大.算法设计:对于给定的n行数字组成的三角形,计算从三角形顶至底的路径经过的数字和的最大值.数据输入:由文件input.txt提供输入数据.文件的第1行数字三角形的行数n,1n100.接下来n行是数字三角形各行中的数字.所有数字在099之间.结果输出:将计算结果输出到文件output.txt,文件第1行中的数是计算出的最大值.,输入文件示例input.txt5738810274445265,输出文件示例output.txt30,738810274445265数字三角形,第3章动态规划,动规,两种方式,自顶向下,自底向上自顶向下定义mi,j为从第1行到第i行第j列能得到的最大分数,那么mi,j=ai,j+maxmi-1,j,mi-1,j-1,当ji;=0,当ji或j=0.,1.m2:n=0,m1=a1,1,m0=0,2.对i=2:n3.对j=i:14.若mj-1mj,则mj=mj-15.mj+=ai,j6.输出maxmj|1jn,第3章动态规划,动规,两种方式,自顶向下,自底向上自底向上定义mi,j为从第1行到第i行第j列能得到的最大分数,那么mi,j=ai,j+maxmi+1,j,mi+1,j+1,当ji,1.对j=1:n,mj=an,j,2.对i=n-1到13.对j=1到i4.若mj+1mj,则mj=mj+15.mj+=ai,j,6.输出m1,第四章贪心,1.字符ah出现的频率恰好是前8个Fibonacci数,它们的Huffman编码是什么?将结果推广到n个字符的频率恰好是前n个Fibonacci数的情形.解:根据ah的频率,画出Huffman编码树如右图所以各字符编码为:h:1,g:01,f:001,e:0001,d:00001,c:000001,b:0000001,a:0000000,推广到n个符号的情形.记第i个符号为i,则fi=fi-1+fi-2由数学归纳法易证明sumi=1kfim,是在前m位男运动员已配对的情况下,男运动员i配对其她女运动员的上界定义函数Upb(m,x)=f(m+1,m,x)+f(m+2,m,x)+f(n,m,x).当前m位男运动员已配对的情况下,cs+Upb(m,x)是余下情况配对的上界,由此可以设计剪枝(限制)条件cs+Upb(m,x)bests注1:有的同学没有设计剪枝条件,这不能体现回溯的优势.注2:有同学使用csn,返回2.对j=i:n3.|交换xi,xj,cs+=Pixi*Qxii,4.|若cs+Upb(m,x)bests,5.|若csbests,则bests=cs,6.|backtrace(i+1)6.|cs-=Pixi*Qxii,交换xi,xj,主程序执行backtrack(1)即可,第六章分支限界,在解最大团问题的优先队列式分支限界法中,当前扩展节点满足cn+n-ibestn的右儿子节点被插入到优先队列中.如果将这个条件改为满足cn+n-ibestn右儿子节点插入优先队列仍能满足算法正确性吗?为什么?答:会影响算法正确性.改成大于号会漏掉一些最优解,但是不会降低最优值.所以如果在回溯时要搜索所有最优解,则不能改成大于.如果在回溯时只希望得到最优值和一个最优解可以改成大于.但对分支限界,如果改成大于会造成不能插入第n+1层节点而不能正确结束.注:本教材作者的解答有错误.这个语句出现在当前扩展节点右分支处,此时团顶点数上界是cn+n-i.因为当前n个节点团顶点数是cn,还有n-i个节点没有考虑.作者认为此时上界是cn+n-i+1是错误的.例如,当程序中第一次进循环时,到这里的团顶点数上界就是n-1.,第八章网络流,1.飞行员配对问题描述:第二次世界大战时期,英国皇家空军从沦陷国征募了大量外籍飞行员.由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2名飞行员,其中一名是英国飞行员,另一名是外籍飞行员,在众多的飞行员中,每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合.如何选择配对的飞行员才能使一次派出最多的飞机.算法设计:对于给定的外籍飞行员与英国飞行员的配合情况,找出一个最佳飞行员配对方案,使得皇家空军能派出最多的飞行员.数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数m和n.n是皇家空军的飞行员总数(n0,令w=0p10p10p1,x,y,z(|y|0,|xy|p,w=xyz)令i=0,xz=0p-|y|10p10p1AA非正则语言,计算理论第3章作业,3.2对于识别w|w=u#u,u0,1*的图灵机M1(见左图),在下列输入串上,给出M所进入的格局序列.c.1#1,d.10#11,e.10#10解：,补充说明:没有画出的箭头指向拒绝状态,假设这些箭头都不改写右移且qr是拒绝状态.,c.q11#1,xq3#1,x#q5#1,x#qr1,拒绝,d.q110#11,xq30#11,x0q3#11,x0#q511,x0q6#x1,xq70#x1,q7x0#x1,xq10#x1,xxq2#x1,xx#q4x1,xx#xq41_,xx#x1qr_,拒绝,e.q110#10,xq30#10,x0q3#10,x0#q510,x0q6#x0,xq70#x0,q7x0#x0,xq10#x0,xxq2#x0,xx#q4x0,xx#xq40,xx#q6xx,e.继续xxq6#xx,xq7x#xx,xxq1#xx,xx#q8xx,xx#xq8x_,xx#xxq8_,xx#xx_qac_接受,计算理论第3章作业,3.2对于识别w|w=u#u,u0,1*的图灵机M1(见左图),在下列输入串上,给出M所进入的格局序列.c.1#1,d.10#11,e.10#10解：,(q0,0)=(p,#,R)的状态图表示:,简记为,计算理论第3章作业,3.8下面的语言都是字母表0,1上的语言,以实现水平的描述给出判定这些语言的图灵机:b.B=w|w所包含的0的个数是1的个数的两倍c.C=w|w所包含的0的个数不是1的个数的两倍解:b.构造如下的图灵机M=“对于输入串w,1)从左至右扫描,重复以下步骤直到带上没有0或没有12)从左至右扫描,删除遇到的第一个1.3)从左至右扫描,删除遇到的前两个0,若没有则拒绝.4)若带上既没有0也没有1,则接受;否则,拒绝.”若输入w中0的个数是1的个数的两倍,则停机接受;否则,停机拒绝.所以一方面M的语言是B;另一方面M对所有输入串都能停机,是判定器.补充细节说明:可以针对第一个符号使用不同关于左端标记和删除标记。若第一个符号是0,则可第一次扫描时改写为$,需要删除时改写为!;若第一个符号是0,则可第一次扫描时改写为%,需要删除时改写为*.这样当读到$,!,%,*都表示到了最左端.,计算理论第3章作业,3.8下面的语言都是字母表0,1上的语言,以实现水平的描述给出判定这些语言的图灵机:b.B=w|w所包含的0的个数是1的个数的两倍c.C=w|w所包含的0的个数不是1的个数的两倍解:c.构造如下的图灵机M=“对于输入串w,1)从左至右扫描,重复以下步骤直到带上没有0或没有12)从左至右扫描,删除遇到的第一个1.3)从左至右扫描,删除遇到的前两个0,若没有则拒绝.4)若带上既没有0也没有1,则拒绝;否则,接受.”若输入w中0的个数是1的个数的两倍,则停机接受;否则,停机拒绝.所以一方面M的语言是C;另一方面M对所有输入串都能停机,是判定器.,计算理论第3章作业,3.15b证明图灵可判定语言类在连接运算下封闭.证明:设A和B是图灵可判定语言,则有判定器T和Q使得L(T)=A,L(Q)=B,构造如下的图灵机M=“对于输入串w,设w长度为n,即w=w1w2wn,1)对于i=0到n,2)令x=w1wi,y=wi+1wn,(其中若i=0则x=,若i=n则y=)3)在x上运行T,在y上运行Q,4)若两个都接受,则停机接受.5)停机拒绝.”若w属于AB,则M会停机接受;否则,M会停机拒绝.所以是判定器而且M的语言是AB.证毕,计算理论第3章作业,3.16d证明图灵可识别语言类在交运算下封闭.证明:设A和B是图灵可判定语言,则有判定器T和Q使得L(T)=A,L(Q)=B,构造如下的图灵机M=“对于输入串w,1)在w上运行T,在w上运行Q,2)若两个都接受,则接受;否则拒绝.”若w属于AB,则M会停机接受;否则,M会停机拒绝.所以是判定器而且M的语言是AB.证毕,计算理论第4章作业,4.1对于右图所示的DFAM,回答下列问题，并说明理由a.ADFA?b.ADFA?c.ADFA?e.EDFA?f.EQDFA?解:a)因为M接受0100,所以ADFA.b)因为M不接受011,所以ADFA.c)不符合ADFA的编码,所以ADFA.e)因为M的语言包含0,00等字符串,所以M的语言非空,所以EDFA.f)因为M和M自己语言相同,所以EQDFA.,计算理论第4章作业,4.2考虑一个DFA和一个正则表达式是否等价的问题。将这个问题描述为一个语言并证明它是可判定的。解:一个DFA是否与一个正则表达式是否等价可以表示为如下的语言:A=|M是一个DFA,R是一个正则表达式,满足L(M)=L(R).构造如下的图灵机P=“对输入,M是DFA,R是正则表达式,1)将R转换为等价的NFA,再转换为等价的DFAT,2)构造DFAQ使得L(Q)=(L(M)L(T)c)(L(T)L(M)c)3)检查Q的语言是否空(起始状态是否与某个接受状态连通)4)若不连通,则接受;否则拒绝.”(不连通即为空)若M与R等价,则Q的语言空,P会接受;否则Q的语言非空,P会拒绝.所以P是判定器,而且P的语言是A.证毕补充说明:正则语言对补,交,并都是封闭的,所以L(M)与L(T)的对称差仍正则,计算理论第4章作业,4.3设ALLDFA=|A是一个识别*的DFA.证明ALLDFA可判定.证明:构造如下的图灵机P=“对输入,A是DFA1)标记所有与起始状态连通的状态.2)若所有有标记的状态都是接受状态,则接受;否则拒绝.”若A的所有被标记状态都是接受状态,则所有输入都会被接受,A的语言是*;否则,A的语言不是*.P是判定器,且P的语言是ALLDFA,所以ALLDFA是可判定语言.证毕,计算理论第4章作业,4.15设A=|R是一个正则表达式，其所描述的语言中至少有一个串w以111为子串.证明A是可判定的。证明:构造一个DFAT使得L(T)=w|w以111为子串,构造如下的图灵机P=“对输入,R是正则表达式,1)构造与R等价的DFAQ.2)构造DFAS使得L(S)=L(R)L(T)3)标记S中与起始状态连通的所有状态4)若有接受状态被标记,则接受;否则拒绝.”若S有接受状态被标记,则L(R)与L(T)交非空,A;否则L(R)与L(T)交为空,A.所以P是判定器且L(P)=A.所以A是可判定