算法lecture考试时间12月29日下午

1、安排时间：12月29日 下午 2:004:00地点：二教 307, 308, 309注意事项：带学生证、按指定教室进入考场因病等特殊原因不能参加请表并经主管院长签字批准答疑时间：12月28日下午2:00-5:00者需在填写缓考申12月29日上午8:30-11:30答疑地点：1622 / 理科一号楼1要求数学基础：估计函数的阶、递推方程求解、求和技术算法设计技术：分治策略、动态规划、贪心法、回溯与分支估界能进行简单应用算法分析技术：对算法进行和平均时间复杂度分析证明某些简单问题的复杂度的下界计算复杂性理论图灵机的定义理解计算复杂性理论的基本概念和重要结果NP-hard 问题的证明方法2处理难解问

2、题的策略对问题施加限制固定参数算法改进指数时间算法3SAT、指数时间假设启发式方法启发式方法、随机化策略、重启策略、模拟退火平均情形的复杂性G(n,p)、回路、DistNP完全难解算例的生成对问题施加限制.SAT问题二元可满足性（2SAT）属于PHornSAT：输入限制为公式（析取式中正文字，即不带否定号的变量）至多出现一次，属于P图P问题D 2D 3VCHC2334顶点三23反馈顶点集给定D团任意固定参数算法通常把优化问题转化为判定问题时，都会在输入中引入一个参数，这是固定参数算法中参数的来源之一.输入中带有一个参数 k，当输入规模为 n时运行时间为O(f(k)nc) 的算法，这里的 f(k

3、)是与 n 无关的函数，c 是与 n和 k 都无关的常数.例VC:给定图G, 正整数 K(不超过G的顶点数)，问是否存在不超过 K 的顶点覆盖？固定常数 k，输入为(G, k). 穷举所有 k元 顶点子集，看看是否存在顶点覆盖.算法复杂度大约是)=O(knk+1)O(k存在O(2kkn)的算法.5改进的指数时间算法O*：表示忽略了多项式因子. 如O*(2n)=O(nO(1)2n)当一个问题的蛮力算法为O*(2n)时间时，对任何满足1 c 2的常数c，时间复杂度为O*(cn)的指数时间算法称为非平凡的指数时间算法，或改进的指数时间算法.可证明在O*(1.8393n)时间内正确求解3SAT，截止到

4、2010年底 最好结果：O*(1.321n)时间的随机算法和O*(1.439n)时间的确定型算法.问题都有O*(3n)的算法.任意色数的图的顶点背包问题有比O*(2n/2)更好的算法.货郎问题也有比O*(2n)更好的算法.6其他处理难解问题的策略启发式方法（Heuristics）：目前无法从理论上给出任何性能保证，但在实践中效果良好，就把这类方法统称为启发式方法（Heuristics）.常用的启发式方法主要包括：回溯与分支限界法、局部搜索法（随机化策略、重启策略、模拟退火）、遗传算法等.平均情况下的复杂度有些NP完全问题在平均复杂性度量下是易解的，回路问题的平均情况下对图G(n,1/2)有O(

5、n3)时间的算法.难解算例生成:确定紧的实例基于统计物理的消息传递算法算法设计与分析的实例P2P的服务器文件配置NAND Flash控制器验证XML关键字的查询改写平面点集的凸包网络优化最大流及其应用8问题1P2P的服务器文件配置背景决定P2P的服务器文件本的放置，在代价和代价的权衡中取得最优实例S1, S2, , Sn为n个服务器, 每个Si 有代价ci用户向 Si 发请求，若Si 没文件，则顺序Si+1,直到在 Sj找到，其问题代价为 ji，Sn必须存放1份文件要求一样多（不妨设都等于1），假设每个服务器的如何放置文件，使得总代价（和）达到最小？9算法设计实例：服务器S1, S2, S3，

6、c1=5, c2=8, c3=2副本放 S3:副本放 S1,S3:代价=2+1+c3=2+1+2=5代价=c1+1+c3=8副本放 S2,S3:副本放 S1,S2,S3:代价=1+c2+c3=11代价=c1+c2+c3=15动态规划：OPT(j)表示副本放在Sj，从 S1到 Sj 的最小代价OPT( j) c j minOPT(i) C (i 1, j)j 10 i jC (i 1, j) ( j i 1) . 2 1 （ j i)( j i 1) / 2OTP(0) 01ii+1j时间复杂度：O(n2)10问题2NANDFlash控制器验证背景该控制器支持NANDFlash的操作：擦除、读写

7、用于实例系统的设计开发验证时需将内存文件以页为写入NANDflash设备若文件字节数2112，放入1页；大于2112，放入连续的几页给定t个文件的字节数 f1,f2, ft(n+m=t)，n, m分别为字节大于和小于2112的文件数，通常n2112 thenfi=fi mod 2112先按从大到小次序把大于2112的文件装入页面，每个文件最后一个页面大小改为2112fi 按照文件fi ( 不超过2112) 从大到小排序，然后装入第一个适合它的页面算法分析O(nlogn)+O(mlogm)+O(mn+m2)=O(m2 )近似比1.212实例f1=5560, f2=3124,f3=267, f4=

8、359,f5=123,f6=1560先放 f1,f2，页面3 和 5 的剩余分别为776，1100排序f3, f4, f5, f6为：依次放入f6=1560,f4=359,f3=276,f5=1231100552f1f4f3f5问题3平面点集的凸包背景图形处理中用于形状识别：字形识别、碰撞检测平面凸包算法是算法问题（平面凸包）给定大量离散点的集合Q，求一个最小的凸多边形，使得Q中的点在该多边形内或者边上.14分治算法算法以d=ymax,ymin 划分L为左点集 Lleft 和右点集 LrightDeal(Llesft)；DeDeal(Lleft)bpymax把距离 d 最远点 P 加入凸包检查

9、 L中其他点是否在三角a形内；在则从 L中删除； 否则根据在 a 或 b 边的外侧划分在两个子问题中Deal(a)Deal(b)ymin15算法分析初始用d 划分Deal 递归调用O(n)找凸包顶点PO(n)确定点是否在三角形O(n)(OW(n1)W( n )n(W1)情况为O(n2)1T(n)=O(n)+W(n)=O(n2)16问题4网络优化背景树状连通网络，每条线路有传输延迟，只能改进K条线路，以降低传输延迟，如何选择？实例节点集 V=1,2, n，E=e1,e2,en-1，Kn-1wt 是边 et 的传输延迟，t=1,2, n-1，W(i,j)是 i 到 j 的延迟 (从 i 到 j 路

10、径上所有边延迟之和)对ei 改进后，边上的延迟减少了pwi，p1为常数问题: 选 AE,|A|=K, 使得WA min WA (i , j ) ,| A| K , A E 1 i j n17贪心法设计与分析改进ei之后总延迟减少了ci| Si | | Si | pwi选择A后总延迟为eiSiSiW Wmaxc A贪心法iei Aj计算ci，i=1,2,n-1排序 ei 使得 c1 c2 cn-1A= e1, e2, , eK 利用交换论证可以证明算法得到最优解18算法分析与实现主要工作量在于计算 ci选定树根，DFS遍历确定结点的深度自底向上按照深度为 d, d-1, , 1, 0层计算连接树

11、叶 i 的边的 叶端点Si 值 =1，Si= n-Si如果结点 i 的子结点为a,b, c, 那么连接的边 e 的 Si 值与Si 值分别为i 和它的父结点Si eSa+Sb+Sc+1,时间为O(n)Si=n-Sii cab算法时间为 O(n)+O(nlogn)SaSbSc19问题5XML关键字的查询改写背景基于XML的 key 的搜索中，通过把原始查询Q的关键字序列改为新关键字序列，从而提高查全率实例设S=k1,k2,kn和T=k1,k2,km为key的序列R=r1,r2,r3,r4为操作集(替换,拆分,合并,删除)，操作rj有代价c(rj)，从 S到T的改写代价c(S,T)为把S 改写成T

12、 的系列操作代价之和问题找到使 c(S,T) 最小的操作序列20查询改写实例21动态规划算法Ci表示改写 k1, , ki 的最小代价，则if ki TCi1Ci 1 删除 k 的代价if k TiiCi | l(r ) | 应用 r 规则的代价jjif ki T and rj Rl(rj)表示从i向前改写规则rj作用的关键字个数22问题6网络的最大流流网络是有向图 G=(V,E)每条边 e 关联一个容量ce 0u2010单一源点 sVtV一st30没有边进入 s，没有边离开 t每个结点至少连接一条边1020v23流的定义与最大流算法流定义一个s-t 流是函数 f:ER+， f(e)表示边 e 携带的流量，f 必须满足下面性质:(容量条件) eE 有 0 f(e) ce(守恒条件) 除 s 与 t 之外，对每个结点v，有f (e) f (e)eve从 出v 来进入Ford-Fulkerson算法增广路径技术若容量是整数，时间为O(mC)，m为边数，C ce出s 发e从24实例增广路径：suvt ，增加流20u2010svut，增加流10解20101030s10tf(su) = 20,f(sv) =