第 4 课 计算学科的形成及其 基本问题http:/user.qzone.qq.com/19757 31184/infocenter#!app=2 else / 将n - 1个盘从left柱移到middle柱，以right柱为辅助柱 move(n - 1, left, middle, right); / 将最下的圆盘从left柱移到right柱 System.out.println(“将#“+n+“盘从“+left+“移到“+right); / 将n - 1个盘从middle柱移到right柱，以left柱为辅助柱 move(n - 1, middle, right, left); public static void main(String args) / 将4个圆盘从A柱移到C柱，移动时利用B柱为辅助柱 move(4, A, C, B); 35运行结果示例E:APPTESTjavac HanoiTower.java E:APPTESTjava HanoiTower 将#1盘从A移到B 将#2盘从A移到C 将#1盘从B移到C 将#3盘从A移到B 将#1盘从C移到A 将#2盘从C移到B 将#1盘从A移到B 将#4盘从A移到C 将#1盘从B移到C 将#2盘从B移到A 将#1盘从C移到A 将#3盘从B移到C 将#1盘从A移到B 将#2盘从A移到C 将#1盘从B移到C36算法的复杂性 按照上面的算法，n个盘子的梵天塔问题需要移动的 盘子数是n-1个盘子的梵天塔问题需要移动的盘子数 的 2 倍加 1。于是 h(n)=2h(n-1)+1 =2(2h(n-2)+1)+1=22h(n-2)+2+1 =23h(n-3)+22+2+1 =2nh(0)+2n-1+22+2+1 =2n-1+22+2+1=2n-1 启示：理论上可以计算的问题，实际上并不一定能 行（称为“难解问题”）37复杂性理论 复杂性理论主要指算法与问题复杂性理论 2个基本概念： 问题：指需要回答的一般性提问 算法：指求解某个问题的一系列具体步骤 如果一个算法能解答一个问题的任何实例，那么就说 这个算法能解答这个问题 如果针对一个问题至少存在一个算法可解答这个问题 ，那么就说这个问题是可解的(resolvable)，否则就说 这个问题是不可解的(unresolvable)38算法复杂性 一个算法复杂性通常用称之为“大O”的符号来 表示，它表示了算法复杂性的数量级 f(n)=O(g(n)意味着存在一个常数c和n0使得 对一切nn0，有f(n)c|g(n)| 如：若f(n)=17n+10，则f(n)=O(n)，因为存在 c=18，n0=1039算法复杂性分类 算法复杂性分类 多项式的(polynomial): 复杂性为O(nc)(c为常数) 若c=0，就称它是常量(constant)的，复杂性为O(1) 若c=1，就称它是线性(linear)的，复杂性为O(n) 若c=2，就称它是二次(quadratic)的，复杂性为O(n2) 指数的(exponential): 复杂性为O(ch(n)(c为常数，h(n)为 多项式) 当h(n)大于常数而低于线性函数时，如h(n)=log2n，就称它是超 多项式(superpolynomial)的40问题复杂性 在问题复杂性理论中，重要的是关于NP与 NP完全问题的理论 一个问题的复杂性可理解为由解该问题的 最有效的算法所需的时间与空间来度量41问题的分类 问题的分类 P类问题: 在多项式时间内可以解决的问题 P类问题的全体，记为P NP类问题:在多项式时间内可以验证的问题 NP类问题的全体，记为NP，显然P NP，但还未证明PNP 如：大整数的素因子分解问题、背包问题、可满足性问题、离 散对数问题 NP-完全类问题 所谓一个NP问题是NP完全的，如果NP中的任何一个问题都 可以通过多项式时间转换为该问题 如：背包问题、可满足性问题、离散对数问题、旅行商问题、 哈密尔顿回路问题 NP-完全类问题的全体，记为NPC 若NPC中的任何一个问题属于P，则所有的NP问题都属于P， 且P=NP422 证比求易算法 “证比求易算法”童话：从前，有一个酷爱数学的 年轻国王向邻国一位聪明美丽的公主求婚。公主 出了这样一道题：求出48 770 428 433 377 171 的一个真因子。若国王能在一天之内求出答案， 公主便接受他的求婚。 办法1：国王回去后立即开始逐个数地进行计算，他从 早到晚，共算了三万多个数，最终还是没有结果。国 王向公主求情，公主将答案相告：223 092 827是它的 一个真因子。国王很快就验证了这个数的确能除尽48 770 428 433 377 171 办法2：由于对一个17位的数，其最小的一个真因子不 会超过9位，于是按自然数的顺序给全国的老百姓每人 编一个号发下去，等公主给出数目后，立即将它们通 报全国，让每个老百姓用自己的编号去除这个数，除 尽了立即上报，赏金万两 43问题的实质 该问题实质上是一个素因子分解问题，分别 用顺序算法和并行算法进行求解 顺序算法其复杂性表现在时间方面 并行算法其复杂性表现在空间方面44阿达尔定律 设f为求解某个问题的计算存在的必须串行执行的操 作占整个计算的百分比，p为处理器的数目，Sp为并 行计算机系统最大的加速能力（单位：倍），则 设f=1%，p则Sp=100 启示：对难解性问题而言，单纯的提高计算机系统 的速度是远远不够的，而降低算法复杂度的数量级 才是最关键的问题453 旅行商问题与组合爆炸问题 旅行商问题：有若干个城市，任何两个城市之间的 距离都是确定的，现要求一旅行商从某城市出发， 必须经过每一个城市且只能在每个城市逗留一次， 最后回到原出发城市。问如何事先确定好一条最短 的路线，使其旅行的费用最少 原始办法：列出每一条可供选择的路线（即对给定 的城市进行排列组合），计算出每条路线的总里程 ，最后从中选出一条最短的路线 若设城市数目为n时，那么组合路径数则为(n-1)!46组合路径图47组合爆炸问题 随着城市数目的不断增大，组合路线数将呈 指数级数规律急剧增长，以至达到无法计算 的地步 解决组合爆炸问题一个合理的办法是寻找其 启发式算法、近似算法、概率算法等48判为素数的概率算法 若Miller-Rabin算法返回 “composite” ，则该数一 定不是素数 否则，该数是素数或伪素数。可以证明，此时是伪 素数的概率小于 因此若反复用不同随机数a测试，则通过连续t次测 试均是返回 “maybe prime”后，n是素数的概率 至少就是: Pr = 1-4-t 如: 对于t=10, n是素数的概率大于0.999999494 找零问题、背包问题与贪婪算法 找零问题 背包问题 贪婪算法50找零问题 设有不同面值的钞票，要求用最小数量的钞票给顾 客找某数额的零钱，这就是通常说的找零问题。 例如，有一个顾客拿一张面值100元的钞票(人民币) 在超市买了5元钱的商品，收银员需找给他95元零钱 。售货员在找零钱时可有多种选择： 9张10元的、1张5元的 95张1元的 950张1角的 1张50元、2张20元和1张5元的51贪婪算法 贪婪算法是一种传统的启发式算法，它采用逐步构 造最优解的方法，即在算法的每个阶段都做出在当 时看上去最好的决策，以获得最大的“好处”，换言 之，就是在每一个决策过程中都要尽可能的“贪”， 直到算法中的某一步不能继续前进时，算法才停止 。 在算法的过程中，“贪”的决策一旦做出，就不可再 更改，做出“贪”的决策的依据称为贪婪准则。 贪婪算法是从局部的最优考虑问题的解决方案，它 简单而又快捷，因此常被人们所使用。但是，这种 从局部，而不是从整体最优上考虑问题的算法，并 不能保证求得的最后解为最优解。52背包问题 给定n种物品和一个背包，设Wi为物品i的重量，Vi 为其价值，C为背包的重量容量，要求在重量容量的 限制下，尽可能使装入的物品总价最大，这就是背 包问题。 例如，假设n=3：W1=100，V1=60；W2=20， V2=40；W3=20，V3=40；C=110。 贪婪准则1：每次都选择价值最大的物品装包。此时，选 物品1，这种方案的总价值为60。而最优解选物品为2和3 ，总价值为80 贪婪准则2：每次都选择Vi/Wi值(价值密度)最大的物品装 包。此时，选择物品2和3，总价值为80，结果为最优解53类似的问题与求解算法 与找零问题、背包问题等类似的可以用贪婪 算法求解的问题还有货箱装船问题、拓扑排 序问题、二分覆盖问题、最短路径问题、最 小代价生成树等。 贪婪算法是一种传统的启发式算法，用于求 解一类问题的启发式算法还有分而治之法、 动态规划法、分支限界法、A*算法、遗传算 法、蚂蚁算法以及演化算法等。545 一个不可计算问题：停机问题 停机问题：能否找到这样一个测试程序，它 能判断出任意的程序在接收了某个输入并执 行后能否终止。若能找到，则停机问题可解 ；否则，不可解。55停机问题的反证 结论是：若S终止，则S不终止；若S不终止，则S终止。结 论矛盾，故可以确定这样的测试程序是不存在的，从而证明 停机问题的不可解。已知：若P 可终止，则 x=1；否则 x=056可计算问题与不可计算问题的启示 启示：对于问题而言，并不都是可以计算的 ，即使是可以计算的问题，也存在是多项式 时间内可以计算的，还是非多项式时间内可 以计算的，当然，还存在着神秘的NP问题。57相关图灵奖获得者 米凯尔拉宾和达纳斯科特 1976年图灵奖获得者，非确定性有限状态自动机理论的 开创者 斯蒂芬库克 1982年图灵奖获得者，NP完全性理论奠基人 理查德卡普 1985年图灵奖获得者，发明“分枝限界法”的三栖学者 尤里斯哈特马尼斯和理查德斯特恩施 1993年图灵奖获得者，计算复杂性理论的主要奠基人58相关图灵奖获得者 曼纽尔布卢姆 1995年图灵奖获得者，计算复杂性理论的奠基人之一 约翰霍普克洛夫和罗伯特陶尔扬 1986年图灵奖获得者，硕果累累的算法设计大师 姚期智 2000年图灵奖获得者，计算理论领域卓越的开拓者 利维斯、沙米尔和阿德勒曼 2002年图灵奖获得者，最具影响力的公钥密码算法RSA 的发明人59米凯尔拉宾和达纳斯科特（1931?）（1932?）60斯蒂芬库克（1939?）61理查德卡普（1935?） 62尤里斯哈特马尼斯和理查德斯特恩施（1928?）（1936?）63曼纽尔布卢姆（1938?）64约翰霍普克洛夫和罗伯特陶尔扬（1939?）（1948?）65姚期智（1946?） 66利维斯、沙米尔和阿德勒曼（1947?）（1945?）（1952?）674.2.3 GOTO语句问题及程序设计方法学 程序的 3 种基本结构 “GOTO语句”问题的争论68程序的 3 种基本结构 1966年C.Bhm和G.Jacopini发表了关于“程 序结构”的重要论文，指出：任何程序的逻辑 结构都可以用3种最基本的结构，即顺序结构 、选择结构和循环结构来表示69“GOTO语句”问题的争论 1968年，首次提出了“GOTO语句是有害的”问题， 引发了激烈的争论 公正的论述：滥用GOTO语句是有害的，完全禁止 也不明智，在不破坏程序良好结构的前提下，有控 制地使用一些GOTO语句，就有可能使程序更清晰 ，效率也更高 关于“GOTO语句”问题的争论直接导致了一个新的 学科分支领域，即程序设计方法学的产生 程序设计方法学是对程序的性