计算学科的形成及其基本问题.ppt

第 4 课 计算学科的形成及其 基本问题 /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移到C 36 算法的复杂性 按照上面的算法，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=10 39 算法复杂性分类 算法复杂性分类 多项式的(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=NP 42 2 证比求易算法 “证比求易算法”童话：从前，有一个酷爱数学的 年轻国王向邻国一位聪明美丽的公主求婚。公主 出了这样一道题：求出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 启示：对难解性问题而言，单纯的提高计算机系统 的速度是远远不够的，而降低算法复杂度的数量级 才是最关键的问题 45 3 旅行商问题与组合爆炸问题 旅行商问题：有若干个城市，任何两个城市之间的 距离都是确定的，现要求一旅行商从某城市出发， 必须经过每一个城市且只能在每个城市逗留一次， 最后回到原出发城市。问如何事先确定好一条最短 的路线，使其旅行的费用最少 原始办法：列出每一条可供选择的路线（即对给定 的城市进行排列组合），计算出每条路线的总里程 ，最后从中选出一条最短的路线 若设城市数目为n时，那么组合路径数则为(n-1)! 46 组合路径图 47 组合爆炸问题 随着城市数目的不断增大，组合路线数将呈 指数级数规律急剧增长，以至达到无法计算 的地步 解决组合爆炸问题一个合理的办法是寻找其 启发式算法、近似算法、概率算法等 48 判为素数的概率算法 若Miller-Rabin算法返回 “composite” ，则该数一 定不是素数 否则，该数是素数或伪素数。可以证明，此时是伪 素数的概率小于 因此若反复用不同随机数a测试，则通过连续t次测 试均是返回 “maybe prime”后，n是素数的概率 至少就是: Pr = 1-4-t 如: 对于t=10, n是素数的概率大于0.999999 49 4 找零问题、背包问题与贪婪算法 找零问题 背包问题 贪婪算法 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*算法、遗传算 法、蚂蚁算法以及演化算法等。 54 5 一个不可计算问题：停机问题 停机问题：能否找到这样一个测试程序，它 能判断出任意的程序在接收了某个输入并执 行后能否终止。若能找到，则停机问题可解 ；否则，不可解。 55 停机问题的反证 结论是：若S终止，则S不终止；若S不终止，则S终止。结 论矛盾，故可以确定这样的测试程序是不存在的，从而证明 停机问题的不可解。 已知：若P 可终止，则 x=1；否则 x=0 56 可计算问题与不可计算问题的启示 启示：对于问题而言，并不都是可以计算的 ，即使是可以计算的问题，也存在是多项式 时间内可以计算的，还是非多项式时间内可 以计算的，当然，还存在着神秘的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?） 67 4.2.3 GOTO语句问题及程序设计方法学 程序的 3 种基本结构 “GOTO语句”问题的争论 68 程序的 3 种基本结构 1966年C.Bhm和G.Jacopini发表了关于“程 序结构”的重要论文，指出：任何程序的逻辑 结构都可以用3种最基本的结构，即顺序结构 、选择结构和循环结构来表示 69 “GOTO语句”问题的争论 1968年，首次提出了“GOTO语句是有害的”问题， 引发了激烈的争论 公正的论述：滥用GOTO语句是有害的，完全禁止 也不明智，在不破坏程序良好结构的前提下，有控 制地使用一些GOTO语句，就有可能使程序更清晰 ，效率也更高 关于“GOTO语句”问题的争论直接导致了一个新的 学科分支领域，即程序设计方法学的产生 程序设计方法学是对程序的性质及其设计的理论和方法进 行研究的学科 70 相关图灵奖获得者 埃德斯加狄克斯特拉 1972年图灵奖获得者，最先察觉”goto有害”的计 算机科学大师 唐纳德克努特 1974年图灵奖获得者，经典巨著计算机程序设 计的艺术的年轻作者 罗伯特弗洛伊德 1978年图灵奖获得者，前后断言法的创始人 71 相关图灵奖获得者 尼克劳斯沃思 1984年图灵奖获得者，PASCAL之父及结构化程 序设计的首创者 阿米尔伯努利 1996午图灵奖获得者，把时态逻辑引入计算机科 学 奥尔约翰戴尔和克利斯登奈加特 2001年图灵奖获得者，挪威计算机科学家，面向 对象技术奠基人 72 埃德斯加狄克斯特拉 （19302002） 73 唐纳德克努特 （1938?） 74 罗伯特弗洛伊德 （19362001） 75 尼克劳斯沃思 （1934?） 76 阿米尔伯努利 （1941?） 77 奥尔约翰戴尔和克利斯登奈加特 （19302002）（19262002） 78 4.2.4 哲学家共餐问题与计算机资源管 理 生产者-消费者问题 哲学家共餐问题 79 生产者-消费者问题与哲学家共餐问题 都是并发程序设计中有关进程同步的问题， 即如何协调多个进程互斥地访问有限资源 n个进程 m个共享资源 80 生产者-消费者问题 所谓消费者是指使用某一软硬件资源时的进 程；而生产者是指提供或释放某一软硬件资 源时的进程 借用了火车信号系统中的信号灯来表示进程 之间的互斥 81 “哲学家共餐”问题 5个哲学家围坐在一张圆桌旁，每个人的面前摆有一碗面条 ，碗的两旁各摆有一只筷子。哲学家的生活除了吃饭就是思 考问题，其生活进程表示为： （1）思考问题 （2）饿了停止思考，左手拿一只筷子（如果左侧哲学家已持有它，则 需等待） （3）右手拿一只筷子（如果右侧哲学家已持有它，则需等待） （4）进餐 （5）放右手筷子 （6）放左手筷子 （7）重新回到思考问题状态（1） 问题：如何协调5个哲学家的生活进程，使得每一个哲学家 最终都可以进餐？ 82 可能出现的两种情况 （1）所有的哲学家都同时拿起左手筷子，并等 待拿右手筷子。（死锁Deadlock） （2）所有的哲学家都同时拿起左手筷子，然后 同时放下左手的筷子，等一会又同时拿起左 手的筷子，如此这样永远重复下去。（饥饿 Starvation） 可利用Petri网、并发程序语言等工具解决这 类问题 83 相关图灵奖获得者 肯尼思汤普森和丹尼斯里奇 1983年图灵奖获得者，C和UNIX的发明者 费尔南多考巴脱 1990年图灵奖获得者，实现分时系统的功臣 巴特勒兰普森 1992年图灵艾获得者，从Alto系统的首席科学家到微软的 首席技术宫 艾伦凯 2003年图灵奖获得者，“个人计算机之父”及Smalltalk语 言发明人 84 肯尼思汤普森和丹尼斯里奇 （1943?）（1941?） 85 费尔南多考巴脱 （1926?） 86 巴特勒兰普森 （1943?） 87 艾伦凯 （1940?） 88 4.2.5 两军问题与计算机网络 两军问题 互联网软件的分层结构 89 两军问题 两军问题可以这样描述： 一支白军被围困在一个山谷中，山谷的两侧是蓝军。 困在山谷中的白军人数多于山谷两侧的任一支蓝军，而少 于两支蓝军的总和。 若一支蓝军对白军单独发起进攻，则必败无疑；但若两支 蓝军同时发起进攻，则可取胜。 两支蓝军希望同时发起进攻，这样他们就要传递信息，以 确定发起攻击的具体时间。 假设他们只能派遣士兵穿越白军所在的山谷(唯一的通信 信道)来传递信息，那么在穿越山谷时，士兵有可能被俘 ，从而造成消息的丢失。 问题是：如何通信，以便蓝军必胜？ 90 两军问题 91 两军问题 两军问题通信协议设计： 两步握手协议： 一支蓝军指挥官发出消息：“我建议在明天拂晓发起进攻，请确认 ”，另一支蓝军指挥官同意这一建议。 三步握手协议： 一支蓝军指挥官发出消息：“我建议在明天拂晓发起进攻，请确认 ”，另一支蓝军指挥官同意这一建议，最初提出建议的指挥官将收 到的确认信息告诉对方。 四步握手协议： 结论是：不存在使蓝军必胜的通信约定(协议)。 92 TCP三向握手过程 93 互联网软件的分层结构 网络协议(简称协议)是为网络中的数据交换而 建立的规则、标准或约定的集合。 在Internet上，就是通过一个分层的具有不同 功能的软件来实现数据交换的。这就像邮寄 一个包裹的过程。 94 包裹邮寄的层次结构 95 Internet软件的层次结构 Internet软件有4个层次，即应用层、传输层、网络 层和链路层，每层均有相应的协议进行支撑，每台 Internet上的机器都具有这样的软件及层次结构。 一条信息在应用层产生，向下通过传输层和网络层 的处理，然后通过链路层被传递。这个信息由目的 地的链路层接收，通过网络层和传输层的逆操作， 最后将信息送到应用层。 为了确保网络协议的安全，研究人员提出了一系列 新的理论(如BAN类逻辑、Kailar逻辑、串空间理论 等)，研制了不少用于形式化验证的工具(如SMV、 SPIN、Athena等)，开辟了一个薪的研究领域：安 全协议工程。 96 Internet软件的层次结构 97 在协议栈中数据封装过程 98 相关图灵奖获得者 理查德哈明 1968年图灵奖获得者,发明纠错码的大数学家和信 息学专家 文登塞夫和罗们特凯恩 2004年图灵奖获得者，Internet基础通信协议 TCPIP之父 99 理查德哈明 （19151998） 100 文登塞夫和罗们特凯恩 （1943？）（1938？） 101 4.2.6 人工智能中的若干哲学问题 1 图灵测试 2 西尔勒的“中文屋子” 3 计算机中的博弈问题 102 1 图灵测试 测试机器是否能思维从功能的角度来判定机器 是否能思维 做法： 提问者（C）提出问题让一个男人（A）或一个女人（B） 回答，从中鉴别哪个是男人，哪个是女人 把上面这个游戏中的男人（A）换成一部机器来扮演 如果提问者在与机器、女人的游戏中作出的错误判断与在 男人、女人之间的游戏中作出错误判断的次数是相同的， 那么，就可以判定这部机器是能够思维的 103 “图灵测试”的意义 “图灵测试”标志着人工智能领域研究的开始 其哲学基础：思维就是计算（认知就是计算 ） 但由于人们对心理学和生物学的认识还很不 成熟，要对人类思维的本质进行描述，还是 相当遥远的事情，因此，到目前为止，人们 对人工智能的研究并无实质性的突破 104 2 西尔勒的“中文屋子” 西尔勒将自己比作一台机器，被单独关在一个屋子 里。他对中文一窍不通，但很擅长按照指令娴熟地 处理一些汉字符号。 为此，他按照屋外人编制的规则指令将递进来的一 串汉语字符进行一番搬弄，之后将一串新组成的字 符送出屋外。结果与一个地道的中国人作出的答案 没什么不同。但是我们能说西尔勒真的懂中文吗？ 启示： 形式化的计算机仅有语法，没有语义。 机器永远也不可能代替人脑 105 3 计算机中的博弈问题 从广义上讲，博弈就是对策或斗智，是人工智能领 域研究的重点内容之一 北京时间1997年5月初，在美国纽约公平大厦，“深 蓝”计算机与国际象棋冠军卡斯帕罗夫交战，前者以 两胜一负三平战胜后者 “深蓝”计算机中的关键技术：博弈树搜索 博弈树类似于状态图和问题求解搜索中使用的搜索树 搜索树上的每一个结点对应一个棋局，一般博弈树非常大 如何将搜索树修改到一个合理的范围，是一个值得研究的 问题 106 “深蓝与卡