算法导论复习资料

1、算法导论复习资料软件0902為超算法导论复习资料一、选择题：第一章的槪念.术语。二、考点分析：1、复杂度的渐进表示，复杂度分析。2s正确性证明。夸点：1)正确性分析(冒泡，归并，选择)；2)复杂度分析(渐进表示()，Q, ,替换法证 明，先猜想，然后绐出递归方程)。循环不变性的三个性质：1) 初始化：它在循环的第一轮迭代开始之前，应该是正确的；2) 保持：如果在循环的某一次迭代开始之前它是正确的，那么，在下一次迭代开始之前，它也 应该保持正确；3) 当循环结束时，不变式给丁我们一个有用的性质，它有助于表明算法是正确的。插入排序算法：INSERTION-SORT(A)1 for j2 to le

2、ngth A2 do key Aj3 a Insert Aj into the sorted sequence A1、 j - 1.4 i j 15 while i 0 and Af key6 do Ai + 1 Ai7 i i- 18 Ai + 1 key插入排序的正确性证明：课本11页。归并排序算法：课本17页及19页。归并排序的正确性分析：课本20页。3、分治法(基本步骤，复杂度分析)。一许多问题都可以递归求解誇点:快速排序，归并排序，渐进排序，例如：12球里面有一个坏球，怎样用最少的次数找出 来。(解：共有24种状态，至少称重3次可以找出不同的球)不是誇点：线性时间选择，杲接近点对，斯

3、特拉算法求解。解：基本步骤：一、分解：将原问题分解成一系列的于问题；二、解决：递归地解各于问题。若于问题足够小，则直接求解；三、合并：将于问题的结果合并成原问题的解。复杂度分析：分分治算法中的递归式是基于基本模式中的三个步骤的，T(n)为一个规模为n的运 行时间，得到递归式T(n)=Q(l) nc附加习题：请给出一个运行时间为Q(nlgn)的算法，使之能在给定的一个由n个整教构成的集台S 和另一个整教X时，判断出S中是否存在有两个其和等于X的元素。Give a 0( n lg n) time algorithm for decermining if rhere exist two elemen

4、ts in an set S whose sum is exactlv some value xAlgorithm 4 CheckSums( Ax)Input: An array A and a value x.Output: A booleaii value indicating if there is two elements in A whose sum is x. A 1 SORTI A) n 4AJfor i 0 and Binary-Search(A, Ai xj.n) thenreturn trtieend ifend forreturn falseClear!； this al

5、gorithm does the job(I【is assumed that nil cannot be tme in the if-statement.)1 +2+3+I5+6+7+8+9+10+11+12亠r少一3一4-5-6一7-8- 旷1（厂11-12_1+ 2十 3+ 4+ 5一 6- 7 82 34 一5+6+7+8+9十10十11+12+9一lo-ir12weighNZ MZ MZ一1 _亠 一 3 _亠 一 1 一 7 一 -3 一亠 一1 _2一 一 7 一亠z z z pZj pZj4. 动态规划（堰优子结构性质，自底向上填表计算最优解值（即屡长公共子序列），导出屡优 解）

6、。誇点:最优于结构性质，自底向上埴表计算最优解值，导出最优解。a）动态规划算法设计的4个步骤：1）描述最优解的结构；2）递归定义黒优解的值；3）按自底 向上的方式计算最优解的值；4）由计算出的结果构造一个最优解。b）黒优于结构道循的共同模式：1）问题的一个解可以是做一个选择，做这种选择可能会得到一个或多个有待解决的于问题；2）假设对一个给定的问题，巳知的是一个可以导致最优解 的选择，不必关心如何确定这个选择，尽管假定它是已知的；3）在巳知这个选择后，要确定哪 些于问题会随之发生，以&如何最好地描述所得到的于问题的空间；4）利用一种“剪切粘贴 法”，来证明在问题的一个黒优解中，使用的于问题的解本

7、身也必须是罠优的。备注：A problem exhibits optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems.Whenever a problem exhibits optimal substucture it is a good clue that dynamic programming mi 曲 t apply.c) 最长公共于序列的算法：这里以两个序列x= xl,x2,- ,xmfnv= y 1 ,y2,-,yn输入

8、，注意裸 本211页的自底向上埴表方法。LCS.LENGTH(X,Y)注：此程序运行时间为()(mn),每个表顶的计算时间为()(1)1 m -length X2 n length73 fori1 to m4do ci, 0 一 05 for j0 to n6do c0, j 07 fori1 to m8do for j1 t9 do if xi = yj10 then ci, j 一 ci-l,j-l + 111 bi, j-12 elseifci- l,j cRjl13 thencRj - ci-l,j14 bi,j-”f15 else ci, j - ci, j - 116 bi,j _

9、 “ _ “17 return c and bPRINT-LCSCb, X, i, j)注：此程序运行时间为()(m+n)1 if i = 0 or j = 02 then return3iFbi,j = “=“4 then PRINT-LCS(b,XJ- l,j- 1)5 print xi6elseifbiJ = M t7 then PRNT-LCS(b, XJ- 1,j)8 else PRlT-LCS(b,X, i,j- 1)d) 拒阵链乘法的算法：参照课本上的矩阵链表得出矩阵相乘的最小算法。fnh j=m inf/n讥+ mk +1 Jikj+ PWPjMATRIXHAIN-ORDER(

10、p)每个表项的負杂度是()(n),共有()(if2)表项，则为()(23)1 n length p - 12 for i 1 to n3 do mi, i 04 for 12 to n I is the chain length.5 do for i 1 to n 1 + 16 do j i + 1 17 mi, j 一 oo8 fork i to j - 19 do q mi, k + mk + 1, j + pi-1 pkpj10 j11 then mi, j q12 si, j - k13 return m and sPIUNT-OPTIMAL-PARENS(s, i, j)lifi =

11、 j2343then print MAi nelse printPRIXT-OPTINLAL-PARENS(s, i, si, j)PR1NT-OPT1NLAL-PAR ENS(s,si,j + l,j)6 print H）HC）备忘录算法：1）程序结构采用自顶向上；2）保留了递归结构，开销较大；3）当所有的于 问题都需要求解时，自底向上的方法效率较高，否则可以采用缶忘录方法。杳忘录算法的代码可以参照课本207页。0最优二叉查找树：1） 一棵最优二叉査找树不一定是一棵整体高度最小的树，也不一定总是 把有最大概率的关键宇放在根部来构造一棵昙优二叉査找树。5、贪心法（遇优子结构性质+贪心选择性质）

12、。誇点:学会证明最优于结构性质和贪心选择性质的问题。Q活动选择问题：Jo也j=max也幻+c伙,刀+1 ifSij丰0ikj注意课本上224页地贪婪法定理证明，这就是贪婪法的台理性证明oRECURSIVEACnVITYSELECTOR(s, i, j)1 m i + 12 while m j and sm fi Find the first activity in Sij.3 do m m + 14ifm fi6 then A AU am7 i m8 return Ab）贪心算法道循的步骤：1）决定问题的最优于结构；2）设计出一个递归解；3）证明在递归 的任一阶段，最优选择之一总是贪心选择，那

13、么，做贪心选择总是安全的；4）证明通过做贪心 选择，所有的于问题（出一个以外）都为空；5）设计出一个实现贪心策珀的递归算法；6）将 递归算法转换成迭代算法。c）根据贪心选择来构進最优于结构：1）将优化问题捷化成这样一个问题，即先做出选择，再 解决剩下的一个于问题；2）证明原问题总是有一个最优解是做贪心选择得到的，从而说明贪心 选择的安全；3）说明在做贪心选择后，剩余的于问题具有这样的一个性质，即如果将于问题的 果优解和我们所作的贪心、选择联台起来，可以得出原问题的一个最优解。d）贪心选择性质：证明定理16.1C）最优于结构性质：课本229页。6、搜索（回溯法、剪枝国数、摄小成本优先）。誇点：回

14、溯，剪枝函教，最小成本优先的问题；分支界限法，剪枝函数所具备的性质。a）回溯法：1）定义:回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目标。 但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通 就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点” O2）回溯法解题的步骤：a. 针对所给的问题，定义问题的解空间；b、确定易于搜索的解空间结构；C、以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。2）回溯法铮决的n后问题：在一个n 5的棋盘上放賈n个王后，使得n后彼此不受攻击。3）回溯法解决背包问题：附：证明部分背

15、包问题具有贪心选择性质。课本练习题16.2-3:算法导论复习资料软件0902為超此问题的形式化描述是，给定C0,0, % 0. K/C n.且分别对 %进行排序后有IGUm 1,要求找一个力元向量&p x2,，xj0, 1/, 1，G?,使得G且刀瞬达到最大。我们用贪心算法求解这个问题。 /=1 /=1此问题采用以重量最轻者先装的贪心选择策略具体算法 如下：int Partioi或 int z int 1. int r) = temp) &( i j) ) j；iff ij) w i十十=w j:while( ( w i = temp) &( i j) ) i + + ：if( i j) w|

16、 j -=w i| : vvhile( i! =j):w| i| = temp；rettmi i：void QuickSoi1( int* w. int l. iitt r) int i：if( lr) i = Partion( w. l.r)： QuiclSort( w. I. i - I) !Quic kSort( w. i + 1, r)： . .void Loading ( int* :x. int* w. int c int n) int t = new i lit | 口 十 1 ；QnickSoit(讥j L n):fbr( int i = 1 ： i = n i 十十)a i

17、= 0；fbr( int i = 1 ： i = &* t| i| | /)3，花,.,耳)0kn剪枝函数的必要条件：典型例题：1)求不等式的整数解5m+4x2 口 10,1 X. 3, 7 = 1,2,32)装载问题：c)最小成本优先算法：注：分支限界的基本思想：1回溯法的深度优先比较盲目2广度优先代价太高4 能优先搜索那些最有希望得到解的路径6深入分析问题，得到有用的启发信息7利用启发信息构造成本函数8杲小成本优先的搜索策菇9结台剪枝函教典型题型：重拍九宫问题。7、墨大流(概念，最大流昱小割定理，Edmonds-Karp算法)。考点：呈大流的相关槪念，最大流 小割定理，Edmonds-Ka

18、rp算法，要求拿握Ford-Fulkcrson 算法的相关内容。1) 流网络定义：有向图G=(E),如果图G满足：-存在源结点(source) s (啲入度为0)-存在汇结点(sink) r (创出度为0)- 任意结点卩 V,有s p r- 容長函数C E 疋称G为流网络。流的定义：流网络G 若函数P：卩u 7T满足下述条件：- 容長限制：对任意(”期 E,有0=p(u,v)=c(u,v)-守恒条件：对任意u (V-s,t),有X pQj v)一 X p(叫 “)=verver则称P为G上的流。注意课本399页的引理。2) 对源点顶点来说，离开它的正流要比迸入它的正流更多；对汇点顶点来说，迸入

19、它的正流要 比商开它的正流更多。先证明如下：|F戶f (s, V)=f (V, V) -f (V-s, V)=f (V, V-s)=f (V, t) +f (V, V-s-t)=f (v, t)3) Ford-Fulkerson方法：此方法依翰三中重要思想，a、残留网络；b、增广路径；c、害叽这些 是最大流果小割宦理的精tioCFord-Fulkcrson方法沿增广路径反复增加流，知道找出昙大流为止; 而最大流最小割定理吿诉我们：一个流是屋大流，当且仅当它的残留网络不包含增广阳径。)一、残留网络：在不超过容長C(U, V)的条件下，从U到V之间可以压入的额外网络流長， 就是(U, v)残留容長

20、，定义为Cf (u, v) =c (u, v) -f (u, v)o注意课本401页的残留网络的 例于。残留网络Gf本身也是一个流网络，其容長由$给出，且|Ef|=2|E|o注意课本402页的引理26.2 o二、増广路径：注意裸本403页引理26.3和引理26.4。三、流网络的割：注意403页的几个引理。四、最大流最小割定理：几个相互等价的条件。FORD-FULKERSON(G, s, t)1 for each edge (u, v) EG2 do v 03 fv, n 04 while there exists a path p from s to t in the residual Rew

21、ork Gf5 docf(p) min cf(u, v): (u, v) is in )6 for each edge (u, v) in p7 do fu, v fu, v + cf(p)8 fv, u -fu, vFORP-FULKERSON的复杂性：FORP-FULKERSON程的运行时间取决于如何决定第四行中 的增广路径，选择不奸，算法可能不会终止。假设容長是整教13行()(冋)48循环执行()(|f*|)找增广路0(1 E|)O(|E|f*|)FORP-FULKERSON算法有其缺点，可以参照裸本406页。4) Edmonds-KarpM法：如果左第四行中用广度优先搜索来实现对増光聒

22、径p的计算。即如果增 光路径是残留网络中从s到t的黒短阳径(其中每条边为单位距离，或权)，则能够改进 FORD-FULKERSON算法的界；称FORP-FULKERSON方法的这种实现为Edmonds-Karp算法。 Edmonds-Karp算法的运行时间为O (V*E2)注意课本407页关于Edmonds-Karp算法的一些证明。8、NP宪全问题(多项式时间规约)。誇点：多项式时间内的规约问题，拿握NP完全问题的证明方法。P类问题：是在多项式时间內可解的问题，即都是在()(卅)时间内求解的问题，此处k为某个常 数，门是问题的输入规模。NP类问题：是在多项式时间内“可验证”的问题即能够在问题输

23、入规模的多项式时间内，验证 该问题是正确的。注意：P问题包含于NP问题。但P不一定是NP问题的真于集。NPC问题：NP完全问题，即任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题, 那么这个NP问题就成为NPC问题。换言之，如果这个问题解决了，那么所有的NP问题也都能解 决了。若问题L满足一 L W NP, and-1/ a3DEj = al j,a2j ,al 0,a3O, a20,a3j 覆盖至少包含了中的两个顶点，否则不能覆盖中的三角形 联络边：沟通分星之间的关系 对于每个于句cj,设cj= 力加,则Ej =alj,xj,a2D,yj,a3j,2jG = (V,E)V =(y EV2E.EVn)E(H EV2 E.EVm，) E=ElEE2E.EEn)E(El EE2f E.EEm，) 电(E1 EE2* E.EEm，)K = n +2m显然构造可在多项式时间完成 例如u = ul,u2,u3,u4,C = u