计算机科学导论-基于计算思维的思想与方法（第4版） 课件【ch02】计算机学科体系

计算机科学导论基于计算思维的思想与方法计算机学科体系第二章新工科建设之路·计算机类系列教材01计算机学科体系的构建计算机学科体系的构建011.什么是科学从词源上说，“科学”一词的英文“Science"源于拉丁文Scientia，

意为知识和学问。中国《辞海》(1999年版)对科学的解释是：科学是运用范畴、定理和定律等思维形式反映现实世界中各种现象的本质和运动规律的知识体系。《韦氏字典》中对科学的定义：科学是从确定研究对象的性质和规律这一且标出发，通过观察、调查和实验而得到的系统知识。一、科学与学科的概念计算机学科体系的构建012.什么是学科学科本身具有二重含义：首先是指相对独立的知识体系或学术分类，含义较广；其次是指为培养人才而设立的教学科目。我们通常意义上所讲的学科既具有第一重含义的特征，又包含第二重含义的特征，特别指高等学校或研究部门为培养高级专门人才而设立的教学科目。一、科学与学科的概念计算机学科体系的构建013.学科与科学的关系“学科”与“科学”两者之间有着自然和必然的关系：科学是以问题为基础的，凡是有问题的地方就会有科学和科学研究；学科是在科学的发展中不断分化和整合而形成的，是科学研究发展成熟的产物。但并不是所有的科学研究领域最后都能发展成为学科。一、科学与学科的概念计算机学科体系的构建01二、计算作为一门学科1.计算学科的起源1989年1月，该工作组提交了ComputingasaDiscipline(计算作为一门学科)的报告，其主要内容刊登在1989年1月的CommumicationsoftheACM(ACM通讯)杂志上。这个报告回答了计算学科中长期以来一直争论的一些问题，完成了计算学科的“存在性”证明，确定了计算学科的“知识框架”体系以及对知识框架进行研究的思想方法。计算机学科体系的构建01二、计算作为一门学科2.计算学科的定义计算学科(ComputingDiscipline)是对信息描述和变换的算法过程(包括对其理论分析、设计、效率分析、实现和应用等)进行的系统研究。计算学科的研究包括了从算法与可计算性的研究以及可计算硬件和软件的实际实现问题的研究。这样，计算学科不但包括从总体上对算法和信息处理过程进行研究的内容，而且包括满足给定规格要求的有效而可靠的软件、硬件设计，包括所有科目的理论、研究、实验方法和工程设计。计算机学科体系的构建01三、CC2005学科体系1.计算学科的分支学科CC2005中包含多个报告，并将计算学科划分为5个分支学科，其构成如图2-1所示。计算机学科体系的构建01三、CC2005学科体系2.计算机科学的课程体系ACM和IEEE-CS提出的计算机科学知识体系概念，为各分支学科体系的建立提供了范式，将各分支学科(也称为专业方向)划分为知识领域(Area)、知识单元(Unit)和知识点(Topic)三个层次：知识领域代表分支学科中的课程名称；知识单元代表知识领域中的基础内容，分为核心单元和选修单元，核心单元代表该学科都必须学习的基础内容，选修单元代表该学科选择学习的基础内容；知识点代表知识单元中单独的主题模块。计算机学科体系的构建01四、CCC2002学科体系1.中国计算机教程我国计算机专业本科教育始于1956年哈尔滨工业大学开设的“计算装置与仪器”专业，随后许多大学相继开设类似专业，经历了计算机及应用、计算机软件、计算机科学教育、计算机器件及设备等名称的变化。1998年，教育部进行本科专业目录调整，计算机类专业名称统一为计算机科学与技术专业。从2001年开始，在原有专业的基础上，增设了软件工程专业和网络工程专业。计算机学科体系的构建01四、CCC2002学科体系2.中国计算机专业规范(1)在计算机科学与技术专业名称下，鼓励不同的学校根据社会需求和自身实际情况，为学生提供不同人才培养类型的教学计划和培养方案。(2)将人才培养的规格归纳为四个专业方向、三种类型：计算机科学(研究型)、计算机工程(工程型)、软件工程(工程型)、信息技术(应用型)。(3)给出了4个专业方向的专业规范，包括培养目标和规格、教育内容和知识体系、办学条件、主要参考指标、核心课程描述等内容。计算机学科体系的构建01四、CCC2002学科体系3.计算机科学与技术学科体系国务院学位委员会将计算机科学与技术学科划分为一个一级学科和3个二级学科，如图2-2所示。02计算机学科方法论计算机学科方法论021.计算机学科方法论的定义计算机学科方法论在哲学方法论和一般科学论方法论的指导下，对计算机领域认识和实践过程中的一般方法、性质、特点、内在联系和变化规律进行系统研究和理论总结。一、计算机学科方法论概念计算机学科方法论022.计算机学科方法论的体现(1)在计算机硬件方面：由以运算器为中的“冯·诺依曼结构”改进为以存储器为中心的现代体系结构，并且采用流水线处理器系统、并行处理器系统、多处理器系统、精简指令系统等。(2)在计算机软件方面：由程序控制发展为用操作系统对硬件系统全面控制和管理。(3)在程序设计方面：程序设计语言由低级语言发展成为高级语言，由面向过程语言发展成为面向对象语言；程序设计方法由流程图→模块化→结构化，并由程序开发发展成为软件工程。(4)在应用技术方面：科学计算→多媒体→数据处理→人工智能→数据库→计算机网络。一、计算机学科方法论概念计算机学科方法论023.计算机学科方法论的研究目前计算机学科方法论的研究成果主要体现在以下6个方面。(1)计算机学科的知识体系(2)计算机学科的三个形态(3)计算机学科的核心概念(4)计算机科学的典型方法(5)计算机学科的数学方法(6)计算思维方法一、计算机学科方法论概念计算机学科方法论02二、计算机学科的三个形态1.抽象形态抽象源于建模，是自然科学的根本，其研究内容：一是建立对客观事物进行抽象描述的方法；二是采用统一的描述方法(符号化、图形化语言)建立具体问题的概念模型，从而获得对客观世界的感性认识。抽象的基本步骤：数据采集和假设的形式说明→模型的构造与预测→实验分析→结果分析，为可能的算法、数据结构和系统结构等构造模型时使用的过程。抽象的结果是概念、符号、模型。计算机学科方法论02二、计算机学科的三个形态2.理论形态理论源于数学，是数学的根本，其研究内容：一是建立完整的理论体系；二是在现有理论的指导下建立具体问题的数学模型，从而实现对客观世界的理性认识，成为分析问题的思想指导。理论的基本步骤：定义→公理→定理→证明，使用形式化方法对事物进行严密的定义和论证。计算机学科方法论02二、计算机学科的三个形态3.设计形态设计源于工程，是工程的根本，所研究的内容包括：一是在对客观世界的感性认识和理性认识的基础上完成一个具体的任务；二是对工程设计中所遇到的问题进行总结、提出问题、由理论界去解决，并将工程设计中所积累的经验和教训进行总结，形成方法，以便指导以后的工程设计。设计的基本步骤：需求分析→建立规格说明→设计并实现该系统→对系统进行测试与分析。计算机学科方法论02二、计算机学科的三个形态4.三个形态之间的关系三个形态之间的相互关系如图2-3所示。计算机学科方法论02三、计算机学科的核心概念计算机学科方法论02三、计算机学科的核心概念计算机学科方法论02四、计算机学科的典型方法(1)问题描述语义抽象(2)计算系统分层抽象(3)程序设计语言抽象(4)程序设计方法抽象1.抽象方法计算机学科方法论02四、计算机学科的典型方法构造是指由基本元素进行有机组合形成新的结构体，构造性是指结构体所呈现的基本要素和特性。构造性是计算机学科最本质的方法，在计算机学科中构造性方法可以概括为以下3个方面。(1)计算机系统的构造性(2)计算机语言的构造性(3)计算机数学的构造性2.构造性方法计算机学科方法论02四、计算机学科的典型方法公理化方法是一种构造理论体系的演绎方法，即从尽可能少的基本概念和公理出发，运用演绎推理规则推导出一系列的命题，从而建立整个理论体系。构造性是计算机软/硬件系统的最基本特征，递归和迭代是最具代表性的构造性数学方法，已经被广泛应用于计算机学科的各领域。用公理化构建的理论体系称为公理系统，它是一套完整的理论法则，3.公理化方法计算机学科方法论02四、计算机学科的典型方法形式化方法是一种基于命题逻辑的数学方法，即采用数理逻辑证明的手段对计算机系统进行建模、规约、分析、推理和验证，把各种具有不同内容的思维形式(命题和推理)加以比较，找出其中各个部分相互联结的方式，如命题中包含概念彼此间的联结，推理中则是各个命题之间的联结，抽取出它们共同的形式结构，利用表达形式结构的符号语言，严密、精确而又毫无歧义地描述系统的方法。4.形式化方法计算机学科方法论02四、计算机学科的典型方法计算机学科中的系统科学方法主要体现在以下5个方面。(1)系统分析方法(2)信息甄别方法(3)功能模拟方法(4)黑盒检验方法(5)整体优化方法5.系统科学方法03计算机学科中的数学方法计算机学科中的数学方法031.数学方法的基本特征数学是研究现实世界的空间形式及其数量关系的一门学科，数学方法具有以下3个基本特征。(1)高度的抽象性(2)严密的逻辑性(3)普遍的实用性一、数学方法及其作用体现计算机学科中的数学方法032.数学方法的基本策略数学方法是一种科学方法，使用数学方法解决实际问题所涉及的基本策略可概括以下两类。(1)归纳、演绎、类比方法：归纳是从个别到一般，演绎则是从一般到个别，两者是认识过程中解决问题的两个相反相成的方法，而类比是归纳和演绎的综合运用。(2)分析、综合、抽象方法：分析是把事物分解为各个部分并加以考察的方法；综合是把事物看成一个有机整体来加以考察的方法。一、数学方法及其作用体现计算机学科中的数学方法033.数学方法的作用表现数学方法在科学技术方法论中的作用主要表现在以下3个方面。(1)为科学技术研究提供简洁的形式化语言(2)为科学技术研究提供定量分析和计算方法(3)为科学技术研究提供严密的逻辑推理工具一、数学方法及其作用体现计算机学科中的数学方法031.直接证明法直接证明法是指假设命题A为真，通过使用公理或已证明的定理以及正确的推理规则证明B也为真，以此证明蕴涵式A→B为真。二、构造性数学与证明方法计算机学科中的数学方法032.间接证明法间接证明是相对于直接证明而言的，因为蕴涵式A→B为真与其逆否命题B→一4等价，因此可通过证明B→4来证明蕴涵式A→B为真。间接证明的常用方法是反证法，其证明过程是首先提出命题，然后设定反命题，并依据推理规则进行推演，以证明反命题的虚假。二、构造性数学与证明方法计算机学科中的数学方法033.数学归纳法数学归纳法是一种用于证明某个给定命题在整个自然数范围内成立的方法。该方法是用“有限”的步骤解决“无穷”的对象的论证问题。数学归纳法的基本步骤为：当n=1时，显然成立；当n=k时也成立；则当n=k+1时仍成立，则原命题对任意正整数均成立。二、构造性数学与证明方法计算机学科中的数学方法034.存在性证明存在性证明是指存在一个x使命题P(x)成立，并且可表示为

，我们把对形如

命题的证明称为存在性证明。换句话说，存在性证明通常表现为间接证明，即假设所述对象不存在，就会导致矛盾。二、构造性数学与证明方法计算机学科中的数学方法035.构造性证明构造性证明是计算机科学中广泛使用的一种证明方法，它是通过找出一个使得命题P(a)为真的元素a，从而完成该函数值的存在性证明。具体说，就是构造一个带有命题所要求的特定性质的实例，以显示具有该性质的物体或概念的存在性。二、构造性数学与证明方法计算机学科中的数学方法036.递归方法与迭代方法(1)递归方法：递归方法是在“有限”步骤内根据特定法则或公式对一个或多个前面的元素进行运算，以此确定一系列元素。(2)迭代方法：是通过反复替换处理的重复性计算问题。二、构造性数学与证明方法计算机学科中的数学方法03三、计算机学科的根本问题问题的可计算性是指什么是可计算的和不可计算的。由于数字计算机是一种离散结构，只能处理离散的或离散化了的数量关系，因此可计算性决定了计算机的体系结构和计算机所处理的对象都只能是离散型的，而非离散(连续)的对象必须转化为离散型。1.问题的可计算性计算机学科中的数学方法03三、计算机学科的根本问题问题求解过程的能行性逻辑关系如图2-4所示。2.计算过程的能行性计算机学科中的数学方法03三、计算机学科的根本问题计算结果的正确性是任何计算工具和计算方法研究中不可回避的问题，特别是使用自动计算机器进行的各种计算。一个问题在给出了能行的操作系列并解决了其效率问题之后，必须确保计算结果的正确性，否则，计算便毫无意义。3.计算结果的正确性04计算机学科的经典问题计算机学科的经典问题04一、现实意义上的不可计算问题——计算复杂性1.汉诺塔问题计算机学科的经典问题04一、现实意义上的不可计算问题——计算复杂性2.旅行商问题旅行商问题也被称为旅行推销员问题，是哈密顿和英国数学家柯克曼于19世纪初提出的一个数学问题：若干城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发，必须经过每个城市且只能在每个城市停留一次，最后回到原出发城市。计算机学科的经典问题04一、现实意义上的不可计算问题——计算复杂性3.四色问题四色问题又被称为四色猜想或四色定理(Four-ColorTheorem)，1852年首先由英国大学生古思里(FrancisGuthrie)提出。4.P=NP?问题解决NP完全问题的可行方法是寻找具有多项式时间复杂度的近似算法，即求得的是最优解的近似解，但算法的复杂度大为降低，是可用于实际计算的算法。计算机学科的经典问题04二、理论意义上的可计算问题——计算机智能问题1.图灵测试图灵测试方法和过程为：由一个男人A、一个女人B和一个性别不限的提问者c来完成。提问者C待在与两个回答者相隔离的房间里，如图2-14所示。计算机学科的经典问题04二、理论意义上的可计算问题——计算机智能问题2.西尔勒中文小屋与人工智能有关的另一