1、大学计算机基础第八章第八章 计算思维基础计算思维基础主要内容主要内容8.1 8.1 计算科学与计算学科计算科学与计算学科8.2 8.2 计算思维的概念计算思维的概念8.3 8.3 计算思维的内涵计算思维的内涵8.4 8.4 计算思维的应用计算思维的应用 思维本身让人沉醉 计算思维除了给计算机技术带来变革，它还让人们在探索的过程中体验和谐、对称、完备、简洁等美学属性。 科学的美不逊于艺术的美。1.1.科学的概念科学的概念达尔文“科学就是整理事实，从中发现规律，作出结科学就是整理事实，从中发现规律，作出结论。论。”科学是运用范畴、定理和定律等思维形式反映现科学是运用范畴、定理和定律等思维形式反映现
2、实世界中各种现象的本质和运动规律的知识体系。实世界中各种现象的本质和运动规律的知识体系。“science”science”来源于拉丁文来源于拉丁文”scientia”, scientia”, 意为意为“知识知识与学问与学问”。词源词源2. 2. 科学的分类科学的分类p广义科学广义科学 自然科学：以自然界为主要研究对象，运用实证、理性和自然科学：以自然界为主要研究对象，运用实证、理性和臻美等方法，解释自然的奥秘。臻美等方法，解释自然的奥秘。 人文科学：以人类为主要研究对象，运用实地考察、诠人文科学：以人类为主要研究对象，运用实地考察、诠释和启示等方法，认识人、人性和人生的意义，提升人的精释和启示
3、等方法，认识人、人性和人生的意义，提升人的精神素质和思想境界。神素质和思想境界。 社会科学：以社会领域为主要研究对象，运用调查、统计社会科学：以社会领域为主要研究对象，运用调查、统计和归纳等方法，把握社会规律，解决社会问题，促进社会进和归纳等方法，把握社会规律，解决社会问题，促进社会进步。步。p狭义科学狭义科学 自然科学（有时也指基础理论科学）自然科学（有时也指基础理论科学） 3.3.科学思维及其分类科学思维及其分类1 1）科学思维）科学思维科学思维（科学思维（Scientific Thinking)Scientific Thinking)是指经过感性阶段获取是指经过感性阶段获取的大量材料通过
4、整理和改造，形成概念、判断和推理，以的大量材料通过整理和改造，形成概念、判断和推理，以便反映事物的本质和规律。便反映事物的本质和规律。科学思维是大脑对科学信息的加工活动。科学思维是大脑对科学信息的加工活动。科学思维涵盖内容：科学思维涵盖内容： - - 思维要与客观实际相符思维要与客观实际相符 - - 要求遵循形式逻辑的规律和规则要求遵循形式逻辑的规律和规则 - - 思维要具有创新性思维要具有创新性 科学研究的方法：科学研究的方法： - - 理论研究理论研究 - - 实验研究实验研究 - - 计算研究计算研究理论科学、实验科学和计算科学是推动人类文明进步和科技发理论科学、实验科学和计算科学是推动
5、人类文明进步和科技发展的主要途径。展的主要途径。2 2）科学思维的分类）科学思维的分类对应的三大科学研究的思维是理论思维、实验思维和计算思维。对应的三大科学研究的思维是理论思维、实验思维和计算思维。理论思维理论思维： 又称推理思维，以推理和演绎为特征，以数学学科为代表。又称推理思维，以推理和演绎为特征，以数学学科为代表。实验思维实验思维： 又称实证思维，以观察和总结自然规律为特征，以物理学科又称实证思维，以观察和总结自然规律为特征，以物理学科为代表。为代表。计算思维计算思维： 又称构造思维，以设计和构造为特征，以计算机学科为代表。又称构造思维，以设计和构造为特征，以计算机学科为代表。 计算思维
6、就是思维过程或功能的计算模拟方法论，其研究的目的是提供计算思维就是思维过程或功能的计算模拟方法论，其研究的目的是提供适当的方法，使人们借助现代和将来的计算机，逐步实现人工智能的较高适当的方法，使人们借助现代和将来的计算机，逐步实现人工智能的较高目标。诸如：模式识别、决策、优化和自控等算法都属于计算思维的范畴。目标。诸如：模式识别、决策、优化和自控等算法都属于计算思维的范畴。 三大思维都是人类科学思维方式中固有的部分。其中，三大思维都是人类科学思维方式中固有的部分。其中，理论思维强调理论思维强调推理，实验思维强调归纳，计算思维希望能自动求解推理，实验思维强调归纳，计算思维希望能自动求解。他们以不
7、同的方式。他们以不同的方式推动着科学的发展和人类文明的进步。推动着科学的发展和人类文明的进步。几千年前：几千年前： 科学是以观察或实验为依据的，经验的描述科学是以观察或实验为依据的，经验的描述自然现象自然现象近几百年：近几百年： 派生出理论的派生出理论的 使用模型进行一般化推理使用模型进行一般化推理近几十年：近几十年： 派生出计算的派生出计算的 用计算机辅助分析复杂现象用计算机辅助分析复杂现象 采集数据采集数据软件处理软件处理结果分析和统计结果分析和统计8理论科学理论科学测试理论提出理论解释结果制作模型提出模型建模过程提出实验数据分析驱动装置大型计算模型验证数据生产解释结果生产模型精确计算验证
8、理论生产数据提出理论3）理论科学、实验科学和计算科学的研究关系）理论科学、实验科学和计算科学的研究关系p计算科学与计算学科计算科学与计算学科计算科学计算科学计算科学（计算科学（Computing ScienceComputing Science）是应用高性能计算能）是应用高性能计算能力预测和了解客观世界物质运动或复杂现象演化规律的力预测和了解客观世界物质运动或复杂现象演化规律的科学，它包括数值模拟、过程仿真、高效计算机系统和科学，它包括数值模拟、过程仿真、高效计算机系统和应用软件等。应用软件等。- -计算学科计算学科计算学科（计算学科（Computing DisciplineComputing
9、 Discipline）是对描述和变化信）是对描述和变化信息的算法过程进行系统的研究，它包括算法过程理论、息的算法过程进行系统的研究，它包括算法过程理论、分析、设计、效率分析、实现和应用等。计算学科的根分析、设计、效率分析、实现和应用等。计算学科的根本问题是本问题是“什么能被（有效地）自动进行什么能被（有效地）自动进行”。 人要成功融入社会所必备的思维能力，是由其人要成功融入社会所必备的思维能力，是由其解决问题时所能获得工具或过程决定的解决问题时所能获得工具或过程决定的工业社会工业社会 了解物理特性，思考如何用原料生成新事物了解物理特性，思考如何用原料生成新事物 组装线组装线 自动化自动化 草
10、图草图 制造制造 工艺美术工艺美术11计算思维简介信息社会信息社会 为了问题求解，如何利用技术定位和使用信息为了问题求解，如何利用技术定位和使用信息 电信、电信、EmailEmail、信息空间、信息空间 网络、网络、LANLAN、ModemModem、blogblog WYSIWYG(WYSIWYG(What You See Is What You Get )、文件、图标、文件、图标、光标光标 芯片、芯片、RFID(RFID(射频识别)、USBUSB12超越信息社会超越信息社会 利用数据和构想解决问题利用数据和构想解决问题 超越使用工具和信息，进而创造工具和信息超越使用工具和信息，进而创造工具
11、和信息 需要抽象、数据处理等技能，和大量计算机科学概念的支需要抽象、数据处理等技能，和大量计算机科学概念的支持持 这就是这就是“计算思维计算思维” 人类思维与计算机能力的综合人类思维与计算机能力的综合 在在2121世纪，将是每个人所必备的基本技能世纪，将是每个人所必备的基本技能 读、写、算术读、写、算术13计算思维举例计算思维举例 在排好序的花名册中查找某在排好序的花名册中查找某个人个人线性搜索、二分查找线性搜索、二分查找 在银行窗口、超市排队在银行窗口、超市排队任务调度的性能分析任务调度的性能分析 将小孩一天要上的课的课本将小孩一天要上的课的课本放入书包放入书包预取与缓冲预取与缓冲 送小孩去
12、参加各种兴趣班送小孩去参加各种兴趣班货郎担问题货郎担问题( (旅行商问题）旅行商问题）14准备晚餐并行处理清理衣柜替换留下需要的、丢掉不用并且占地方的帮小孩收纳玩具Hash按类型分别收纳、按形状、按材质各种算术运算方法 1. 1. 计算思维概念的引入计算思维概念的引入 20062006年年美国国家科学基金会（美国国家科学基金会（NSFNSF）组织了计算教育与科）组织了计算教育与科学领域以及其他相关领域的专家，对学领域以及其他相关领域的专家，对“大学第一年计算机课大学第一年计算机课程的构建程的构建”、“多学科的融合多学科的融合”等问题进行研讨等问题进行研讨。 NSF NSF先后启动了旨在振兴美国
13、计算教育的四项国家计先后启动了旨在振兴美国计算教育的四项国家计划：划： - BPC- BPC（扩大计算参与面）（扩大计算参与面） - CPATH- CPATH（大学计算教育振兴途径）（大学计算教育振兴途径） - CDI- CDI（计算使能的科学发现和技术创新）（计算使能的科学发现和技术创新） - CE21- CE21（21 21 世纪计算科学教育）世纪计算科学教育） 目的是提高目的是提高K-14K-14（中小学和大学一、二年级）老师与学（中小学和大学一、二年级）老师与学生的计算思维能力生的计算思维能力。 计算思维概念的定义计算思维概念的定义 周以真定义：周以真定义：计算思维计算思维（Compu
14、tational ThinkingComputational Thinking，CTCT）是）是运用计算机科学的基础概念进行运用计算机科学的基础概念进行问题求解问题求解、系系统设计统设计、和、和理解人类行为理解人类行为等涵盖计算机科学广等涵盖计算机科学广度的一系列思维活动。度的一系列思维活动。目的是培养学生像拥有阅读、写作和算术（目的是培养学生像拥有阅读、写作和算术（3R3R）基本技能一样拥有计算思维技能，并能自觉地基本技能一样拥有计算思维技能，并能自觉地应用于日常的学习、研究与将来的工作中，应用于日常的学习、研究与将来的工作中，要要像计算机科学家那样思考问题。像计算机科学家那样思考问题。周以
15、真：原美国卡内基梅隆大学教授，2013年任微软全球资深副总裁、负责微软研究院全球各核心研究机构及学术合作部 。2006年对计算思维进行了清晰、系统的阐述，使计算思维的概念得到人们的极大关注。2. 2. 计算思维定义计算思维定义2022-5-2417 2011 2011年，国际教育技术协会年，国际教育技术协会(ISTE) (ISTE) 和计算机科学教师协会和计算机科学教师协会(CSTA) (CSTA) 给计算思维下了一个操作性的定义给计算思维下了一个操作性的定义： 计算思维是一个问题解决的过程，该过程包括：计算思维是一个问题解决的过程，该过程包括：制定问题，并能够利用计算机和其他工具来帮助解决该
16、问题；制定问题，并能够利用计算机和其他工具来帮助解决该问题；符合逻辑地组织和分析数据；符合逻辑地组织和分析数据；通过抽象（如模型、仿真等）再现数据；通过抽象（如模型、仿真等）再现数据；通过算法（一系列有序的步骤）支持自动化的解决方案；通过算法（一系列有序的步骤）支持自动化的解决方案；识别、分析和实施可能的解决方案，并整合这些最有效的方识别、分析和实施可能的解决方案，并整合这些最有效的方案和资源；案和资源；将该问题的求解过程进行推广并移植到更广泛的应用中。将该问题的求解过程进行推广并移植到更广泛的应用中。2. 2. 计算思维定义计算思维定义J.M. Wing, “Computational Th
17、inking,” CACMViewpoint, March 2006, pp. 33-35.Paper off http:/www.cs.cmu.edu/wing/ P.J.Denning观点ACM前主席DenningDenning认为：计算原理可以总结为认为：计算原理可以总结为7 7类。类。计算计算-Computation-Computation 通信通信-Communication-Communication 协作协作-Coordination-Coordination 记忆记忆-Recollection-Recollection 自动化自动化-Automation-Automation
18、评估评估-Evaluation-Evaluation设计设计-Design-Design7类原理：类原理：计算机理的功能角度计算机理的功能角度Computation： meaning and limits of computationCommunication：reliable data transmissionCoordination：cooperation among networked entitiesRecollection：storage and retrieval of informationAutomation：meaning and limits of automationEv
19、aluation：performance prediction and capacity planningDesign：building reliable software systems4类核心实践类核心实践ProgrammingSystems and systems thinkingModeling, validating, testing, and measuringInnovatingP.J.Denning观点例例1 1 计算函数计算函数f(x)f(x)区间区间 a,ba,b 上的积分。上的积分。在高等数学中，计算积分是使用牛顿在高等数学中，计算积分是使用牛顿莱布尼兹公式，莱布尼兹公式
20、，即首先求即首先求f(x)f(x)的原函数的原函数F(x),F(x),然后计算然后计算F(x) F(x) ，解决，解决这个问题不用黎曼积分的原因是计算量太大。这个问题不用黎曼积分的原因是计算量太大。在计算机中，计算积分的方法是使用黎曼积分，即在计算机中，计算积分的方法是使用黎曼积分，即对区间对区间 a,ba,b 进行进行n n等分，然后计算各小矩形的面积。等分，然后计算各小矩形的面积。这里不用牛顿这里不用牛顿莱布尼兹公式的原因有两个：一是不莱布尼兹公式的原因有两个：一是不同的同的f(x)f(x)求原函数的方法是不同的；二是并不是所有求原函数的方法是不同的；二是并不是所有的的f(x)f(x)都能
21、找到原函数都能找到原函数F(x).F(x).ab例例2 2：计算函数：计算函数n n的阶乘的阶乘f(n)=n!f(n)=n!在计算机中，采用两种方法：在计算机中，采用两种方法：1 1）递归法：将计算）递归法：将计算f(n)f(n)的问题分解为计算一个较的问题分解为计算一个较小的问题小的问题f(n-1),f(n-1),再将计算再将计算f(n-1)f(n-1)的问题分解为的问题分解为计算一个更小的问题计算一个更小的问题f(n-2)f(n-2)，直至分解到，直至分解到f(1)=1f(1)=1为止，然后从为止，然后从f(1)f(1)逐步计算到逐步计算到f(n)f(n)。 递推递推回代回代2 2）迭代法
22、：）迭代法： f(1)=1f(1)=1，根据，根据f(1)f(1)计算计算f(2)f(2)最后最后根据根据f(n-1)f(n-1)计算计算f(n)f(n)。（1 1）问题）问题 只有一个服务窗口，有三个服务顾客，分别需要服务时间为：只有一个服务窗口，有三个服务顾客，分别需要服务时间为： C1: 12 minC1: 12 min； C2 : 5 min C2 : 5 min ； C3: 3 minC3: 3 min（2 2）引发思考）引发思考如何评价不同方案如何评价不同方案不同情况服务顺序如何决定？不同情况服务顺序如何决定？到达时间不同、有不同的服务优先级、服务允许被中断到达时间不同、有不同的服
23、务优先级、服务允许被中断（3 3）“讨论讨论”出服务排队的核心方法出服务排队的核心方法先来先服务（先来先服务（FCFS)FCFS)短任务优先（短任务优先（SJF)SJF)最短剩余时间优先（最短剩余时间优先（SRTF)SRTF)优先级调度（优先级调度（HPF)HPF)时间片轮转（时间片轮转（RR)RR)在日常生活中，当小学生早晨去上学时，他把当天所需要在日常生活中，当小学生早晨去上学时，他把当天所需要的东西放进书包，这就是的东西放进书包，这就是“预置预置”；当有人丢了东西，你建议他沿着走过的路线去寻找，这就当有人丢了东西，你建议他沿着走过的路线去寻找，这就叫叫“回退回退”；你永远不知道下一步会怎
24、样，只能根据过去经验和当前情你永远不知道下一步会怎样，只能根据过去经验和当前情况来决定现在的行为。人生就是况来决定现在的行为。人生就是“在线算法在线算法”；在超市付费时，应当去排哪一个队呢？这就是在超市付费时，应当去排哪一个队呢？这就是“多服务器多服务器系统系统”；为什么停电时电话仍然可以使用呢？这就是为什么停电时电话仍然可以使用呢？这就是“失败的无关失败的无关性性”和和”设计的冗余性设计的冗余性“。“晴带雨伞晴带雨伞“，”饱带饥粮饱带饥粮”，就是一种，就是一种“预立预立”。计算思维的本质：计算思维的本质：抽象抽象（AbstractionAbstraction）和）和自动化自动化（Automa
25、tionAutomation）。）。 计算思维的本质反映了计算的根本问题，即什么能被有计算思维的本质反映了计算的根本问题，即什么能被有效地自动进行。计算是抽象地自动进行，自动化需要某种计效地自动进行。计算是抽象地自动进行，自动化需要某种计算机去解释现象。从操作层面上讲，计算就是如何寻找一台算机去解释现象。从操作层面上讲，计算就是如何寻找一台计算机去求解问题，选择合适的抽象，选择合适的计算机去计算机去求解问题，选择合适的抽象，选择合适的计算机去解释执行抽象，后者就是自动化。解释执行抽象，后者就是自动化。 计算思维中的抽象完全超越物理的时空观，并完全用符计算思维中的抽象完全超越物理的时空观，并完全
26、用符号来表示。其中，数字抽象只是一类特例。自动化就是机械号来表示。其中，数字抽象只是一类特例。自动化就是机械地一步一步自动执行，其基础和前提是抽象。地一步一步自动执行，其基础和前提是抽象。 案例：案例：1818世纪著名古典数学问题世纪著名古典数学问题哥尼斯堡七桥问题。哥尼斯堡七桥问题。3. 3. 计算思维的本质计算思维的本质26哥尼斯堡城地处东普鲁士，位于普雷格尔河的两岸及河中心的两个哥尼斯堡城地处东普鲁士，位于普雷格尔河的两岸及河中心的两个岛上，城市各部分由七座桥与两岸连结起来。多年来，当地的居民岛上，城市各部分由七座桥与两岸连结起来。多年来，当地的居民总有一个愿望：从家里出去散步，能否通过
27、每座桥恰好一次，再返总有一个愿望：从家里出去散步，能否通过每座桥恰好一次，再返回家中？但是任何人也没有找到这样一条理想的路径。回家中？但是任何人也没有找到这样一条理想的路径。抽象案例：18世纪著名古典数学问题哥尼斯堡七桥问题。274. 4. 计算思维的特征计算思维的特征（1 1）计算机思维是人类求解问题的一条途径，是属于人的思）计算机思维是人类求解问题的一条途径，是属于人的思维方式，不是计算机的思维方式。维方式，不是计算机的思维方式。 计算机之所以能够求解问题，是因为人将计算思维的计算机之所以能够求解问题，是因为人将计算思维的思想赋予了计算机，计算机才能够进行如迭代、递归等计思想赋予了计算机，
28、计算机才能够进行如迭代、递归等计算。算。（2 2）计算思维的过程可以由人执行，也可以由计算机执行。）计算思维的过程可以由人执行，也可以由计算机执行。 这些计算人和计算机都可以做，只不过人的速度慢而这些计算人和计算机都可以做，只不过人的速度慢而已。借助于超算能力的计算机，人类就可以去解决那些在已。借助于超算能力的计算机，人类就可以去解决那些在计算时代之前不敢尝试的问题，实现只有想不到的，没有计算时代之前不敢尝试的问题，实现只有想不到的，没有做不到的境界。做不到的境界。（3 3）计算思维是思想，不是人造物。）计算思维是思想，不是人造物。 计算思维不是硬件，而是计算这一概念用于求解问题、计算思维不是
29、硬件，而是计算这一概念用于求解问题、管理日常生活以及与他人交流和互动的思想。管理日常生活以及与他人交流和互动的思想。（4 4）计算思维是概念化，不是程序化。）计算思维是概念化，不是程序化。 计算机科学并不仅仅是计算机编程，像计算机科学家计算机科学并不仅仅是计算机编程，像计算机科学家那样去思维意味着远不止能为计算机编程，还要求能够在那样去思维意味着远不止能为计算机编程，还要求能够在抽象的多个层次上思维抽象的多个层次上思维。1.计算思维的基本问题计算思维的基本问题 计算思维是研究计算的思维，研究计算思维的基本问题计算思维是研究计算的思维，研究计算思维的基本问题是要了解哪些问题是可计算的，哪些问题是
30、不可计算的，以是要了解哪些问题是可计算的，哪些问题是不可计算的，以及计算的复杂性如何度量。及计算的复杂性如何度量。 （1 1）可计算性）可计算性 一个问题是可计算的是指可以使用计算机在有限步骤内一个问题是可计算的是指可以使用计算机在有限步骤内完成计算。完成计算。 图灵论题给出可计算性的定义：一个问题是可计算的，图灵论题给出可计算性的定义：一个问题是可计算的，当且仅当它在图灵机上经过有限步骤之后可以得到正确的结当且仅当它在图灵机上经过有限步骤之后可以得到正确的结果。果。 （2 2）计算复杂性）计算复杂性 计算复杂性就是指用计算机求解问题的难易程度，通计算复杂性就是指用计算机求解问题的难易程度，通
31、常可用时间复杂度和空间复杂度来衡量。常可用时间复杂度和空间复杂度来衡量。 计算复杂性理论是用数学方法研究各类问题的计算复计算复杂性理论是用数学方法研究各类问题的计算复杂性学科。它研究各种可计算问题在计算过程中时间和空杂性学科。它研究各种可计算问题在计算过程中时间和空间的耗费情况，以及在不同计算模型下，使用不同类型的间的耗费情况，以及在不同计算模型下，使用不同类型的资源和不同数量的资源时，各类问题复杂性的本质特性和资源和不同数量的资源时，各类问题复杂性的本质特性和相互关系。相互关系。【问题描述】相传古印度的僧侣在进行一种被称为汉诺塔的游戏，如图所示。条件是： 每次只能移动一个盘； 每次移动都不允
32、许大盘移到小盘之上； B B塔作为辅助，中间过渡的塔。【分析分析】这个移动过程很复杂与烦琐，但规律性却很强。这个移动过程很复杂与烦琐，但规律性却很强。使用递归调用技术来解决这个移动过程，先得找到使用递归调用技术来解决这个移动过程，先得找到一个递归调用模型。一个递归调用模型。想要得到汉诺塔问题的简单解法，着眼点应该是移想要得到汉诺塔问题的简单解法，着眼点应该是移动动A A塔最底部的大盘，而不是其顶部的小盘。塔最底部的大盘，而不是其顶部的小盘。考虑考虑N N个盘的一般情况。个盘的一般情况。初始状态初始状态N-1N-1N N第一步：第一步：A塔上的塔上的N-1盘移至盘移至B塔塔汉诺塔的分解操作：汉诺
33、塔的分解操作：N-1N-1N N第二步：第二步：A塔上的塔上的N盘移至盘移至C塔塔汉诺塔的分解操作：汉诺塔的分解操作：N-1N-1N N第三步：第三步：B塔上的塔上的N-1盘移至盘移至C塔塔汉诺塔的分解操作：汉诺塔的分解操作：N-1N-1N N我们看到，步骤我们看到，步骤2 2只需移动一次就可以完成；步骤只需移动一次就可以完成；步骤1 1与与3 3的的操作则完全相同，操作则完全相同， 唯一区别仅在于各塔的作用有所不同。唯一区别仅在于各塔的作用有所不同。这样，原问题被转换为与原问题相同性质的、规模小一些这样，原问题被转换为与原问题相同性质的、规模小一些的新问题。的新问题。即：即：HANOI(N,
34、A,B,C)HANOI(N,A,B,C) 可转化为可转化为 HANOI(N-1,A,C,B)HANOI(N-1,A,C,B)与与 HANOI(N-1,B,A,C)HANOI(N-1,B,A,C)其中其中HANOIHANOI中的参数分别表示需移动的盘数、起始塔、临中的参数分别表示需移动的盘数、起始塔、临时塔与终止塔，时塔与终止塔， 这种转换直至转入的盘数为这种转换直至转入的盘数为0 0为止，因为为止，因为这时已无盘可移了，这就是需要找的递归调用模型。这时已无盘可移了，这就是需要找的递归调用模型。可以采用递归的方法，进行求解。可以采用递归的方法，进行求解。问题：当问题：当n=64 n=64 时，即
35、有移动时，即有移动6464个盘子时，需要移动多少个盘子时，需要移动多少次盘子？耗费多少时间呢？次盘子？耗费多少时间呢？h(n)=2h(n)=2h(n-1)+1h(n-1)+1 =2 =2 22h(n-2)+1+1h(n-2)+1+1 = 2 = 22 2 h(n-2)+1+2+1h(n-2)+1+2+1 =2 =2n n h(0)+ 2h(0)+ 2n-1n-1+ 2+ 22+2+2+12+1 = 2 = 2n-1n-1+ 2+ 22+2+2+12+1 = 2 = 2n n-1 =2-1 =26464-1=18 446 744 073 709 551 615-1=18 446 744 073
36、709 551 615假定移动一个盘子假定移动一个盘子1 1秒，僧侣要花费秒，僧侣要花费58495849亿年的时间。亿年的时间。假定计算机每秒可移动假定计算机每秒可移动10001000万个盘子，也需要花费约万个盘子，也需要花费约58 58 490490年的时间。年的时间。理论上可以计算的问题，实际上并不一定能行。分类分类关注点关注点核心概念核心概念计算计算可计算性和计算复杂性可计算性和计算复杂性计算模型、可计算性、计算复杂性计算模型、可计算性、计算复杂性抽象抽象关注对象的本质特征关注对象的本质特征抽象、抽象层次、概念模型、实现模型抽象、抽象层次、概念模型、实现模型自动化自动化信息处理的算法设计
37、信息处理的算法设计算法、程序，迭代、递归，启发式策略、随机策略算法、程序，迭代、递归，启发式策略、随机策略，智能，智能设计设计可靠和可信系统的构建可靠和可信系统的构建分解、复合、折中，可靠性、安全性、重用性分解、复合、折中，可靠性、安全性、重用性评估评估复杂系统的性能评价复杂系统的性能评价评价指标与基准、瓶颈、冗余、容错、性能仿真评价指标与基准、瓶颈、冗余、容错、性能仿真通信通信不同过程和对象间的可靠不同过程和对象间的可靠信息传递信息传递信息及其表示、信息量（熵）、编码与解码、信息信息及其表示、信息量（熵）、编码与解码、信息压缩、信息加密、校验与纠错、协议压缩、信息加密、校验与纠错、协议协作协
38、作多个自主计算实体间的有多个自主计算实体间的有效配合和时序控制效配合和时序控制同步、并发、并行、事件、服务同步、并发、并行、事件、服务记忆记忆信息的表示、存储和检索信息的表示、存储和检索数据类型、数据结构、数据组织、检索与索引、局数据类型、数据结构、数据组织、检索与索引、局部性与缓存部性与缓存1. 1. 生物学生物学 计算生物学是指开发和应用数据分析及理论的方法、数学建模、计算机仿真技术等。用于生物学、行为学、和社会群体系统研究的一门学科。 由于生物学数据量和复杂性不断增长，每14个月基因研究产生的数据就会翻一番，仅依靠观察和实验已难以应付。必须依靠大规模计算技术，从海量信息中提取有用的数据。
39、 有生物序列的片段拼接、序列对接、基因识别、蛋白质结构预测、生物数据库等。2. 2. 脑科学脑科学- 模拟大脑像计算机脑科学是研究人脑结构与功能的综合脑科学是研究人脑结构与功能的综合性学科，以揭示人脑高级意识功能为性学科，以揭示人脑高级意识功能为宗旨，与教育学、心理学、人工智能、宗旨，与教育学、心理学、人工智能、认知学科以及创造学等学科有紧密联认知学科以及创造学等学科有紧密联系和交叉渗透。系和交叉渗透。- 通过机器学习分析脑成像通过分析脑成像技术（通过分析脑成像技术（fMRI） ，对，对大脑的研究便可扩展至记忆、注意力、大脑的研究便可扩展至记忆、注意力、决定等。在某些情况下，脑成像技术决定等。
40、在某些情况下，脑成像技术甚至能够识别研究对象所见到的图像甚至能够识别研究对象所见到的图像或者阅读的词语。或者阅读的词语。- - 从患者身上提取皮从患者身上提取皮肤细胞，转成干细胞，肤细胞，转成干细胞，再将干细胞分裂成所再将干细胞分裂成所需要的神经元，最后需要的神经元，最后得到大脑细胞，首次得到大脑细胞，首次在细胞水平上观察精在细胞水平上观察精神分裂患者的脑细胞。神分裂患者的脑细胞。3. 3. 计算化学计算化学 计算化学是根据基本的物理化学理论，以大量数值运算计算化学是根据基本的物理化学理论，以大量数值运算方式来探讨化学系统的性质。方式来探讨化学系统的性质。 主要以分子模拟为工具实现各种核心化学
41、的计算问题，主要以分子模拟为工具实现各种核心化学的计算问题，架起了理论化学与实验化学之间的桥梁。主要有如下研究架起了理论化学与实验化学之间的桥梁。主要有如下研究方向：方向： 1 1）化学中的数值计算）化学中的数值计算 2 2）化学模拟）化学模拟 3 3）化学中的模式识别）化学中的模式识别 4 4）化学数据库及检索）化学数据库及检索 5 5）化学专家系统）化学专家系统4. 4. 数学数学-发现了发现了E8E8李群李群(Lie group E8)(Lie group E8)这是这是18名世界顶级数学家凭借他们不名世界顶级数学家凭借他们不懈的努力，借助超级计算机，经过懈的努力，借助超级计算机，经过4
42、年年零零77小时，处理了小时，处理了2亿个数据，完成亿个数据，完成了世界上最复杂的数学结构之一了世界上最复杂的数学结构之一“E8”的计算过程。如果在纸上列出整个计的计算过程。如果在纸上列出整个计算过程所产生的数据，其所需用纸面算过程所产生的数据，其所需用纸面积可以覆盖整个曼哈顿积可以覆盖整个曼哈顿 。- - 借助计算机辅助证明了四色定理借助计算机辅助证明了四色定理5. 计算经济学计算经济学- 零和博弈零和博弈 博弈论研究的不是真正的游戏，而是与游戏有着共同本质特征的决策博弈论研究的不是真正的游戏，而是与游戏有着共同本质特征的决策或策略问题。或策略问题。 零和博弈又称又称“零和游戏零和游戏”，是
43、，是博弈论的一个概念，属的一个概念，属非合作博弈，指参与博弈的各方，指参与博弈的各方， 一方的收益必然意味着另一方的损失，博弈各方一方的收益必然意味着另一方的损失，博弈各方的收益和损失相加总和永远为的收益和损失相加总和永远为“零零”。如：赌博、期货等。如：赌博、期货等。 - 囚徒困境囚徒困境 是博弈论的专家设计的典型示例，其模型可以用来描述两个企业的价是博弈论的专家设计的典型示例，其模型可以用来描述两个企业的价格大战等许多经济现象。格大战等许多经济现象。- 双赢对局双赢对局 双方都采取高价策略的对局形式，双方都采取高价策略的对局形式，- 自动设计机制在电子商务中应用（广告投放、在线拍卖等）自动
44、设计机制在电子商务中应用（广告投放、在线拍卖等）6. 6. 工程（电子、海洋、材料、航空航天等）工程（电子、海洋、材料、航空航天等）-计算高阶项可以提高精度，进而降低重量，减少浪费并节约制造成本-波音777飞机完全通过计算机进行模拟测试，而没有经过风洞测试- 混合自动机对网络物理系统的建模分析- 航空航天工程中，用成像技术检测带回来的月球样本，更好的了解月球7. 新闻新闻- 人群采购作为一种新的方式得到消息提示- 为了验证消息来源的可信度计算方法8.机器学习信用卡超市运动娱乐：购物，音乐，旅行 本章主要介绍了计算思维的基本概念、计算思维本章主要介绍了计算思维的基本概念、计算思维的本质与应用领域。的本质与应用领域。 通过本章的学习，能够帮助学生认识和了解计算通过本章的学习，能够帮助学生认识和了解计算思维在学习中的重要性，建立自觉、主动学习提高计思维在学习中的重要性，建立自觉、主动学习提高计算思维能力的意识和兴趣。算思维能力的意识和兴趣。搜索有关计算思维的文章 - -周以真: Computational ThinkingComputational Thinking - Denning:伟大的计算原理搜集1-2个你所遇到有关计算思维案例 你是如何解决的？你准备如何解决？
