【2017年整理】计算机导论.pptVIP

第8章 计算机领域的典型问题;8.1 图论问题 ;8.1.1 歌尼斯堡七桥问题;8.1.1 歌尼斯堡七桥问题;欧拉的3条判定规则 如果通奇数座桥的地方不止两个，满足要求的路径是找不到的。 如果只有两个地方通奇数座桥，可以从这两个地方之一出发，找到所要求的路径。 如果没有一个地方是通奇数座桥的，则无论从哪里出发，所要求的路径都能实现。;欧拉图 经过图中每条边一次且仅一次的路径称为欧拉路径。 如果欧拉路径的起点和终点为图中的同一个顶点，这时的欧拉路径称为欧拉回路。 包含有欧拉回路的图称为欧拉图。;欧拉的研究工作奠定了图论的基础 涉及到的后续课程 离散数学 数据结构 应用领域 计算机网络性能分析 交通运输网络调度 地下管网配置 社会网络分析;8.1.2 哈密顿回路问题;哈密顿回路与欧拉回路的区别 哈密顿回路是访问图的每个顶点一次，而欧拉回路是访问图的每条边一次。 对于一个图是否存在欧拉回路，已给出充要条件；而对于一个图是否存在哈密顿回路，至今仍未找到充要条件。;问题描述 一个邮递员应如何选择一条路线，使他能够从邮局出发，走遍他负责送信的所有街道，最后回到邮局，并且所走的路程最短。 归结为图论问题：给定一个连通无向图，求该图的一条经过每条边至少一次的最短回路。 对于欧拉图，找到一条欧拉回路即可。 对于非欧拉图，才是中国邮路问题的 研究重点。 ;8.2 算法复杂性问题 ;8.2.1 汉诺塔问题;8.2.1 汉诺塔问题;递归思想 将一个较大的问题的求解归约为一个或多个子问题的求解。而这些子问题比原问题简单，且在结构上与原问题相同。;8.2.1 汉诺塔问题;8.2.1 汉诺塔问题;8.2.2 旅行商问题;8.2.2 旅行商问题;8.2.3 NP完全问题;8.3 计算机智能问题 ;8.3.1 图灵测试;8.3.1 图灵测试;8.3.1 图灵测试;8.3.2 西尔勒中文小屋;8.3.2 西尔勒中文小屋;8.3.2 西尔勒中文小屋;人工智能的含义 研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。 人工智能研究的目标 使机器能够胜任一些通常需要人类智能才能完成的复杂工作。 ;人工智能的不同观点 符号主义：人的认知基元是符号，人是一??物理符号系统，计算机也是一个物理符号系统，因而能够用计算机来模拟人的智能行为。 连接主义：认为人的思维基元是神经元，而不是符号处理过程。认为人脑不同于电脑，主张人工智能应着重于结构模拟。 行为主义：认为智能取决于感知和行动，提出智能行为的感知－动作模式。;人工智能的展望 目前人们对心理学和生物学的认识还很不成熟，对人脑的结构还没有真正了解，无法建立起人脑思维完整的数学模型。 让计算机具有和人脑完全一样的智能，不是短期内能够实现的。 在相当长的时间内，只能从不同的侧面、以不同的方式让计算机具有某些类似人的智能。;8.3.3 博弈问题;8.3.3 博弈问题;博弈树 博弈树类似于状态图和问题求解有哪些信誉好的足球投注网站中使用的有哪些信誉好的足球投注网站树。 有哪些信誉好的足球投注网站树上的一个结点对应一个棋局，树的分支表示棋的走步，根结点表示棋局的开始，叶结点表示棋局的结束。 博弈树是非常大的，国际象棋有10120个结点，中国象棋来有10160个结点，快速有哪些信誉好的足球投注网站非常重要。;中国象棋博弈树;8.4 并发控制问题 ;8.4.1 生产者-消费者问题;8.4.1 生产者-消费者问题;8.4.2 哲学家共餐问题;8.4.2 哲学家共餐问题;8.4.2 哲学家共餐问题;8.4.2 哲学家共餐问题;8.5 本章小结