计算机学科方法论.ppt

1、第9章 计算机学科方法论,内容来源 中国计算机学会计算机学科教程研究组发布 中国计算机科学与技术学科教程2002。 教育部计算机教学指导委员会编制 高等学校计算机发展战略研究报告暨专业规范（2006）。 IEEE-CS/ACM发布 CC1991（Computing Curricular 1991）. CC2001, CC2004, CC2005.,第9章 计算机学科方法论,学习目的 深入理解计算机学科的本质。 提高学习质量。 提高科学研究和技术开发能力。 拓宽思路、强化知识的系统性、培养创新思维。 知识、方法、思想。,第9章 计算机学科方法论,9.1 计算机学科方法论简介 9.2 计算机学科的

2、定义 9.3 计算机学科方法论 9.4 计算机学科的三个过程 9.5 计算机学科中的核心概念 9.6 计算机学科中的数学方法 9.7 计算机学科中的系统科学方法 9.8 本章小结,9.1 计算机学科方法论简介,计算机学科的发展 计算机专业教学背景,9.1.1 计算机学科的发展,计算机学科的划分 计算机科学。 计算机工程/软件工程。 信息系统/信息技术。 扩充之后的计算机学科也称为计算学科（Computing Discipline）,知识体系的变化 计算机发展早期 数学/离散数学/电子学/程序设计。 20世纪60-70年代 数据结构与算法/计算机组成原理。 编译原理/操作系统/数据库原理。 20

3、世纪80年代以后 并行技术/分布计算/网络技术。 软件工程/嵌入式系统。,9.1.1 计算机学科的发展,国际背景 1962年美国普渡大学 首开计算机学位课程。 1991年IEEE-CS/ACM发布 Computing Curricula 1991（CC1991）. 2001年IEEE-CS/ACM发布 Computing Curricula 2001（CC2001）. 目前演变成CC2004, CC2005.,9.1.2 计算机专业教学背景,国内背景 专业设置 1956年哈尔滨工业大学首开计算装置与仪器专业。 经历了计算机及应用、计算机软件、计算机科学教育、计算机器件及设备等名称的变化。 19

4、98年统一为计算机科学与技术专业。 从2001年开始又增设了软件工程和网络工程专业。 招生学校与人数 2004年全国有505所高校开办有计算机本科专业，在校学生数近30万人。,9.1.2计算机专业教学背景,国内背景 教学计划 2002年中国计算机学会计算机学科教程研究组发布 中国计算机科学与技术学科教程2002。 2006年教育部计算机教学指导委员会编制 高等学校计算机专业发展战略研究报告暨专业规范。 2008年教育部计算机教学指导委员会编制 高等学校计算机科学与技术专业公共核心知识体系与课程。 高等学校计算机科学与技术专业实践教学体系与规范。,9.1.2 计算机专业教学背景,计算的本质 计算

5、机学科的根本问题,9.2 计算机学科的定义,9.2.1 计算的本质,图灵描述了计算的本质 计算就是计算者对一条两端可无限延长的纸带上的一串0和1执行指令；一步一步地改变纸带上的0或1；经过有限步骤, 最后得到一个满足预先规定的符号串的变换过程。 任一过程是能行的, 当且仅当它能够被一台图灵机实现。 图灵机反映的是一种具有能行性的用数学方法精确定义的计算模型，现代计算机正是这种模型的具体实现。,9.2.2 计算机学科的根本问题,计算机学科的定义 计算机学科是研究计算机的设计、制造和利用计算机进行信息获取、表示、存储、处理、控制等的理论、原则、方法和技术的学科，包括科学和技术两方面。 计算机科学侧

6、重于研究现象、揭示规律。 计算机技术侧重于研制计算机和研究使用计算机进行信息处理的方法和手段。 科学与技术相辅相成，相互作用。,计算机学科还具有较强的工程性 理论教学与实践教学并重。 基础理论知识扎实/动手能力强。 计算机学科是科学性/工程性/技术性的统一 侧重点不同的学科分支 计算机科学/计算机工程/软件工程/信息技术。 计算机学科和数学密切相关,9.2.2 计算机学科的根本问题,9.3 计算机学科方法论,计算机学科方法论的定义 计算机学科方法论的主要内容 计算机学科方法论研究的意义,Computer Science,9.3.1 计算机学科方法论的定义,计算机学科方法论 对计算机领域认识和实

7、践过程中一般方法及其性质、特点、内在联系和变化规律进行系统研究的理论总结。 是认知计算机学科的方法和工具，也是计算机学科认知领域的理论体系。 对于计算机领域的科学研究、技术开发和人才培养具有重要指导意义。,9.3.2 计算机学科方法论的主要内容,主要内容 学科的三个过程 抽象过程/理论总结过程/设计过程。 重复出现的12个核心概念 绑定/大问题的复杂性/概念和形式模型。 一致性和完备性/效率/演化/抽象层次。 按空间排序/按时间排序/重用/安全性/折衷和结论。 典型的学科方法 数学方法/系统科学方法。,9.3.3 计算机学科方法论研究的意义,重要意义 有助于总结经验，促进计算机学科的快速发展。

8、 有助于确立正确的思维方式，把握正确的研究方向。 有助于计算机学科的建设和人才培养 。,9.4 计算机学科的三个过程,理论总结过程 科学理论是经过实践检验的系统化了的科学知识体系，它是由科学概念、科学原理以及对这些概念、原理的理论论证所组成的体系。 计算机学科的理论与数学所用的方法类似，主要要素为定义和公理、定理、证明、结果的解释。 用这一过程来建立和理解计算机学科所依据的数学原理。其研究内容的基本特征是构造性数学特征。,9.4 计算机学科的三个过程,抽象过程 抽象是指在思维中对同类事物去除其现象的、次要的方面，抽取其共同的、主要的方面，从而做到从个别中把握一般，从现象中把握本质的认知过程和思

9、维方法。 抽象源于现实世界, 是对现实原型的理想化。,9.4 计算机学科的三个过程,设计过程 用来开发求解给定问题的系统和设备。 包括需求分析、建立规格说明、设计并实现系统、对系统进行测试分析、修改完善等内容。 三个过程贯穿计算机学科各个分支领域 图论中体现的是抽象与理论过程。 软件工程中综合体现了设计、抽象与理论三个过程。,9.5 计算机学科中的核心概念,绑定（Binding） 通过把一个抽象的概念和附加特性相联系，从而使抽象的概念具体化。 具体问题的抽象描述和抽象描述对具体问题的表示。 大问题的复杂性（Complexity of Large Problems） 随着问题规模的增长而使求解该

10、问题的复杂性呈非线性增加的效应。 是区分和选择各种现有方法和技术的重要因素。,9.5 计算机学科中的核心概念,概念和形式模型（Conceptual and Format Models） 对一个想法或问题进行形式化、特征化、可视化思维的各种方法。 计算机求解问题的基础就是对问题的概念抽象和形式化描述。 概念和形式模型是实现计算机问题求解的最典型、最有效的途径。,9.5 计算机学科中的核心概念,一致性和完备性（Consistency and Completeness） 一致性包括 一组公理的一致性/事实和理论的一致性。 一种语言或接口设计的内部一致性。 完备性包括 给出的一组公理，使其能获得预期行

11、为的充分性。 软件和硬件系统功能的充分性。 系统处于出错和非预期情况下保持正常行为的能力。 在计算机系统设计中，正确性、健壮性和可靠性就是一致性和完备性的具体体现。,9.5 计算机学科中的核心概念,效率（Efficiency） 关于空间、时间、人力、财力等资源消耗的度量。 在计算机软硬件系统的设计实现中，要充分考虑效率问题。 要想在空间、时间、人力、财力各方面都达到最优是不可能的，可以根据具体环境重点考虑某一方面达到最优或考虑达到综合最优。,9.5 计算机学科中的核心概念,演化（Evolution） 系统的结构、状态、特征、行为和功能等随着时间的推移而发生的更改。 对计算机硬件进行更新换代，要

12、考虑到已有软件的适应性，对软件进行更新换代，要考虑到现有硬件的适应性。 向下兼容是一种很好的演化模式。,9.5 计算机学科中的核心概念,抽象层次（Levels of Abstraction） 通过对不同层次的细节和指标的抽象，对一个系统或实体进行表述。 在复杂系统的设计中，对系统进行不同层次的抽象描述，从而既能控制系统的复杂程度，又能充分描述系统的特性。 在数据库系统设计中，分层E-R图的思想就是这一核心概念的具体应用。,9.5 计算机学科中的核心概念,按时间排序（Ordering in Time） 事件的执行对时间的依赖性 在具有时态逻辑的系统中，要考虑与时间有关的时序问题。 在分布式系统中

13、，要考虑进程同步的时间问题。 在依赖于时间的算法执行中，要考虑其基本的组成要素。,9.5 计算机学科中的核心概念,按空间排序（Ordering in Space） 各种定位方式 物理上的定位，如在网络和存储中的定位。 组织方式上的定位，如处理机进程、类型定义和有关操作的定位。 概念上的定位，如软件的辖域、耦合、内聚等。 是计算技术中一个局部性和相邻性的概念。,9.5 计算机学科中的核心概念,重用（Reuse） 在新的环境下，系统中各类实体、技术、概念等可被再次使用的能力。 在软件工程中，软件重用是一个重要的研究领域，有着很好的应用前景。,9.5 计算机学科中的核心概念,安全性（Security

14、） 计算机软硬件系统对合法用户的响应及对非法请求的抗拒，以保护系统不受外部影响和攻击的能力。 一旦遭受攻击受损，系统恢复到正确状态的能力。,9.5 计算机学科中的核心概念,折衷和结果（Tradeoff and Consequences） 折衷指的是为满足系统的可实施性而对系统设计中的技术方案所作出的一种合理的取舍。 折衷的结果是指选择一种方案代替另一种方案所产生的技术、经济、文化及其他方面的影响。 折衷存在于计算机学科领域的各个层次上。 在设计算法时，要考虑空间和时间的折衷。 在设计系统时，要考虑成本和可靠性的折衷。,9.6 计算机学科中的数学方法,数学的基本特征 数学方法的作用 数学中的证明

15、方法 递归方法与迭代方法 公理化方法 形式化方法,计算机数学,9.6.1 数学的基本特征,数学 研究现实世界的空间形式和数量关系的一门科学。 三个特征 高度的抽象性/严密的逻辑性/普遍的适用性。 算法(程序)设计的基础是数学。,9.6.2 数学方法的作用,对科学技术研究的作用 提供简洁精确的形式化语言 提供定量分析和计算的方法 提供严密的逻辑推理工具,9.6.3 数学中的证明方法,直接证明法 含义：假定A为真，通过使用公理或已证明的定理以及正确的推理规则证明B也为真，以此证明蕴含式AB为真。 示例：若n为奇数，则n+1为偶数。 证明：因为 n为奇数； 所以 n = 2k+1（k为整数）； 因此

16、有 n+1 = 2k+2 = 2（k+1）； 所以 n+1是偶数。,9.6.3 数学中的证明方法,反证法 含义：首先假定要证明的命题不成立，然后通过正确的推理得出与已知（或假设）条件、公理、定理等相互矛盾或自相矛盾的结果，以此证明假定要证明的命题不成立是错误的，成立才是正确的。 示例：若n2为奇数，则n为奇数。 证明：假定在n2为奇数的前提下，n为偶数； 则有 n = 2k（k为整数）； 于是有 n2 = (2k)2 = 4k2 = 2（2k2）； 则有 n2是偶数，与原假定n2为奇数矛盾； 所以假定n为偶数是错误的，n应为奇数。,9.6.3 数学中的证明方法,数学归纳法 含义：是一种用于证明

17、与自然数有关的命题正确性的证明方法，该方法能用有限的步骤解决无穷对象的论证问题。 示例：一棵非空二叉树的第i层（i1）上最多有2i-1个结点。 证明：设i=1，由于此时二叉树只有一个结点，而2i-1=20=1， 所以i=1时正确； 设i=k（k1）时结论正确，即第k层上有2k-1个结点； 那么，i=k+1时，第k+1层上最多有22k-1=2k=2（k+1）-1 个结点； 结论得以证明。,9.6.3 数学中的证明方法,构造性证明 存在性证明 存在一个x使命题P(x)成立可表示为xP(x)，对形如 xP(x)的命题的证明。 构造性证明 通过找出一个使得命题P(a)为真的元素a，从而完成该函数值的存

18、在性证明。,9.6.3 数学中的证明方法,构造性证明 存在性证明示例：每个喜欢步行的人都不喜欢坐汽车；每个人或者喜欢坐汽车或者喜欢骑自行车；有的人不喜欢骑自行车，因而有的人不喜欢步行。 假设谓词如下： H(x)：x是人； P(x)：x喜欢坐汽车； Q(x)：x喜欢骑自行车； R(x)：x喜欢步行。 则题目中的句子可符号化为： 前提： x ( H(x)R(x) P(x)， x( H(x) P(x)Q(x)， (x)(H(x)Q(x) 结论：(x)(H(x)R(x),9.6.4 递归方法与迭代方法,递归方法 含义：一种在有限步骤内，根据特定的法则或公式对一个或多个前面的元素进行运算，以确定一系列元

19、素的方法。 示例： 数列的递归定义。 对于数列1，2，3，5，8，13，21，34，55，89， 可以给出如下递归定义公式： a1=1； a2=2； an=an-1+an-2 （n3）。,迭代方法 含义：迭代就是反复替换的意思。在程序设计中，为了处理重复性计算的问题，最常用的方法就是迭代方法。 示例：用如下公式求的近似值，直到最后一项的绝对值小于10-4为止。 计算过程：循环做累加操作，当然每次累加项的值是不一样的，当累加项的绝对值小于10-4时循环累加结束。,9.6.4 递归方法与迭代方法,9.6.5 公理化方法,公理化方法 一种构造理论体系的演绎方法，它是从尽可能少的基本概念、公理出发，运

20、用演绎推理规则，推导出一系列的命题，从而建立整个理论体系的思想方法。 用公理化方法构建的理论体系称为公理系统，公理系统需要满足如下条件： 无矛盾性。 独立性。 完备性。,9.6.6 形式化方法,具体公理系统和抽象公理系统 具体公理系统：有现实背景的公理系统。 抽象公理系统：没有现实背景的公理系统。 形式化方法 形式化实质上就是一个算法，即一个可机械地实现的过程，用于将概念、断言、事实、规则、推演乃至整个被描述系统表述得严密、精确而又无需任何专门的知识即可被毫无歧义地感知。,9.6.6 形式化方法,形式系统 理论系统或实际系统形式化的产物，在这种系统中所进行的推演均可被机械地测试，以确定它们是否

21、是正确的。 形式系统的组成部分 初始符号/形式规则/公理/变形规则 对计算机学科的影响 图灵机就是对计算的形式化描述。 一阶谓词演算形式系统为知识的形式表示及定理的机器证明奠定了重要基础。,9.7 计算机学科中的系统科学方法,系统科学的基本思想 系统科学的基本概念 系统科学方法遵循的一般原则,9.7.1 系统科学的基本思想,系统科学的定义 人类对于复杂系统规律的认识的总结；它在自然科学与社会科学各领域的大量实际经验的基础之上，总结出人类认识、描述、设计、管理、控制复杂系统的一般性的理念、方法与具体步骤，用以加深人类对于宇宙的认识，提高人们做事的效率和有效性。 系统科学与计算机学科 随着计算机科

22、学技术的迅猛发展，计算机软硬件系统变得越来越复杂，系统科学方法在计算机学科中的作用也日显重要。,9.7.1 系统科学的基本思想,系统科学强调的重点 强调整体性。 注重动态和过程。 注重质变。 注重层次之间的差别。 关注由活的主体组成的系统。 对于不确定性的关注和研究。 对于人为事物和做事方法的关注和研究。,9.7.2 系统科学的基本概念,系统和子系统 系统是指由相互联系、相互作用的若干元素构成的，具有特定功能的统一整体。 一个大的系统往往是复杂的，它通常可以划分为若干个较小的系统，这些较小的系统称为子系统。,9.7.2 系统科学的基本概念,结构和结构分析 结构是指系统内各组成部分（元素和子系统）之间相互联系、相互作用的框架。 结构分析的重要内容就是划分子系统，并研究各子系统的结构以及各子系统之间的相互关系。,9.7.2 系统科学的基本概念,层次和层次分析 层次是指某个子系统在整个系统结构中所处的相对位置。 在一个系统中，系统、子系统、更小的子系统是处在不同层次上的，并且相互之间存在层次关系，高层次包含和支配低层次，低层次隶属和支撑高层次。 层次分析的主要内容有：系统是否划分层次，划分了哪些层次，各层次的内容，层次