1 计算思维概述

计算思维与计算机文化第一章计算思维基础知识第一章计算思维基础知识主要内容1.1科学与科学思维1.2计算思维的概念1.3计算思维的核心概念和方法1.4计算思维的应用领域思维本身让人沉醉……计算思维除了给计算机技术带来变革，它还让人们在探索的过程中体验和谐、对称、完备、简洁等美学属性。科学的美不逊于艺术的美。1.1科学与科学思维1.科学的概念达尔文“科学就是整理事实，从中发现规律，作出结论。”科学是运用范畴、定理和定律等思维形式反映现实世界中各种现象的本质和运动规律的知识体系。“science”来源于拉丁文”scientia”,意为“知识与学问”。词源1.1科学与科学思维2.科学的分类广义科学自然科学：以自然界为主要研究对象，运用实证、理性和臻美等方法，解释自然的奥秘。人文科学：以人类为主要研究对象，，运用实地考察、诠释和启示等方法，认识人、人性和人生的意义，提升人的精神素质和思想境界。社会科学：以社会领域为主要研究对象，运用调查、统计和归纳等方法，把握社会规律，解决社会问题，促进社会进步。狭义科学自然科学（有时也指基础理论科学）3.科学思维及其分类1）科学思维•科学思维（ScientificThinking)是指经过感性阶段获取的大量材料通过整理和改造，形成概念、判断和推理，以便反映事物的本质和规律。•科学思维是大脑对科学信息的加工活动。•科学思维涵盖内容：--思维要与客观实际相符--要求遵循形式逻辑的规律和规则--思维要具有创新性科学研究的方法：--理论研究--实验研究--计算研究理论科学、实验科学和计算科学是推动人类文明进步和科技发展的主要途径。1.1科学与科学思维2）科学思维的分类对应的三大科学研究的思维是理论思维、实验思维和计算思维。理论思维：又称推理思维，以推理和演绎为特征，以数学学科为代表。实验思维：又称实证思维，以观察和总结自然规律为特征，以物理学科为代表。计算思维：又称构造思维，以设计和构造为特征，以计算机学科为代表。计算思维就是思维过程或功能的计算模拟方法论，其研究的目的是提供适当的方法，使人们借助现代和将来的计算机，逐步实现人工智能的较高目标。诸如：模式识别、决策、优化和自控等算法都属于计算思维的范畴。三大思维都是人类科学思维方式中固有的部分。其中，理论思维强调推理，实验思维强调归纳，计算思维希望能自动求解。他们以不同的方式推动着科学的发展和人类文明的进步。1.1科学与科学思维计算科学理论科学实验科学测试理论提出理论解释结果制作模型提出模型建模过程提出实验数据分析驱动装置大型计算模型验证数据生产解释结果生产模型精确计算验证理论生产数据提出理论3）理论科学、实验科学和计算科学的研究关系马克思：一门学科，只有运用了数学才算是成熟了的学科。H.Davy：没有什么比应用新工具更有助于知识的发现。在不同的时期，人们的业绩不同，与其说是他们天赋智能所致，倒不如说是他们所拥有的工具和软资源不同所致。戴维（SirHumphryDavy1778～1829），英国化学家名人名言我们认为：一门学科一旦运用了计算科学，它就成为了先进的学科。有研究报告显示：计算很可能是人类的一种本能。1.1科学与科学思维1.2计算思维的概念1.2计算思维的概念1.计算思维概念的引入周以真定义：计算思维（ComputationalThinking，CT）是运用计算机科学的基础概念进行问题求解、系统设计、和理解人类行为等涵盖计算机科学广度的一系列思维活动。目的是培养学生像拥有阅读、写作和算术（3R）基本技能一样拥有计算思维技能，并能自觉地应用于日常的学习、研究与将来的工作中，要像计算机科学家那样思考问题。周以真：原美国卡内基·梅隆大学教授，2013年任微软全球资深副总裁、负责微软研究院全球各核心研究机构及学术合作部。2006年对计算思维进行了清晰、系统的阐述，使计算思维的概念得到人们的极大关注。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：meaningandlimitsofcomputation•Communication：reliabledatatransmission•Coordination：cooperationamongnetworkedentities•Recollection：storageandretrievalofinformation•Automation：meaningandlimitsofautomation•Evaluation：performancepredictionandcapacityplanning•Design：buildingreliablesoftwaresystems4类核心实践•Programming•Systemsandsystemsthinking•Modeling,validating,testing,andmeasuring•InnovatingP.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:12；C2:5；C3:3（2）引发思考：–如何评价不同方案–不同情况服务顺序如何决定？•到达时间不同、有不同的服务优先级、服务允许被中断（3）“讨论”出服务排队的核心方法：–先来先服务（FCFS)–短任务优先（SJF)–最短剩余时间优先（SRTF)–优先级调度（HPF)–时间片轮转（RR)例4装箱问题模拟问题：用尽可能少的箱子装下若干物体#includestdio.hmain(){inti,j,Cur,N,Max=0;staticintS[1001];scanf(%d,&N);for(i=1;i=N;i++){scanf(%d,&Cur);for(j=1;j=N;j++)if(S[j]+Cur=100)break;S[j]+=Cur;if(jMax)Max=j;printf(%d%d\n,Cur,j);}printf(%d\n,Max);}案例….•信息表示与编码（Communication）–猜姓游戏、图像编码、图像校验•资源竞争与调度（Coordination、Evaluation）–服务窗口排队问题、装箱问题、书籍缓存问题•社会关系与网络（Automation）–朋友圈形成、团体发现•问题分解与递归（Design）–二分查找猜数、最大和子序列、海盗分赃计算思维在美国产生的背景1).针对“计算学科与日俱增的重要性与学生对计算学科兴趣的下降”，美国NSF组织了计算教育与科学领域，以及其他相关领域的专家分四个大区（东北、中西、东南、西北）进行研讨，形式四份重要报告：①ReportofNSFWorkshoponIntegrativeComputingEducationandResearch(ICER)NortheastWorkshop②ReportofNSFMidwestRegionWorkshoponICER:PreparingITGraduatesfor2010andBeyond③ReportfromtheSoutheastRegionWorkshoponICER:PreparingITGraduatesfor2010andBeyond④ICERFinalReportoftheNorthwestRegionalMeeting•内容及建议以上四个文件分析了美国计算教育出现的问题，报告建议在美国国家科学基金的资助下全面改革美国的计算教育。以下两个问题和一个建议值得我们注意：①大学第一年计算机课程的构建问题；②多学科的融合问题；③报告建议加强美国中小学学生抽象思维与写作能力的训练，目的，使学生平稳过渡到大学的学习。21计算思维在美国产生的背景2).2007年美国NSF的CPATH计划•CPATH（PathwaystoRevitalizedUndergraduateComputingEducation，大学计算教育重生的途径）计划认为：计算普遍存在于我们的日常生活之中，培养未来能够参与全球竞争、掌握计算核心概念的美国企业家和员工就变得非常重要。•CPATH计划认为：尽管有的研究机构和大学对此做出了卓越的、开创性的工作，但目前美国更多的大学计算教育仍然沿袭的是几十年前的教学模式。鉴于此，NSF2007年启动了CPATH计划，当年投入600万美元，2008年投入500万美元，2009年投入1000万美元，力图改变这种情况。3).2008年美国NSF的CDI计划•CDI（Cyber-EnabledDiscoveryandInnovation，计算使能的科学发现和技术创新）是美国国家科学基金会的一个革命性的、富有独创精神的五年计划，该计划旨在通过“计算思维”领域的创新和进步来促进自然科学和工程技术领域产生革命性的成果。•CDI计划2008年启动，当年批准了共计4200万美元的72个项目的立项申请，2009年投入2600万美元，2010年投入3600万美元。2010年，成立了九校联盟，发表了C9联盟声明召开各种规模的、各种形式的论坛、报告会院士、专家挂帅进行研讨，请来了周以真做报告2012年教育部设立了以计算思维为切入点的“大学计算机课程改革项目”2013.7第二届计算思维与大学计算机课程教学改革研讨会哈尔滨会议，教育部高等学校大学计算机课程教学指导委员会发布“计算思维教学改革白皮书(征求意见稿)”白皮书的主要内容：一、科学思维以及逻辑思维、实证思维与计算思维的关系二、计算思维的表达体系三、大学计算机课程知识体系与核心概念的关系国内计算思维的研究计算思维的本质：抽象（Abstraction）和自动化（Automation）。计算思维的本质反映了计算的根本问题，即什么能被有效地自动进行。计算是抽象地自动进行，自动化需要某种计算机去解释现象。从操作层面上讲，计算就是如何寻找一台计算机去求解问题，选择合适的抽象，选择合适的计算机去解释执行抽象，后者就是自动化。计算思维中的抽象完全超越物理的时空观，并完全用符号来表示。其中，数字抽象只是一类特例。自动化就是机械地一步一步自动执行，其基础和前提是抽象。案例：18世纪著名古典数学问题——哥尼斯堡七桥问题。2.计算思维的本质25哥尼斯堡城地处东普鲁士，位于普雷格尔河的两岸及河中心的两个岛上，城市各部分由七座桥与两岸连结起来。多年来，当地的居民总有一个愿望：从家里出去散步，能否通过每座桥恰好一次，再返回家中？但是任何人也没有找到这样一条理想的路径。哥尼斯堡普莱格尔河哥尼斯堡七桥问题261736年，瑞士数学家欧拉