大学计算机基础之计算机思维基础教学课件

大学计算机基础第八章计算思维基础第八章计算思维基础主要内容8.1计算科学与计算学科8.2计算思维的概念8.3计算思维的内涵8.4计算思维的应用思维本身让人沉醉……计算思维除了给计算机技术带来变革，它还让人们在探索的过程中体验和谐、对称、完备、简洁等美学属性。科学的美不逊于艺术的美。科学的概念8.1计算科学与计算学科达尔文“科学就是整理事实，从中发现规律，作出结论。”科学是运用范畴、定理和定律等思维形式反映现实世界中各种现象的本质和运动规律的知识体系。“science”来源于拉丁文”scientia”,意为“知识与学问”。词源2.科学的分类广义科学自然科学：以自然界为主要研究对象，运用实证、理性和臻美等方法，解释自然的奥秘。人文科学：以人类为主要研究对象，，运用实地考察、诠释和启示等方法，认识人、人性和人生的意义，提升人的精神素质和思想境界。社会科学：以社会领域为主要研究对象，运用调查、统计和归纳等方法，把握社会规律，解决社会问题，促进社会进步。狭义科学自然科学（有时也指基础理论科学）

8.1计算科学与计算学科科学思维及其分类1）科学思维科学思维（ScientificThinking)是指经过感性阶段获取的大量材料通过整理和改造，形成概念、判断和推理，以便反映事物的本质和规律。科学思维是大脑对科学信息的加工活动。科学思维涵盖内容：

--思维要与客观实际相符

--要求遵循形式逻辑的规律和规则

--思维要具有创新性科学研究的方法：

--理论研究

--实验研究

--计算研究理论科学、实验科学和计算科学是推动人类文明进步和科技发展的主要途径。8.1计算科学与计算学科2）科学思维的分类对应的三大科学研究的思维是理论思维、实验思维和计算思维。理论思维：又称推理思维，以推理和演绎为特征，以数学学科为代表。实验思维：又称实证思维，以观察和总结自然规律为特征，以物理学科为代表。计算思维：又称构造思维，以设计和构造为特征，以计算机学科为代表。

计算思维就是思维过程或功能的计算模拟方法论，其研究的目的是提供适当的方法，使人们借助现代和将来的计算机，逐步实现人工智能的较高目标。诸如：模式识别、决策、优化和自控等算法都属于计算思维的范畴。三大思维都是人类科学思维方式中固有的部分。其中，理论思维强调推理，实验思维强调归纳，计算思维希望能自动求解。他们以不同的方式推动着科学的发展和人类文明的进步。8.1计算科学与计算学科几千年前：

科学是以观察或实验为依据的，经验的描述自然现象近几百年：

派生出理论的

使用模型进行一般化推理近几十年：

派生出计算的

用计算机辅助分析复杂现象

采集数据——软件处理——结果分析和统计8计算科学理论科学实验科学测试理论提出理论解释结果制作模型提出模型建模过程提出实验数据分析驱动装置大型计算模型验证数据生产解释结果生产模型精确计算验证理论生产数据提出理论3）理论科学、实验科学和计算科学的研究关系计算科学与计算学科计算科学计算科学（ComputingScience）是应用高性能计算能力预测和了解客观世界物质运动或复杂现象演化规律的科学，它包括数值模拟、过程仿真、高效计算机系统和应用软件等。-计算学科计算学科（ComputingDiscipline）是对描述和变化信息的算法过程进行系统的研究，它包括算法过程理论、分析、设计、效率分析、实现和应用等。计算学科的根本问题是“什么能被（有效地）自动进行”。人要成功融入社会所必备的思维能力，是由其解决问题时所能获得工具或过程决定的工业社会了解物理特性，思考如何用原料生成新事物组装线自动化草图制造工艺美术11计算思维简介信息社会为了问题求解，如何利用技术定位和使用信息电信、Email、信息空间网络、LAN、Modem、blogWYSIWYG(WhatYouSeeIsWhatYouGet)、文件、图标、光标芯片、RFID(射频识别)、USB……12计算思维简介超越信息社会利用数据和构想解决问题超越使用工具和信息，进而创造工具和信息需要抽象、数据处理等技能，和大量计算机科学概念的支持这就是“计算思维”……人类思维与计算机能力的综合……在21世纪，将是每个人所必备的基本技能读、写、算术13计算思维简介计算思维举例在排好序的花名册中查找某个人线性搜索、二分查找在银行窗口、超市排队任务调度的性能分析将小孩一天要上的课的课本放入书包预取与缓冲送小孩去参加各种兴趣班货郎担问题(旅行商问题）14计算思维简介准备晚餐并行处理清理衣柜替换——留下需要的、丢掉不用并且占地方的帮小孩收纳玩具Hash——按类型分别收纳、按形状、按材质……各种算术运算方法

1.计算思维概念的引入

2006年美国国家科学基金会（NSF）组织了计算教育与科学领域以及其他相关领域的专家，对“大学第一年计算机课程的构建”、“多学科的融合”等问题进行研讨。NSF先后启动了旨在振兴美国计算教育的四项国家计划：

-BPC（扩大计算参与面）

-CPATH（大学计算教育振兴途径）

-CDI（计算使能的科学发现和技术创新）

-CE21（21世纪计算科学教育）

目的是提高K-14（中小学和大学一、二年级）老师与学生的计算思维能力。8.2计算思维概述

计算思维概念的定义周以真定义：计算思维（ComputationalThinking，CT）是运用计算机科学的基础概念进行问题求解、系统设计、和理解人类行为等涵盖计算机科学广度的一系列思维活动。目的是培养学生像拥有阅读、写作和算术（3R）基本技能一样拥有计算思维技能，并能自觉地应用于日常的学习、研究与将来的工作中，要像计算机科学家那样思考问题。周以真：原美国卡内基·梅隆大学教授，2013年任微软全球资深副总裁、负责微软研究院全球各核心研究机构及学术合作部。2006年对计算思维进行了清晰、系统的阐述，使计算思维的概念得到人们的极大关注。2.计算思维定义2023/7/5172011年，国际教育技术协会(ISTE)和计算机科学教师协会(CSTA)给计算思维下了一个操作性的定义：

计算思维是一个问题解决的过程，该过程包括：①制定问题，并能够利用计算机和其他工具来帮助解决该问题；②符合逻辑地组织和分析数据；③通过抽象（如模型、仿真等）再现数据；④通过算法（一系列有序的步骤）支持自动化的解决方案；⑤识别、分析和实施可能的解决方案，并整合这些最有效的方案和资源；⑥将该问题的求解过程进行推广并移植到更广泛的应用中。2.计算思维定义J.M.Wing,“ComputationalThinking,”CACMViewpoint,March2006,pp.33-35.Paperoff/~wing/P.J.Denning观点ACM前主席Denning认为：计算原理可以总结为7类。

计算---Computation

通信---Communication

协作---Coordination

记忆---Recollection

自动化-Automation

评估---Evaluation

设计---Design7类原理：计算机理的功能角度Computation：meaningandlimitsofcomputationCommunication：reliabledatatransmissionCoordination：cooperationamongnetworkedentitiesRecollection：storageandretrievalofinformationAutomation：meaningandlimitsofautomationEvaluation：performancepredictionandcapacityplanningDesign：buildingreliablesoftwaresystems4类核心实践ProgrammingSystemsandsystemsthinkingModeling,validating,testing,andmeasuringInnovatingP.J.Denning观点例1计算函数f(x)区间[a,b]上的积分。在高等数学中，计算积分是使用牛顿—莱布尼兹公式，即首先求f(x)的原函数F(x),然后计算F(x)，解决这个问题不用黎曼积分的原因是计算量太大。在计算机中，计算积分的方法是使用黎曼积分，即对区间[a,b]进行n等分，然后计算各小矩形的面积。这里不用牛顿—莱布尼兹公式的原因有两个：一是不同的f(x)求原函数的方法是不同的；二是并不是所有的f(x)都能找到原函数F(x).计算思维示例ab例2：计算函数n的阶乘f(n)=n!在计算机中，采用两种方法：1）递归法：将计算f(n)的问题分解为计算一个较小的问题f(n-1),再将计算f(n-1)的问题分解为计算一个更小的问题f(n-2)……，直至分解到f(1)=1为止，然后从f(1)逐步计算到f(n)。

递推—回代2）迭代法：f(1)=1，根据f(1)计算f(2)……最后根据f(n-1)计算f(n)。例3服务窗口排队（1）问题只有一个服务窗口，有三个服务顾客，分别需要服务时间为：

C1:12min；C2:5min；C3:3min（2）引发思考如何评价不同方案不同情况服务顺序如何决定？到达时间不同、有不同的服务优先级、服务允许被中断（3）“讨论”出服务排队的核心方法先来先服务（FCFS)短任务优先（SJF)最短剩余时间优先（SRTF)优先级调度（HPF)时间片轮转（RR)在日常生活中，当小学生早晨去上学时，他把当天所需要的东西放进书包，这就是“预置”；当有人丢了东西，你建议他沿着走过的路线去寻找，这就叫“回退”；你永远不知道下一步会怎样，只能根据过去经验和当前情况来决定现在的行为。人生就是“在线算法”；在超市付费时，应当去排哪一个队呢？这就是“多服务器系统”；为什么停电时电话仍然可以使用呢？这就是“失败的无关性”和”设计的冗余性“。“晴带雨伞“，”饱带饥粮”，就是一种“预立”。计算思维的理解……计算思维的本质：抽象（Abstraction）和自动化（Automation）。计算思维的本质反映了计算的根本问题，即什么能被有效地自动进行。计算是抽象地自动进行，自动化需要某种计算机去解释现象。从操作层面上讲，计算就是如何寻找一台计算机去求解问题，选择合适的抽象，选择合适的计算机去解释执行抽象，后者就是自动化。计算思维中的抽象完全超越物理的时空观，并完全用符号来表示。其中，数字抽象只是一类特例。自动化就是机械地一步一步自动执行，其基础和前提是抽象。

案例：18世纪著名古典数学问题——哥尼斯堡七桥问题。3.计算思维的本质26哥尼斯堡城地处东普鲁士，位于普雷格尔河的两岸及河中心的两个岛上，城市各部分由七座桥与两岸连结起来。多年来，当地的居民总有一个愿望：从家里出去散步，能否通过每座桥恰好一次，再返回家中？但是任何人也没有找到这样一条理想的路径。哥尼斯堡普莱格尔河抽象案例：18世纪著名古典数学问题——哥尼斯堡七桥问题。

27

1736年，瑞士数学家欧拉(Euler)解决问题的方法是把陆地抽象为一个点，用连接两个点的线段表示桥梁，将该问题抽象成点与线的连接图的数学问题。实际问题的独特之处是把一个实际问题抽象成合适的“数学模型”。这就是计算思维中的抽象。4.计算思维的特征（1）计算机思维是人类求解问题的一条途径，是属于人的思维方式，不是计算机的思维方式。

计算机之所以能够求解问题，是因为人将计算思维的思想赋予了计算机，计算机才能够进行如迭代、递归等计算。（2）计算思维的过程可以由人执行，也可以由计算机执行。

这些计算人和计算机都可以做，只不过人的速度慢而已。借助于超算能力的计算机，人类就可以去解决那些在计算时代之前不敢尝试的问题，实现只有想不到的，没有做不到的境界。（3）计算思维是思想，不是人造物。

计算思维不是硬件，而是计算这一概念用于求解问题、管理日常生活以及与他人交流和互动的思想。（4）计算思维是概念化，不是程序化。

计算机科学并不仅仅是计算机编程，像计算机科学家那样去思维意味着远不止能为计算机编程，还要求能够在抽象的多个层次上思维。1.计算思维的基本问题

计算思维是研究计算的思维，研究计算思维的基本问题是要了解哪些问题是可计算的，哪些问题是不可计算的，以及计算的复杂性如何度量。

（1）可计算性

一个问题是可计算的是指可以使用计算机在有限步骤内完成计算。

图灵论题给出可计算性的定义：一个问题是可计算的，当且仅当它在图灵机上经过有限步骤之后可以得到正确的结果。

8.3计算思维的内涵（2）计算复杂性计算复杂性就是指用计算机求解问题的难易程度，通常可用时间复杂度和空间复杂度来衡量。计算复杂性理论是用数学方法研究各类问题的计算复杂性学科。它研究各种可计算问题在计算过程中时间和空间的耗费情况，以及在不同计算模型下，使用不同类型的资源和不同数量的资源时，各类问题复杂性的本质特性和相互关系。例汉诺塔问题【问题描述】相传古印度的僧侣在进行一种被称为汉诺塔的游戏，如图所示。条件是：每次只能移动一个盘；每次移动都不允许大盘移到小盘之上；

B塔作为辅助，中间过渡的塔。【分析】这个移动过程很复杂与烦琐，但规律性却很强。使用递归调用技术来解决这个移动过程，先得找到一个递归调用模型。想要得到汉诺塔问题的简单解法，着眼点应该是移动A塔最底部的大盘，而不是其顶部的小盘。考虑N个盘的一般情况。汉诺塔问题初始状态N-1N例

汉诺塔问题第一步：A塔上的N-1盘移至B塔汉诺塔的分解操作：N-1N例

汉诺塔问题第二步：A塔上的N盘移至C塔汉诺塔的分解操作：N-1N例

汉诺塔问题第三步：B塔上的N-1盘移至C塔汉诺塔的分解操作：N-1N我们看到，步骤2只需移动一次就可以完成；步骤1与3的操作则完全相同，唯一区别仅在于各塔的作用有所不同。这样，原问题被转换为与原问题相同性质的、规模小一些的新问题。即：HANOI(N,A,B,C)

可转化为

HANOI(N-1,A,C,B)与HANOI(N-1,B,A,C)

其中HANOI中的参数分别表示需移动的盘数、起始塔、临时塔与终止塔，这种转换直至转入的盘数为0为止，因为这时已无盘可移了，这就是需要找的递归调用模型。例

汉诺塔问题可以采用递归的方法，进行求解。问题：当n=64时，即有移动64个盘子时，需要移动多少次盘子？耗费多少时间呢？h(n)=2×h(n-1)+1=2×[2×h(n-2)+1]+1=22×h(n-2)+1]+2+1……=2n×h(0)+2n-1+……+22+2+1=2n-1+……+22+2+1=2n-1=264-1=18446744073709551615假定移动一个盘子1秒，僧侣要花费5849亿年的时间。假定计算机每秒可移动1000万个盘子，也需要花费约58490年的时间。理论上可以计算的问题，实际上并不一定能行。2.计算思维的核心概念分类关注点核心概念计算可计算性和计算复杂性计算模型、可计算性、计算复杂性抽象关注对象的本质特征抽象、抽象层次、概念模型、实现模型自动化信息处理的算法设计算法、程序，迭代、递归，启发式策略、随机策略，智能设计可靠和可信系统的构建分解、复合、折中，可靠性、安全性、重用性评估复杂系统的性能评价评价指标与基准、瓶颈、冗余、容错、性能仿真通信不同过程和对象间的可靠信息传递信息及其表示、信息量（熵）、编码与解码、信息压缩、信息加密、校验与纠错、协议协作多个自主计算实体间的有效配合和时序控制同步、并发、并行、事件、服务记忆信息的表示、存储和检索数据类型、数据结构、数据组织、检索与索引、局部性与缓存1.生物学计算生物学是指开发和应用数据分析及理论的方法、数学建模、计算机仿真技术等。用于生物学、行为学、和社会群体系统研究的一门学科。由于生物学数据量和复杂性不断增长，每14个月基因研究产生的数据就会翻一番，仅依靠观察和实验已难以应付。必须依靠大规模计算技术，从海量信息中提取有用的数据。有生物序列的片段拼接、序列对接、基因识别、蛋白质结构预测、生物数据库等。8.4计算思维的应用2.脑科学-模拟大脑像计算机脑科学是研究人脑结构与功能的综合性学科，以揭示人脑高级意识功能为宗旨，与教育学、心理学、人工智能、认知学科以及创造学等学科有紧密联系和交叉渗透。-通过机器学习分析脑成像通过分析脑成像技术（fMRI）

，对大脑的研究便可扩展至记忆、注意力、决定等。在某些情况下，脑成像技术甚至能够识别研究对象所见到的图像或者阅读的词语。-从患者身上提取皮肤细胞，转成干细胞，再将干细胞分裂成所需要的神经元，最后得到大脑细胞，首次在细胞水平上观察精神分裂患者的脑细胞。3.计算化学

计算化学是根据基本的物理化学理论，以大量数值运算方式来探讨化学系统的性质。主要以分子模拟为工具实现各种核心化学的计算问题，架起了理论化学与实验化学之间的桥梁。主要有如下研究方向：

1）化学中的数值计算

2）化学模拟3）化学中的模式识别

4