1、2一、科学的概念一、科学的概念 达尔文对科学定义达尔文对科学定义：科学就是整理事实，从：科学就是整理事实，从中发现规律并做出结论。中发现规律并做出结论。达尔文的定义指出了达尔文的定义指出了科学的内涵，即科学的内涵，即事实事实与与规规律律。科学要发现人所未知。科学要发现人所未知的事实，并以此为依据，的事实，并以此为依据，实事求是。至于规律是指实事求是。至于规律是指客观事物之间内在的本质客观事物之间内在的本质的必然联系。的必然联系。3爱因斯坦认为爱因斯坦认为：设法将人们杂乱无：设法将人们杂乱无章的感觉经验加以整理，使之符合章的感觉经验加以整理，使之符合逻辑一致的思想系统，就叫科学。逻辑一致的思想系
2、统，就叫科学。科学作为一种存在的事科学作为一种存在的事物和完整的事物，是人类认物和完整的事物，是人类认知的事物中最客观的。但科知的事物中最客观的。但科学在形成过程中，作为追求学在形成过程中，作为追求的目的，却如同人类的其他的目的，却如同人类的其他认知一样，是主观的也是受认知一样，是主观的也是受心理制约的。心理制约的。4 美国美国韦伯斯特新世界词典韦伯斯特新世界词典对科学定义对科学定义：科学是从确定研究对象的性质和规律这一目的出科学是从确定研究对象的性质和规律这一目的出发，通过观察、调查和实验得到的系统知识。发，通过观察、调查和实验得到的系统知识。中国中国辞海辞海对科学定义对科学定义：科学是运用
3、范畴、：科学是运用范畴、定理和定律等思维形式反映现实世界各种现象的定理和定律等思维形式反映现实世界各种现象的本质和运动规律的知识体系。本质和运动规律的知识体系。科学的定义科学的定义：反映现实世界中各种现象及其客观规：反映现实世界中各种现象及其客观规律的知识体系。科学作为人类知识的最高形式，已律的知识体系。科学作为人类知识的最高形式，已成为人类社会普遍的文化理念。成为人类社会普遍的文化理念。5 科学的种类科学的种类：按照研究对象的不同按照研究对象的不同自然科学、社会科学、思维科学自然科学、社会科学、思维科学 按照与实践联系的不同按照与实践联系的不同 理论科学、技术科学、应用科学理论科学、技术科学
4、、应用科学 按照人类对自然规律利按照人类对自然规律利用的直接程度用的直接程度 自然科学、实验科学自然科学、实验科学 按照人类目标的不同按照人类目标的不同广义的科学、狭义的科学广义的科学、狭义的科学 广义的科学广义的科学概念是自然科学、人文科学和社会科学等所有概念是自然科学、人文科学和社会科学等所有学科的总称，学科的总称，狭义的科学狭义的科学概念则专指自然科学，有时甚至概念则专指自然科学，有时甚至直指基础理论科学。直指基础理论科学。6自然科学自然科学Natural Science以自然界为主要研究对象，运用以自然界为主要研究对象，运用实证实证、理性理性和和臻美臻美等方法，揭示自然的奥秘，获取自然
5、等方法，揭示自然的奥秘，获取自然的真知。的真知。人文科学人文科学humanities以人类作为主要研究对象，运用以人类作为主要研究对象，运用实地考察实地考察、诠释诠释和和启示启示等方法，认识人、人性和人生的等方法，认识人、人性和人生的意义，提升人的精神素质和思想境界。意义，提升人的精神素质和思想境界。社会科学社会科学Social Science以社会领域为主要研究对象，运用以社会领域为主要研究对象，运用调查调查、统统计计和和归纳归纳等方法，把握社会规律，解决社会等方法，把握社会规律，解决社会问题，促进社会进步。问题，促进社会进步。如何界定自然科学如何界定自然科学？物理学，化学，？物理学，化学，
6、计算科学？数学？计算科学？数学？7 美国能源部报告认为美国能源部报告认为：高端计算目前已经与理论研究、实验：高端计算目前已经与理论研究、实验手段一起，成为获得科学发现的三大支柱。因此，手段一起，成为获得科学发现的三大支柱。因此，理论科学理论科学、实实验科学验科学和和计算科学计算科学是推动人类文明进步和科技发展的重要途径。是推动人类文明进步和科技发展的重要途径。8二、计算科学与计算学科二、计算科学与计算学科 计算科学计算科学/Computational Science/Computational Science：一种与：一种与数学模型构建、定量分析方法以及利用计算机来数学模型构建、定量分析方法以
7、及利用计算机来分析和解决科学问题的研究领域。分析和解决科学问题的研究领域。(计算视角计算视角)计算科学计算科学/Computing Science/Computing Science：应用高性能：应用高性能计算能力预测和了解实际世界物质运动或复杂现计算能力预测和了解实际世界物质运动或复杂现象演化规律的科学，它包括数值模拟、工程仿真象演化规律的科学，它包括数值模拟、工程仿真高效计算机系统和应用软件等。高效计算机系统和应用软件等。(计算机视角计算机视角)9 19931993：高性能计算与通信：高性能计算与通信-HPCC-HPCC计划计划 20192019：加速战略计算创新：加速战略计算创新-ASC
8、I-ASCI计划计划 20192019：高性能计算系统：高性能计算系统-HPCS-HPCS计划计划20192019：计算科学：计算科学-确保美国的竞争力确保美国的竞争力报告建议：应将计报告建议：应将计算科学长期置于国家科学与技术领域中心的领导地位。算科学长期置于国家科学与技术领域中心的领导地位。计算科学是运用高级计算能力来理解和处理复杂问计算科学是运用高级计算能力来理解和处理复杂问题的学科，已经成为对科学领导力、经济竞争力以及国题的学科，已经成为对科学领导力、经济竞争力以及国家安全都至关重要的一门科学。家安全都至关重要的一门科学。我们相信计算科学是我们相信计算科学是2121世纪最重要的技术领域
9、之一，世纪最重要的技术领域之一，因为它对整个社会的进步都是十分重要的。计算科学为因为它对整个社会的进步都是十分重要的。计算科学为研究者提供了一个独特的窗口，他们可以通过它来研究研究者提供了一个独特的窗口，他们可以通过它来研究那些不切实际或很难解决的问题，为高经济效益提供高那些不切实际或很难解决的问题，为高经济效益提供高级工业方法，如高效设计比价格昂贵又费时的风洞试验级工业方法，如高效设计比价格昂贵又费时的风洞试验更有效的机翼计算试验。更有效的机翼计算试验。10 学科学科：指高校中讲授或研究知识的分科。：指高校中讲授或研究知识的分科。计算学科计算学科/Computational Discipli
10、ne/Computational Discipline:利利用计算科学对其他学科中的问题进行计算机模拟用计算科学对其他学科中的问题进行计算机模拟或者其他形式的计算而形成的诸如计算物理、计或者其他形式的计算而形成的诸如计算物理、计算化学等学科统称为计算学科。算化学等学科统称为计算学科。(计算视角计算视角)计算学科计算学科/Computing Discipline/Computing Discipline:是对描述是对描述和变换信息的算法过程进行系统的研究，它包括和变换信息的算法过程进行系统的研究，它包括算法过程的理论、分析、设计、效率分析、实现算法过程的理论、分析、设计、效率分析、实现和应用等。
11、和应用等。(计算机视角计算机视角)11 计算学科计算学科是在数学和电子科学基础上发展起是在数学和电子科学基础上发展起来的一门新兴学科，它既是一门来的一门新兴学科，它既是一门理论性理论性很强的学很强的学科，又是一门科，又是一门实践性实践性很强的学科。很强的学科。12三、计算机科学与计算机学科三、计算机科学与计算机学科 计算机科学计算机科学/Computer Science：研究计算机及：研究计算机及其周围各种现象和规律的科学。其周围各种现象和规律的科学。分类分类：理论计算机科学、应用计算机科学。：理论计算机科学、应用计算机科学。计算机学科计算机学科/Computer Discipline：即计算
12、机科：即计算机科学与技术，它是研究计算机的设计与制造和利用计算学与技术，它是研究计算机的设计与制造和利用计算机进行信息获取、表示、储存、处理、控制等的理论、机进行信息获取、表示、储存、处理、控制等的理论、原则、方法和技术的学科。原则、方法和技术的学科。计算机科学计算机科学侧重研究现象与揭示规律。侧重研究现象与揭示规律。计算机技计算机技术术侧重研制计算机及使用计算机进行信息处理的方法侧重研制计算机及使用计算机进行信息处理的方法和技术手段。和技术手段。13一、思维的概念一、思维的概念 思维是精神思维是精神地球上最美丽的花朵地球上最美丽的花朵。2.2.思维的组成思维的组成 思维原料思维原料(自然界自
13、然界)、思维主体、思维主体(人脑人脑)思维工具思维工具(认识的反映形式认识的反映形式)1.1.思维的定义思维的定义 思维是人脑对客观事物的一种概括的、间思维是人脑对客观事物的一种概括的、间接的反映，它反映客观事物的本质和规律。接的反映，它反映客观事物的本质和规律。14 3.3.思维的特征思维的特征 概括性概括性思维是在人的感性基础上，将一类事物的共思维是在人的感性基础上，将一类事物的共同本质的特征和规律抽取出来，加以概括。同本质的特征和规律抽取出来，加以概括。如人们感知如人们感知(日出东方、日落西山日出东方、日落西山)，通过思，通过思维概括揭示是地球自转的结果。维概括揭示是地球自转的结果。间接
14、性间接性指非直接的，以其它事物做媒介来反映客观指非直接的，以其它事物做媒介来反映客观事物。如根据医学知识和临床经验，医生询事物。如根据医学知识和临床经验，医生询问病史和辅助检查，判断病情，作出治疗。问病史和辅助检查，判断病情，作出治疗。能动性能动性不仅能认识和反映世界，而且还能对客观世不仅能认识和反映世界，而且还能对客观世界进行改造。如人们不仅能认知宇宙速度，界进行改造。如人们不仅能认知宇宙速度，还能制造宇宙飞船飞向太空。还能制造宇宙飞船飞向太空。15 4.4.思维的类型思维的类型按照思维的进程方向按照思维的进程方向 横向思维、纵向思维横向思维、纵向思维发散思维、收敛思维发散思维、收敛思维 按
15、照思维的抽象程度按照思维的抽象程度 直观行动思维直观行动思维具体形象思维具体形象思维抽象逻辑思维抽象逻辑思维 按照思维的形成和应用按照思维的形成和应用领域领域 科学思维科学思维日常思维日常思维 16二、科学思维二、科学思维 科学思维科学思维：指理性认识及其过程，即经过感：指理性认识及其过程，即经过感性阶段获得的大量材料，通过整理和改造，形成性阶段获得的大量材料，通过整理和改造，形成概念、判断和推理，以便反映事物本质和规律。概念、判断和推理，以便反映事物本质和规律。简而言之，科学思维是人脑对科学信息的加工活动。简而言之，科学思维是人脑对科学信息的加工活动。科学思维的主要表现科学思维的主要表现：科
16、学的理性思维科学的理性思维科学的逻辑思维科学的逻辑思维科学的系统思维科学的系统思维科学的创造性思维科学的创造性思维 17三、科学思维的分类三、科学思维的分类理论思维理论思维理论源于数学，理论思维支撑着所有的学科领域。理论源于数学，理论思维支撑着所有的学科领域。正如数学一样，定义是理论思维的灵魂，定理和证正如数学一样，定义是理论思维的灵魂，定理和证明是其精髓，公理化方法是最重要的理论思维方法明是其精髓，公理化方法是最重要的理论思维方法实验思维实验思维实验思维的先驱是意大利科学家伽利略，被人们誉实验思维的先驱是意大利科学家伽利略，被人们誉为为“近代科学之父近代科学之父”。与理论思维不同，实验思维。
17、与理论思维不同，实验思维往往需要借助于某些特定的设备，使用它们来获取往往需要借助于某些特定的设备，使用它们来获取数据以便进行分析。数据以便进行分析。计算思维计算思维计算思维是思维过程或功能的计算模拟方法论，其计算思维是思维过程或功能的计算模拟方法论，其研究目的是提供适当的方法，使人们能借助计算机研究目的是提供适当的方法，使人们能借助计算机逐步达到人工智能的较高目标。逐步达到人工智能的较高目标。18 三种科学对应着三种思维三种科学对应着三种思维：理论科学理论科学理论思维理论思维 理论思维又称逻辑思维，它以推理和演绎为特征，理论思维又称逻辑思维，它以推理和演绎为特征，以数学学科为代表。以数学学科为
18、代表。实验科学实验科学实验思维实验思维 实验思维又称实证思维，它以观察和总结自然规律实验思维又称实证思维，它以观察和总结自然规律为特征，以物理学科为代表。为特征，以物理学科为代表。计算科学计算科学计算思维计算思维 计算思维又称构造思维，它以设计和构造为特征，计算思维又称构造思维，它以设计和构造为特征，以计算机学科为代表。以计算机学科为代表。19一、计算思维的定义一、计算思维的定义 计算思维计算思维(Computational Thinking(Computational Thinking，CT)CT)周以真认为周以真认为：计算思维是运用计算机科学的：计算思维是运用计算机科学的基础概念去基础概念
19、去求解问题求解问题、设计系统设计系统和和理解人类行为理解人类行为的涵盖了计算机科学之广度的一系列思维活动。的涵盖了计算机科学之广度的一系列思维活动。20 针对上述定义解释如下：针对上述定义解释如下：中的计算思维中的计算思维 利用计算手段求解问题的过程是：首先要把利用计算手段求解问题的过程是：首先要把实际的应用问题转换为数学问题，可能是一组偏实际的应用问题转换为数学问题，可能是一组偏微分方程，其次将微分方程，其次将PDEPDE离散为一组代数方程组，离散为一组代数方程组，然后建立模型、设计算法和编程实现，最后在实然后建立模型、设计算法和编程实现，最后在实际的计算机中运行并求解。际的计算机中运行并求
20、解。前两步是计算思维中的抽象，后两步是计算前两步是计算思维中的抽象，后两步是计算思维中的自动化。思维中的自动化。21 中的计算思维中的计算思维 R.KarpR.Karp认为认为：任何自然系统和社会系统都可：任何自然系统和社会系统都可视为一个动态演化系统，演化伴随着物质、能量视为一个动态演化系统，演化伴随着物质、能量和信息的交换，这种交换可以映射为符号变换，和信息的交换，这种交换可以映射为符号变换，使之能用计算机进行离散的符号处理。使之能用计算机进行离散的符号处理。当动态演化系统抽象为离散符号系统后，就当动态演化系统抽象为离散符号系统后，就可以采用形式化的规范描述，建立模型、设计算可以采用形式化
21、的规范描述，建立模型、设计算法和开发软件来揭示演化的规律，实时控制系统法和开发软件来揭示演化的规律，实时控制系统的演化并自动执行。的演化并自动执行。22 中的计算思维中的计算思维 王飞跃认为王飞跃认为(中科院中科院)：计算思维是基于可计：计算思维是基于可计算的手段，以定量化的方式进行的思维过程。计算的手段，以定量化的方式进行的思维过程。计算思维就是应对信息时代新的社会动力学和人类算思维就是应对信息时代新的社会动力学和人类动力学所要求的思维。在人类的动力学所要求的思维。在人类的物理世界物理世界、精神精神世界世界和和人工世界人工世界等三个世界中，计算思维是建设等三个世界中，计算思维是建设人工世界需
22、要的主要思维方式。人工世界需要的主要思维方式。利用计算手段来研究人类的行为，可视为社利用计算手段来研究人类的行为，可视为社会计算，即通过各种信息技术手段，设计、实施会计算，即通过各种信息技术手段，设计、实施和评估人与环境之间的交互。和评估人与环境之间的交互。23波尔普的三个世界观点波尔普的三个世界观点24二、计算思维的详细描述二、计算思维的详细描述 计算思维是通过计算思维是通过约简、嵌入、转化约简、嵌入、转化和和仿真仿真等方等方法，把一个看来困难的问题重新阐释成一个人法，把一个看来困难的问题重新阐释成一个人们知道怎样解决的问题。们知道怎样解决的问题。计算思维是一种计算思维是一种递归思维递归思维
23、，是一种，是一种并行处理并行处理，是一种把代码译成数据又能把数据译成代码，是一种把代码译成数据又能把数据译成代码，是一种多维分析推广的类型检查方法。是一种多维分析推广的类型检查方法。计算思维是一种采用计算思维是一种采用抽象抽象和和分解分解来控制庞杂的来控制庞杂的任务或进行巨大复杂系统设计的方法，是一种任务或进行巨大复杂系统设计的方法，是一种基于关注点分离的方法。基于关注点分离的方法。25计算思维是一种选择合适的方式去计算思维是一种选择合适的方式去陈述陈述一个问题，一个问题，或对一个问题的相关方面或对一个问题的相关方面建模建模并使其易于处理的并使其易于处理的思维方法。思维方法。计算思维是按照计算
24、思维是按照预防预防、保护保护及通过及通过冗余冗余、容错容错和和纠错纠错方式，从最坏情况进行系统恢复的一种思维方式，从最坏情况进行系统恢复的一种思维方法。方法。计算思维是利用计算思维是利用启发式启发式推理寻求解答，也即在不推理寻求解答，也即在不确定情况下的规划、学习和调度的思维方法。确定情况下的规划、学习和调度的思维方法。计算思维是利用计算思维是利用海量数据海量数据来加快计算，在时间和来加快计算，在时间和空间之间，在处理能力和存储容量之间进行折中空间之间，在处理能力和存储容量之间进行折中的思维方法。的思维方法。26三、计算思维的特征三、计算思维的特征 1.1.概念化，不是程序化概念化，不是程序化
25、 计算机科学不是计算机编程计算机科学不是计算机编程。像计算机科学家那。像计算机科学家那样去思维意味着远远不仅限于计算机编程，还要求能样去思维意味着远远不仅限于计算机编程，还要求能够在抽象的多个层次上思维。计算机科学不只是关注够在抽象的多个层次上思维。计算机科学不只是关注计算机，就像音乐产业不只是关注麦克风一样。计算机，就像音乐产业不只是关注麦克风一样。2.2.根本的，不是刻板的技能根本的，不是刻板的技能 计算思维是一种根本技能，是每一个人为了在现计算思维是一种根本技能，是每一个人为了在现代社会中发挥职能所必须掌握的。刻板的技能意味着代社会中发挥职能所必须掌握的。刻板的技能意味着简单的机械重复。
26、简单的机械重复。27 3.3.是人的，不是计算机的思维是人的，不是计算机的思维 计算思维是人类求解问题的一条途径，但决非要计算思维是人类求解问题的一条途径，但决非要使人类像计算机那样地思考。计算机枯燥且沉闷，人使人类像计算机那样地思考。计算机枯燥且沉闷，人类聪颖且富有想象力。是人类赋予计算机激情。计算类聪颖且富有想象力。是人类赋予计算机激情。计算机赋予人类强大的计算能力，人类应该好好的利用这机赋予人类强大的计算能力，人类应该好好的利用这种力量去解决各种需要大量计算的问题种力量去解决各种需要大量计算的问题。4.4.是思想，不是人造物是思想，不是人造物 不只是将生产的软硬件等人造物到处呈现给我们不
27、只是将生产的软硬件等人造物到处呈现给我们的生活，更重要的是计算概念，它被人们用来问题求的生活，更重要的是计算概念，它被人们用来问题求解、日常生活的管理，以及与他人进行交流和互动。解、日常生活的管理，以及与他人进行交流和互动。28 5.5.数学和工程思维的互补与融合数学和工程思维的互补与融合 计算机科学在本质上源自数学思维，它的形式化基计算机科学在本质上源自数学思维，它的形式化基础建筑于数学之上。计算机科学又从本质上源自工程思础建筑于数学之上。计算机科学又从本质上源自工程思维，因为我们建造的是能够与实际世界互动的系统。所维，因为我们建造的是能够与实际世界互动的系统。所以设计思维是数学和工程思维的
28、互补与融合。以设计思维是数学和工程思维的互补与融合。6.6.面向所有的人，所有地方面向所有的人，所有地方 当计算思维真正融入人类活动的整体时，它作为一当计算思维真正融入人类活动的整体时，它作为一个问题解决的有效工具，人人都应当掌握，处处都会被个问题解决的有效工具，人人都应当掌握，处处都会被使用。使用。29四、计算思维的本质四、计算思维的本质 抽象抽象(Abstract)(Abstract)、自动化自动化(Automation)(Automation)。它反映了计算的根本问题，即什么能被有效它反映了计算的根本问题，即什么能被有效的自动进行。的自动进行。计算是抽象的自动执行，自动化需要某种计计算是
29、抽象的自动执行，自动化需要某种计算机去解释抽象。算机去解释抽象。从操作层面上讲，计算就是如何寻找一台计从操作层面上讲，计算就是如何寻找一台计算机去求解问题，隐含地说就是要确定合适的抽算机去求解问题，隐含地说就是要确定合适的抽象，选择合适的计算机去解释执行该抽象，后者象，选择合适的计算机去解释执行该抽象，后者就是自动化。就是自动化。30五、计算思维与计算机的关系五、计算思维与计算机的关系 计算思维虽然具有计算机的许多特征，但是计算计算思维虽然具有计算机的许多特征，但是计算思维本身并不是计算机的专属。实际上，即使没有计思维本身并不是计算机的专属。实际上，即使没有计算机，计算思维也会逐步发展，甚至有
30、些内容与计算算机，计算思维也会逐步发展，甚至有些内容与计算机没有关系。但是，正是由于计算机的出现，给计算机没有关系。但是，正是由于计算机的出现，给计算思维的发展带来了根本性的变化。思维的发展带来了根本性的变化。31一、生物学一、生物学 计算机科学许多领域渗透到生物信息学中的计算机科学许多领域渗透到生物信息学中的应用研究，包括数据库、数据挖掘、人工智能、应用研究，包括数据库、数据挖掘、人工智能、算法、图形学、软件工程、并行计算和网络技术算法、图形学、软件工程、并行计算和网络技术等都被用于生物计算的研究。等都被用于生物计算的研究。从各种生物的从各种生物的DNADNA数据中挖掘数据中挖掘DNADNA
31、序列自身规律和序列自身规律和DNADNA序列进化序列进化规律，可以帮助人们从分子层次规律，可以帮助人们从分子层次上认识生命的本质及其进化规律上认识生命的本质及其进化规律 DNA DNA序列实际上是一种用四种序列实际上是一种用四种字母表达的字母表达的“语言语言”。32二、脑科学二、脑科学 脑科学是研究人脑结构与功能的综合性学科脑科学是研究人脑结构与功能的综合性学科它以揭示人脑高级意识功能为宗旨，与心理学、它以揭示人脑高级意识功能为宗旨，与心理学、人工智能、认知科学和创造学等有着交叉渗透。人工智能、认知科学和创造学等有着交叉渗透。美国神经生理学家罗杰美国神经生理学家罗杰斯佩里斯佩里进行了进行了裂脑
32、实验裂脑实验，提出大脑两半，提出大脑两半球功能分工理论。他认为：大脑球功能分工理论。他认为：大脑左右半球完全可以以不同的方式左右半球完全可以以不同的方式进行思维活动，左脑侧重于抽象进行思维活动，左脑侧重于抽象思维，如逻辑抽象、演绎推理和思维，如逻辑抽象、演绎推理和语言表达等；右脑侧重于形象思语言表达等；右脑侧重于形象思维，如直觉情感、想象创新等。维，如直觉情感、想象创新等。33三、化学三、化学 计算机科学在化学中的应用包括：化学中的计算机科学在化学中的应用包括：化学中的数值计算、化学模拟、化学中的模式识别、化学数值计算、化学模拟、化学中的模式识别、化学数据库及检索、化学专家系统等。数据库及检索
33、、化学专家系统等。基于非结构网格和分区并行基于非结构网格和分区并行算法，为求解多组分化学反算法，为求解多组分化学反应流动守恒方程组开发了单应流动守恒方程组开发了单程序多数据流形式的并行程程序多数据流形式的并行程序，对己有的预混可燃气体序，对己有的预混可燃气体中高速飞行的弹丸的爆轰现中高速飞行的弹丸的爆轰现象进行了有效的数值模拟。象进行了有效的数值模拟。34四、经济学四、经济学 计算博弈论正在改变人们的思维方式。计算博弈论正在改变人们的思维方式。囚徒困境囚徒困境是博弈论专家设计的典型示例，但是博弈论专家设计的典型示例，但是囚徒困境博弈模型可以用来描述两家企业的是囚徒困境博弈模型可以用来描述两家企
34、业的价价格大战格大战等许多经济现象。等许多经济现象。百事可乐百事可乐可口可乐可口可乐高价高价低价低价低价低价 高价高价106060103030505035五、艺术五、艺术 计算机艺术是科学与艺术相结合的一门新兴计算机艺术是科学与艺术相结合的一门新兴的交叉学科，它包括绘画、音乐、舞蹈、影视、的交叉学科，它包括绘画、音乐、舞蹈、影视、广告、书法模拟、服装设计、图案设计、产品和广告、书法模拟、服装设计、图案设计、产品和建筑造型设计以及电子出版物等众多领域。建筑造型设计以及电子出版物等众多领域。36六、其他领域六、其他领域工程学工程学(电子、土木、机械、航空航天等电子、土木、机械、航空航天等)：计算高
35、阶项可以提高精度计算高阶项可以提高精度,进而降低重量、减少浪进而降低重量、减少浪费并节省制造成本；波音费并节省制造成本；波音777777飞机完全是采用计算机模飞机完全是采用计算机模拟测试的，没有经过风洞测试。拟测试的，没有经过风洞测试。社会科学社会科学：社交网络是社交网络是MySpaceMySpace和和YouTubeYouTube等发展壮大的原因等发展壮大的原因之一；统计机器学习被用于推荐和声誉服务系统之一；统计机器学习被用于推荐和声誉服务系统,例如例如NetflixNetflix和联名信用卡等。和联名信用卡等。地质学、天文学、数学、医学、法律、娱乐、体育等地质学、天文学、数学、医学、法律、
36、娱乐、体育等37一、排序问题一、排序问题 排序是把给定数据集合中的元素按照一定的排序是把给定数据集合中的元素按照一定的标准来安排先后次序的过程。标准来安排先后次序的过程。选择排序算法选择排序算法：对给定的一个：对给定的一个数据表，算法从第一个元素开始扫数据表，算法从第一个元素开始扫描整个列表，找到最小或最大的元描整个列表，找到最小或最大的元素，并将其与第一个位置的元素交素，并将其与第一个位置的元素交换。然后算法从第二个位置的元素换。然后算法从第二个位置的元素开始扫描剩下的列表，找到次小或开始扫描剩下的列表，找到次小或次大的元素，并将其与第二个位置次大的元素，并将其与第二个位置的元素交换。如此循
37、环，直到所有的元素交换。如此循环，直到所有的元素都被排好序为止。的元素都被排好序为止。选择排序算法是由一选择排序算法是由一个双层循环控制，算个双层循环控制，算法时间复杂度是法时间复杂度是O(nO(n2 2)38 部分排序算法的时间效率比较部分排序算法的时间效率比较 (单位：毫秒单位：毫秒)每一种排序算法对时间的效率和空间的要求不尽相同，每一种排序算法对时间的效率和空间的要求不尽相同，没有哪一种是绝对最优的，在实用时需要根据不同情况没有哪一种是绝对最优的，在实用时需要根据不同情况适当选用，也可多种方法结合使用。适当选用，也可多种方法结合使用。排序算法排序算法10101001001K1K10K10
38、K100K100K1M1M插入排序插入排序0.0002580.0002580.0086190.0086190.7640.764565651455145515621515621冒泡排序冒泡排序0.0002760.0002760.0056430.0056430.5450.545616181748174549432549432选择排序选择排序0.0002370.0002370.0064380.0064380.4880.488474747174717478694478694快速排序快速排序0.0002910.0002910.0030510.0030510.0300.0300.3110.3113.634
39、3.6343939归并排序归并排序0.0007230.0007230.0062250.0062250.0660.0660.5610.5615.485.487070基数排序基数排序0.0051810.0051810.0210.0210.1650.1651.651.6511.42811.428117117哈希排序哈希排序0.0005220.0005220.0033720.0033720.0360.0360.5180.5184.1524.152616139二、汉诺塔问题二、汉诺塔问题印度古老传说印度古老传说：在世界中心贝拿勒斯的圣庙里，一块黄铜板上：在世界中心贝拿勒斯的圣庙里，一块黄铜板上插着三根宝
40、石针插着三根宝石针A A、B B和和C C。印度教的主神梵天在创造世界时，。印度教的主神梵天在创造世界时，在其中一根针上从下到上地穿好了由大到小的在其中一根针上从下到上地穿好了由大到小的6464片金片，这就片金片，这就是所谓的汉诺塔问题。是所谓的汉诺塔问题。不论白天黑夜，总有一个僧侣在按不论白天黑夜，总有一个僧侣在按下面的法则移动这些金片：一次只下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当必须在大片上面。僧侣们预言，当所有金片移到另外一根针上时，世所有金片移到另外一根针上时，世界将在一声霹雳中消灭，而梵塔、界将在一声霹
41、雳中消灭，而梵塔、庙宇和众生也都将同归于尽。庙宇和众生也都将同归于尽。40 不管这个传说的可信度有多大，如果仅考虑把不管这个传说的可信度有多大，如果仅考虑把6464片金片，由片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢？这里需要使用要多少次移动呢？这里需要使用递归算法递归算法。假设有假设有n n片，移动次数是片，移动次数是f(n)f(n)显然显然f(1)=1f(1)=1，f(2)=3f(2)=3，f(3)=7f(3)=7，且，且f(k+1)=2f(k+1)=2*f(k)+1f(k)+1 不难证明不难证明
42、f(n)=2n-1f(n)=2n-1 当当n=64n=64时，时，f(64)=264-1=18446744073709551615f(64)=264-1=18446744073709551615次次 如果每秒钟移动一次，共需多长时间呢？如果每秒钟移动一次，共需多长时间呢？一年有一年有3153600031536000秒，则秒，则18446744073709551615/31536000=584918446744073709551615/31536000=5849亿年亿年41三、国王的婚姻三、国王的婚姻国王：艾述国王：艾述(喜爱数学喜爱数学)宰相：孔唤石宰相：孔唤石(数学家数学家)公主：秋碧贞楠公
43、主：秋碧贞楠(邻国邻国)公主：求出公主：求出4877042864483689948770428644836899的一个真因子的一个真因子国王：国王：2,3,4,300002,3,4,30000多数据多数据(一天一天)公主：验证一下，公主：验证一下，223092871223092871宰相：将全国百姓按自然数的顺序编号，百姓用自己的编号宰相：将全国百姓按自然数的顺序编号，百姓用自己的编号去除公主的数，谁除尽来领赏。去除公主的数，谁除尽来领赏。童话说明童话说明：国王本人计算：国王本人计算(串行算法，时间复杂性串行算法，时间复杂性)全国百姓计算全国百姓计算(并行算法，空间复杂性并行算法，空间复杂性)
44、42四、旅行商问题四、旅行商问题 旅行商问题旅行商问题(TSP)(TSP)的描述的描述：一位商人去：一位商人去n n个城个城市推销货物，所有城市走一遍后，再回到起点，市推销货物，所有城市走一遍后，再回到起点，问如何事先确定好一条最短的路线，使其旅行的问如何事先确定好一条最短的路线，使其旅行的费用最少。费用最少。路径路径ABCDAABCDA的总距离是：的总距离是：4+2+4+2=124+2+4+2=12路径路径ABDCAABDCA的总距离是：的总距离是：4+6+4+6=204+6+4+6=20路径路径ACBDAACBDA的总距离是：的总距离是：6+2+6+2=166+2+6+2=16路径路径AC
45、DBAACDBA的总距离是：的总距离是：6+4+6+4=206+4+6+4=20路径路径ADCBAADCBA的总距离是：的总距离是：2+4+2+4=122+4+2+4=12路径路径ADBCAADBCA的总距离是：的总距离是：2+6+2+6=162+6+2+6=1643 城市数目为城市数目为4 4时，组合路径数为时，组合路径数为6 6 城市数目为城市数目为n n时，组合路径数为时，组合路径数为(n-1)!(n-1)!当城市数目不多时要找到最短距离的路线并不难，当城市数目不多时要找到最短距离的路线并不难，但随着城市数目的不断增大，组合路线数将呈指数级数但随着城市数目的不断增大，组合路线数将呈指数级
46、数规律急剧增长，以至到达无法计算的地步，这就是所谓规律急剧增长，以至到达无法计算的地步，这就是所谓的组合爆炸问题。的组合爆炸问题。假如城市的数目增为假如城市的数目增为2020个，组合路径数则为个，组合路径数则为(20-1)(20-1)！1.2161.21610101717 若计算机以每秒检索若计算机以每秒检索10001000万条路线的速度计算，万条路线的速度计算，也需要花上也需要花上386386年的时间。年的时间。44 科学的定义和种类科学的定义和种类理论科学理论科学、实验科学实验科学、计算科学计算科学 计算科学和计算学科计算科学和计算学科(不同视角不同视角)计算机科学知识体计算机科学知识体(
47、14(14个知识领域个知识领域)计算机科学与计算机学科计算机科学与计算机学科(不同视角不同视角)计算机科学与技术一级学科、二级学科计算机科学与技术一级学科、二级学科 思维的定义、组成、特征和类型思维的定义、组成、特征和类型 科学思维的定义和分类科学思维的定义和分类理论思维理论思维、实验思维实验思维、计算思维计算思维45 计算思维的定义、详细描述、特征和本质计算思维的定义、详细描述、特征和本质 计算思维与计算机的关系计算思维与计算机的关系 计算思维的应用领域计算思维的应用领域 （生物学、脑科学、化学、经济学、艺术、（生物学、脑科学、化学、经济学、艺术、工程学、社会科学等）工程学、社会科学等）计算学科的典型问题计算学科的典型问题 （通过排序问题、汉诺塔问题、国王的婚姻、（通过排序问题、汉诺塔问题、国王的婚姻、旅行商问题来说明旅行商问题来说明人所固有的能力与局限性、人所固有的能力与局限性、计算机的计算能力与局限性，以及问题到底有计算机的计算能力与局限性，以及问题到底有多复杂）多复杂）
