计算机领域的典型问题精选PPT.ppt

《计算机领域的典型问题精选PPT.ppt》由会员分享，可在线阅读，更多相关《计算机领域的典型问题精选PPT.ppt（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机算机领域的典型域的典型问题第1页，此课件共39页哦8.1 图论问题图论问题 歌尼斯堡七桥问题歌尼斯堡七桥问题哈密尔顿回路问题哈密尔顿回路问题中国邮路问题中国邮路问题 第2页，此课件共39页哦8.1.1 歌尼斯堡七桥问题歌尼斯堡七桥问题问题描述问题描述一个人怎样不重复地走完七座桥，最后还能回到原出发地点一个人怎样不重复地走完七座桥，最后还能回到原出发地点？第3页，此课件共39页哦8.1.1 歌尼斯堡七桥问题歌尼斯堡七桥问题欧拉对欧拉对哥尼斯堡哥尼斯堡七桥问题进行了研究七桥问题进行了研究1736年，欧拉论证了该问题无解。年，欧拉论证了该问题无解。从一点出发不重复地走遍从一点出发不重复地走遍7

2、座桥，最后又回到原来出发点座桥，最后又回到原来出发点是不可能的。是不可能的。欧拉对了问题进行了抽象欧拉对了问题进行了抽象 描述：用描述：用4个字母个字母A、B、C、D代表代表4个城区，并用个城区，并用 7条边表示条边表示7座桥。座桥。第4页，此课件共39页哦欧拉的欧拉的3 3条判定规则条判定规则如果通奇数座桥的地方不止两个，满足要求的路如果通奇数座桥的地方不止两个，满足要求的路径是找不到的。径是找不到的。如果只有两个地方通奇数座桥，可以从这两个地如果只有两个地方通奇数座桥，可以从这两个地方之一出发，找到所要求的路径。方之一出发，找到所要求的路径。如果没有一个地方是通奇数座桥的，则无论从哪如果没

3、有一个地方是通奇数座桥的，则无论从哪里出发，所要求的路径都能实现。里出发，所要求的路径都能实现。8.1.1 歌尼斯堡七桥问题歌尼斯堡七桥问题第5页，此课件共39页哦欧拉的研究工作奠定了图论的基础欧拉的研究工作奠定了图论的基础涉及到的后续课程。涉及到的后续课程。离散数学。离散数学。数据结构。数据结构。应用领域。应用领域。计算机网络性能分析。计算机网络性能分析。交通运输网络调度。交通运输网络调度。地下管网配置。地下管网配置。8.1.1 歌尼斯堡七桥问题歌尼斯堡七桥问题航空网络第6页，此课件共39页哦8.1.2 哈密顿回路问题哈密顿回路问题问题描述（周游世界游戏）问题描述（周游世界游戏）找一条从某个

4、城市出发，经过每个城市恰好一次，最后回到找一条从某个城市出发，经过每个城市恰好一次，最后回到出发地的路径。出发地的路径。第7页，此课件共39页哦哈密顿回路哈密顿回路与与欧拉回路欧拉回路的区别的区别哈密顿回路问题哈密顿回路问题是访问每个顶点一次，而是访问每个顶点一次，而欧拉回路问题欧拉回路问题是访是访问每条边一次。问每条边一次。对于一个图是否存在对于一个图是否存在欧拉回路欧拉回路，已给出充要条件；而对于，已给出充要条件；而对于一个图是否存在一个图是否存在哈密顿回路哈密顿回路至今仍未找到充要条件。至今仍未找到充要条件。8.1.2 哈密顿回路问题哈密顿回路问题第8页，此课件共39页哦问题描述问题描述

5、一一个个邮邮递递员员应应如如何何选选择择一一条条路路线线，使使他他能能够够从从邮邮局局出出发发，走走遍遍他负责送信的所有街道，最后回到邮局，并且所走的路程最短。他负责送信的所有街道，最后回到邮局，并且所走的路程最短。归归结结为为图图论论问问题题：给给定定一一个个连连通通无无向向图图，求求该该图图的的一一条条经经过过每条边至少一次的最短回路。每条边至少一次的最短回路。对对于于欧欧拉拉图图，找找到到一一条条欧欧拉拉回回路路即即可可。对对于于非非欧欧拉拉图图，才才是是中国邮路问题的研究重点。中国邮路问题的研究重点。8.1.3 中国邮路问题中国邮路问题第9页，此课件共39页哦8.2 算法复杂性问题算法

6、复杂性问题 汉诺塔问题汉诺塔问题旅行商问题旅行商问题 NP完全问题完全问题第10页，此课件共39页哦8.2.1 汉诺塔问题汉诺塔问题问题描述问题描述将第一根柱子上的将第一根柱子上的64个盘子借助第二根柱子全部移到第三根个盘子借助第二根柱子全部移到第三根柱子上。柱子上。64个盘子63个盘子第11页，此课件共39页哦8.2.1 汉诺塔问题汉诺塔问题移动规则移动规则每次只能移动一个盘子。每次只能移动一个盘子。盘子只能在三根柱子上移动，不能放在他处。盘子只能在三根柱子上移动，不能放在他处。在移动过程中，三根柱子上的盘子必须始终保持在移动过程中，三根柱子上的盘子必须始终保持大盘在下，小盘在上。大盘在下，

7、小盘在上。第12页，此课件共39页哦递归思想递归思想将一个较大的问题的求解归约为一个或多个子问题的求将一个较大的问题的求解归约为一个或多个子问题的求解。而这些子问题比原问题简单，且在结构上与原问题解。而这些子问题比原问题简单，且在结构上与原问题相同。相同。8.2.1 汉诺塔问题汉诺塔问题第13页，此课件共39页哦8.2.1 汉诺塔问题汉诺塔问题用递归方法求解用递归方法求解移动移动n个盘子的汉诺塔问题需要移动的盘子数是个盘子的汉诺塔问题需要移动的盘子数是n-1个盘子的汉诺个盘子的汉诺塔问题需要移动的盘子数的塔问题需要移动的盘子数的2倍加倍加1。h(n)=2h(n-1)+1 =2(2h(n-2)+

8、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第14页，此课件共39页哦8.2.1 汉诺塔问题汉诺塔问题用递归方法求解用递归方法求解每次只能移动一个盘子，要完成汉诺塔的搬迁，每次只能移动一个盘子，要完成汉诺塔的搬迁，需要移动盘子的次数为：需要移动盘子的次数为：264-1=18 446 744 073 709 551 615每秒移动一次，需要大约每秒移动一次，需要大约5849亿年的时间。亿年的时间。第15页，此课件共39页哦8.2.2 旅行商问题旅行商问题问题描述问题描述一旅行商从某城市出发，必

9、须经过每个城市且只能经过一次，最后回到原出一旅行商从某城市出发，必须经过每个城市且只能经过一次，最后回到原出发城市。发城市。要求找到一条距离最短的路径（或费用最少的路径）。要求找到一条距离最短的路径（或费用最少的路径）。原始的解决办法原始的解决办法列出每条可能的路径。列出每条可能的路径。从中选择距离最短的路径。从中选择距离最短的路径。第16页，此课件共39页哦8.2.2 旅行商问题旅行商问题遇到的困难遇到的困难城市个数较多时难以实现。城市个数较多时难以实现。组合爆炸问题。组合爆炸问题。可行的解决办法可行的解决办法启发式算法。启发式算法。近似算法。近似算法。第17页，此课件共39页哦8.2.3

10、NP完全问题完全问题P类问题类问题将所有可以在多项式时间内求解的问题称为将所有可以在多项式时间内求解的问题称为P类问题。类问题。NP类问题类问题将所有在多项式时间内可以验证的问题称为将所有在多项式时间内可以验证的问题称为NP类问题。类问题。NP完全问题完全问题在在NP类问题中，某些问题的复杂性与整个类的复杂性类问题中，某些问题的复杂性与整个类的复杂性有关，如果这些问题中的任意一个能在多项式的时间有关，如果这些问题中的任意一个能在多项式的时间内求解，则所有内求解，则所有NP类问题都能在多项式时间内求解，类问题都能在多项式时间内求解，这些这些NP类问题称为类问题称为NP完全问题。完全问题。第18页

11、，此课件共39页哦8.3 计算机智能问题计算机智能问题 图灵测试图灵测试西尔勒中文小屋西尔勒中文小屋博弈问题博弈问题第19页，此课件共39页哦8.3.1 图灵测试图灵测试机器能思维吗机器能思维吗？第20页，此课件共39页哦8.3.1 图灵测试图灵测试图灵测试游戏图灵测试游戏游戏的参与者游戏的参与者一个男人、一个女人和一个不限性别的提问者。一个男人、一个女人和一个不限性别的提问者。游戏目标游戏目标提问者通过对其他两人的提问，来鉴别其中的男女。提问者通过对其他两人的提问，来鉴别其中的男女。游戏要求游戏要求提问者呆在与其他两个游戏者相隔离的房间里。提问者呆在与其他两个游戏者相隔离的房间里。提问者和两

12、游戏者之间通过电传打字机进行沟通。提问者和两游戏者之间通过电传打字机进行沟通。第21页，此课件共39页哦8.3.1 图灵测试图灵测试图灵测试游戏图灵测试游戏把游戏中的男人换成机器。把游戏中的男人换成机器。若提问者在与机器、女人的游戏中作出的错误判断与若提问者在与机器、女人的游戏中作出的错误判断与在男人、女人之间的游戏中作出的错误判断，其次数在男人、女人之间的游戏中作出的错误判断，其次数相同或更多，则判定这部机器能够思维。相同或更多，则判定这部机器能够思维。根据图灵当时的预测，到根据图灵当时的预测，到2000年能有机器通过这样的测试。年能有机器通过这样的测试。有人认为，在有人认为，在1997年战

13、胜国际象棋大师卡斯帕罗夫的年战胜国际象棋大师卡斯帕罗夫的深深蓝蓝计算机可以看作通过了图灵测试。计算机可以看作通过了图灵测试。第22页，此课件共39页哦8.3.2 西尔勒中文小屋西尔勒中文小屋问题描述问题描述西尔勒被关在一个小屋中，屋子里有序地堆放着足够的西尔勒被关在一个小屋中，屋子里有序地堆放着足够的中文字符，而他对中文一窍不通。中文字符，而他对中文一窍不通。屋外的人递进一串中文字符，同时还附有一本用英文编屋外的人递进一串中文字符，同时还附有一本用英文编写的处理中文字符的规则，这些规则将递进来的字符和写的处理中文字符的规则，这些规则将递进来的字符和小屋中的字符之间的转换作了形式化的规定。小屋中

14、的字符之间的转换作了形式化的规定。西尔勒按照规则对这些字符进行处理后，将一串新的西尔勒按照规则对这些字符进行处理后，将一串新的中文字符送出屋外。中文字符送出屋外。第23页，此课件共39页哦8.3.2 西尔勒中文小屋西尔勒中文小屋问题描述问题描述实际上，送进来的字符串就是屋外人提出的实际上，送进来的字符串就是屋外人提出的问题问题，送出去，送出去的字符串就是所提出问题的的字符串就是所提出问题的答案答案。但西尔勒并不清楚自己在。但西尔勒并不清楚自己在做什么？做什么？第24页，此课件共39页哦8.3.2 西尔勒中文小屋西尔勒中文小屋西尔勒的观点西尔勒的观点形式化的计算机仅有语法，没有语义，只是按规形式

15、化的计算机仅有语法，没有语义，只是按规则办事，并不理解规则的含义及自己在做什么？则办事，并不理解规则的含义及自己在做什么？机器永远也不可能代替人脑。机器永远也不可能代替人脑。图灵的观点图灵的观点不要求机器与人脑在内部构造上一样，只要与人不要求机器与人脑在内部构造上一样，只要与人脑有相同的功能就认为机器有思维。脑有相同的功能就认为机器有思维。第25页，此课件共39页哦人工智能的含义人工智能的含义研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。及应用系统的一门新的技术科学。人工智能研究的目标人工智能研究的

16、目标使机器能够胜任一些通常需要人类智能才能完成的复杂工作。使机器能够胜任一些通常需要人类智能才能完成的复杂工作。8.3.2 西尔勒中文小屋西尔勒中文小屋第26页，此课件共39页哦人工智能的不同观点人工智能的不同观点符号主义符号主义：认为人的认知基元是符号，认为人是一个物理符认为人的认知基元是符号，认为人是一个物理符号系统，计算机也是一个物理符号系统，因而能够用计算机来模号系统，计算机也是一个物理符号系统，因而能够用计算机来模拟人的智能行为。拟人的智能行为。连接主义连接主义：认为人的思维基元是神经元，而不是符号处理过程。认为人的思维基元是神经元，而不是符号处理过程。认为人脑不同于电脑，主张人工智

17、能应着重于结构模拟。认为人脑不同于电脑，主张人工智能应着重于结构模拟。行为主义行为主义：认为智能取决于感知和行动，提出智能行为的认为智能取决于感知和行动，提出智能行为的感知动作感知动作模式。模式。8.3.2 西尔勒中文小屋西尔勒中文小屋第27页，此课件共39页哦人工智能的展望人工智能的展望目前人们对心理学和生物学的认识还很不成熟，对人目前人们对心理学和生物学的认识还很不成熟，对人脑的结构还没有真正了解，无法建立起人脑思维完整脑的结构还没有真正了解，无法建立起人脑思维完整的数学模型。的数学模型。让计算机具有和人脑完全一样的智能，不是短期内能够实现让计算机具有和人脑完全一样的智能，不是短期内能够实

18、现的。的。在相当长的时间内，只能从不同的侧面、以不同的方式让计算在相当长的时间内，只能从不同的侧面、以不同的方式让计算机具有某些类似人的智能。机具有某些类似人的智能。8.3.2 西尔勒中文小屋西尔勒中文小屋第28页，此课件共39页哦8.3.3 博弈问题博弈问题博弈的含义博弈的含义狭义上讲，博弈是指下棋、玩扑克牌、掷骰子等狭义上讲，博弈是指下棋、玩扑克牌、掷骰子等具有输赢性质的游戏。具有输赢性质的游戏。广义上讲，博弈就是对策或斗智。广义上讲，博弈就是对策或斗智。第29页，此课件共39页哦8.3.3 博弈问题博弈问题双人完备博弈双人完备博弈两位选手对垒，轮流走步，其中一方完全知道另两位选手对垒，轮

19、流走步，其中一方完全知道另一方已经走过的棋步以及未来可能的棋步。一方已经走过的棋步以及未来可能的棋步。对弈的结果要么是一方赢（另一方输），要么是对弈的结果要么是一方赢（另一方输），要么是和局。和局。对于任何一种双人完备博弈，都可以用一个博弈对于任何一种双人完备博弈，都可以用一个博弈树来描述，并通过博弈树搜索策略寻找最佳解。树来描述，并通过博弈树搜索策略寻找最佳解。第30页，此课件共39页哦博弈树博弈树博弈树类似于状态图和问题求解搜索中使用的搜博弈树类似于状态图和问题求解搜索中使用的搜索树。索树。搜索树上的一个结点对应一个棋局，树的分支表搜索树上的一个结点对应一个棋局，树的分支表示棋的走步，根结

20、点表示棋局的开始，叶结点表示棋的走步，根结点表示棋局的开始，叶结点表示棋局的结束。示棋局的结束。博弈树是非常大的，国际象棋有博弈树是非常大的，国际象棋有10120个结点，中个结点，中国象棋来有国象棋来有10160个结点。个结点。8.3.3 博弈问题博弈问题第31页，此课件共39页哦8.4 并发控制问题并发控制问题 生产者生产者-消费者问题消费者问题哲学家共餐问题哲学家共餐问题第32页，此课件共39页哦8.4.1 生产者生产者-消费者问题消费者问题问题描述问题描述有有n个生产者和个生产者和m个消费者，在生产者和消费者之个消费者，在生产者和消费者之间设置了一个能存放间设置了一个能存放k个产品的货架

21、。个产品的货架。只要货架未满，生产者只要货架未满，生产者pi生产的产品就可以放入生产的产品就可以放入货架，每次放入一个产品；货架，每次放入一个产品；只要货架非空，消费者只要货架非空，消费者cj就可以货架取走产品消就可以货架取走产品消费，每次取走一个。费，每次取走一个。所有生产者的产品生产和消费者的产品消费都可所有生产者的产品生产和消费者的产品消费都可以按自己的意愿进行，即相互之间是独立的。以按自己的意愿进行，即相互之间是独立的。第33页，此课件共39页哦8.4.1 生产者生产者-消费者问题消费者问题约束条件约束条件不允许消费者从空货架取产品，现实中也是取不不允许消费者从空货架取产品，现实中也是

22、取不到的。到的。不允许生产者向一个已装满产品的货架中再放入不允许生产者向一个已装满产品的货架中再放入产品。产品。应用背景应用背景是对操作系统中并发进程同步的一种抽象描述，是对操作系统中并发进程同步的一种抽象描述，多个进程虽然看起来是按异步方式执行的，但相多个进程虽然看起来是按异步方式执行的，但相互有关的进程应有一种协调机制。互有关的进程应有一种协调机制。第34页，此课件共39页哦8.4.2 哲学家共餐问题哲学家共餐问题问题描述问题描述哲学家的生活除了吃面条就是思考问题。哲学家的生活除了吃面条就是思考问题。吃面条的时候需要左、右手各拿起一支筷子。吃面条的时候需要左、右手各拿起一支筷子。吃完后将筷

23、子放回原处，继续思考问题。吃完后将筷子放回原处，继续思考问题。第35页，此课件共39页哦8.4.2 哲学家共餐问题哲学家共餐问题一个哲学家的活动进程表示一个哲学家的活动进程表示思考问题。思考问题。饿了停止思考，左手拿一支筷子（拿不到就等）。饿了停止思考，左手拿一支筷子（拿不到就等）。右手拿一支筷子（拿不到就等）右手拿一支筷子（拿不到就等）。进餐。进餐。放右手筷子。放右手筷子。放左手筷子。放左手筷子。重新回到思考问题状态。重新回到思考问题状态。第36页，此课件共39页哦8.4.2 哲学家共餐问题哲学家共餐问题可能出现的问题可能出现的问题当所有的哲学家都同时拿起左手筷子时，则所有的哲学家都将当所有

24、的哲学家都同时拿起左手筷子时，则所有的哲学家都将拿不到右手的筷子，并处于等待状态，那么哲学家都将无法进拿不到右手的筷子，并处于等待状态，那么哲学家都将无法进餐，最终饿死。餐，最终饿死。将哲学家的活动进程修改一下，变为当右手的筷子拿不到时，将哲学家的活动进程修改一下，变为当右手的筷子拿不到时，就放下左手的筷子。就放下左手的筷子。可能在一个瞬间，所有的哲学家都同时拿起左手的筷子，则自然可能在一个瞬间，所有的哲学家都同时拿起左手的筷子，则自然拿不到右手的筷子，于是都同时放下左手的筷子，等一会，又同拿不到右手的筷子，于是都同时放下左手的筷子，等一会，又同时拿起左手的筷子，如此这样永远重复下去，则所有的

25、哲学家仍时拿起左手的筷子，如此这样永远重复下去，则所有的哲学家仍然无法进餐。然无法进餐。第37页，此课件共39页哦8.4.2 哲学家共餐问题哲学家共餐问题应用背景应用背景描述了多个进程以互斥方式访问有限资源的问题。描述了多个进程以互斥方式访问有限资源的问题。计算机系统不可能总是提供足够多的资源，但又计算机系统不可能总是提供足够多的资源，但又想尽可能多地同时满足多个用户的使用要求。想尽可能多地同时满足多个用户的使用要求。研究人员已经采取了一些非常有效的方法来尽量研究人员已经采取了一些非常有效的方法来尽量满足多个用户对有限资源的同时访问需求，同时满足多个用户对有限资源的同时访问需求，同时尽可能少地

26、出现死锁现象的发生。尽可能少地出现死锁现象的发生。第38页，此课件共39页哦8.5 本章小结本章小结歌尼斯堡七桥问题、哈密顿回路问题、中国邮路问题等问歌尼斯堡七桥问题、哈密顿回路问题、中国邮路问题等问题促进了题促进了图论图论的产生和发展。的产生和发展。旅行商问题、汉诺塔问题有助于对旅行商问题、汉诺塔问题有助于对算法复杂性算法复杂性的研究，的研究，并促使人们设计出更好的解决问题的实用算法。并促使人们设计出更好的解决问题的实用算法。图灵测试问题、西尔勒中文小屋问题、博弈问题能促进对图灵测试问题、西尔勒中文小屋问题、博弈问题能促进对人人工智能工智能的深入理解和研究。的深入理解和研究。生产者生产者-消费者问题、哲学家共餐问题对于深入理解并实现消费者问题、哲学家共餐问题对于深入理解并实现并发控制并发控制是非常有益的。是非常有益的。第39页，此课件共39页哦