计算学科中的科学问题.pptVIP

第二章 计算学科中的科学问题 文坤梅 E-Mail:kunmei.wen@ 智能与分布计算实验室 Intelligence and Distributed Computing Lab 科学问题的定义 科学问题是指一定时代的科学认识主体，在已完成的科学知识和科学实践的基础上，提出的需要解决且有可能解决的问题。它包含一定的求解目标和应答域，但尚无确定的答案。 能否在所从事的工作中提出关键和重要的科学问题，对我们每个人来说都是一个挑战。 科学问题的主要特征 时代性：每一个时代都有它自己的科学问题 混沌性：渴望对新知识的追求，追求开始的时候是模糊不清的 可解决性 可变异性：能引出另外具有可解决性的科学问题 可待解性：绝非永远不可解决 1 哥尼斯堡(Konigsberg)七桥问题 17世纪的东普鲁士有一座哥尼斯堡城，城中有一座奈佛夫岛，普雷格尔河的两条支流环绕其旁，并将整个城市分成北区、东区、南区和岛区4个区域，全城共有7座桥将4个城区相连起来。 人们常通过这7座桥到各城区游玩，于是产生了一个有趣的 数学难题：寻找走遍这7座桥，且只许走过每座桥一次，最后 又回到原出发点的路径。该问题就是著名的“哥尼斯堡七桥问 题”。 哈密尔顿回路问题 在图论中还有一个很著名的“哈密尔顿回路问题”。 爱尔兰著名学者威廉·哈密尔顿爵士在1859年提出： 在任一给定的图中，能不能找到这样的路径，即从一点出发不重复地走过所有的结点（不必通过图中每一条边），最后又回到原出发点。 解题过程（3个圆盘问题） 顺序算法和并行算法 顺序算法--时间复杂性大； 并行算法--空间复杂性大。 直觉上，顺序算法解决不了的问题完全可以用并行算法来解决，是这样吗？ 8．博弈树有哪些信誉好的足球投注网站（信息科学导论 ） 国际象棋、西洋跳棋与围棋、中国象棋一样都属于双人完备博弈。所谓双人完备博弈就是两位选手对垒，轮流走步，其中一方完全知道另一方已经走过的棋步以及未来可能的走步，对弈的结果要么是一方赢（另一方输），要么是和局。 对于任何一种双人完备博弈，都可以用一个博弈树（与或树）来描述，并通过博弈树有哪些信誉好的足球投注网站策略寻找最佳解。 博弈树类似于问题求解有哪些信誉好的足球投注网站中使用的有哪些信誉好的足球投注网站树。有哪些信誉好的足球投注网站树上的第一个结点对应一个棋局，树的分支表示棋的走步，根节点表示棋局的开始，叶节点表示棋局的结束。一个棋局的结果可以是赢、输或者和局。 博弈树的规模： 国际跳棋--1040个结点 国际象棋--10120个结点（棋局总数） 中国象棋--估计有10160个结点， 围棋--盘面状态达10768。 7、J.R.Searle 的 “中文屋子” Soft Artificial Intelligence：计算机是一个工具 Strong Artificial Intelligence：不仅是一个工具，而且 具有意识 “中文屋子”反驳SAI观点 Searle 真的懂中文吗？ 形式化的计算机仅有语法，没有语义 ? 人在计算能力上超过机器是不现实的 机器永远也不可能代替人脑 8、博弈树有哪些信誉好的足球投注网站 信息科学导论 P283-286 一字棋例 课程回顾：1、计算机发展沿革、趋势、词汇 2、计算机科学技术大的构架：十四个主领域和3个过程，满足人类思维的基本特征，抽象→理论→设计 什么是算法：解决问题的一套规则、一系列步骤或指令 算法分为串行和并行两种 时间复杂度：time complexity对算法运行所需要的时间的度量→算法执行的步骤数目（非时间单位秒，效率的度量）→非精确的、数量级的 空间复杂度：space complexity 非精确的：如人的阶段：婴儿、儿童、少年、青年。。。老年 度量反映一种趋势，随问题规模的增大（n），所需时间（T）的增长趋势，曲线图 学生 50双不同的袜子，一次洗，配对 时间复杂度，反映的趋势：算法1：O(n2) 算法2：O(n) 算法2以空间换时间，算法1时健要求更高，算法2空间要求更高 一个问题有不同的解决方法，就时间复杂度来说 导致了计算机科学与技术中12个基本概念之一：折衷，时空折衷 对一个算法应该出时、空复杂度分析（P88） 是一个难解问题 抽象：找一个好理论→递归，解决问题 大三开设计算机图形学课程 模型 Model 线框model：直线+折线逼近图形、像 曲面model：空间曲面 描述物体 立体model：基本立体，包括圆、球、圆柱体、圆锥体等9种基本立体，如人：可用一个圆球、五个圆柱和四个圆锥体组成 动画：美工+计算机实现 必须解决的两个问题：1、模拟，要真实；2、要能用计算机实现 分形学：模拟、刻画流动的物体，如白云、火焰、浪花、烟火等，用算法提出新的模型，以上三种基本模型不能刻画 计算机模拟雪花 三角形演化：图形示例（板书） 以上被称为自相似