计算理论与算法分析设计第一章

1、教材教材: 1王王 王晓东王晓东,计算机算法设计与分析计算机算法设计与分析(第第4版版),电子工业电子工业. 2S 唐常杰等译唐常杰等译, Sipser著著, 计算理论导引计算理论导引, 机械工业机械工业. 参考资料参考资料:3C 潘金贵等译潘金贵等译, Cormen等著等著, 算法导论算法导论, 机械工业机械工业. 4M 黄林鹏等译黄林鹏等译, Manber著著, 算法引论算法引论-一种创造性方一种创造性方法法, 电子电子. 5刘刘 刘汝佳等刘汝佳等, 算法艺术与信息学竞赛算法艺术与信息学竞赛, 清华大学清华大学.6L Lewis等著等著, 计算理论基础计算理论基础, 清华大学清华大学. 计

2、算理论与计算理论与算法分析设计算法分析设计 刘刘 庆庆 晖晖 课程内容课程内容l算法算法: 概述概述, 递归与分治递归与分治, 动态规划动态规划, 贪心法贪心法, 回溯法回溯法, 分支限界法分支限界法, 概率算法概率算法, 线性规划与网络流线性规划与网络流l计算理论基础计算理论基础: 集合关系与语言集合关系与语言, 有穷自动机有穷自动机, 图灵机图灵机, 不可判定性不可判定性, 计算复杂性计算复杂性, NP完全性等完全性等.l 56学时学时l成绩成绩l平时成绩平时成绩30%, 期末闭卷成绩期末闭卷成绩70 第一章第一章 算法概述算法概述第一部分第一部分 什么是算法什么是算法 第二部分第二部分

3、算法分析与分析起步算法分析与分析起步 第一部分第一部分什么是算法什么是算法什么是算法什么是算法教材教材(王王)上的解释上的解释是指解决问题的一种方法或一个过程是指解决问题的一种方法或一个过程是若干指令的有穷序列是若干指令的有穷序列, 满足满足: (1) 输入输入: 零个或多个外部提供的量零个或多个外部提供的量 (2) 输出输出: 产生至少一个量作为输出产生至少一个量作为输出 (3) 确定性确定性: 每条指令是清晰每条指令是清晰, 无歧义无歧义 (4) 有限性有限性: 每条指令的执行次数每条指令的执行次数, 时间有限时间有限什么是算法什么是算法算法导论算法导论C:解决可计算问题的一个工具解决可计

4、算问题的一个工具将输入转换为输出的一个可计算步骤序列将输入转换为输出的一个可计算步骤序列韦氏大学词典韦氏大学词典:求解问题的一个过程求解问题的一个过程, 步骤有限步骤有限, 通常有重复操作通常有重复操作; 广义地说广义地说, 是按部就班解决一个问题的过程是按部就班解决一个问题的过程.以上这些都可以说是算法的直观解释以上这些都可以说是算法的直观解释 . 会不会有问题没有算法呢会不会有问题没有算法呢?找最大数问题找最大数问题l输入输入: 一个实数序列一个实数序列a1,an.l输出输出: max a1,an .l输入样例输入样例: 1.1, 2.3, 4, 10, 8, 7, 3, 8对应输出对应输

5、出: 10 l算法算法: l1. 令令max=a1. l2. 对对 i = 2 到到 n, l3. 若若 max ai , 则则 max = ai . l4. 输出输出max. 输入输入,输出输出 确定性确定性有限性有限性可计算步骤可计算步骤 一个过程一个过程 有重复操作有重复操作 按部就班按部就班PCP问题没有算法问题没有算法Post Corresponding Problem(S)输入输入: 一簇骨牌一簇骨牌t1b1,t2b2tkbk解解(匹配匹配)是一个序列是一个序列i1,i2,il1,k, 使得使得lliiiiiibbbttt2121 l 输出输出: 给定骨牌簇是否有解给定骨牌簇是否有

6、解. bcaaabcaaabcc,2 1 3 2 43n+1问题目前不知道有没有算法问题目前不知道有没有算法l输入输入: 一个整数一个整数n,l映射映射: f(n) = n/2, 若若n是偶数是偶数; f(n) = 3n+1, 若若n是奇数是奇数. l迭代迭代: 5168, 到到1则停止则停止l输出输出: n可在可在f迭代下是否能停止迭代下是否能停止 l直接模拟是正确的算法吗直接模拟是正确的算法吗?l27需迭代需迭代111步步(见右图见右图) l151018都能到都能到1.(wiki)什么是正确的算法什么是正确的算法l对每个输入样例对每个输入样例, l 都能停机都能停机, 并输出正确的结果并输

7、出正确的结果. (C)l什么是不正确的算法什么是不正确的算法? 为什么需要严格定义算法为什么需要严格定义算法? l什么问题被解决了什么问题被解决了? (找最大数找最大数)什么问题没有被解决什么问题没有被解决? (3n+1问题问题)什么问题没有解决方案什么问题没有解决方案? (PCP问题问题)l将在计算理论部分给出算法的严格定义将在计算理论部分给出算法的严格定义. 程序程序=数据结构数据结构+算法算法l数据结构是数据结构是l为方便获取和修改数据而存储组织数据的方为方便获取和修改数据而存储组织数据的方式式 l本课程主要关注算法本课程主要关注算法, l仅在有必要的时候讲解相关数据结构仅在有必要的时候

8、讲解相关数据结构 算法技术算法技术l很多著名算法书很多著名算法书:计算机程序设计艺术、算法导论计算机程序设计艺术、算法导论 等等可作为算法可作为算法“菜谱菜谱”.l但实际工作中总会遇到菜谱中没有的问题但实际工作中总会遇到菜谱中没有的问题.l所以需要学习算法设计和分析技术所以需要学习算法设计和分析技术l本课程涉及的技术本课程涉及的技术(王王)有有:分治分治, 动态规划动态规划, 贪心贪心, 回溯回溯, 分支限界分支限界, 随机等随机等 l本课程约涉及本课程约涉及50个问题个问题(王王):01背包问题背包问题,单源最短路单源最短路, 旅行售货员问题等旅行售货员问题等算法的效率算法的效率l什么是高效

9、的算法什么是高效的算法?l 运行速度和占用空间可以用来度量效率运行速度和占用空间可以用来度量效率输入规模输入规模n n耗费时间耗费时间1 1小时小时/ /天天/ /年可解的问题实例的最大规模年可解的问题实例的最大规模计算机计算机快快100100倍计算机倍计算机快快10001000倍计算机倍计算机多多项项式式时时间间n nN1N1100 N1100 N11000 N11000 N1n2n2N2N210 N210 N231.6 N231.6 N2n3n3N3N34.64 N34.64 N310 N310 N3n5n5N4N42.5 N42.5 N43.98 N43.98 N4指数指数时间时间2n2

10、nN5N5N5 + 6.64N5 + 6.64N5 + 9.97N5 + 9.973n3nN6N6N6 + 4.19N6 + 4.19N6 + 6.29N6 + 6.29高效的算法高效的算法l多项式时间算法在理论上是高效的算法多项式时间算法在理论上是高效的算法l指数时间完全问题指数时间完全问题l 例例: 全量词化布尔公式是否真全量词化布尔公式是否真(TQBF)x1y1x2y2P(x1,y1,x2,y2,) 其中其中P是布尔是布尔公式公式lNP(非确定性多项式时间非确定性多项式时间)完全问题完全问题l 也是可以多项式时间验证解正确性的问题也是可以多项式时间验证解正确性的问题.l 例例: 布尔公式

11、是否有真赋值布尔公式是否有真赋值(CNF-SAT)=(x)y) (x(z)有真赋值有真赋值(x,y,z)=(F,T,F) 例例: 3-SAT, CLIQUE, 顶点覆盖顶点覆盖, 哈密顿回路等哈密顿回路等 NP完全问题完全问题l目前还没有找到多项式时间算法目前还没有找到多项式时间算法七大千禧问题之一七大千禧问题之一l密码系统设计密码系统设计l说明目前没有好算法说明目前没有好算法l解决方案解决方案: 修改问题修改问题, 或使用近似算法或使用近似算法第二部分第二部分算法设计与分析起步算法设计与分析起步设计算法的步骤设计算法的步骤: 确定问题确定问题 给出算法给出算法, 分析算法复杂度分析算法复杂度

12、 寻求最优算法寻求最优算法 找最大数问题找最大数问题l输入输入: 一个实数序列一个实数序列a1,an.l输出输出: max a1,an .序列序列32572918最大最大33577999修改次数修改次数10110100比较次数比较次数01111111l输入样例的规模输入样例的规模 N = 8l输入样例输入样例 I = 3,2,5,7,2,9,1,8l时间复杂度时间复杂度: c1N T(N,I) c2 N (很难计算精确很难计算精确值值) l以比较次数以比较次数(N)计算时间复杂度比较合理计算时间复杂度比较合理关于算法复杂度的度量关于算法复杂度的度量l 如何计算算法的复杂度如何计算算法的复杂度?

13、l 时间时间: 时间复杂度时间复杂度l 空间空间: 空间复杂度空间复杂度l 输入规模输入规模l 同样输入规模需要的时间空间也经常不同同样输入规模需要的时间空间也经常不同l 最坏时间复杂度最坏时间复杂度, 平均时间复杂度平均时间复杂度 f(n)l 系统不同、缓存大小不同等系统不同、缓存大小不同等 诸多影响因素诸多影响因素 l 需要约定输入规模的度量需要约定输入规模的度量: 数列数列, 图等图等找最大次大数问题找最大次大数问题(M): 方法一方法一l输入输入: 一个实数序列一个实数序列a1,an.l输出输出: 最大和次大的数最大和次大的数.序列序列32572918最大最大3次大次大2比较次数比较次

14、数1l输入规模输入规模 N = 8, I = 3,2,5,7,2,9,1,8找最大次大数问题找最大次大数问题(M): 方法一方法一l输入输入: 一个实数序列一个实数序列a1,an.l输出输出: 最大和次大的数最大和次大的数.序列序列32572918最大最大35次大次大23比较次数比较次数11l输入规模输入规模 N = 8, I = 3,2,5,7,2,9,1,8找最大次大数问题找最大次大数问题(M): 方法一方法一l输入输入: 一个实数序列一个实数序列a1,an.l输出输出: 最大和次大的数最大和次大的数.序列序列32572918最大最大357次大次大235比较次数比较次数111l输入规模输入

15、规模 N = 8, I = 3,2,5,7,2,9,1,8找最大次大数问题找最大次大数问题(M): 方法一方法一l输入输入: 一个实数序列一个实数序列a1,an.l输出输出: 最大和次大的数最大和次大的数.序列序列32572918最大最大3577次大次大2355比较次数比较次数1112l输入规模输入规模 N = 8, I = 3,2,5,7,2,9,1,8找最大次大数问题找最大次大数问题(M): 方法一方法一l输入输入: 一个实数序列一个实数序列a1,an.l输出输出: 最大和次大的数最大和次大的数.序列序列32572918最大最大3577999次大次大2355778比较次数比较次数11121

16、22l输入规模输入规模 N = 8, I = 3,2,5,7,2,9,1,8l对所有规模对所有规模N输入输入, 比较次数最多比较次数最多2(N-2)+1=2N-3 l渐近意义上已经最优渐近意义上已经最优 , 但是能否进一步改进但是能否进一步改进? 最大次大最大次大(M): 方法二方法二-分治分治l分治法分治法: 设规模设规模n比较次数最多比较次数最多T(n)T(n) = 2T(n/2) + 2, l T(2)=1, T(3)=3l若若n=2k, T(n)=1.5n-2; (M)l若若n=32k, T(n)=5n/3-2l对一般对一般n, 可归纳证明可归纳证明 1.5n-2 T(n) 5n/3-

17、2 l 证明见本证明见本ppt附录附录. 3 2 5 7 2 9 1 83 2 5 72 9 1 8759898找最大次大数问题找最大次大数问题(M): 方法三方法三l输入输入: 一个实数序列一个实数序列a1,an.l输出输出: 最大和次大的数最大和次大的数.序列序列32572918最大最大3次大次大2比较次数比较次数1找最大次大数问题找最大次大数问题(M): 方法三方法三l输入输入: 一个实数序列一个实数序列a1,an.l输出输出: 最大和次大的数最大和次大的数.序列序列32572918最大最大377次大次大255比较次数比较次数112找最大次大数问题找最大次大数问题(M): 方法三方法三l

18、输入输入: 一个实数序列一个实数序列a1,an.l输出输出: 最大和次大的数最大和次大的数.序列序列32572918最大最大37799次大次大25527比较次数比较次数11212找最大次大数问题找最大次大数问题(M): 方法三方法三l输入输入: 一个实数序列一个实数序列a1,an.l输出输出: 最大和次大的数最大和次大的数.序列序列32572918最大最大3779989次大次大2552718比较次数比较次数1121212对所有规模对所有规模n输入输入, 比较次数最多比较次数最多 3(n-2)/2 +1 = 3 n/2 - 2 1.5n-2 注注: C中对最大最小数问题使用了这个算法中对最大最小

19、数问题使用了这个算法. 找最大次大数问题找最大次大数问题(M): 方法四方法四3 2 5 7 2 9 1 83 2 5 72 9 1 875,398,297,8,22 95 71 83 2修改的分治修改的分治: 维护可能次大集维护可能次大集 比较次数比较次数:n-1+log2n32759281复杂度复杂度f(n)的渐近记法的渐近记法l称称g(n)是是f(n)的渐进上界的渐进上界, 即即f(n) = O(g(n), 若若 c0, N0, nN, f(n) c g(n) 例例: n2 n = O(n3), n2 n = O(n2) l称称g(n)是是f(n)的渐进下界的渐进下界, 即即f(n) =

20、 (g(n), 若若 c0, N0, nN, f(n) c g(n)例例: n2 n = (n), n2 n = (n2) lf(n) = (g(n) 渐近同阶渐近同阶 ( 王王, C), 若若 f(n) = O(g(n) 且且 f(n) = (g(n) 例例: n2 n = (n2) l注注: n0, n2 n2 n 10001n2. 渐近记法的等价极限定义渐近记法的等价极限定义O, , 示意图示意图f(n)c0g(n)c1g(n)n0f(n) = (g(n) f(n)cg(n)n0f(n) = O(g(n) f(n)cg(n)n0f(n) = (g(n) 常用渐近函数常用渐近函数f(n)

21、= O(g(n) 为方便为方便, g(n)通常取通常取 nk, /多项式多项式 nklogn, /含对数项含对数项 en 或或 eO(n) /指数函数指数函数注注: 为本课程为本课程ppt书写方便书写方便logn是是log2n 例如例如: log n3 = O(log n), log 3n = O(n)时间复杂度的分析技巧时间复杂度的分析技巧l直接估计、递推关系直接估计、递推关系l均摊分析均摊分析l 累计法累计法, 记账法记账法, 势能法势能法(C) l例例: k位二进制计数器问题位二进制计数器问题l从从0执行加执行加1操作操作, 直到到直到到n. l关键量关键量: 位反转次数位反转次数l粗略

22、估计粗略估计O(kn)或或O(nlogn) 从从0到到n需要的时间需要的时间-累计法累计法累计法累计法: 每位反转总次数每位反转总次数 n+n/2+n/4+2n 均摊均摊: (累计后均摊累计后均摊) 每次操作平均反转每次操作平均反转2次次 从从0到到n需要的时间需要的时间-记账法记账法Ai我我时间时间0变变11变变02元元1元元0元元1元元 每次每次+1 只有只有1位从位从0变变1 总收入总收入 = 2n, 总支出总支出 2n 2n-k 从从0到到n需要的时间需要的时间-势能法势能法势能法的原理势能法的原理Di : 第第i次操作后的数据结构次操作后的数据结构, i=0:n ci : 第第i次操

23、作的实际耗费时间次操作的实际耗费时间, i=1:n : 势能函数势能函数, 将将Di映射为一个实数映射为一个实数 (Di) di = ci + (Di) - (Di-1)第第i次操作的均摊时间次操作的均摊时间 i=1n di = i=1n (ci + (Di) - (Di-1) = i=1n ci + (Dn) - (D0)若若 (Di) (D0) (势能势能), 则则 i=1n di i=1n ci . 应用到计数器问题应用到计数器问题. (Di) = Di中中1的个数的个数. di = ci + (Di) - (Di-1) = 2 证明证明: 设从设从Di-1到到Di有有b位位1变变0,

24、1位位0变变1, 则则ci=1+b, (Di) - (Di-1) =1-b一些符号和公式一些符号和公式 x : 小于等于小于等于x的最大整数的最大整数, x :大于等于大于等于x 的最小整数的最小整数 anbbnaloglog )1(1()(2!nennnn 1110 xxxnnkknkOnk1) 1 (ln1log n! = (n log n) 等比级数求和等比级数求和 调和级数调和级数 Stirling公式公式本章小结和作业本章小结和作业算法分析题算法分析题 1-1, 1-2, 1-4 1-1 求下列函数的渐近表达式求下列函数的渐近表达式: 3n2+10n; n2/10+2n; 21+1/

25、n; log n3; 10log3n. 1-2 试论试论O(1)与与O(2)的区别的区别. 1-4 (1) 假设某算法在输入规模为假设某算法在输入规模为n时的计算时间为时的计算时间为T(n)=32n. 在某台计算机在某台计算机上上实现并完成该算法的时间为实现并完成该算法的时间为t秒秒. 现有另一台计算机现有另一台计算机, 其运行速度是第一台的其运行速度是第一台的64倍倍, 那么在这台新机器上用同一算法在那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题秒内能解输入规模为多大的问题?(2) 若上述算法的计算时间改进为若上述算法的计算时间改进为T(n)=n2, 其余条件不变其余条件不变, 则在新机器上用则在新机器上用t秒秒时间能解输入规模为多大的问题时间能解输入规模为多大的问题?(3) 若上述算法的计算时间改进为若上述算法的计算时间改进为T(n