计算科学导论知识讲解

《计算科学导论知识讲解》由会员分享，可在线阅读，更多相关《计算科学导论知识讲解（73页珍藏版）》请在金锄头文库上搜索。

1、2020/7/20,1,计算科学导论(一) 计算机与信息学院 蒋川群 13002187038 2012年10月,2020/7/20,2,目录,一、知识、能力与素质 二、计算科学的定义 三、图灵与计算本质 四、计算思维 五、抽象典型实例 六、可计算问题与不可计算问题 七、核心概念,2020/7/20,3,教育,哲学家费希特： 教育必须培养人的自我决定能力，而不是培养人们去适应传统世界； 教育重要的不是着眼于实用性、传播知识和技能，而是要唤醒学生的力量，培养其自我性、主动性、抽象的归纳力和理解力。,2020/7/20,4,教育,教育定义（联合国教科文组织） “有组织有目的的知识传授活动” “能够导

2、致学习的交流活动”,2020/7/20,6,知识、能力与素质,“知识”是基础、是载体、是表现形式。 知识具有“载体”属性，能力的培养和素质的提高必须部分地通过具体知识的传授来实施，否则就会成为空中楼阁。 要发挥知识的载体作用，需挖掘知识深层的内容，重视科学的世界观和方法学的启蒙教育。 在许多场合下，能力与素质，尤其是专业能力和专业素质，是通过知识表现出来的。,2020/7/20,7,知识、能力与素质,“能力”是技能化的知识，是知识的综合体现。 “能力”把知识运用的综合性、灵活性与探索性作为自己的重要内容。要保证知识运用的综合性、灵活性与探索性，就需要有丰富的知识作为支撑，并将其用于实践。,20

3、20/7/20,8,知识、能力与素质,“素质”是知识和能力的升华。 素质教育是在知识和能力的基础上，以全面提高受教育者的基本素质为目的，以尊重学生的主体作用和主动精神，注重开发人的潜能，形成健全的人格为根本特征的教育。,2020/7/20,9,知识、能力与素质,“素质”是知识和能力的升华。 素质是在潜移默化中提高的，它具有不易见性、不易获得性、终身受用性。素质除表现为“提高的潜移默化特性”外，它还需要通过人的能力、知识才能表现出来。素质的这种“表现的非直接性”和“隐藏性”，导致现有的考核方法难以对其给出准确的评价。这使得人们容易在工作中忽视它，这是值得注意的。,2020/7/20,10,知识、

4、能力与素质,“素质”是知识和能力的升华。 素质是在潜移默化中提高的，它具有不易见性、不易获得性、终身受用性。素质除表现为“提高的潜移默化特性”外，它还需要通过人的能力、知识才能表现出来。素质的这种“表现的非直接性”和“隐藏性”，导致现有的考核方法难以对其给出准确的评价。这使得人们容易在工作中忽视它，这是值得注意的。,2020/7/20,11,知识、能力与素质,“素质”是知识和能力的升华。 素质的“不易获得性”主要表现在需要较长期的积累，而且素质提升所涉及的学习内容很多属于一些难度较大的课程，特别是很多内容与一些课程深层的内容相关，这些又使得它很容易被舍弃。但其“终身受用性”却使我们不得不重视它

5、。,2020/7/20,12,知识、能力与素质,知识、能力、素质是进行高科技创新的基础。只有将三者贯通于教育的全过程，才能培养出高水平的人才。 爱因斯坦说过，想象力比知识更重要。 在大学里，除了通常意义下的素质培养外，重点是进行专业能力和专业素质的培养。,2020/7/20,13,追求教育的实效,听过的会忘记 看过的会记得 做过的才理解 会的程度：会用/会套用,2020/7/20,14,追求教育的实效,教了什么 学了什么 学到什么 会做什么,2020/7/20,15,计算科学的定义,计算科学是对描述和变换信息的算法过程进行的系统研究，包括理论、分析、设计、效率、实现和应用等。 计算科学的研究包

6、括从算法与可计算性的研究到根据可计算硬件和软件的实际问题的研究。,2020/7/20,16,计算科学的定义,计算科学不但包括从总体上对算法和信息处理过程进行研究的内容，也包括对规格要求的有效而可靠的软硬件设计它包括理论研究、实验方法和工程设计。,2020/7/20,17,图灵与计算本质,图灵对计算本质的揭示 所谓计算就是计算者（人或机器）对一条两端可无限延长的纸带上的一串0和1执行指令，一步一步地改变纸带上的0或1，经过有限步骤，最后得到一个满足预先规定的符号串的变换过程。,2020/7/20,18,图灵与计算本质,图灵对计算本质的揭示 图灵的研究成果：可计算性=图灵可计算性 算法：也称为能行

7、方法或能行过程，是对解题（计算）过程的精确描述，它由一组定义明确且能机械执行的规则（语句、指令等）组成。 结论：任一过程是能行的（能够具体表现在一个算法中），当且仅当它能够被一台图灵机实现。,2020/7/20,19,计算思维,计算思维（Computational ThinKing,CTK） 核心是基于计算机考虑问题求解,2020/7/20,20,计算思维,广义，计算思维可理解为：如何有效地利用计算机技术进行问题的求解。 即：在拥有了计算机这个工具后，如何有效地将其用于生产、生活和科学实践活动，提高工作效率，高质量地解决遇到的问题。 计算思维能力是现代人都应该具备的能力。,2020/7/20,

8、21,计算思维,狭义，计算思维可以理解为如何按照计算机求解问题的基本方法去考虑问题的求解，以便构建出相应的算法和基本程序等。 如何使计算机具有更强的工作能力，主要包括形式化、模型化描述和抽象思维与逻辑思维能力。,2020/7/20,22,计算思维,计算机专业人员研究一个问题的求解时，首先要解决问题的表示。 需要通过抽象进行形式化，建立适当的模型，然后对此抽象描述进行表示和处理。同时，让计算机系统“独立”实现对问题的求解之前，还要事先在自身的头脑中“构建”并“运行”各个适当抽象级别上的处理系统（过程）。,2020/7/20,23,计算思维,上述活动的有效进行主要依靠计算思维能力的支撑。 程序（计

9、算系统最基本的“成分”） 具有非物理特性，这种非物理特性要求研究人员具有抽象描述、抽象思维和逻辑思维能力。 学科基本教学原理是抽象第一。,2020/7/20,24,计算思维,针对计算机专业人才的培养，我们按照狭义的理解探讨计算思维能力。 计算思维能力主要包括： 问题的符号表示、问题求解过程的符号表示、逻辑思维、抽象思维、形式化证明、建立模型、实现类计算、实现模型计算、利用计算机技术等。,2020/7/20,25,案例：斯坦福大学实践型课程分类,表1 斯坦福大学2009-2010学年实践型课程类别,应用技术类课程 紧紧把握了信息技术的最新动态 讲授的知识是业界最新最火的技术 是随需而设的（这类课

10、程在10年的跨度里有76%会消失，只有将近24%会保留下来。 ） 意味着教学管理部门要敏锐地感知市场变化，定期地调整课程体系,应用方法学类课程 重点是传授学生应对常见问题的正确态度和方法 充分体现了“授人以渔”的教育精神 让学生在“态度、观念、视角”层面受益，对促进学生成长方面起到的作用不容小觑 课程的生命周期较长且内容相对稳定,2020/7/20,26,计算思维,误区 掌握计算机技术就是“会用”计算机、会上网、会将计算机联入网络、会写主页、会装计算机等 学一些基础理论知识是枯燥的、无意义的 干扰 起源：系统开发工具 友好性、傻瓜性 教师中的“实用主义”教育观点 学生中的浮躁情绪,2020/7

11、/20,27,计算思维,若将精力大量地投入到流行系统的具体使用上，人生将永远处于“培训班”。,2020/7/20,28,抽象典型实例(哥尼斯堡七桥问题),问题：寻找走遍这7座桥，且只许走过每座桥一次，最后又回到原出发点的路径。 原则：抽象出问题本质的东西，忽视问题非本质的东西。 方法：区域抽象为点、桥抽象为边。 问题转化：经过图中每边一次且仅一次的回路问题。,2020/7/20,29,欧拉3条判定规则： (1)如果奇数点（即连接的边数）大于2个，则不存在“经过图中每边一次且仅一次的路线”。 (2)如果奇数点（即连接的边数）等于2个，则存在“经过图中每边一次且仅一次的路线”（可从一个奇数点出发）

12、。 (3)如果奇数点（即连接的边数）为0个，则存在“经过图中每边一次且仅一次的回路”（可从任意一个点出发）。,抽象典型实例(哥尼斯堡七桥问题),2020/7/20,30,哈密尔顿回路问题 在任一给定的图中，能不能找到这样的路径，即从一点出发不重复地走过所有的结点一次（不必通过图中每一条边），最后又回到原出发点。 哈密尔顿回路问题：访问每个结点一次。 欧拉回路：访问每条边一次。 离散数学,抽象典型实例(哥尼斯堡七桥问题),2020/7/20,31,可计算问题与不可计算问题,梵天塔(汉诺塔)问题 移动规则 (1)每次只能移动一个盘子； (2)盘子只能在三根柱子上来回移动，不能放在他处； (3)在移

13、动过程中，三根柱子上的盘子必须始终保持大盘在下，小盘在上。 天神说：当这64个盘子全部移到第三根柱子上后，世界的末日就要到了。,2020/7/20,32,可计算问题与不可计算问题,所谓递归，就是将一个较大的问题规约为一个或多个性质（结构）相同的子问题的求解方法。 初始终极条件。,2020/7/20,33,可计算问题与不可计算问题,Hanoi(int n,char left,char middle,char right) if (n=1) move(1,one,_,three); else hanoi(n-1,left,right,middle) move(1,left,_,right) han

14、oi(n-1,middle,left,right) ,2020/7/20,34,可计算问题与不可计算问题,H(n)=2n-1 264-1=18446744073709551615 每秒移动一次，一年有31536000秒，需要花费大约5849亿年。 理论上的能行性隐含着计算模型的正确性，而实际实现中的能行性还包含时间与空间的有效性。算法复杂度,2020/7/20,35,可计算问题与不可计算问题,Ackermann函数 A(0,n)=n+1n=0,1, A(m,0)=A(m-1,1)m=1,2, A(m,n)=A(m-1,A(m,n-1) m=1,2, n=1,2,2020/7/20,36,可计算

15、问题与不可计算问题,算法复杂性中的难解性问题、P类问题和NP问题 算法复杂度：空间复杂度和时间复杂度 一个问题求解算法的时间复杂度大于多项式（如指数函数）时，算法的执行时间将随n的增加而急剧增长，以致即使是中等规模的问题也不能求解出来，于是在计算复杂性中，将这一类问题称为难解性问题。,2020/7/20,37,可计算问题与不可计算问题,算法复杂性中的难解性问题、P类问题和NP问题 P类问题：所有可以在多项式时间内求解的问题(确定性算法)。 NP类问题：所有在多项式时间内可以验证的问题(非确定性算法)。 确定性算法是非确定性算法的一种特例，因此可以断定NP包含P。,2020/7/20,38,可计

16、算问题与不可计算问题,证比求易算法 顺序算法和并行算法 顺序算法时间复杂度 并行算法空间复杂度 当将一个问题分解到多个处理器上解决时，由于算法中不可避免地存在必须串行执行的操作，从而大大地限制了并行计算机系统的加速能力。,2020/7/20,39,可计算问题与不可计算问题,阿达尔定律 Sp1/(f+(1-f)/p) f为求解某个问题的计算存在的必须串行执行的操作占整个计算的百分比， p为处理器的数目， Sp为并行计算机系统最大的加速能力(倍) 设：f=1%，p，则Sp=100,2020/7/20,40,可计算问题与不可计算问题,阿达尔定律启示 对难解性问题而言，单纯地提高计算机系统的速度是远远不够的，而降低算法复杂度的数量级才是最关键的问题。,2020/7/20,41,可计算问题与不可计算问题,P=?NP 若P=NP，则所有在多项式时间内可验证的问题都将是在多项式时间内可求解（或可判定）。 NP完全性问题：NP类中的某些问题的复杂性与整个类的复杂性有关，当这些问题中的任何一个存在多项式时间算法时，则所有这些NP问题都是多项式时间可解的。 等价、同构,2020/7/20