计算科学导论.ppt

2019/4/30,1,计算科学导论(一) 计算机与信息学院 蒋川群 13002187038 cqjiangsspu.cn 2012年10月,2019/4/30,2,目录,一、知识、能力与素质 二、计算科学的定义 三、图灵与计算本质 四、计算思维 五、抽象典型实例 六、可计算问题与不可计算问题 七、核心概念,2019/4/30,3,教育,哲学家费希特： 教育必须培养人的自我决定能力，而不是培养人们去适应传统世界； 教育重要的不是着眼于实用性、传播知识和技能，而是要唤醒学生的力量，培养其自我性、主动性、抽象的归纳力和理解力。,2019/4/30,4,教育,教育定义（联合国教科文组织） “有组织有目的的知识传授活动” “能够导致学习的交流活动”,2019/4/30,5,知识、能力与素质,“知识”是基础、是载体、是表现形式 知识具有“基础”属性，即一个具有较强能力和良好素质的人必须掌握丰富的知识；而一个掌握丰富知识的人并不一定具有较强的能力和良好的素质。,2019/4/30,6,知识、能力与素质,“知识”是基础、是载体、是表现形式。 知识具有“载体”属性，能力的培养和素质的提高必须部分地通过具体知识的传授来实施，否则就会成为空中楼阁。 要发挥知识的载体作用，需挖掘知识深层的内容，重视科学的世界观和方法学的启蒙教育。 在许多场合下，能力与素质，尤其是专业能力和专业素质，是通过知识表现出来的。,2019/4/30,7,知识、能力与素质,“能力”是技能化的知识，是知识的综合体现。 “能力”把知识运用的综合性、灵活性与探索性作为自己的重要内容。要保证知识运用的综合性、灵活性与探索性，就需要有丰富的知识作为支撑，并将其用于实践。,2019/4/30,8,知识、能力与素质,“素质”是知识和能力的升华。 素质教育是在知识和能力的基础上，以全面提高受教育者的基本素质为目的，以尊重学生的主体作用和主动精神，注重开发人的潜能，形成健全的人格为根本特征的教育。,2019/4/30,9,知识、能力与素质,“素质”是知识和能力的升华。 素质是在潜移默化中提高的，它具有不易见性、不易获得性、终身受用性。素质除表现为“提高的潜移默化特性”外，它还需要通过人的能力、知识才能表现出来。素质的这种“表现的非直接性”和“隐藏性”，导致现有的考核方法难以对其给出准确的评价。这使得人们容易在工作中忽视它，这是值得注意的。,2019/4/30,10,知识、能力与素质,“素质”是知识和能力的升华。 素质是在潜移默化中提高的，它具有不易见性、不易获得性、终身受用性。素质除表现为“提高的潜移默化特性”外，它还需要通过人的能力、知识才能表现出来。素质的这种“表现的非直接性”和“隐藏性”，导致现有的考核方法难以对其给出准确的评价。这使得人们容易在工作中忽视它，这是值得注意的。,2019/4/30,11,知识、能力与素质,“素质”是知识和能力的升华。 素质的“不易获得性”主要表现在需要较长期的积累，而且素质提升所涉及的学习内容很多属于一些难度较大的课程，特别是很多内容与一些课程深层的内容相关，这些又使得它很容易被舍弃。但其“终身受用性”却使我们不得不重视它。,2019/4/30,12,知识、能力与素质,知识、能力、素质是进行高科技创新的基础。只有将三者贯通于教育的全过程，才能培养出高水平的人才。 爱因斯坦说过，想象力比知识更重要。 在大学里，除了通常意义下的素质培养外，重点是进行专业能力和专业素质的培养。,2019/4/30,13,追求教育的实效,听过的会忘记 看过的会记得 做过的才理解 会的程度：会用/会套用,2019/4/30,14,追求教育的实效,教了什么 学了什么 学到什么 会做什么,2019/4/30,15,计算科学的定义,计算科学是对描述和变换信息的算法过程进行的系统研究，包括理论、分析、设计、效率、实现和应用等。 计算科学的研究包括从算法与可计算性的研究到根据可计算硬件和软件的实际问题的研究。,2019/4/30,16,计算科学的定义,计算科学不但包括从总体上对算法和信息处理过程进行研究的内容，也包括对规格要求的有效而可靠的软硬件设计它包括理论研究、实验方法和工程设计。,2019/4/30,17,图灵与计算本质,图灵对计算本质的揭示 所谓计算就是计算者（人或机器）对一条两端可无限延长的纸带上的一串0和1执行指令，一步一步地改变纸带上的0或1，经过有限步骤，最后得到一个满足预先规定的符号串的变换过程。,2019/4/30,18,图灵与计算本质,图灵对计算本质的揭示 图灵的研究成果：可计算性=图灵可计算性 算法：也称为能行方法或能行过程，是对解题（计算）过程的精确描述，它由一组定义明确且能机械执行的规则（语句、指令等）组成。 结论：任一过程是能行的（能够具体表现在一个算法中），当且仅当它能够被一台图灵机实现。,2019/4/30,19,计算思维,计算思维（Computational ThinKing,CTK） 核心是基于计算机考虑问题求解,2019/4/30,20,计算思维,广义，计算思维可理解为：如何有效地利用计算机技术进行问题的求解。 即：在拥有了计算机这个工具后，如何有效地将其用于生产、生活和科学实践活动，提高工作效率，高质量地解决遇到的问题。 计算思维能力是现代人都应该具备的能力。,2019/4/30,21,计算思维,狭义，计算思维可以理解为如何按照计算机求解问题的基本方法去考虑问题的求解，以便构建出相应的算法和基本程序等。 如何使计算机具有更强的工作能力，主要包括形式化、模型化描述和抽象思维与逻辑思维能力。,2019/4/30,22,计算思维,计算机专业人员研究一个问题的求解时，首先要解决问题的表示。 需要通过抽象进行形式化，建立适当的模型，然后对此抽象描述进行表示和处理。同时，让计算机系统“独立”实现对问题的求解之前，还要事先在自身的头脑中“构建”并“运行”各个适当抽象级别上的处理系统（过程）。,2019/4/30,23,计算思维,上述活动的有效进行主要依靠计算思维能力的支撑。 程序（计算系统最基本的“成分”） 具有非物理特性，这种非物理特性要求研究人员具有抽象描述、抽象思维和逻辑思维能力。 学科基本教学原理是抽象第一。,2019/4/30,24,计算思维,针对计算机专业人才的培养，我们按照狭义的理解探讨计算思维能力。 计算思维能力主要包括： 问题的符号表示、问题求解过程的符号表示、逻辑思维、抽象思维、形式化证明、建立模型、实现类计算、实现模型计算、利用计算机技术等。,2019/4/30,25,案例：斯坦福大学实践型课程分类,表1 斯坦福大学2009-2010学年实践型课程类别,应用技术类课程 紧紧把握了信息技术的最新动态 讲授的知识是业界最新最火的技术 是随需而设的（这类课程在10年的跨度里有76%会消失，只有将近24%会保留下来。 ） 意味着教学管理部门要敏锐地感知市场变化，定期地调整课程体系,应用方法学类课程 重点是传授学生应对常见问题的正确态度和方法 充分体现了“授人以渔”的教育精神 让学生在“态度、观念、视角”层面受益，对促进学生成长方面起到的作用不容小觑 课程的生命周期较长且内容相对稳定,2019/4/30,26,计算思维,误区 掌握计算机技术就是“会用”计算机、会上网、会将计算机联入网络、会写主页、会装计算机等 学一些基础理论知识是枯燥的、无意义的 干扰 起源：系统开发工具 友好性、傻瓜性 教师中的“实用主义”教育观点 学生中的浮躁情绪,2019/4/30,27,计算思维,若将精力大量地投入到流行系统的具体使用上，人生将永远处于“培训班”。,2019/4/30,28,抽象典型实例(哥尼斯堡七桥问题),问题：寻找走遍这7座桥，且只许走过每座桥一次，最后又回到原出发点的路径。 原则：抽象出问题本质的东西，忽视问题非本质的东西。 方法：区域抽象为点、桥抽象为边。 问题转化：经过图中每边一次且仅一次的回路问题。,2019/4/30,29,欧拉3条判定规则： (1)如果奇数点（即连接的边数）大于2个，则不存在“经过图中每边一次且仅一次的路线”。 (2)如果奇数点（即连接的边数）等于2个，则存在“经过图中每边一次且仅一次的路线”（可从一个奇数点出发）。 (3)如果奇数点（即连接的边数）为0个，则存在“经过图中每边一次且仅一次的回路”（可从任意一个点出发）。,抽象典型实例(哥尼斯堡七桥问题),2019/4/30,30,哈密尔顿回路问题 在任一给定的图中，能不能找到这样的路径，即从一点出发不重复地走过所有的结点一次（不必通过图中每一条边），最后又回到原出发点。 哈密尔顿回路问题：访问每个结点一次。 欧拉回路：访问每条边一次。 离散数学,抽象典型实例(哥尼斯堡七桥问题),2019/4/30,31,可计算问题与不可计算问题,梵天塔(汉诺塔)问题 移动规则 (1)每次只能移动一个盘子； (2)盘子只能在三根柱子上来回移动，不能放在他处； (3)在移动过程中，三根柱子上的盘子必须始终保持大盘在下，小盘在上。 天神说：当这64个盘子全部移到第三根柱子上后，世界的末日就要到了。,2019/4/30,32,可计算问题与不可计算问题,所谓递归，就是将一个较大的问题规约为一个或多个性质（结构）相同的子问题的求解方法。 初始终极条件。,2019/4/30,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) hanoi(n-1,middle,left,right) ,2019/4/30,34,可计算问题与不可计算问题,H(n)=2n-1 264-1=18446744073709551615 每秒移动一次，一年有31536000秒，需要花费大约5849亿年。 理论上的能行性隐含着计算模型的正确性，而实际实现中的能行性还包含时间与空间的有效性。算法复杂度,2019/4/30,35,可计算问题与不可计算问题,Ackermann函数 A(0,n)=n+1 n=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,2019/4/30,36,可计算问题与不可计算问题,算法复杂性中的难解性问题、P类问题和NP问题 算法复杂度：空间复杂度和时间复杂度 一个问题求解算法的时间复杂度大于多项式（如指数函数）时，算法的执行时间将随n的增加而急剧增长，以致即使是中等规模的问题也不能求解出来，于是在计算复杂性中，将这一类问题称为难解性问题。,2019/4/30,37,可计算问题与不可计算问题,算法复杂性中的难解性问题、P类问题和NP问题 P类问题：所有可以在多项式时间内求解的问题(确定性算法)。 NP类问题：所有在多项式时间内可以验证的问题(非确定性算法)。 确定性算法是非确定性算法的一种特例，因此可以断定NP包含P。,2019/4/30,38,可计算问题与不可计算问题,证比求易算法 顺序算法和并行算法 顺序算法时间复杂度 并行算法空间复杂度 当将一个问题分解到多个处理器上解决时，由于算法中不可避免地存在必须串行执行的操作，从而大大地限制了并行计算机系统的加速能力。,2019/4/30,39,可计算问题与不可计算问题,阿达尔定律 Sp1/(f+(1-f)/p) f为求解某个问题的计算存在的必须串行执行的操作占整个计算的百分比， p为处理器的数目， Sp为并行计算机系统最大的加速能力(倍) 设：f=1%，p，则Sp=100,2019/4/30,40,可计算问题与不可计算问题,阿达尔定律启示 对难解性问题而言，单纯地提高计算机系统的速度是远远不够的，而降低算法复杂度的数量级才是最关键的问题。,2019/4/30,41,可计算问题与不可计算问题,P=?NP 若P=NP，则所有在多项式时间内可验证的问题都将是在多项式时间内可求解（或可判定）。 NP完全性问题：NP类中的某些问题的复杂性与整个类的复杂性有关，当这些问题中的任何一个存在多项式时间算法时，则所有这些NP问题都是多项式时间可解的。 等价、同构,2019/4/30,42,核心概念,学科的核心概念是学科中最关键、最重要的概念，它涉及学科研究的内涵、对象、本质、核心要素等内容 基本特征 (1)在学科中多处出现 (2)在各分支领域及抽象、理论和设计的各个层面上都有很多示例 (3)在技术上有高度的独立性 (4)一般都在数学、科学和工程中出现,2019/4/30,43,核心概念算法,算法是最具有方法论性质的核心概念 算法是计算科学的灵魂 算法设计的优劣决定着软件系统的性能 对算法进行研究能深刻理解问题的本质以及可能的求解技术,2019/4/30,44,核心概念算法,算法的非形式化定义 一个算法，就是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的运算序列,2019/4/30,45,核心概念算法,算法的重要特性 (1)有穷性：在执行有穷步之后必须结束 (2)确定性：每一个步骤必须要确切地定义 (3)输入：有零个或多个的输入 (4)输出：有一个或多个的输出 (5)能行性：有待执行的运算和操作必须是相当基本的,2019/4/30,46,核心概念算法,算法的形式化定义 算法是一个四元组，即(Q,I,F) (1)Q是一个包含子集I和的集合，它表示计算的状态； (2)I表示计算的输入集合； (3)表示计算的输出集合； (4)F表示计算的规则，它是一个由Q到它自身的函数，且具有自反性，即对任何一个元素qQ，有F(q)=Q。,2019/4/30,47,核心概念算法,算法的形式化定义 一个算法是对于所有的输入元素x，都是在有穷步骤内终止的一个计算方法 对于任何一个元素xI，x均满足以下性质：x0=x，xk+1=F(xk)，(k0) 该性质表示任何一个输入元素x均有一个计算序列，即x0，x1，x2，xk。对任何输入元素x，该序列表示算法在第k步结束,2019/4/30,48,核心概念算法,例：求123100 设变量X表示加数，Y表示被加数 将1赋值给X 将2赋值给Y 将X与Y相加，结果存放在X中 将Y加1，结果存放在Y中 若Y小于或等于100，转到步骤继续执行；否则，算法结束，结果为X,2019/4/30,49,核心概念算法,例：求解调和级数Hn=1/1+1/2+1/n 设变量X表示累加和，变量I表示循环的次数 将0赋值给X 将1赋值给I 将X与1/I相加，然后将结果存入X 将I加1 若I大于等于n，算法结束，结果为X;否则转到步骤继续执行,2019/4/30,50,核心概念算法,例：求解斐波那契数 F0=0，F1=1，Fn+2=Fn+1+Fn，n0 设变量X表示前一个数的值，即定义中的Fn，变量Y表示当前数的值，即定义中的Fn+1，变量Z表示后一个数的值，即定义中的Fn+2。 如果n=0，那么将0赋值给Y，并输出Y，转步骤(11)，否则继续执行 将0赋值给X，将1赋值给Y 输出X，Y 将1赋值给I,2019/4/30,51,核心概念算法,例：求解斐波那契数 F0=0，F1=1，Fn+2=Fn+1+Fn，n0 如果I大于n-1，则转到步骤(11)，否则继续执行 将X和Y的和赋值给Z 将Y赋值给X 将Z赋值给Y 将Y输出 将I加1，转步骤继续执行 (11)算法结束,2019/4/30,52,核心概念算法,算法的表示方法 自然语言 图形工具：流程图、盒图、问题求解图 伪代码 计算机程序设计语言,2019/4/30,53,核心概念算法,算法分析 (1)算法的时间复杂度 (2)算法的空间复杂度 (3)算法是否便于阅读、修改和测试 在算法最好、平均和最坏的情况下区别执行效率的不同。,2019/4/30,54,核心概念算法,算法分析大O记号： 设f(n)是一个关于正整数n的函数，若存在一个正整数n0和一个常数C，当nn0时，T(n)Cf(n)均成立，则称f(n)为T(n)的同数量级的函数。于是，算法时间复杂度T(n)可表示为： T(n)=O(f(n),2019/4/30,55,核心概念算法,算法分析大O记号： O(1)称为常数级 O(logn)称为对数级 O(n)称为线性级 O(nc)称为多项式级 O(cn)称为指数级 O(n!)称为阶乘级,2019/4/30,56,核心概念数据结构,数学模型有定量模型和定性模型两类之分 定量模型指的是可以用数值方程表示的一类模型 定性模型指的是非数值性的数据结构（如表、树和图等）及其运算 数据结构指的是一类定性的数学模型，它是计算机算法设计的基础，在计算科学中占有十分重要的地位,2019/4/30,57,核心概念数据结构,数据结构的组成 数据结构是一类定性的数学模型，由数据的逻辑结构、数据的存储结构（或称物理结构）及其运算3部分组成 数据逻辑结构的形式化定义 DS D表示数据的集合 R表示数据D上关系的集合,2019/4/30,58,核心概念数据结构,数据的存储结构 指在反映数据逻辑关系的原则下，数据在存储器中的存储方式 顺序存储结构：借助元素在存储器中的相对位置来表示数据元素的逻辑关系 链式存储结构：借助指针来表示数据元素之间的逻辑关系，通常在数据元素上增加一个或多个指针类型的属性来实现,2019/4/30,59,核心概念程序,计算机程序就是按照工作步骤事先编排好的、具有特殊功能的指令序列 算法数据结构程序 算法是程序的核心，它在程序编制、软件开发，乃至在整个计算机科学中都占据重要地位。 数据结构是加工的对象，一个程序要进行计算或处理总是以某些数据为对象的，而要设计一个好的程序就需将这些松散的数据按某种要求组成一种数据结构。,2019/4/30,60,核心概念软件,软件指计算机系统中的程序及其文档，指在研究、开发、维护以及使用上述含义下的软件所涉及的理论、方法、技术所构成的分支学科。 系统软件：计算机系统中最靠近硬件层次的软件。如操作系统、编译程序等。 支撑软件：支撑其他软件的开发与维护的软件。如数据库管理系统、网络软件、各种接口软件和开发工具等。 应用软件：特定应用领域的专用软件。如商业会计软件、教学软件等。,2019/4/30,61,核心概念硬件,构成计算机系统的所有物理器件、部件、设备，以及相应的工作原理与设计、制造、检测等技术的总称。 物理元器件包括集成电路、印刷电路板以及其他磁性元件、电子元件等 部件和设备包括控制器、运算器、存储器、输入输出设备、电源等 硬件工程技术包括印制电路板制造、高密度组装、抗环境干扰、抗恶劣环境破坏等技术，还包括在设计和制造过程中为提高计算机性能所采取的措施等。,2019/4/30,62,核心概念硬件,计算机就是由计算机硬件和计算机软件组成的 硬件是计算机的“躯体” 软件是计算机的“灵魂”,2019/4/30,63,CC1991报告提取的核心概念,核心概念是CC1991报告首次提出的，是具有普遍性、持久性的重要思想、原则和方法 报告认为，熟练掌握和应用这些核心概念是一个成熟的计算机科学家和工程师的标志之一,2019/4/30,64,CC1991报告提取的核心概念,1.绑定（Binding） 通过将一个对象（或事物）与其某种属性相联系，从而使抽象的概念具体化的过程。 2.大问题的复杂性（Complexity of Large Problems） 指随着问题规模的增长而使问题的复杂性呈非线性增加的效应。,2019/4/30,65,CC1991报告提取的核心概念,3.概念与形式模型（Conceptual and Format Models） 概念和形式模型是对一个想法或问题进行形式化、特征化、可视化思维的方法 概念模型：抽象数据类型、语义数据类型以及指定系统的图形语言等 形式模型：逻辑、开关理论和计算理论中的模型等,2019/4/30,66,CC1991报告提取的核心概念,4.一致性和完备性（Consistency and Completeness） 一致性包括用于形式说明的一组公理的一致性，以及这种语言或接口设计的内部一致性。 完备性包括给出的一组公理，使其能获得预期行为的充分性、软件和硬件系统功能的充分性，以及系统处于出错和非预期情况下保持正常行为的能力等。,2019/4/30,67,CC1991报告提取的核心概念,5.效率（Efficiency） 关于空间、时间、人力、财力等资源消耗的度量。 6.演化（Evolution） 系统的结构、状态、特征、行为和功能等随时间的推移而发生的更改。,2019/4/30,68,CC1991报告提取的核心概念,7.抽象层次（levels of Abstraction） 通过对不同层次的细节和指标的抽象对一个系统或实体进行表述。 在复杂系统的设计中，隐藏细节，对系统各层次进行描述（抽象），从而控制系统的复杂程度。,2019/4/30,69,CC1991报告提取的核心概念,8.按空间排序（Ordering in Space） 各种定位方式，如物理上的定位（如网络和存储中的定位），组织方式上的定位（如处理机进程、类型定义和有关操作的定位）以及概念上的定位（如软件的辖域、耦合、内聚等）。,2019/4/30,70,CC1991报告提取的核心概念,9.按时间排序（ Ordering in Time） 事件的执行对时间的依赖性。 10.重用（Reuse） 在新的环境下，系统中各类实体、技术、概念等被再次使用的能力。,2019/4/30,71,CC1991报告提取的核心概念,11.安全性（Security） 计算机软硬件系统对合法用户的响应及对非法请求的抗拒，以保护自己不受外部影响和攻击的能力。,2019/4/30,72,CC1991报告提取的核心概念,12.折衷和结论（Tradeoff and Consequences） 折衷指的是为满足系统的可实施性而对系统设计中的技术、方案所作出的一种合理的取舍。结论是折衷的结论，即选择一种方案代替另一种方案所产生的技术、经济、文化及其他方面的影响。,2019/4/30,73,祝大家： 身 健 康 ！,