计算思维操作性定义.ppt

HPM&S计算思维操作性定义计算思维操作性定义李波 13709218618 高效能建模与仿真研究小组西安交通大学 2012年11月HPM&S汇报提纲汇报提纲缘与使命对计算本质认识的变革计算思维主要定义对问题求解的认识引起对计算机教学的再认识计算机学科的本质特点计算思维操作性定义HPM&S缘与使命缘与使命图灵诞生100周年龙女计算思维西安首届1912年6月23日生于伦敦HPM&S Dragon LadyIn 1983,I went to China for two months with a Chinese-American student tour group.We spent two weeks in Xian,where we were each handed a sword,and every morning we had to wake up at 5 oclock and we were supposed to learn this sword dance.I really took to it.To me,it was like ballet.Doing a Chinese sword dance,which I learned in Xian,ChinaHPM&S缘与使命缘与使命图灵诞生100周年龙女计算思维西安首届使命使命传承计算文化传承计算文化弘扬计算之美弘扬计算之美培养计算思维培养计算思维HPM&S汇报提纲汇报提纲缘与使命对计算本质认识的变革计算思维主要定义对问题求解的认识引起对计算机教学的再认识计算机学科的本质特点计算思维操作性定义HPM&SPeter J.DenningCOMMUNICATIONS OF THE ACM July 2007/Vol.50,No.7HPM&S对计算本质认知的变革对计算本质认知的变革1940s工具阶段11980s方法阶段22000s基本过程阶段3电子数字计算机时代1.Computation was seen as a tool for solving equations,cracking codes,analyzing data,managing business processes,running simulations,and solving models.2.Computation soon established itself as a powerful tool that made formerly intractable analyses tractable.3.It took many technologies to new heights,such as atomic energy,advanced aircraft and ship design,drug design,structural analyses of buildings,and weather prediction.HPM&S对计算本质认知的变革对计算本质认知的变革1940s工具阶段11980s方法阶段22000s基本过程阶段3Computation had advanced from a tool to exploit existing knowledge to a means of discovering new knowledge.Nobel Physics Laureate Ken Wilson was among the first to say that computation had become a third leg of science,joining the traditions of theory and experiment.He and others coined the term“computational science”to refer to the search for new discoveries using computation as the main method.HPM&S1940s工具阶段11980s方法阶段22000s基本过程阶段3Scientists from many fields were saying they had discovered information processes in the deep structures of their fields.BiologyNobel Laureate and Caltech President David Baltimore“Biology is today an information science.The output of the system,the mechanics of life,are encoded in a digital medium and read out by a series of reading heads.Biology is no longer solely the province of the small laboratory.Contributions come from many directions.”(The Invisible Future,Wiley,2001,p.45.)对计算本质认知的变革对计算本质认知的变革HPM&SNatural information processes.:nature long ago learned how to encode information about organisms in DNA and then to generate new organisms from DNA through its own computational methods.PhysicsPhysicists said that quantum waves carry information that generates physical effects.They have made significant advances with quantum computation and quantum cryptography.Nobel Laureate Richard Feynman became famous for showing that quantum electrodynamics(QED)was natures computational method for combining quantum particle interactions.In his book A New Kind of Science(2002),Stephen Wolfram proclaimed that nature is written in the language of computation,challenging Galileos claim that it is written in mathematics.Jeanette Wing has concluded that computational concepts are deeply embedded into everyday thinking in many fields.Computation is everywhere.HPM&S相关学科发展背景相关学科发展背景HPM&S中国至中国至2050年信息科技发展路线图年信息科技发展路线图 发展泛在的信息科学技术，构建泛在的信息网络，重点围绕无处不在的网络信息技术应用，信息基础设施升级换代，信息器件、设备与软件的变革性突破，新信息科学与前沿交叉科学等四个层次进行战略安排。HPM&S2020年前后年前后突破低成本器件和系统设计技术，物理世界的新型感知机理、语义检索和分析技术等。发展可扩展、高可信的下一代互联网和自组织的无线传感网络，积极推进三网融合。按照延续、扩展和跨越摩尔定律摩尔定律三条途径发展微电子技术和新型信息器件，突破多核芯片设计、片上光互联和片上大规模光计算、艾级（1018）超级计算技术等。突破网络科学网络科学、分布式交互算法设计理论分布式交互算法设计理论、大规模工业软件、自然的人机界面、蛋白质结构预测等；构建“平行社平行社会会”系统系统。HPM&S2035年前后年前后突破网络信息理论网络信息理论、网络算法理论网络算法理论、网络计算模型网络计算模型等。建立可持续网络服务体系，突破低功耗芯片和系统设计、实用的知识本体与知识网格技术等。实现超越TCP/IP的未来网络和具有感知与认知能力的无线通信系统，突破分组交换的全光网络技术等。突破纳米、量子等变革性器件和电路技术，实现泽级（1021）超级计算，软件开发成本平均每两年降低50%。突破可信计算系统、情感理解技术等；构建人类基因组差异数据库。HPM&S2050年前后年前后建立普适的信息科学，计算成为自然系统、人造计算成为自然系统、人造系统、社会系统领域的基本思维方式系统、社会系统领域的基本思维方式；构建可持续发展的计算基础设施和应用服务；继计算与网络融合、计算与物理系统融合之后，脑科学与认知科学取得重大突破，实现计算与智能的融合，形成较成熟成熟的信息科学。HPM&SComputational LensHPM&SHPM&S三栖学者三栖学者理查德卡普（Richard Karp）教授现任美国加州大学伯克利分校计算机科学讲座教授，美国科学院、美国工程院、美国艺术与科学院、欧洲科学院院士。因其在计算机科学领域的基础贡献曾获图灵奖、冯诺依曼奖、美国国家科学勋章、哈佛大学百年奖章等奖项，还担任美国科学院会刊（PNAS）等多个国际著名刊物编委。卡普之所以被称为“三栖学者”是因为他知识渊博，贯通多个学科专业，因而同时被加州大学伯克利分校的电气工程和计算机系、数学系以及工业工程和运筹学系三个系聘为教授。卡普被授予图灵奖，是因为他在算法的设计与分析、计算复杂性理论、随机化算法等诸多方面作出了创造性贡献。生物信息学的开创人HPM&SRichard M.Karp提出的“计算透镜”（Computational Lens）理念被认为是未来二十年计算机科学可能的发展方向之一。其核心理念是将计算作为一种通用通用的思维方式思维方式，通过这种广义的计算广义的计算（涉及信息处理、执行算法、关注复杂度）来描述各类自然过程和社会过程，从而解决各个学科的问题。这一理念试图将计算机科学由最初的数值计算工具、仿真与可视化技术以及后来基于网络、面向多学科的e-Science平台，变成普遍适用于自然和社会领域的通用思维模式通用思维模式。HPM&SComputational Social Science计算社会科学计算社会科学HPM&SComputational Social Science6 FEBRUARY 2009 VOL 323 SCIENCEDavid Lazer,Alex Pentland,Lada Adamic,Sinan Aral,Albert-Lszl Barabsi,Devon Brewer,Nicholas Christakis,Noshir Contractor,James Fowler,Myron Gutmann,Tony Jebara,Gary King,Michael Macy,Deb Roy,Marshall Van AlstyneHarvard University,MIT,University of Michigan,New York University,Northeastern University,Interdisciplinary Scientific Research,Northwestern University,University of CaliforniaSan Diego,Columbia University,Cornell University,Boston UniversityHPM&SScience2009年2月发表的一篇关于计算社会科学的文章ComputationalSocial Science，该文由美国11个大学及研究机构的共15名研究人员共同编写。文章从计算社会科学的数据获取、研究方法、制约因素、人才培养4个方面，描述了计算社会科学的发展、讨论了社会科学研究的特点等。其主要目的是想借此文向广大读者介绍计算社会科学这一学科理念，推动、提高社会科学研究水平，进一步繁荣社会科学研究工作。HPM&S数字印记数字印记（Digital Traces)目前人们广泛地以各种不同形式、方式生活在各种网络中：人们频繁地检查电子邮件和使用搜索引擎随时随地拨打移动电话和发送短信每天刷卡乘坐交通工具经常使用信用卡购买商品。写博客、发微薄、通过SNS来维护人际关系在公共场所，监视器可以记录人们的活动情况在医院，人们的医疗记录以数字形式被保存以上的种种事情都留下了人们的数字印记（踪迹）数字印记（踪迹）。HPM&S这些数据中蕴含的关于个人和群体行为的规律可能足以改变我们对个人生活、组织机构乃至整个社会的认知。相比较生物和物理等其他学科领域，数据驱动的“计算社会科学”要出现的晚一些，而随着对这种大量社会数据的记录和分析，就逐步产生了计算社会科学。随着信息化和网络化的不断普及与深入，社会动态变化的速度和规模已经提高到一个前所未有的水平，计算社会科学成为新的热点。定义A field is emerging that leverages the capacity to collect and analyze data at a scale that may reveal patterns of individual and group behaviors.一个新兴的领域：利用大规模数据收集和分析能力揭示个人和群体的行为模式行为模式。HPM&S与传统社会科学通过问卷调查形式获得的数据不同，我们可以借助以上种种新技术获得长时间的、连续的、大量人群的各种行为和互动的数据。这些数据为研究动态的人际交流、大型社会网络的演化演化等方面的问题提供了坚实的基础。例如：可以通过电子邮件的记录研究一个群体是趋向稳定还是趋向变化、成员之间什么样的交流模式有利于提高效率、接收信息的多样化是否会提高成员的活力和表现等问题；可以通过给成员佩戴实时记录位置、移动等信息的小电子装置收集数据，研究成员的流动和相互交流的模式对于团体产出的影响；可以通过电子商务网站的查询和交易记录，以及网上电话记录等范围覆盖全球的人际互动数据研究人际互动在经济生产力、公众健康等方面产生的影响；可以利用互联网上的搜索和浏览记录研究什么是当前公众关心的焦点；可以通过网络社区上的帖子研究个体在网络中的位置对他们的品味爱好、情绪和健康的影响；可以通过移动电话追踪人们的位置，研究传染病的传播等等。HPM&SAgent-based-ModellingHPM&SWhy did nobody notice it？HPM&S Luis Garicano at LSE shows Queen Elizabeth II a chart explaining how the credit crunch was caused.A group of eminent economists has come to the Queens rescue after she asked why no one had predicted the credit crunch during a visit to the London School of Economics in November.HPM&SPage.302016年的一天早上，电子显示屏上的橙色报警灯突然不停闪烁着，美国政府的专家们探测到一个关乎国家安全的预警信号。由于这个电子显示屏背后关联着世界上最大的一些金融机构，包括银行、政府、对冲基金、网络银团等。而橙色预警灯闪烁表明美国的对冲基金已经积聚在相同的金融资产上，此时，如果某个基金突然变现卖出，警示信号就会出现，而这种下挫价格的行为，迫使其他基金尾随卖出，加速资产价格下挫。很多基金可能在短短的30分钟内就会破产，对整个金融系统造成极大的威胁。但是，运用高性能计算机对海量的数据运行并处理后，可以对不可预知的风险进行“情景”预现，此时，金融监管部门及时介入从而可以安全平息此次潜在的金融风险事件。Buchanan,M.(2009),Meltdown modelling,Nature 460,680-682.HPM&SMark Buchanan,Meltdown modelling:Could agent-based computer models prevent another financial crisis?Nature,2009。该文认为，传统的经济模型已经失败了多次，到现在为止，在没有任何前期试验下，我们还在建立新的经济估算；专家之间的不同知识，可以互撞，并产生新的知识；基于智能体的建模也许可以来预防下一次金融危机。EURACEEURACE是是欧欧盟盟经经济济体体共共同同投投资资开开发发中中的的研研究究欧欧盟盟宏宏观观经经济济政政策策的的仿仿真真系系统统。其其主主要要科科学学目目标标是是建建立立一一个个以以微微观观经经济济为为基基础础的的宏宏观观经经济济分分析析框框架架，提提供供分分析析全全球球规规则则涌涌现现的的新新视视角角。其其主主要要的的社社会会目目标标是是通通过过仿仿真真分分析析财财政政政政策策和和货货币币政政策策的的协协调调、外外部部环环境境震震荡荡下下稳稳定定宏宏观观经经济济的的政政策策、鼓鼓励励科科技技变变革革和和创创新新等等经经济济政政策策的的影影响响，以不断调整和改善经济政策以不断调整和改善经济政策在在EURACEEURACE平平台台中中，其其市市场场的的构构建建分分为为劳劳动动力力市市场场、资资本本产产品品市市场场和和消消费费品品市市场场，以及能源市场和信贷消费市场，并且这些市场之间是相互交互的以及能源市场和信贷消费市场，并且这些市场之间是相互交互的the model currently represents some 10 million households,100,000 firms and about 100 banksHPM&S Farmer和Foley（2009）在Nature上提出：在IT高度发达的今天，人们会想当然地假定，奥巴马及其经济团队会采用高超的计算模型来指引美国走出危机。然而遗憾的是，他们并没有没有这样做。因此，政策制订者往往依赖于经验和感觉，采用”屁股决定脑袋”的方式决策Farmer,D.and D.Foley(2009),The economy needs agent-based modeling,Nature 460,685-686.HPM&S当今经济的理论模型，可以分为两大类：计量经济方法和动态随机均衡方法。计量经济方法只可在经济环境变化不大的时候具有较好的预测性，但是当经济环境出现重大改变的时候就不再适用了。动态随机均衡方法一般都是基于比较理想化的假设条件，而这通常与现实差别较大，特别当现实中出现市场失灵等情况时。基于“基于智能体的建模（Agent Based Modelling，ABM）”方法是经济建模的下一个突破口ABM方法是将经济系统模拟成一个由众多智能体（agent）之间交互的计算机系统，然后以计算机模拟去研究经济问题；ABM方法不需要完全竞争和一般均衡等假设，微观层面上每个智能体基于自身状况和外界条件做出反映反映。HPM&SASPEN计划 ASPEN是是由由美美国国Sandia国国家家实实验验室室开开发发的的一一套套模模拟拟美美国国经经济济运运行行的的系系统统，该该系系统统采采用用了了基基于于Agent的的思思想想进进行行建建模模，在在模模型型中中包包含含了了家家庭庭、企企业业、政政府府、银银行行、联联邦邦储储备备局局等等多多类类Agent，这这些些Agent能能够够在在劳劳动动力力市市场场、产产品品市市场场、债债券券市市场场和和信信贷贷市市场场上上进进行行活活动动，衍衍生生出出各各种种不不同同的的市市场场情情景景和和极极端端风风险险事事件件，为为国国家家的的政政策制定和风险管理提供有利的工具策制定和风险管理提供有利的工具HPM&S通过网络实现的科学发现与技术创新通过网络实现的科学发现与技术创新Cyber-Enabled Discovery and Innovation，CDIHPM&SCDI2008 年NSF CISE启动了“通过网络实现的科学发现与技通过网络实现的科学发现与技术创新术创新”（Cyber-Enabled Discovery and Innovation，CDI）的5年研究计划。是实现计算思维的第一个美国国家科学基金会的重大计划重大计划。它的目的是，通过计算思维的创新和进步(包括概念概念、方法方法、模型模型、算法算法、工具工具和系统系统等)，对科学与工程领域产生新理新理解解、新模式新模式，创造革命性革命性的研究成果。HPM&SFrom Data to Knowledge:enhancing human cognition and generating new knowledge from a wealth of heterogeneous digital data;数据特点Huge DistributedDynamicHeterogeneousNoisyUnstructured/semi-structuredHPM&S从数据中发现知识（从数据中发现知识（From Data to Knowledge）其基本目的是从大量的、杂乱无章的、难以理解的数据数据中抽取并推导出对于某些特定的人们来说是有价值、有意义的知识知识,并作为决策决策的依据。数据大致可分成结构化结构化数据和非结构化非结构化数据难点判定判定一个数据集里面含不含某种知识如何发现其中的知识知识如何表示。已发现的知识与实际蕴藏的知识之间的关系。HPM&S39Nontraditional ChallengesTraditionallyCope with the complexity of the problemNew challengesHow to efficiently compute on massive data sets?Restricted access to the dataNot enough time to read the whole dataTiny fraction of the data can be held in main memory How to find desired information in the data?How to summarize the data?How to clean the data?Massive Data SetsCope with the complexity of the dataHPM&S例：例：Model,simulate,analyze,and validate complex systems with large data sets.用大数据集描述，模拟，分析和验证复杂系统HPM&S利用大规模数据集完成对复杂系统的利用大规模数据集完成对复杂系统的建模建模，仿真仿真，分析分析，和，和验证验证。从从可能包含噪声的高维度的数据中提取出重要的可能包含噪声的高维度的数据中提取出重要的特征特征和和模式模式，在，在大量的大量的应用场景应用场景中是至关重要的。中是至关重要的。Model,simulate,analyze,and validate complex systems with large data sets.Extraction of significant features and patterns from high-dimensional data,which can be noisy,is crucial in a great variety of settings.例如，例如，地球系统地球系统（地球科学），（地球科学），引力波引力波（物理），（物理），星系星系的形成（天文的形成（天文学），高度复杂的学），高度复杂的动态系统动态系统仿真、健康监测、预测、设计和控制（工仿真、健康监测、预测、设计和控制（工程），程），Examples include the Earth system(geosciences),gravitational waves(physics),galaxy formation(astronomy),highly complex dynamical systems simulation,health monitoring,prediction,design and control(engineering),HPM&S通通信信和和网网络络的的控控制制和和优优化化（信信息息技技术术），人人类类和和社社会会行行为为仿仿真真（社社会会科科学学），灾灾难难响响应应模模拟拟和和反反恐恐准准备备（国国土土安安全全），设设计计减减轻轻外外部部威威胁胁的的自自动动响响应应式式的的智智能能系系统统（国国土土安安全全），多多尺尺度度预预测测生生态态和和进进化化过过程程（生生物物科科学学），软软件件开开发（信息技术），以及风险分析。发（信息技术），以及风险分析。communication and network control and optimization(information technology),human and social behavior simulation(social sciences),disaster response simulation and anti-terrorism preparation(homeland defense),design of smart systems for mitigation of exogenous threats using autonomic response(homeland security),predictive understanding of ecological and evolutionary processes at multiple scales(biological sciences),software development(information technology),and risk analysis.HPM&S一些系统的关键问题是如何一些系统的关键问题是如何判断和理解判断和理解当一个输入达到临界点的时候，当一个输入达到临界点的时候，系统是否会进入根本不同的行为模式；例如，全球的气候（与大气中系统是否会进入根本不同的行为模式；例如，全球的气候（与大气中二氧化碳含量相关）和美国经济（与联邦基金利率相关）。二氧化碳含量相关）和美国经济（与联邦基金利率相关）。A key issue for some systems is understanding whether they will enter a fundamentally different mode of behavior when an input crosses a tipping point;examples include the Earths climate(due to atmospheric carbon dioxide)and the U.S.economy(due to the federal funds interest rate).主题主题:知识数据，复杂性知识数据，复杂性领域领域:所有科学和工程领域所有科学和工程领域Themes:Data to Knowledge,Complexity.Domains:all fields of science and engineering.HPM&S汇报提纲汇报提纲缘与使命对计算本质认识的变革计算思维主要定义对问题求解的认识引起对计算机教学的再认识计算机学科的本质特点计算思维操作性定义HPM&SJeannette Wings definition(s)2006 CT CACM 49,3335.CT involves solving problems,designing systems,and understanding human behavior,by drawing on the concepts fundamental to computer science.To flourish in todays world,computational thinking has to be a fundamental part of the way people think and understand the world.CT is taking an approach to solving problems,designing systems and understanding human behavior that draws on concepts fundamental to computing(Wing 2006).Computing is the automation of our abstractions.（Computing:abstraction and automation）The essence of CT is abstraction.CT is a kind of analytical thinking.HPM&SFrom Jeannette M.WingThe First A to CTAbstractions are our“mental”toolsThe abstraction process includesChoosing the right abstractionsOperating simultaneously at multiple layers of abstractionDefining the relationships the between layersHPM&SThe Second A to CTThe power of our“mental”tools is amplified by our“metal”tools.Automation is mechanizing our abstractions,abstraction layers,and their relationshipsMechanization is possible due to precise and exacting notations and modelsThere is some“computer”below human or machine,virtual or physicalFrom Jeannette M.WingHPM&STwo As to C.T.Combined Computing is the automation of our abstractionsThey give us the audacity and ability to scale.CTchoosing the right abstractions,etc.choosing the right“computer”for the taskFrom Jeannette M.WingCT=Computing NOT Computer literacy,i.e.,how to use Word and Excel or even Google Computer programming,i.e.,beyond Java Programming 101HPM&S17 November 2010 her research notes：CT:What and Why?2010,Jan Cuny,Larry Snyder,and Jeannette M.Wing,“Demystifying CT for Non-Computer Scientists,”work in progress.“CT is the thought processes involved in formulating problems and their solutions so that the solutions are represented in a form that can be effectively carried out by an information-processing agent.”Informally,CT describes the mental activity in formulating a problem to admit a computational solution.The solution can be carried out by a human or machine,or more generally,by combinations of humans and machines.CT is used in the design and analysis of problems and their solutions,broadly interpreted.计算思维是与形式化问题及其解决方案相关的一个思维过程，其解决问题的表示形式应该能有效地被信息处理代理执行合理抽象 高效算法（算法思维角度）合理建模 高效实施（工程思维角度）HPM&SNSFCyber-Enabled Discovery and Innovation(CDI)is NSFs bold five-year initiative to create revolutionary science and engineering research outcomes made possible by innovations and advances in CT.CT is defined comprehensively to encompass computational concepts,methods,models,algorithms,and tools.Applied in challenging science and engineering research and education contexts,CT promises a profound impact on the Nations ability to generate and apply new knowledge.Collectively,CDI research outcomes are expected to produce paradigm shifts in our understanding of a wide range of science and engineering phenomena and socio-technical innovations that create new wealth and enhance the national quality of life.HPM&SISTE&CSTA-Operational Definition for K-12（2011）CT is a problem-solving process that includes(but is not limited to)the following characteristics:Formulating problems in a way that enables us to use a c