计算思维概述.ppt
计算思维与计算机文化,第一章 计算思维基础知识,第一章 计算思维基础知识,主要内容1.1 科学与科学思维1.2 计算思维的概念1.3 计算思维的核心概念和方法1.4 计算思维的应用领域,思维本身让人沉醉计算思维除了给计算机技术带来变革，它还让人们在探索的过程中体验和谐、对称、完备、简洁等美学属性。科学的美不逊于艺术的美。,1.1 科学与科学思维,科学的概念,达尔文,“科学就是整理事实，从中发现规律，作出结论。”,科学是运用范畴、定理和定律等思维形式反映现实世界中各种现象的本质和运动规律的知识体系。,“science”来源于拉丁文”scientia”,意为“知识与学问”。,1.1 科学与科学思维,2.科学的分类广义科学 自然科学：以自然界为主要研究对象，运用实证、理性和臻美等方法，解释自然的奥秘。人文科学：以人类为主要研究对象，运用实地考察、诠释和启示等方法，认识人、人性和人生的意义，提升人的精神素质和思想境界。社会科学：以社会领域为主要研究对象，运用调查、统计和归纳等方法，把握社会规律，解决社会问题，促进社会进步。狭义科学 自然科学（有时也指基础理论科学）,科学思维及其分类1）科学思维科学思维（Scientific Thinking)是指经过感性阶段获取的大量材料通过整理和改造，形成概念、判断和推理，以便反映事物的本质和规律。科学思维是大脑对科学信息的加工活动。科学思维涵盖内容：-思维要与客观实际相符-要求遵循形式逻辑的规律和规则-思维要具有创新性 科学研究的方法：-理论研究-实验研究-计算研究理论科学、实验科学和计算科学是推动人类文明进步和科技发展的主要途径。,1.1 科学与科学思维,2）科学思维的分类对应的三大科学研究的思维是理论思维、实验思维和计算思维。理论思维：又称推理思维，以推理和演绎为特征，以数学学科为代表。实验思维：又称实证思维，以观察和总结自然规律为特征，以物理学科为代表。计算思维：又称构造思维，以设计和构造为特征，以计算机学科为代表。计算思维就是思维过程或功能的计算模拟方法论，其研究的目的是提供适当的方法，使人们借助现代和将来的计算机，逐步实现人工智能的较高目标。诸如：模式识别、决策、优化和自控等算法都属于计算思维的范畴。三大思维都是人类科学思维方式中固有的部分。其中，理论思维强调推理，实验思维强调归纳，计算思维希望能自动求解。他们以不同的方式推动着科学的发展和人类文明的进步。,1.1 科学与科学思维,测试理论,提出理论,解释结果,制作模型,提出模型,建模过程,提出实验,数据分析,驱动装置,大型计算,模型验证,数据生产,解释结果,生产模型,精确计算,验证理论,生产数据,提出理论,3）理论科学、实验科学和计算科学的研究关系,马克思：一门学科，只有运用了数学才算是成熟了的学科。,H.Davy：没有什么比应用新工具更有助于知识的发现。在不同的时期，人们的业绩不同，与其说是他们天赋智能所致，倒不如说是他们所拥有的工具和软资源不同所致。戴维（SirHumphry Davy 17781829），英国化学家,名 人 名 言,我们认为：一门学科一旦运用了计算科学，它就成为了先进的学科。有研究报告显示：计算很可能是人类的一种本能。,1.1 科学与科学思维,1.2 计算思维的概念,1.2 计算思维的概念,1.计算思维概念的引入 周以真定义：计算思维（Computational Thinking，CT）是运用计算机科学的基础概念进行问题求解、系统设计、和理解人类行为等涵盖计算机科学广度的一系列思维活动。目的是培养学生像拥有阅读、写作和算术（3R）基本技能一样拥有计算思维技能，并能自觉地应用于日常的学习、研究与将来的工作中，要像计算机科学家那样思考问题。,周以真：原美国卡内基梅隆大学教授，2013年任微软全球资深副总裁、负责微软研究院全球各核心研究机构及学术合作部。2006年对计算思维进行了清晰、系统的阐述，使计算思维的概念得到人们的极大关注。,J.M.Wing,“Computational Thinking,”CACMViewpoint,March 2006,pp.33-35.Paper off http:/wing/,观点ACM前主席,Denning认为：计算原理可以总结为7类。计算-Computation 通信-Communication 协作-Coordination 记忆-Recollection 自动化-Automation 评估-Evaluation设计-Design,7类原理：计算机理的功能角度Computation：meaning and limits of computationCommunication：reliable data transmissionCoordination：cooperation among networked entitiesRecollection：storage and retrieval of informationAutomation：meaning and limits of automationEvaluation：performance prediction and capacity planningDesign：building reliable software systems,4类核心实践ProgrammingSystems and systems thinkingModeling,validating,testing,and measuringInnovating,观点,计算思维示例,例1 计算函数f(x)区间a,b上的积分。在高等数学中，计算积分是使用牛顿莱布尼兹公式，即首先求f(x)的原函数F(x),然后计算F(x)解决这个问题不用黎曼积分的原因是计算量太大。在计算机中，计算积分的方法是使用黎曼积分，即对区间a,b进行n等分，然后计算各小矩形的面积。不用牛顿莱布尼兹公式的原因有两个：一是不同的f(x)求原函数的方法是不同的；二是并不是所有的f(x)都能找到原函数F(x).,a,b,例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:12；C2:5；C3:3（2）引发思考：如何评价不同方案不同情况服务顺序如何决定？到达时间不同、有不同的服务优先级、服务允许被中断（3）“讨论”出服务排队的核心方法：先来先服务（FCFS)短任务优先（SJF)最短剩余时间优先（SRTF)优先级调度（HPF)时间片轮转（RR),例4 装箱问题模拟,问题：用尽可能少的箱子装下若干物体#include main()int i,j,Cur,N,Max=0;static int S1001;scanf(%d,案例.,信息表示与编码（Communication）猜姓游戏、图像编码、图像校验资源竞争与调度（Coordination、Evaluation）服务窗口排队问题、装箱问题、书籍缓存问题社会关系与网络（Automation）朋友圈形成、团体发现问题分解与递归（Design）二分查找猜数、最大和子序列、海盗分赃,计算思维在美国产生的背景,1).针对“计算学科与日俱增的重要性与学生对计算学科兴趣的下降”，美国NSF组织了计算教育与科学领域，以及其他相关领域的专家分四个大区（东北、中西、东南、西北）进行研讨，形式四份重要报告：Report of NSF Workshop on Integrative Computing Education and Research(ICER)Northeast WorkshopReport of NSF Midwest Region Workshop on ICER:Preparing IT Graduates for 2010 and BeyondReport from the Southeast Region Workshop on ICER:Preparing IT Graduates for 2010 and BeyondICER Final Report of the Northwest Regional Meeting 内容及建议以上四个文件分析了美国计算教育出现的问题，报告建议在美国国家科学基金的资助下全面改革美国的计算教育。以下两个问题和一个建议值得我们注意：大学第一年计算机课程的构建问题；多学科的融合问题；报告建议加强美国中小学学生抽象思维与写作能力的训练，目的，使学生平稳过渡到大学的学习。,21,计算思维在美国产生的背景,2).2007年美国NSF的CPATH计划CPATH（Pathways to Revitalized Undergraduate Computing Education，大学计算教育重生的途径）计划认为：计算普遍存在于我们的日常生活之中，培养未来能够参与全球竞争、掌握计算核心概念的美国企业家和员工就变得非常重要。CPATH计划认为：尽管有的研究机构和大学对此做出了卓越的、开创性的工作，但目前美国更多的大学计算教育仍然沿袭的是几十年前的教学模式。鉴于此，NSF 2007年启动了CPATH计划，当年投入600万美元，2008年投入500万美元，2009年投入1000万美元，力图改变这种情况。3).2008年美国NSF的CDI计划CDI（Cyber-Enabled Discovery and Innovation，计算使能的科学发现和技术创新）是美国国家科学基金会的一个革命性的、富有独创精神的五年计划，该计划旨在通过“计算思维”领域的创新和进步来促进自然科学和工程技术领域产生革命性的成果。CDI计划2008年启动，当年批准了共计4200万美元的72个项目的立项申请，2009年投入2600万美元，2010年投入3600万美元。,2010年，成立了九校联盟，发表了C9联盟声明召开各种规模的、各种形式的论坛、报告会院士、专家挂帅进行研讨，请来了周以真做报告2012年教育部设立了以计算思维为切入点的“大学计算机课程改革项目”2013.7第二届计算思维与大学计算机课程教学改革研讨会 哈尔滨会议，教育部高等学校大学计算机课程教学指导委员会发布“计算思维教学改革白皮书(征求意见稿)”白皮书的主要内容：一、科学思维以及逻辑思维、实证思维与计算思维的关系二、计算思维的表达体系三、大学计算机课程知识体系与核心概念的关系,国内计算思维的研究,计算思维的本质：抽象（Abstraction）和自动化（Automation）。计算思维的本质反映了计算的根本问题，即什么能被有效地自动进行。计算是抽象地自动进行，自动化需要某种计算机去解释现象。从操作层面上讲，计算就是如何寻找一台计算机去求解问题，选择合适的抽象，选择合适的计算机去解释执行抽象，后者就是自动化。计算思维中的抽象完全超越物理的时空观，并完全用符号来表示。其中，数字抽象只是一类特例。自动化就是机械地一步一步自动执行，其基础和前提是抽象。案例：18世纪著名古典数学问题哥尼斯堡七桥问题。,2.计算思维的本质,25,哥尼斯堡城地处东普鲁士，位于普雷格尔河的两岸及河中心的两个岛上，城市各部分由七座桥与两岸连结起来。多年来，当地的居民总有一个愿望：从家里出去散步，能否通过每座桥恰好一次，再返回家中？但是任何人也没有找到这样一条理想的路径。,哥尼斯堡,普莱格尔河,哥尼斯堡七桥问题,26,1736年，瑞士数学家欧拉(Euler)解决问题的方法是把陆地抽象为一个点，用连接两个点的线段表示桥梁，将该问题抽象成点与线的连接图的数学问题。实际问题的独特之处是把一个实际问题抽象成合适的“数学模型”。这就是计算思维中的抽象。,3.计算思维的特征（1）计算机思维是人类求解问题的一条途径，是属于人的思维方式，不是计算机的思维方式。计算机之所以能够求解问题，是因为人将计算思维的思想赋予了计算机，计算机才能够进行如迭代、递归等计算。（2）计算思维的过程可以由人执行，也可以由计算机执行。这些计算人和计算机都可以做，只不过人的速度慢而已。借助于超算能力的计算机，人类就可以去解决那些在计算时代之前不敢尝试的问题，实现只有想不到的，没有做不到的境界。,（3）计算思维是思想，不是人造物。计算思维不是硬件，而是计算这一概念用于求解问题、管理日常生活以及与他人交流和互动的思想。（4）计算思维是概念化，不是程序化。计算机科学并不仅仅是计算机编程，像计算机科学家那样去思维意味着远不止能为计算机编程，还要求能够在抽象的多个层次上思维。,计算思维的核心概念和方法约简、嵌入、转化、仿真用来把一个看来困难的问题重新阐释成一个人们知道问题怎样解决的思维方法。递归、并行把代码译成数据又能把数据译成代码的方法、多维分析推广的类型检查方法。抽象、分解用来控制庞杂的任务或进行巨大的复杂系统设计；基于关注分离的方法。建模选择合适的方式去陈述一个问题的方法、对一个问题的相关方面建模使其易于处理的思维方法。,1.3 计算思维的核心概念和方法,计算思维的核心概念和方法预防、保护、冗余、容错、纠错、恢复按照预防、保护及通过冗余、容错、纠错的方式，并从最坏情况进行系统恢复的一种思维方法。启发式推理、规划、学习、调度用于在不确定情况下的规划，学习和调度的思维方法。海量数据、计算、折中利用海量数据来加快计算，在实践和空间之间，在处理能力和存储容量之间进行折中的思维方法。,1.4 计算思维的应用领域,计算思维不仅渗透到每一个人的生活里，而且影响了其他学科的发展，创造和形成了一系列新的学科分支。,1.计算生物学 计算生物学是指开发和应用数据分析及理论的方法、数学建模、计算机仿真技术等。用于生物学、行为学、和社会群体系统研究的一门学科。由于生物学数据量和复杂性不断增长，每14个月基因研究产生的数据就会翻一番，仅依靠观察和实验已难以应付。必须依靠大规模计算技术，从海量信息中提取有用的数据。有生物序列的片段拼接、序列对接、基因识别、蛋白质结构预测、生物数据库等。,2.脑科学,-模拟大脑像计算机脑科学是研究人脑结构与功能的综合性学科，以揭示人脑高级意识功能为宗旨，与教育学、心理学、人工智能、认知学科以及创造学等学科有紧密联系和交叉渗透。-通过机器学习分析脑成像通过分析脑成像技术（fMRI），对大脑的研究便可扩展至记忆、注意力、决定等。在某些情况下，脑成像技术甚至能够识别研究对象所见到的图像或者阅读的词语。,3.计算化学 计算化学是根据基本的物理化学理论，以大量数值运算方式来探讨化学系统的性质。主要以分子模拟为工具实现各种核心化学的计算问题，架起了理论化学与实验化学之间的桥梁。主要有如下研究方向：1）化学中的数值计算 2）化学模拟 3）化学中的模式识别 4）化学数据库及检索 5）化学专家系统,4.数学,-一个由18位数学家组成的国际研究团队，成功绘制了数学上最庞大也最为复杂的结构之一李群E8(Lie group E8)。18名世界顶级数学家凭借他们不懈的努力，历时四年，完成了世界上最复杂的数学结构之一“E8”的计算过程。如果在纸上列出整个计算过程所产生的数据，其所需用纸面积可以覆盖整个曼哈顿。-四色定理的证明,5.计算经济学,零和博弈 博弈论研究的不是真正的游戏，而是与游戏有着共同本质特征的决策或策略问题。零和博弈又称“零和游戏”，是博弈论的一个概念，属非合作博弈，指参与博弈的各方，一方的收益必然意味着另一方的损失，博弈各方的收益和损失相加总和永远为“零”。如：赌博、期货等。囚徒困境 是博弈论的专家设计的典型示例，其模型可以用来描述两个企业的价格大战等许多经济现象。双赢对局 双方都采取高价策略的对局形式，,7.工程（电子、海洋、材料、航空等）,-高阶项计算意味着精度更高，这意味着在生产中减少浪费，降低成本和重量-波音777测试通过计算机模拟而不是在实际风洞进行-混合自动机对网络物理系统的建模分析,8.新闻,-人群采购作为一种新的方式得到消息提示-为了验证消息来源的可信度计算方法,9.机器学习,信用卡,超市,运动,娱乐：购物，音乐，旅行,本章小结,本章主要介绍了计算思维的基本概念、计算思维的本质与应用领域。通过本章的学习，能够帮助学生认识和了解计算思维在学习中的重要性，建立自觉、主动学习提高计算思维能力的意识和兴趣。,作 业,搜索有关计算思维的文章-周以真:Computational Thinking-Denning:伟大的计算原理搜集有关你所遇到计算思维案例 你是如何解决的？你准备如何解决？,
