计算思维

,HPM&S,一级标题,二级标题,三级标题,计算思维,李波,bobbleee,计算机教学实验中心 高效能建模与仿真研究小组,西安交通大学,2013,年,2,月,25,日,汇报提纲,缘与使命,对计算认识的变革,相关学科发展,背景,计算思维主要定义,计算机学科的本质特点,计算思维操作性定义,不插电的计算机,CTChina,缘与使命,图灵诞生,100,周年,龙女,计算思维,杭州,CS4HS,1912,年,6,月,23,日生于伦敦,Dragon Lady,In,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, China,缘与使命,使命,传承计算文化,弘扬计算之美,培养计算思维,图灵诞生,100,周年,龙女,计算思维,杭州,CS4HS,汇报提纲,缘与使命,对计算认识的变革,相关学科发展,背景,计算思维主要定义,计算机学科的本质特点,计算思维操作性定义,不插电的计算机,CTChina,Peter J. Denning,COMMUNICATIONS OF THE ACM July 2007/Vol. 50, No. 7,什么,是计算？,阶段,1,1940s,工具,阶段,2,1980s,方法,阶段,3,2000s,基本过程,阶段,1,：,Tools,Computation,was seen as a,tool,for,solving equations,cracking codes,analyzing data,managing business processes, running simulations, and,solving models,.,Computation soon established itself as a powerful tool that made formerly,intractable,analyses,tractable,.,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.,什么是计算？,阶段,1,1940s,工具,阶段,2,1980s,方法,阶段,3,2000s,基本过程,阶段,2,：,Methods,Computation 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.,阶段,1,1940s,工具,阶段,2,1980s,方法,阶段,3,2000s,基本过程,阶段,3,：,Fundamental Processes,Scientists from,many fields,were saying they had discovered,information processes,in the,deep structures,of their fields.,什么,是计算？,Biology,Nobel Laureate and Caltech President,David Baltimore,The,Invisible Future, Wiley, 2001,p.,45,“,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.”,Natural 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,.,Physics,Nobel Laureate,Richard Feynman,became famous for showing that quantum electrodynamics (QED) was,natures computational method,for combining quantum particle interactions.,Physicists said that quantum waves carry,information,that generates physical effects.,They have made significant advances with,quantum computation,and,quantum cryptography,.,In his book A New Kind of Science (2002),Stephen Wolfram,proclaimed that,nature is written in the language of computation, challenging,Galileo,s claim that it is written in mathematics.,汇报提纲,缘与使命,对计算认识的变革,相关学科发展,背景,计算思维主要定义,计算机学科的本质特点,计算思维操作性定义,不插电的计算机,CTChina,学科发展,中国至,2050,年信息科技发展,路线图,Computational Lens,4,th,Paradigm,Computational Social Science,Agent based modeling,Cyber-Enabled Discovery and Innovation,，,CDI,中国至,2050,年信息科技发展路线图,中国科学院,信息领域战略研究组,2009,年,战略,发展,泛在,的,信息科学技术,，构建,泛在,的,信息网络,，重点围绕无处不在的网络信息技术应用，信息基础设施升级换代，信息器件、设备与软件的变革性突破，新信息科学与前沿交叉科学等,四个,层次进行战略安排。,2020,年前后,突破低成本器件和系统设计技术，物理世界的新型感知机理、语义检索和分析技术等。,发展可扩展、高可信的下一代互联网和自组织的无线传感网络，积极推进三网融合。,按照延续、扩展和跨越,摩尔定律,三条途径发展微电子技术和新型信息器件，突破多核芯片设计、片上光互联和片上大规模光计算、艾级（,10,18,）超级计算技术等。,突破,网络科学,、,分布式交互算法设计理论,、大规模工业软件、自然的人机界面、蛋白质结构预测等；构建,“平行社会”系统,。,2035,年前后,突破,网络信息理论,、,网络算法理论,、,网络计算模型,等。,建立可持续网络服务体系，突破低功耗芯片和系统设计、实用的知识本体与知识网格技术等。,实现超越,TCP/IP,的未来网络和具有感知与认知能力的无线通信系统，突破分组交换的全光网络技术等。,突破纳米、量子等变革性器件和电路技术，实现泽级（,10,21,）超级计算，软件开发成本平均每两年降低,50%,。,突破可信计算系统、情感理解技术等；构建人类基因组差异数据库。,2050,年前后,建立普适的信息科学，,计算成为自然系统、人造系统、社会系统领域的基本思维方式,；,构建可持续发展的计算基础设施和应用服务；,继计算与网络融合、计算与物理系统融合之后，脑科学与认知科学取得重大突破，实现计算与智能的融合，形成较,成熟,的信息科学。,Computational Lens,三栖学者,理查德,卡普（,Richard Karp,）教授现任美国加州大学伯克利分校计算机科学讲座教授，美国科学院、美国工程院、美国艺术与科学院、欧洲科学院院士。因其在计算机科学领域的基础贡献曾获图灵奖、冯诺依曼奖、美国国家科学勋章、哈佛大学百年奖章等奖项，还担任美国科学院会刊（,PNAS,）等多个国际著名刊物编委。,卡普之所以被称为“三栖学者”是因为他知识渊博，贯通多个学科专业，因而同时被加州大学伯克利分校的电气工程和计算机系、数学系以及工业工程和运筹学系三个系聘为教授。,卡普被授予图灵奖，是因为他在算法的设计与分析、计算复杂性理论、随机化算法等诸多方面作出了创造性贡献。,生物信息学的开创人,Richard M. Karp,提出的“,计算透镜,”（,Computational Lens,）理念被认为是未来二十年计算机科学可能的发展方向之一。,其核心理念是将计算作为一种,通用,的,思维方式,，通过这种,广义的计算,（涉及信息处理、执行算法、关注复杂度）来描述各类自然过程和社会过程，从而解决各个学科的问题。,这一理念试图将计算机科学由最初的数值计算工具、仿真与可视化技术以及后来基于网络、面向多学科的,e-Science,平台，变成普遍适用于自然和社会领域的,通用思维模式,。,Karp,认为：自然问题和社会问题自身的内部就蕴含丰富的属于计算的演化规律。对于现实世界的抽象应该正确反映其演化的本质，并在此基础上设计相应的算法和软件。从这个意义上讲，现在计算机科学和工程中有许多方法是违背这一原则的，有些方法并没有真正揭示所研究问题的内部禀赋的规律，而是通过外部强加的规律来设计算法，解释系统，建立模型，这就导致对于系统的认知与构建从根源上偏离的正确的方向。,第四范式,4,th,Paradigm,图灵奖获得者,Jim Gray,对科学的发展总结出四个范式，是对科学研究方式的一个清晰的,总结,经验积累型,数学理论型,计算模拟型,数据探索型,微软公司于,2009,年,10,月发布了,e-Science,：,科学研究,的第四种范式,论文集，首次全面的描述了,快速,兴起的数据密集型,科学研究。,今天是信息爆炸的时代，各种理论、实验、模拟都统一在,信息处理这种数据探索框架,之下,。,科学研究,就是收集数据，计算数据，分析数据,。,这些,数据的来源可以是传感器也可以是计算模拟结果，通过软件进行分析计算，结果存储在数据库中,。,科学家,必须能够用统计学知识对这些计算数据进行挖掘、探索、和提炼。,Computational Social Science,计算社会科学,Computational Social Science,6 FEBRUARY 2009 VOL 323 SCIENCE,David 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 Alstyne,Harvard University, MIT, University of Michigan, New York University, Northeastern University, Interdisciplinary Scientific Research, Northwestern University, University of CaliforniaSan Diego, Columbia University, Cornell University, Boston University,Science2009,年,2,月发表的一篇关于计算社会科学的文章,ComputationalSocial Science,，该文由美国,11,个大学及研究机构的共,15,名研究人员共同编写。,文章从计算社会科学的,数据获取,、,研究方法,、,制约因素,、,人才培养,4,个方面，描述了计算社会科学的发展、讨论了社会科学研究的特点等。,其,主要目的,是想借此文向广大读者介绍计算社会科学这一,学科理念,，推动、提高社会科学研究水平，进一步繁荣社会科学研究工作。,数字印记,（,Digital Traces),目前人们广泛地以各种不同形式、方式生活在各种网络中：,人们频繁地检查电子邮件和使用搜索引擎,随时随地拨打移动 和发送短信,每天刷卡乘坐交通工具,经常使用信用卡购买商品。,写博客、发微薄、通过SNS来维护人际关系,在公共场所，监视器可以记录人们的活动情况,在医院，人们的医疗记录以数字形式被保存,以上的种种事情都留下了人们的数字印记（踪迹）。,这些数据中,蕴含,的关于个人和群体行为的规律可能足以改变我们对个人生活、组织机构乃至整个社会的认知。,相比较生物和物理等其他学科领域，,数据驱动,的“计算社会科学”要出现的晚一些，而随着对这种大量社会数据的记录和分析，就逐步产生了计算社会科学。,随着信息化和网络化的不断普及与深入，,社会动态变化,的速度和规模已经提高到一个前所未有的水平，计算社会科学成为新的热点。,定义,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.,一个新兴的领域：,利用,大,规模,数据收集,和,分析,能力,揭示,个人和,群体,的,行为模式,。,与传统社会科学通过问卷调查形式获得的数据不同，我们可以借助以上种种新技术获得长时间的、连续的、大量人群的各种行为和互动的数据。,这些数据为研究动态的人际交流、大型社会网络的演化等方面的问题提供了坚实的基础。,例如：,可以通过电子邮件的记录研究一个群体是趋向稳定还是趋向变化、成员之间什么样的交流模式有利于提高效率、接收信息的多样化是否会提高成员的活力和表现等问题；,可以通过给成员佩戴实时记录位置、移动等信息的小电子装置收集数据，研究成员的流动和相互交流的模式对于团体产出的影响；,可以通过电子商务网站的查询和交易记录，以及网上 记录等范围覆盖全球的人际互动数据研究人际互动在经济生产力、公众健康等方面产生的影响；,可以利用互联网上的搜索和浏览记录研究什么是当前公众关心的焦点；,可以通过网络社区上的帖子研究个体在网络中的位置对他们的品味爱好、情绪和健康的影响；,可以通过移动 追踪人们的位置，研究传染病的传播等等。,Albert-Laszlo Barabasi,：当前，数据库广泛地对于每一个个人的行为记录引爆了个人的隐私危机。它同时也创造了一个历史机遇，第一次毫无偏见的为我们提供了成千上万人，而不是少数人的行为模式。,.,，人类的大部分行为都受制于规律，模型和原理法则，而且他们的可重现性与可预测性与自然科学不相上下。,Agent-based-Modelling,Why did nobody notice it,？,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.,Page.,38,2016,年的一天早上，电子显示屏上的橙色报警灯突然不停闪烁着，美国政府的专家们探测到一个关乎国家安全的预警信号。,由于这个电子显示屏背后关联着世界上最大的一些金融机构，包括银行、政府、对冲基金、网络银团等。,而橙色预警灯闪烁表明美国的对冲基金已经积聚在相同的金融资产上，此时，如果某个基金突然变现卖出，警示信号就会出现，而这种下挫价格的行为，迫使其他基金尾随卖出，加速资产价格下挫。很多基金可能在短短的,30,分钟内就会破产,，对整个金融系统造成极大的威胁。,但是，,运用高性能计算机对海量的数据运行并处理后，可以对不可预知的风险进行“情景”预现，此时，金融监管部门及时介入从而可以安全平息此次潜在的金融风险事件,。,Buchanan, M. (2009), Meltdown modelling,Nature,460, 680-682.,Mark Buchanan, Meltdown modelling: Could agent-based computer models prevent another financial crisis? Nature, 2009,。,该文认为，传统的经济模型已经失败了多次，到现在为止，在没有任何前期试验下，我们还在建立新的经济估算；专家之间的不同知识，可以互撞，并产生新的知识；基于智能体的建模也许可以来预防下一次金融危机。,EURACE,是欧盟经济体共同投资开发中的研究欧盟宏观经济政策的仿真系统。其主要科学目标是,建立一个以微观经济为基础的宏观经济分析框架，提供分析全球规则,涌现,的新视角,。其主要的社会目标是通过仿真分析财政政策和货币政策的协调、外部环境震荡下稳定宏观经济的政策、鼓励科技变革和创新等经济政策的影响，以不断调整和改善经济政策,在,EURACE,平台中，其市场的构建分为劳动力市场、资本产品市场和消费品市场，以及能源市场和信贷消费市场，并且这些市场之间是相互交互的,the model currently represents some 10 million households,100,000 firms and about 100 banks,Farmer,和,Foley,（,2009,）在,Nature,上提出：,在,IT,高度发达,的今天，人们会想当然地假定，奥巴马及其经济团队会采用,高超的计算模型,来指引美国走出危机。,然而遗憾的是，他们并,没有,这样做。,因此，政策制订者往往依赖于经验和感觉，采用”屁股决定脑袋”的方式决策,Farmer, D. and D. Foley (2009), The economy needs agent-based modeling,Nature,460, 685-686.,当今经济的理论模型，可以分为两大类：,计量经济方法和动态随机均衡方法。,计量经济方法,只可在经济环境变化不大的时候具有较好的预测性，但是当经济环境出现重大改变的时候就不再适用了。,动态随机均衡方法,一般都是基于比较理想化的假设条件，而这通常与现实差别较大，特别当现实中出现市场失灵等情况时。,基于“基于智能体的建模（,Agent Based Modelling,，,ABM,）”方法是经济建模的下一个突破口,ABM,方法是将经济系统模拟成一个由众多智能体（,agent,）之间,交互,的计算机系统，然后以计算机模拟去研究经济问题；,ABM,方法不需要完全竞争和一般均衡等假设，微观层面上每个智能体基于自身状况和外界条件做出,反映,。,ASPEN,计划,ASPEN,是由美国,Sandia,国家实验室开发的一套,模拟美国经济运行的系统,，该系统采用,了,基于,Agent,的思想进行建模,，在模型中包含了家庭、企业、政府、银行、联邦储备局等多类,Agent,，这些,Agent,能够在劳动力市场、产品市场、债券市场和信贷市场上进行活动，,衍生出各种不同的市场情景和极端风险事件,，为国家的政策制定和风险管理提供有利的工具,通过网络实现的科学发现与技术创新,Cyber-Enabled Discovery and Innovation,，,CDI,CDI,2008,年,NSF CISE,启动了“,通过网络实现的科学发现与技术创新,”（,Cyber-Enabled Discovery and Innovation,，,CDI,）的,5,年研究计划。,是实现计算思维的第一个美国国家科学基金会的,重大计划,。,它的目的是，通过,计算思维,的创新和进步,(,包括,概念,、,方法,、,模型,、,算法,、,工具,和,系统,等,),，对科学与工程领域产生,新理解,、,新模式,，创造,革命性,的研究成果。,From Data to Knowledge:,enhancing human cognition and generating new knowledge from a wealth of,heterogeneous digital data;,数据特点,Huge,Distributed,Dynamic,Heterogeneous,Noisy,Unstructured / semi-structured,从数据中发现知识（,From Data to Knowledge,）,其基本目的是从大量的、杂乱无章的、难以理解的,数据,中抽取并推导出对于某些特定的人们来说是有价值、有意义的,知识,并作为,决策,的依据。,数据大致可分成,结构化,数据和,非结构化,数据,难点,判定,一个数据集里面含不含某种知识,如何发现其中的知识,知识如何表示。,已发现的知识与实际蕴藏的知识之间的关系。,47,Nontraditional Challenges,Traditionally,Cope with the complexity,of the,problem,New challenges,How to efficiently,compute,on massive data sets?,Restricted access to the data,Not enough time to read the whole data,Tiny 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 Sets,Cope with the complexity,of the,data,例：,Model, simulate, analyze, and validate complex systems with large data sets.,用大数据集描述，模拟，分析和验证复杂系统,利用大规模数据集完成对复杂系统的,建模,，,仿真,，,分析,，和,验证,。,从可能包含噪声的高维度的数据中提取出重要的,特征,和,模式,，在,大量的应用场景,中是至关重要的。,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),通信和网络,的控制和优化（信息技术），,人类和社会行为,仿真（社会科学），,灾难响应,模拟和反恐准备（国土安全），设计减轻外部威胁的自动响应式的,智能系统,（国土安全），多尺度预测,生态和进化过程,（生物科学），软件开发（信息技术），以及风险分析。,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.,一些系统的关键问题是如何,判断和理解,当一个输入达到临界点的时候，系统是否会进入根本不同的行为模式；例如，全球的气候（与大气中二氧化碳含量相关）和美国经济（与联邦基金利率相关）。,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.,汇报提纲,缘与使命,对计算认识的变革,相关学科发展,背景,计算思维主要定义,计算机学科的本质特点,计算思维操作性定义,不插电的计算机,CTChina,Jeannette 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,.,The First A to CT,Abstractions,are our “,mental,” tools,The abstraction process includes,Choosing the,right,abstractions,Operating simultaneously at,multiple layers of abstraction,Defining the,relationships,the between layers,The Second,A,to CT,The power of our “mental” tools is amplified by our “,metal,” tools.,Automation,is mechanizing our abstractions, abstraction layers, and their relationships,Mechanization is possible due to precise and exacting,notations,and,models,There is some “computer” below,human or machine, virtual or physical,From,Jeannette M. Wing,Two As to C.T. Combined,Computing is the,automation,of our,abstractions,They give us the audacity and ability to scale.,CT,choosing,the right abstractions, etc.,choosing,the right “computer” for the task,From,Jeannette M. Wing,CT=Computing,NOT,Computer literacy, i.e., how to use Word and Excel or even Google,Computer programming, i.e., beyond Java Programming 101,17 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.,计算思维是与形式化问题及其解决方案相关的一个思维过程，其解决问题的表示形式应该能有效地被信息处理代理执行,合理抽象 高效算法（算法思维角度）,合理建模 高效实施（工程思维角度）,NSF,Cyber-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.,中国学者1992年关于“计算思维”的定义,“计算思维就是思维过程或功能的计算模拟方法论，其研究的目的是提供适当的方法，使人们能借助现代和将来的计算机，逐步达到人工智能的较高目标。”,王飞跃院士的定义,广义计算思维：基于可计算的手段，以定量化的方式进行的思维过程。,狭义计算思维：数据驱动的思维过程（,Data-driven Thinking,）。,计算思维的特征：,是概念化,，不是,程序化,是根本,的，不是刻板的,技能,是人,的，不是计算机的,思维,是,思想，不是人造,品,数学和工程思维的互补与融合,面向所有的人，所有地方,60,计算思维的例子：,是通过,约简、嵌入、转化和仿真等方法，把一个困难的问题阐释成如何求解它的思维方法。,是,一种递归思维，是一种并行处理，是一种把代码译成数据又能把数据译成代码，是一种多维分析推广的类型检查方法。,是一种选择,合适的方式陈述一个问题，或对一个问题的相关方面建模使其易于处理的思维方法。,是按照,预防、保护及通过冗余、容错、纠错的方式,，并从,最坏情况进行系统恢复的一种思维方法。,是,利用启发式推理寻求解答，即在不确定情况下的规划、学习和调度的思维方法,。,61,3,种能力,Computer Literacy,Computer Fluency,Computational Thinking,计算机使用能力,Computer Literacy,the ability to use basic computer applications such as an editor and a web or file-system browser,计算机系统认知能力,Computer Fluency,a high level understanding of the workings of a computer system,计算思维能力,Computational Thinking,Critical, skill set is the intellectual and reasoning skills that a professional needs to master in order to apply computational techniques or computer applications to the problems and projects in their field, whether the field is in the arts, sciences, humanities, or social sciences.,CT,的两个核心,Creating Abstractions,Algorithmic formulations,Modularity,Realizing Abstractions,Creating Abstractions.,Newtonian mechanics,Keynesian economics.,In computer science,?, however,we can often be more creative with,our abstractions, since these abstractions serve more as principled ways to structure a system, rather than as models of real-world processes.,an online retailers computer system.,It incorporates many abstract models: client/server, relational database, distributed transactions, program objects, etc., that enable the designers to create a system that provides the necessary functionality in a reliable and secure way.,Important forms of abstraction in computer science include,：,Algorithmic formulations,and,Modularity,Algorithmic formulations,Many problems in computer science can be formulated as,abstract processes,or,classes of operations on data,that can be solved by,systematic computational methods,.,There is a wide range of possible solution methods that can then be analyzed for both correctness and efficiency.,Often, a single category of algorithm can solve problems across many application domains. So, for example, the idea of,hashing,creating a mapping where the output appears to be randomly distributed even if the input data are notfinds applications in information retrieval, digital signatures, and distributed file sharing.,The study of algorithms is an intellectually deep and compelling subject that we cover from many different perspectives in our courses, with some requiring an extensive mathematical background.,Modularity,Modular design involves,partitioning,a,system,into,components, such that each component can have a,succinct description,of its behavior or properties,hiding the details,of its implementation.,Some common forms of modularity in computer science include,procedures,data abstraction, and,object-oriented programming,.,Of course, modular design is also used in many other domains, ranging from building construction to product supply chains, but the use of modularity in computer science can be much more,complete,and,pervasive,.,Realizing Abstractions,Computer science offers a,wide range of different ways,to implement particular abstractions.,Compared to other fields of engineering, our abstractions are,less coupled,to a particular physical realization.,Most of the traditional focus has been on mapping a computation onto a single, sequential processor,however, there are increasing opportunities to divide up a task and map it onto multiple computing elements, either through parallelism or distribution.,A second dimension concerns iteration versus recursion, two ways of scaling a computation to multiple elements.,Both approaches can be applied to sequential, parallel, and distributed computations.,汇报提纲,缘与使命,对计算认识的变革,相关学科发展,背景,计算思维主要定义,计算机学科的本质特点,计算思维操作性定义,不插电的计算机,CTChina,即使是菜刀这样的工具，也会涉及科学、技术、工程和应用的各个层面。菜刀过于简单，其他学科的知识足够它的需要了，因此没有什么“菜刀科学”。,以色列学者哈雷尔在算法学：计算的本质一书中提出这样的问题：,论技术的影响， 也很大，为什么没有 科学？论技术复杂性，人造卫星很复杂，为什么没有被广泛接受的人造卫星科学。他认为其实计算机是计算的工具，用计算机给这门科学命名，就像用“手术刀科学”给外科学命名一样地不合适。,天文学=望远镜,“,菜刀科学,”,与“计算机科学”,-,陈道蓄,计算机科学,计算机科学是研究计算机以及它们能干什么的一门学科。它研究,抽象计算机,的能力与局限，,真实计算机,的构造与特征，以及用于求解问题的数不清的,计算机应用,。,涉及,符号及其操作,涉及多种,抽象概念,的创造和操作,创造并研究,算法,创造各种,人工结构,，尤其是不受物理定律限制的结构,利用并应对,指数增长,探索计算能力的,基本极限,关注与人类智能相关的,复杂的、分析的、理性的活动,National Research Council Committee on Fundamentals of Computer Science,Computer Science: Reflections on the Field, The National Academies Press, Washington D.C., 2004.,计算机学科的本质,-,个人认知,以简单的有限的离散构造解决无限的问题,以简单的有穷的离散构造解决无穷的问题,有限（穷）,-,无限（穷）,可数（可列）无穷,递归函数,-,以有穷构造无穷的必由之路,手段,过程,递归过程,结构,递归结构,构造举例,谓词合适公式的定义,在谓词演算中合适公式的递归定义如下：,(1),原子谓词公式是合适公式。,