计算思维操作性定义 李波 13709218618 boblee@xjtu.edu.cn weibo.com/bobbleee 计算机教学实验中心 高效能建模与仿真研究小组 西安交通大学 2012年11月 一、冯老师的题目：计算思维驱动的计算机基础课程改革思考和实践 围绕西安交通大学计算机教学实验中心在计算思维教学研讨和思考这一主题，回顾在计算思维的讨论中出现过哪些说法、争论、疑惑？直面回答：计算思维的改革为什么那么难做下去？有哪些认识误区和不清晰之处？操作的团难在哪儿？具体的做法和建议有哪些？ 在回答好上述问题后，介绍基于计算思维的课程体系的构想和实践。主要思路是三个大学计算机基础的方案的定位、培养目标、教学设计和教学效果；程序设计课程的定位、连接和教学大纲；后续课程微机原理和计算机网络等课程如何引入和贯穿计算思维。 二、李波的题目：计算思维操作性定义 回顾计算思维的主要定义，分析现有定义的适用性，从而阐明计算思维操作性定义提出的必要性和其主要作用。总结对计算机学科本质的认识的发展的阶段和过程，分析出本学科的最基本的概念和方法。围绕计算的原理给出计算思维的操纵性定义的知识框架和知识点。 分析此操纵性定义对大学计算机课程的教学改革的指导意义。用大学计算机基础课程为例介绍计算思维操作性定义如何驱动和支撑教学要求、教学目标、课程内容的设计和实现。 最后介绍在计算思维操作性定义指导下的大学计算机课程的应用案例和教学片段

汇报提纲 缘与使命 对计算本质认识的变革 计算思维主要定义 对问题求解的认识引起对计算机教学的再认识 计算机学科的本质特点 计算思维操作性定义

缘与使命 1912年6月23日生于伦敦 图灵诞生100周年 龙女 计算思维 西安 首届 图灵（Alan Mathison Turing）1912年6月23日生于伦敦近郊。1931 年进了剑桥"国王学院”(King’s College)攻读数学。1936年发表论文 “论可计算数及其在判定问题中的应用”，给“可计算性”下了一个严格的数学定义，并提出了一种计算机的抽象模型，现在被大家称作“图灵机 ”(Turing Machine)。 抽象化(Abstraction)是指以缩减一个概念或是一个现象的资讯含量来将其广义化(Generalization)的过程，主要是为了只保存和一特定目的有关的资讯。例如，将一个皮制的足球抽象化成一个球，只保留一般球的属性和行为等资讯。相似地，亦可以将快乐抽象化成一种情绪，以减少其在情绪中所含的资讯量。 Abstraction is a process or result of generalization, removal of properties, or distancing of ideas from objects. This may refer in particular to one of the following: Abstraction (computer science), a process of hiding details of implementation in programs and data Abstraction layers, an application of abstraction in computing Hardware abstraction, an abstraction layer on top of hardware Abstraction (linguistics) Abstraction (mathematics), a process of removing the dependence of a mathematical concept on real-world objects Lambda abstraction, a kind of term in lambda calculus Abstraction (sociology), a process of considering sociological concepts at a more theoretical level 下面是图灵的两张像，一张是他的简单版画头像。你看和那张照片比起来，是不是非常像？虽然它只是红白两色，并无深浅之分，但是很传神。

I really took to it. To me, it was like ballet. Dragon Lady In 1983, I went to China for two months with a Chinese-American student tour group. We spent two weeks in Xi'an, where we were each handed a sword, and every morning we had to wake up at 5 o'clock 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 Xi'an, China

缘与使命 图灵诞生100周年 龙女 计算思维 西安 首届 使命 传承计算文化 弘扬计算之美 培养计算思维

汇报提纲 缘与使命 对计算本质认识的变革 计算思维主要定义 对问题求解的认识引起对计算机教学的再认识 计算机学科的本质特点 计算思维操作性定义

Peter J. Denning COMMUNICATIONS OF THE ACM July 2007/Vol. 50, No. 7

对计算本质认知的变革 阶段1 阶段2 阶段3 1940s 工具 1980s 方法 2000s 基本过程 电子数字计算机时代 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. REVOLUTION IN THE MAKING This revolution has been gestating for a long time. Its three main stages were tools (beginning in the 1940s), methods (beginning in the 1980s), and fundamental processes (beginning in the 2000s). In the 1940s, the era of the first electronic digital computers, 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. By the 1980s, computation had become utterly indispensable in many fields. It 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. This idea was so powerful that, in 1989, the U.S. Congress passed into law the High Performance Computing and Communication Initiative to stimulate technological advances through high-performance computation. By 2000, computation had advanced further. Scientists from many fields were saying they had discovered information processes in the deep structures of their fields. Nobel Laureate and Caltech President David Baltimore commented: “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.) Baltimore was saying that 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. Biologists and computer scientists today collaborate closely as they seek to understand, and eventually to influence, those natural information processes. Biology was not the only field to say this. Physicists 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 nature’s computational method for combining quantum particle interactions. In the early 1980s, computational scientists at NASA-Ames discovered a successful,methane-resistant heat shield material for the Jupiter Probe by computing its molecular structure from the Schroedinger Equation.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. Economists analyze economic systems for their inherent information flows. Management scientists claim workflow,commitments, and social networks as fundamental information processes in all organizations. Artists and humanists use computation for everything from analysis to the creation of new works. Web researchers have discovered new social behaviors and ways of computing by using the entire Web as their laboratory. Computing artifacts have become matters of style and culture (iPod, eBay,Wikipedia, Google, Playstation,Xbox, Wii, and much more). Even politicians are utilizing sophisticated social data analyses,computational gerrymandering,and blogging. Jeanette Wing has concluded that computational concepts are deeply embedded into everyday thinking in many fields . Computation is everywhere.

对计算本质认知的变革 阶段1 阶段2 阶段3 1940s 工具 1980s 方法 2000s 基本过程 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. REVOLUTION IN THE MAKING This revolution has been gestating for a long time. Its three main stages were tools (beginning in the 1940s), methods (beginning in the 1980s), and fundamental processes (beginning in the 2000s). In the 1940s, the era of the first electronic digital computers, 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. By the 1980s, computation had become utterly indispensable in many fields. It 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. This idea was so powerful that, in 1989, the U.S. Congress passed into law the High Performance Computing and Communication Initiative to stimulate technological advances through high-performance computation. By 2000, computation had advanced further. Scientists from many fields were saying they had discovered information processes in the deep structures of their fields. Nobel Laureate and Caltech President David Baltimore commented: “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.) Baltimore was saying that 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. Biologists and computer scientists today collaborate closely as they seek to understand, and eventually to influence, those natural information processes. Biology was not the only field to say this. Physicists 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 nature’s computational method for combining quantum particle interactions. In the early 1980s, computational scientists at NASA-Ames discovered a successful,methane-resistant heat shield material for the Jupiter Probe by computing its molecular structure from the Schroedinger Equation.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. Economists analyze economic systems for their inherent information flows. Management scientists claim workflow,commitments, and social networks as fundamental information processes in all organizations. Artists and humanists use computation for everything from analysis to the creation of new works. Web researchers have discovered new social behaviors and ways of computing by using the entire Web as their laboratory. Computing artifacts have become matters of style and culture (iPod, eBay,Wikipedia, Google, Playstation,Xbox, Wii, and much more). Even politicians are utilizing sophisticated social data analyses,computational gerrymandering,and blogging. Jeanette Wing has concluded that computational concepts are deeply embedded into everyday thinking in many fields . Computation is everywhere.

对计算本质认知的变革 阶段1 阶段2 阶段3 1940s 工具 1980s 方法 2000s 基本过程 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 “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.) REVOLUTION IN THE MAKING This revolution has been gestating for a long time. Its three main stages were tools (beginning in the 1940s), methods (beginning in the 1980s), and fundamental processes (beginning in the 2000s). In the 1940s, the era of the first electronic digital computers, 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. By the 1980s, computation had become utterly indispensable in many fields. It 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. This idea was so powerful that, in 1989, the U.S. Congress passed into law the High Performance Computing and Communication Initiative to stimulate technological advances through high-performance computation. By 2000, computation had advanced further. Scientists from many fields were saying they had discovered information processes in the deep structures of their fields. Nobel Laureate and Caltech President David Baltimore commented: “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.) Baltimore was saying that 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. Biologists and computer scientists today collaborate closely as they seek to understand, and eventually to influence, those natural information processes. Biology was not the only field to say this. Physicists 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 nature’s computational method for combining quantum particle interactions. In the early 1980s, computational scientists at NASA-Ames discovered a successful,methane-resistant heat shield material for the Jupiter Probe by computing its molecular structure from the Schroedinger Equation.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. Economists analyze economic systems for their inherent information flows. Management scientists claim workflow,commitments, and social networks as fundamental information processes in all organizations. Artists and humanists use computation for everything from analysis to the creation of new works. Web researchers have discovered new social behaviors and ways of computing by using the entire Web as their laboratory. Computing artifacts have become matters of style and culture (iPod, eBay,Wikipedia, Google, Playstation,Xbox, Wii, and much more). Even politicians are utilizing sophisticated social data analyses,computational gerrymandering,and blogging. Jeanette Wing has concluded that computational concepts are deeply embedded into everyday thinking in many fields . Computation is everywhere.

Natural information processes 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 Physicists 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 nature’s 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 Galileo’s 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. 大自然早就学会了如何对信息进行编码的DNA,然后对生物体产生新生物从DNA通过它自己的计算方法 quantum electrodynamics 基本翻译 n. [量子] 量子电动力学 网络释义 quantum electrodynamics:量子电动力学

相关学科发展背景

中国至2050年信息科技发展路线图 发展泛在的信息科学技术，构建泛在的信息网络，重点围绕无处不在的网络信息技术应用，信息基础设施升级换代，信息器件、设备与软件的变革性突破，新信息科学与前沿交叉科学等四个层次进行战略安排。

2020年前后 突破低成本器件和系统设计技术，物理世界的新型感知机理、语义检索和分析技术等。 发展可扩展、高可信的下一代互联网和自组织的无线传感网络，积极推进三网融合。 按照延续、扩展和跨越摩尔定律三条途径发展微电子技术和新型信息器件，突破多核芯片设计、片上光互联和片上大规模光计算、艾级（1018）超级计算技术等。 突破网络科学、分布式交互算法设计理论、大规模工业软件、自然的人机界面、蛋白质结构预测等；构建“平行社会”系统。

2035年前后 突破网络信息理论、网络算法理论、网络计算模型等。 建立可持续网络服务体系，突破低功耗芯片和系统设计、实用的知识本体与知识网格技术等。 实现超越TCP/IP的未来网络和具有感知与认知能力的无线通信系统，突破分组交换的全光网络技术等。 突破纳米、量子等变革性器件和电路技术，实现泽级（1021）超级计算，软件开发成本平均每两年降低50%。 突破可信计算系统、情感理解技术等；构建人类基因组差异数据库。

2050年前后 建立普适的信息科学，计算成为自然系统、人造系统、社会系统领域的基本思维方式； 构建可持续发展的计算基础设施和应用服务； 继计算与网络融合、计算与物理系统融合之后，脑科学与认知科学取得重大突破，实现计算与智能的融合，形成较成熟的信息科学。

Computational Lens

三栖学者 理查德·卡普（Richard Karp）教授现任美国加州大学伯克利分校计算机科学讲座教授，美国科学院、美国工程院、美国艺术与科学院、欧洲科学院院士。因其在计算机科学领域的基础贡献曾获图灵奖、冯诺依曼奖、美国国家科学勋章、哈佛大学百年奖章等奖项，还担任美国科学院会刊（PNAS）等多个国际著名刊物编委。 卡普之所以被称为“三栖学者”是因为他知识渊博，贯通多个学科专业，因而同时被加州大学伯克利分校的电气工程和计算机系、数学系以及工业工程和运筹学系三个系聘为教授。 卡普被授予图灵奖，是因为他在算法的设计与分析、计算复杂性理论、随机化算法等诸多方面作出了创造性贡献。 生物信息学的开创人 Bio information bio engineering的创始人

Richard M. Karp提出的“计算透镜”（Computational Lens）理念被认为是未来二十年计算机科学可能的发展方向之一。 其核心理念是将计算作为一种通用的思维方式，通过这种广义的计算（涉及信息处理、执行算法、关注复杂度）来描述各类自然过程和社会过程，从而解决各个学科的问题。 这一理念试图将计算机科学由最初的数值计算工具、仿真与可视化技术以及后来基于网络、面向多学科的e-Science平台，变成普遍适用于自然和社会领域的通用思维模式。 计算科学是一门正在兴起的综合性学科，它依赖于先进的计算机及计算技术对理论科学、大型实验、观测数据、应用科学、国防以及社会科学进行模型化、模拟与仿真、计算等。特别是对极复杂系统进行模型与程序化，然后利用计算机给出严格理论及实验无法达到的过程数据或者直接模拟出整个复杂过程的演变或者预测过程的发展趋势。对基础科学、应用科学、国防科学、社会科学以及工程技术等的发展有着不可估量的科学作用与经济效益。

Computational Social Science 计算社会科学

Computational Social Science 6 FEBRUARY 2009 VOL 323 SCIENCE David Lazer,Alex Pentland,Lada Adamic, Sinan Aral,Albert-László Barabási,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 California–San Diego, Columbia University, Cornell University, Boston University

文章从计算社会科学的数据获取、研究方法、制约因素、人才培养4个方面，描述了计算社会科学的发展、讨论了社会科学研究的特点等。 《Science》2009年2月发表的一篇关于计算社会科学的文章《ComputationalSocial Science》，该文由美国11个大学及研究机构的共15名研究人员共同编写。 文章从计算社会科学的数据获取、研究方法、制约因素、人才培养4个方面，描述了计算社会科学的发展、讨论了社会科学研究的特点等。 其主要目的是想借此文向广大读者介绍计算社会科学这一学科理念，推动、提高社会科学研究水平，进一步繁荣社会科学研究工作。 计算科学是一门正在兴起的综合性学科，它依赖于先进的计算机及计算技术对理论科学、大型实验、观测数据、应用科学、国防以及社会科学进行模型化、模拟与仿真、计算等。特别是对极复杂系统进行模型与程序化，然后利用计算机给出严格理论及实验无法达到的过程数据或者直接模拟出整个复杂过程的演变或者预测过程的发展趋势。对基础科学、应用科学、国防科学、社会科学以及工程技术等的发展有着不可估量的科学作用与经济效益。

数字印记（Digital Traces) 目前人们广泛地以各种不同形式、方式生活在各种网络中： 人们频繁地检查电子邮件和使用搜索引擎 随时随地拨打移动电话和发送短信 每天刷卡乘坐交通工具 经常使用信用卡购买商品。 写博客、发微薄、通过SNS来维护人际关系 在公共场所，监视器可以记录人们的活动情况 在医院，人们的医疗记录以数字形式被保存 以上的种种事情都留下了人们的数字印记（踪迹）。 目前人们广泛地以各种不同形式、方式生活在各种网络中，人们频繁地检查电子邮件和使用搜索引擎，随时随地拨打移动电话和发送短信，每天刷卡乘坐交通工具，经常使用信用卡购买商品。写博客、发微薄、通过SNS来维护人际关系。在公共场所，监视器可以记录人们的活动情况；在医院，人们的医疗记录以数字形式被保存。以上的种种事情都留下了人们的数字印记（踪迹）。 Facebook公司为世界上最大的社交网络，一天积聚的数据比很多大公司一年产生的数据还要多。 截止2008年存储了30千万亿字节（30PB）的数据，大概是Library of Congress存储信息数量的3000倍。在2009年Facebook每天会产生25 Terabytes 的日志数据（Log Data）。

这些数据中蕴含的关于个人和群体行为的规律可能足以改变我们对个人生活、组织机构乃至整个社会的认知。 相比较生物和物理等其他学科领域，数据驱动的“计算社会科学”要出现的晚一些，而随着对这种大量社会数据的记录和分析，就逐步产生了计算社会科学。 随着信息化和网络化的不断普及与深入，社会动态变化的速度和规模已经提高到一个前所未有的水平，计算社会科学成为新的热点。 定义 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. 一个新兴的领域：利用大规模数据收集和分析能力揭示个人和群体的行为模式。 Existing ways of conceiving human behavior were developed without access to terabytes of data describing minute-by-minute interactions and locations of entire populations of individuals. For example, what does existing sociological network theory, built mostly on a foundation of one-time “snapshot” data, typically with only dozens of people, tell us about massively longitudinal data sets of millions of people, including location, financial transactions, and communications? These vast, emerging data sets on how people interact surely offer qualitatively new perspectives on collective human behavior, but our current paradigms may not be receptive.

与传统社会科学通过问卷调查形式获得的数据不同，我们可以借助以上种种新技术获得长时间的、连续的、大量人群的各种行为和互动的数据。 这些数据为研究动态的人际交流、大型社会网络的演化等方面的问题提供了坚实的基础。 例如： 可以通过电子邮件的记录研究一个群体是趋向稳定还是趋向变化、成员之间什么样的交流模式有利于提高效率、接收信息的多样化是否会提高成员的活力和表现等问题； 可以通过给成员佩戴实时记录位置、移动等信息的小电子装置收集数据，研究成员的流动和相互交流的模式对于团体产出的影响； 可以通过电子商务网站的查询和交易记录，以及网上电话记录等范围覆盖全球的人际互动数据研究人际互动在经济生产力、公众健康等方面产生的影响； 可以利用互联网上的搜索和浏览记录研究什么是当前公众关心的焦点； 可以通过网络社区上的帖子研究个体在网络中的位置对他们的品味爱好、情绪和健康的影响； 可以通过移动电话追踪人们的位置，研究传染病的传播等等。

Agent-based-Modelling

Why did nobody notice it？

A group of eminent economists has come to the Queen's rescue after she asked why no one had predicted the credit crunch during a visit to the London School of Economics in November. Luis Garicano at LSE shows Queen Elizabeth II a chart explaining how the credit crunch was caused.

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。 该文认为，传统的经济模型已经失败了多次，到现在为止，在没有任何前期试验下，我们还在建立新的经济估算；专家之间的不同知识，可以互撞，并产生新的知识；基于智能体的建模也许可以来预防下一次金融危机。 the model currently represents some 10 million households,100,000 firms and about 100 banks EURACE是欧盟经济体共同投资开发中的研究欧盟宏观经济政策的仿真系统。其主要科学目标是建立一个以微观经济为基础的宏观经济分析框架，提供分析全球规则涌现的新视角。其主要的社会目标是通过仿真分析财政政策和货币政策的协调、外部环境震荡下稳定宏观经济的政策、鼓励科技变革和创新等经济政策的影响，以不断调整和改善经济政策 在EURACE平台中，其市场的构建分为劳动力市场、资本产品市场和消费品市场，以及能源市场和信贷消费市场，并且这些市场之间是相互交互的 At the University of Genoa in Italy, meanwhile,Silvano Cincotti and his colleagues are creating an agent-based model of the entire European Union economy. Their model includes markets for consumer goods and financial assets, firms that interact with banks to obtain loans, and banks that compete with one another by offering different interest rates. Based on real economic data, the model currently represents some 10 million households,100,000 firms and about 100 banks, all of which can learn and change their strategies if they find more profitable ways of doing business.

在IT高度发达的今天，人们会想当然地假定，奥巴马及其经济团队会采用高超的计算模型来指引美国走出危机。 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能够在劳动力市场、产品市场、债券市场和信贷市场上进行活动，衍生出各种不同的市场情景和极端风险事件，为国家的政策制定和风险管理提供有利的工具 The models simulate the simultaneous operations and interactions of multiple agents, in an attempt to re-create and predict the appearance of complex phenomena. The process is one of emergence from the lower (micro) level of systems to a higher (macro) level. As such, a key notion is that simple behavioral rules generate complex behavior. This principle, known as K.I.S.S. ("Keep it simple and short") is extensively adopted in the modeling community. Another central tenet is that the whole is greater than the sum of the parts. Individual agents are typically characterized as boundedly rational, presumed to be acting in what they perceive as their own interests, such as reproduction, economic benefit, or social status,[2] using heuristics or simple decision-making rules. ABM agents may experience "learning", adaptation, and reproduction.[3]

通过网络实现的科学发现与技术创新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） 其基本目的是从大量的、杂乱无章的、难以理解的数据中抽取并推导出对于某些特定的人们来说是有价值、有意义的知识,并作为决策的依据。 数据大致可分成结构化数据和非结构化数据 难点 判定一个数据集里面含不含某种知识 如何发现其中的知识 知识如何表示。 已发现的知识与实际蕴藏的知识之间的关系。

Nontraditional Challenges Traditionally Cope with the complexity of the problem Massive Data Sets Cope with the complexity of the data 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?

用大数据集描述，模拟，分析和验证复杂系统 例：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 Earth's 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.

汇报提纲 缘与使命 对计算本质认识的变革 计算思维主要定义 对问题求解的认识引起对计算机教学的再认识 计算机学科的本质特点 计算思维操作性定义

Jeannette Wing’s definition(s) 2006 CT CACM 49, 33–35. CT involves solving problems, designing systems, and understanding human behavior, by drawing on the concepts fundamental to computer science. To flourish in today's 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 Computational thinking means creating and making use of different levels of abstraction, to understand and solve problems more effectively. Computational thinking means thinking algorithmically and with the ability to apply mathematical concepts such as induction to develop more efficient, fair, and secure solutions. Computational thinking means understanding the consequences of scale, not only for reasons of efficiency but also for economic and social reasons From Jeannette M. Wing

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 mechanization [,mekənai'zeiʃən, -ni'z-] 基本翻译 n. 机械化；机动化 From Jeannette M. Wing

Two A’s 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 CT==Computing NOT Computer literacy, i.e., how to use Word and Excel or even Google Computer programming, i.e., beyond Java Programming 101 audacity [ɔ:'dæsəti] 基本翻译 n. 厚颜无耻；大胆 scale [skeil] n. 刻度；比例；数值范围；天平；规模；鳞 vi. 攀登；衡量；生水垢；剥落 vt. 攀登；测量；刮鳞；依比例决定 From Jeannette M. Wing

计算思维是与形式化问题及其解决方案相关的一个思维过程，其解决问题的表示形式应该能有效地被信息处理代理执行 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.    计算思维是与形式化问题及其解决方案相关的一个思维过程，其解决问题的表示形式应该能有效地被信息处理代理执行 合理抽象 高效算法（算法思维角度） 合理建模 高效实施（工程思维角度） demystifying [di:ˈmistifaiŋ] 生词本 简明释义 v. 使非神秘化( demystify的现在分词 )

NSF Cyber-Enabled Discovery and Innovation (CDI) is NSF’s 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 Nation’s 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. CT是全面的定义包含计算的 基本认识 概念、方法、模型、算法和工具。

ISTE&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 computer and other tools to help solve them ▪Logically organizing and analyzing data ▪Representing data through abstractions, such as models and simulations ▪Automating solutions through algorithmic thinking (a series of ordered steps) ▪Identifying, analyzing, and implementing possible solutions with the goal of achieving the most efficient and effective combination of steps and resources ▪Generalizing and transferring this problem-solving process to a wide variety of problems 国际教育技术协会(ISTE)和计算机科学教师协会(CSTA)于2011年通过给计算思维的各要素作描述的方式，下了一个操作性的定义，即计算思维是一个问题解决的过程，该过程包括以下特点： 1.制定问题，并能够利用计算机和其他工具来帮助解决该问题； 2.要符合逻辑地组织和分析数据； 3.通过抽象，如模型、仿真等，再现数据； 4.通过算法思想（一系列有序的步骤），支持自动化的解决方案； 5.识别、分析和实施可能的解决方案，找到最有效的方案，并且有效结合这些步骤和资源； 6.将该问题的求解过程进行推广并移植到更广泛的问题中。 formulating 基本翻译 v. 使公式化；系统地阐述；制定…的配方（formulate的ing形式）

Themes characteristic Dispositions or attitudes that are essential dimensions of CT： Confidence in dealing with complexity ▪ Persistence in working with difficult problems ▪ Tolerance for ambiguity ▪ The ability to deal with open-ended problems ▪ The ability to communicate and work with others to achieve a common goal or solution 意志品质和态度的培养

中国学者1992年关于“计算思维”的定义 “计算思维就是思维过程或功能的计算模拟方法论，其研究的目的是提供适当的方法，使人们能借助现代和将来的计算机，逐步达到人工智能的较高目标。” 王飞跃院士的定义 广义计算思维：基于可计算的手段，以定量化的方式进行的思维过程。 狭义计算思维：数据驱动的思维过程（Data-driven Thinking）。

汇报提纲 缘与使命 对计算本质认识的变革 计算思维主要定义 对问题求解的认识引起对计算机教学的再认识 计算机学科的本质特点 计算思维操作性定义

求解问题需要什么？ 三要素 求解问题依赖于 过程 表示 经验 常识（常识性的过程、非规范的表示、朴素思想指导下的经验） 科学知识 （合理的过程、形式化的描述、专家经验） 常识性的不值得教，学生也觉得乏味，但求解问题需要，学生不自觉地能进行应用

Understand the problem 问题求解过程 George Polya How to Solve It ，A New Aspect of Mathematical Method Understand the problem Devise a plan Carry out the plan Look back 太不值得教了- 学时的珍贵性和稀缺性 Real Domain Abstract Model Abstract Machine Real Machine Understand the problem Devise a plan Carry out the plan Look back

Computer Problem-Solving Analysis and Specification Phase Analyze Specification Algorithm Development Phase Develop algorithm Test algorithm Implementation Phase Code algorithm Maintenance Phase Use Maintain

朴素思想与科学 面向对象的分析与设计 OOAD 用UML进行面向对象的分析与设计 OOAD with UML 遵循UP过程的用UML进行面向对象的分析与设计 OOAD with UML by UP 在6个最佳实践指导下的遵循UP过程的用UML进行面向对象的分析与设计 OOAD with UML by UP guided by SIX best practice

Diagrams Are Views of a Model A model is a complete description of a system from a particular perspective It is not necessary to discuss any of these diagrams in detail. The points to make are: 1. More than one diagram is necessary to represent software 2. The UML has made a tremendous contribution in giving us a common visual language to express these models. All of these diagrams can be created using Rational Rose with the exception of the activity diagrams. Deployment Diagrams use-case Scenario Sequence State Component Models Object Collaboration Activity Class The UML provides a rich notation for visualizing our models. This includes the following key diagrams: use-case diagrams to illustrate user interactions with the system. Class diagrams to illustrate logical structure. Object diagrams to illustrate objects and links. State diagrams to illustrate behavior. Component diagrams to illustrate physical structure of the software. Deployment diagrams to show the mapping of software to hardware configurations. Interaction diagrams (i.e., collaboration and sequence diagrams) to illustrate behavior. Activity diagrams to illustrate the flow of events in a use-case. Module 1 - Best Practices of Software Engineering

Traditional Waterfall Development To illustrate a problem with the waterfall model: Suppose you estimate that the project will take 2 years and it really takes 3 years. At the end of 2 years what do I have? Nothing useful works. I have nothing that could be delivered as an early (partial) release. Diagrams and models are great, but they can’t execute. Requirements Analysis Design Code & Unit Testing Subsystem Testing Software has been developed using the waterfall model for more than 30 years. The concepts are familiar to most developers and most project plans are developed with the waterfall in mind. The basic concept is that the entire system goes through the phases linearly and in lock step. First all the requirements are defined, then the design is completed. Finally, code is written and tested. The key assumptions are that when design begins, requirements no longer change. When coding starts, the design ceases to change. These assumptions are, of course, incorrect. Hence problems result and software is late, over budget, and/or unacceptable. System Testing T I M E Module 1 - Best Practices of Software Engineering

Preliminary Iteration(s) Unified Process Phases The iterative model is another key graphic that we will come back to again and again. You can introduce some humor by telling the students that internally we call it the “humpback” chart since to some people the color areas look like a herd of migrating whales. It is a good idea to take a vertical slice and point out how all of the workflows are included to a greater or lesser extent. This is the mini- waterfall. Process Workflows Inception Elaboration Construction Transition Business Modeling Requirements Analysis & Design Implementation Test Deployment Supporting Workflows Configuration & Change Mgmt The iterative approach is supported by the Rational Unified Process (RUP), a full lifecycle software engineering process which embodies all of Rational’s recommended best practices together with the Unified Modeling Language (UML). RUP provides detailed instructions on how to develop a system iteratively. RUP describes the activities, workers, and artifacts of each iteration. It places the iterations in the context of a software development cycle consisting of four phases with well-defined objectives, boundaries, and milestones. RUP will be described in detail in a later module in this course. Note that the process workflows shown in the graphic depicting the iterative model match the waterfall very closely. Taking a vertical slice corresponding to one iteration, one can see that all of the workflows apply to each iteration, although the relative emphasis shifts from phase to phase. We will come back to the iterative model graphic frequently throughout the course in explaining how the iterative approach is applied in practice. It is our roadmap into the process. Project Management Environment Preliminary Iteration(s) Iter. #1 Iter. #2 Iter. #n Iter. #n+1 Iter. #n+2 Iter. #m Iter. #m+1 Iterations Module 1 - Best Practices of Software Engineering

Best Practices of Software Engineering Develop Iteratively Use Component Architectures Manage Requirements Verify Quality Model Visually Control Changes In the remainder of this module, we describe recommended software development practices and give the reasons for these recommendations. We will use this key graphic again and again in presenting the 6 best practices. 三要素 Module 1 - Best Practices of Software Engineering

大学的课堂应该教什么？ 抽象（abstraction）

Different Abstraction 抽象化(Abstraction)是指以缩减一个概念或是一个现象的资讯含量来将其广义化(Generalization)的过程，主要是为了只保存和一特定目的有关的资讯。例如，将一个皮制的足球抽象化成一个球，只保留一般球的属性和行为等资讯。相似地，亦可以将快乐抽象化成一种情绪，以减少其在情绪中所含的资讯量。 Abstraction (computer science), a process of hiding details of implementation in programs and data Abstraction layers, an application of abstraction in computing Hardware abstraction, an abstraction layer on top of hardware Abstraction (linguistics) Abstraction (mathematics), a process of removing the dependence of a mathematical concept on real-world objects Lambda abstraction, a kind of term in lambda calculus Abstraction (sociology), a process of considering sociological concepts at a more theoretical level

exponent Confidence in dealing with complexity Abstraction is a process or result of generalization, removal of properties, or distancing of ideas from objects. The first emphasizes the process of removing detail to simplify and focus attention based on the definitions: • The act of withdrawing or removing something, • The act or process of leaving out of consideration one or more properties of a complex object so as to attend to others. The second emphasizes the process of generalization to identify the common core or essence based on the definitions: The process of formulating general concepts by abstracting common properties of instances A general concept formed by extracting common features from specific examples. 什么是抽象？为什么它这么重要？ 从抽象的定义[10]来看，我们重点关注两个特别相关的方面1。首先，强调的去除详细 1看到一个有趣的有关抽象的讨论[3]。   的定义的基础上，以简化和集中注意力的过程： ·撤回或删除东西的行为， ·考虑留下一个复杂的对象的一个或多个正确关系的行为或过程，从而加入其他对象。 第二，强调过程的泛化识别的基础上，共同的核心或本质。定义： ·过程制定的一般概念，抽象常见的实例的适当关系， ·从具体的例子的功能，提取共同形成一个笼统的概念。 exponent Confidence in dealing with complexity Result and it’s representation

Sample Classes of Computational Abstractions • Algorithms – E.g., mergesort, binary search, string matching, clustering • Data Structures – E.g., sequences(stack,queue), tables, trees, graphs, networks • State Machines – E.g., finite automata, Turing machines • Languages – E.g., regular expressions, …, VDM, Z, …, ML, Haskell, …, Java, Perl • Logics and semantics – E.g., Hoare triples, temporal logic, modal logics, lambda calculus • Heuristics – E.g., A* (best-first graph search), caching • Control Structures – Parallel/sequential composition, iteration, recursion • Communication – E.g., synchronous/asynchronous, broadcast/P2P, RPC, shared memory/message-passing • Architectures – E.g., layered, hierarchical, pipeline, blackboard, feedback loop, client-server, parallel, distributed • … Abstract Data Type Abstract type（Class)

朴素思想与科学 散列法 遗传算法 牛顿迭代法 设计模式 体系结构风格 算法理解的偏差 仅了解算法的形式 不了解算法的思想 庸俗的步骤 有利 对简单问题是有效的，杀鸡焉用牛刀 有弊 水文测报协议 软件开发 数据库表 算法理解的偏差 仅了解算法的形式 不了解算法的思想 庸俗的步骤 庸俗的3层结构 Hash GA

哪个网页最重要？ 路由算法-距离向量算法

常识在求解问题中的作用 不同实现和厂家 网络是复杂的! 诸多 “成分”: 主机 路由器 异质问题 各种介质的链路 应用程序 协议 硬件, 软件

异质性问题解决方法？？ 分层目的 分解和委托 解决异质性问题采用的是分层方法。把复杂的网络互联问题划分为若干个较小的、单一的问题，在不同层上予以解决,这样可以提高互操作性又能减小理解难度。我们将计算机网络层次结构和各层协议的集合，定义为计算机网络体系结构。 分层目的 结构清晰 简化设计与实现 便于更新与维护 较强的独立性和适应性

求解问题的“武功”级别 大学的应该教什么？ 科学体系，专业知识 非朴素思维、常识 级别（5级） 级别搞混了 问题特点 利用常识（朴素知识）求解问题 利用专门知识（各阶段）求解问题的过程 小学数学、初中数学、高中数学、大学数学 小学计算机、初中计算机、高中计算机、大学计算机 利用计算科学的基本概念求解值得计算机求解的问题 利用计算科学的基本概念求解值得计算机求解的可计算的问题 Thinking about problems as if computers will solve them Thinking about problems in terms of computational concepts 利用计算科学的基本概念求看似不可解但实质上能求解的问题（新鲜） 级别搞混了 问题特点 多种类型：算法类问题、系统类问题、数据类问题、交互类问题 复杂程度（规模、病态） 一个令人困惑的、痛苦的、棘手、悬而未决的问题 具有鲜明的计算学科特点，学科才能立足，学科才能发展 大学的应该教什么？ 科学体系，专业知识 非朴素思维、常识 一个令人困惑的、痛苦的、棘手,也没有悬而未决的问题 挑战性： 用ct解决新问题，科学问题 同学认为不不能解决的、难解的问题 多维度的计算思维 CT的培养是个漫长的过程，是个终生学习的过程 计算机科学家具有应用CT在计算平台上来解决问题的能力。而这些能力的培养是从早期计算机科学教育开始，经过了程序设计、算法分析、操作系统、数据库和软件工程等课程的学习和训练，甚至在他们今后的职业生涯中继续发展和养成。 从教学的角度应该分阶段地将CT的培养纳入到幼儿、小学、中学、大学、职业当中。

挑战性 用ct解决新问题，科学问题 同学认为不不能解决的、难解的问题 激发学生兴趣

汇报提纲 缘与使命 对计算本质认识的变革 计算思维主要定义 对问题求解的认识引起对计算机教学的再认识 计算机学科的本质特点 计算思维操作性定义

“菜刀科学”与“计算机科学”-陈道蓄 以色列学者哈雷尔在《算法学：计算的本质》一书中提出这样的问题： 天文学=望远镜 即使是菜刀这样的工具，也会涉及科学、技术、工程和应用的各个层面。菜刀过于简单，其他学科的知识足够它的需要了，因此没有什么“菜刀科学”。 以色列学者哈雷尔在《算法学：计算的本质》一书中提出这样的问题： 论技术的影响，电话也很大，为什么没有电话科学？论技术复杂性，人造卫星很复杂，为什么没有被广泛接受的人造卫星科学。他认为其实计算机是计算的工具，用计算机给这门科学命名，就像用“手术刀科学”给外科学命名一样地不合适。 天文学=望远镜

计算的技术进步（多层的封装，摩尔定律）使得计算机的使用平民化和傻瓜化 每个人都将计算机当作工具用，大家对计算机非常熟悉，直观地知道计算机功能 对比核技术、化工技术、机械工程计算机完全没有了神秘感 人人能说我是搞计算机的 许多人有一种看法：“计算机只不过是工具”，其后面隐含的话就是“主要就是应用”。 这本身没有什么不对，但用它来作为计算机学科定位的出发点就会产生极大的误导。

计算机则不然，它涉及了科学、技术、工程和应用等众多复杂的内容。 一般认为美国卡内基梅隆大学在首位图灵奖得主佩利的领导下建立了最早的计算机科学系 当计算机科学这门新学科出现时主要内容就是“算法”和“形式系统”，是“程序设计的科学”，不是现在大众理解的“编程”。 从1966年开始到2003年共颁奖38届，有47位获奖人，其中有15人主要成果涉及形式系统与程序设计语言和方法，有14人主要成果涉及计算机算法及其复杂性理论。 在计算机科学学科出现近70年后，随着计算环境的发展，有很多还不清楚的问题需要我们去发现其答案。 例如Internet已经发展成一个客观存在，但我们对其中数据与服务的分布、需求的模式、协同方式等等还了解很少，即使是传统的算法领域，很多问题还没有解答。 软件本身日益复杂，如什么是合理的体系结构等等，这些方面的新知识将大大加深我们对计算机软件系统及其有效性的理解。

学科存在性证明 计算机科学应该是试图发现一类非自然结构的内在规律的学科，这类结构中涉及的现象(既非纯粹的自然现象，又非一般意义上的社会现象)的解释不能在已有的学科中得到。 “终极”问题 每个科学学科都有其所谓的“终极”问题。 计算机科学的“终极”问题被认为是“什么可以被自动地计算？”

计算机科学 计算机科学是研究计算机以及它们能干什么的一门学科。它研究抽象计算机的能力与局限，真实计算机的构造与特征，以及用于求解问题的数不清的计算机应用。 涉及符号及其操作 涉及多种抽象概念的创造和操作 创造并研究算法 创造各种人工结构，尤其是不受物理定律限制的结构 利用并应对指数增长 探索计算能力的基本极限 关注与人类智能相关的复杂的、分析的、理性的活动 National Research Council Committee on Fundamentals of Computer Science, Computer Science: Reflections on the Field, The National Academies Press, Washington D.C., 2004. 78

计算机学科的本质-个人认知 以简单的有限的离散构造解决无限的问题 以简单的有穷的离散构造解决无穷的问题 手段 有限（穷）-无限（穷） 可数（可列）无穷 递归函数-以有穷构造无穷的必由之路 手段 过程 递归过程 结构 递归结构

构造举例 谓词合适公式的定义 在谓词演算中合适公式的递归定义如下： (1) 原子谓词公式是合适公式。 　　在谓词演算中合适公式的递归定义如下： 　　(1) 原子谓词公式是合适公式。 　　(2) 若A为合适公式，则～A也是一个合适公式。 　　(3) 若A和B都是合适公式，则(A∧B)，(A∨B)，(A=>B)和(A←→B)也都是合适公式。 　　(4) 若A是合适公式，x为A中的自由变元，则(x)A和(x)A都是合适公式。 　　(5) 只有按上述规则(1)至(4)求得的那些公式，才是合适公式。

Koch curve A variant of the Koch curve which uses only right-angles. variables : F constants : + − start : F rules : (F → F+F−F−F+F) Here, F means "draw forward", + means "turn left 90°", and − means "turn right 90°" Lindenmayer System简称L-System是1968年由匈牙利生物学家Lindenmayer提出的有关生长发展中的细胞交互作用的数学模型，尤其被广泛应用于植物生长过程的研究。 L-system是一个相似重写系统，是一系列不同形式的正规语法规则，多被用于植物生长过程建模，但是也被用于模拟各种生物体的形态。L-system也能用于生成自相似的分形，例如迭代函数系统。

一个形式文法 G 是下述元素构成的一个四元组(N, Σ, P, S)： “非终结符号”集合 N。 “终结符号”集合 Σ ，Σ 与 N 无交。 “起始符号”S，S 属于 N。 一个由形式文法 G = (N, Σ, P, S) 产生的语言是所有如下形式的字符串集合，这些字符串全部由“终结符号”集 Σ 中符号构成，并且可以从“初始符号”S 出发，不断应用 P 中的“产生式规则”而得到。 考虑如下的文法 G ，其中 N = {S, B}, Σ = {a, b, c}, P 包含下述规则 1. S -> aBSc 2. S -> abc 3. Ba -> aB 4. Bb -> bb 非终结符号 S 作为初始符号。下面给出字串推导的例子：（推导使用的产生规则用括号标出，替换的字串用黑体标出） S -> (2) abc S -> (1) aBSc -> (2) aBabcc -> (3) aaBbcc -> (4) aabbcc S -> (1) aBSc -> (1) aBaBScc -> (2) aBaBabccc -> (3) aaBBabccc -> (3) aaBaBbccc -> (3) aaaBBbccc -> (4) aaaBbbccc -> (4) aaabbbccc 很清楚这个文法定义了语言 { anbncn | n > 0 } ，这里 an 表示含有 n 个 a 的字串。

极简的离散构造示例 计算模型-TS TM CA TS:Tag System 标记系统 TM:Turing Machine 图灵机 CA:cellular Automata 元胞自动机

图灵机 A.Turing在1936年介绍了这样一个通用的计算模型，该模 型具有以下两个性质 该模型的每个过程都是有穷可描述的； 过程必须是由离散的、可以机械执行的步骤组成。 图灵机是计算机的一种简单数字模型，尽管简单，但它具 有模拟通用计算机的计算能力。 通过研究TM来研究递归可枚举集和部分递归函数 为算法和可计算性研究提供了形式化描述工具。

应当 尽可能简单 而不是 比较简单地 做每一件事. ——A.爱因斯坦 元胞自动机 Cellular automata-CA是现代计算机之父Von Neumann提出的想法 Stephen Wolfram却将这种带有强烈的纯游戏色彩的原始想法从学术上加以分类整理，并使之最终上升到了科学方法论。 元胞自动机的基础就在于“如果让计算机反复地计算极其简单的运算法则，那么就可以使之发展成为异常复杂的模型，并可以解释自然界中的所有现象”的观点。   应当 尽可能简单 而不是 比较简单地 做每一件事. 　　　　　　——A.爱因斯坦 20世纪50年代，John von Neumann 最早提出； (von Neumann,J.1963，collected works, edited by A.H.Taub) 1970年，John Conway 提出生命游戏 (Conway, J. (1970). In M. Gardner, (Ed.), Scientific American, 223(4), pp. 120-123.) 1983年，Stephen Wolfram 初等元胞自动机 (Stephen Wolfram. Reviews of Modern Physics,1983,Vol.55. Stephen Wolfram. Nature,1984,Vol.311) 1986年至今，理论及应用

元胞自动机的历史（History） Ironically Although von Neumann made many contributions and developments in CA, they are commonly referred to as “non-von Neumann style”, while the standard model of computation (CPU, globally addressable memory, serial processing) is know as “von Neumann style”.

KISS原则是英语 Keep It Simple, Stupid 的首字母缩略字，也有人称“懒人原则”。 原文当中有很多其他版本，包括：、"Keep It Sweet & Simple"、"Keep It Short & Simple"、"Keep it Simple, Sweetheart" 及 "Keep it Simple, Sherlock"。 ISO-OSI TCP/IP ATM CC2001

简单 为什么？ 有限（可表示，进而可自动化）的构造性（可演化为复杂） Abstraction and Automation

《一种新科学》 Stephen Wolfram. A New Kind of Science. Wolfram Media, 2002.

《一种新科学》 数千年来发展而成的全部科学从某种意义上讲，依赖的是一种完全无法预测的方法。 从物理学、化学、生物学到心理学，甚至各种社会学等现有学术领域本来就不应该进行如此分类。 这些科学领域中各种各样的现象，说到底实际上都在受同一种运算法则的支配，利用各种方法对此反复计算就可以生成各种领域的复杂现象。 Wolfram认为，“支持整个宇宙的原理无非就是区区几行程序代码”。  从“完全打破现有的学术体系，按照完全不同的原理来理解自然界”的意义出发，新作被命名为《一种新科学》。   　　   

计算机万能理论 Wolfram认为： 以物理学和数学为中心的传统科学是以方程式为基础而演绎推导出来的 计算机万能理论   Wolfram认为： 以物理学和数学为中心的传统科学是以方程式为基础而演绎推导出来的 计算机则是通过反复计算单纯的程序代码，也可以说是递归推导而出的。 在牛顿生活的17世纪，由于还没有像现在一样的先进计算机，因此当时的科学家不得不依赖于演绎的方法(算式计算)。这一切也可以说是历史上的必然、科学上的偶然。 真正意义上的正确的科学方法是利用像现有那样的计算机来进行的算法运算。 

汇报提纲 缘与使命 对计算本质认识的变革 计算思维主要定义 对问题求解的认识引起对计算机教学的再认识 计算机学科的本质特点 计算思维操作性定义

Several Definitions of CT，Why？ 计算思维存在多维、多态的复杂特征 来源多样：数学、科学、工程 求解问题是心理、认知、思维活动 学科在进化 显式与隐式-传道与悟道 Separation of Concern 本质上：计算思维的多维、多态的复杂特征决定了方案的多样性和差异性 本质上：计算思维的多维、多态的复杂特征决定了方案的多样性和差异性

基础来源 Computer Research Association, “Creating Environments for Computational Researcher Education,” 2010. CSTA “Computational Thinking Resource Set: A Problem-Solving Tool for Every Classroom.” Peter Denning,”Great principles of computing”,2007 Google Exploring Computational Thinking ,2010 The College Board, a new Advanced Placement (AP) course that covers the fundamental concepts of computing and computational thinking, www.csprinciples.org Computational thinking is a fundamental skill for everyone This course is not “Ways to Think Like a Computer Scientist” Why? Computational thinking is broader than what Computer Scientists do, borrowing from probability and statistics, economics, game theory, neuroscience, decision theory, physics, psychology… Computer Scientists, like other experts, “go deep” in their work: important and valuable, but rarely interdisciplinary

CRA-E White Paper-Cognitive Skills（31） 1) Abstractions - creating and validating 2)Algorithmic thinking - representing information, working with constraints and automating the process 3)Analysis - examining the components and structure of concepts, data, and research results 4)Approximations - estimating from data observations and representing in algorithmic form 5)Assumptions - identifying and validating 6)Automation - representing processes in terms of repeated operations such as iteration and recursion 7)Comparing and contrasting - identifying the way in which two or more things are similar and different. The basis for creating abstractions. 8)Critical reading and writing - close attention to the semantics of terms, unstated assumptions, and relationships with other work. Related work sections in research papers and reporting on papers in seminars provide training in this skill 9)Debugging - detecting pattern anomalies, using isolation strategies 10)Decomposing - complex entities into simpler ones

11)Designing - integrating user, performance, simplicity, and reliability concerns 12)Evaluating results in terms of assumptions and goals 13)Exploring - observing and identifying patterns for possible classification 14)Hypotheses - pattern recognition and assumption use in forming 15)Integrating disparate data and concepts 16)Interaction - identifying and representing different roles and their interrelationships; developing communication mechanisms among the different roles 17)Logical analysis of representation relationships 18)Parallel thinking - identifying sub-components that don't share dependencies 19)Patterns - recognition and classification 20)Planning - setting goals, developing strategies, and outlining tasks and schedules to accomplish the goal tinkering 基本翻译 n. 铸补，熔补 v. 做焊锅匠，笨拙的修补（tinker的现在分词形式） 网络释义 tinkering:铸补 | 工艺 | 钳工技能

25)Scaling - understanding time/space/and power constraints 21)Problem solving - working with time and space constraints, decomposing complex problems, 22)Rapid prototyping - integrating representation relationships, implementing, and evaluating the outcomes 23)Reasoning under uncertainty - reasoning and making decisions based on incomplete and/or uncertain data and models 24)Representing abstractions and their relationships through notations and language 25)Scaling - understanding time/space/and power constraints 26)Searching - focused exploration 27)Symbols and notations - representing and manipulating information and relationships 28)Synthesis - combining components of concepts, data, or research into a new construction 29)Tinkering - manipulating portions of existing entities 30)Tradeoffs - working with 31)Translating qualitative insights into computative representations tinkering [ˈtɪŋkərɪŋ] 生词本 简明释义 v. 做焊锅匠( tinker的现在分词 )； 焊补； 胡乱修补； 笨手笨脚地做某事

国际教育技术协会(ISTE)和计算机科学教师协会(CSTA) definition example Data Collection The process of gathering appropriate information Students develop a survey and collect both qualitative and quantitative data to answer the question: “Has global warming changed the quality of life?” Data Analysis Making sense of data, finding patterns, and drawing conclusions Use appropriate statistical methods that will best test the hypothesis: “Global warming has not changed the quality of life.” Data Representation Depicting and organizing data in appropriate graphs, charts, words, or images Groups of students represent the same data in different ways based on a position relating to the question: “Has global warming changed the quality of life?” Different representations may result in varying conclusions. Problem Decomposition Breaking down tasks into smaller,manageable parts Consider the large-scale problem: “What does it take to become a rock star?”Break it into smaller parts. Discuss what variables are within a student’s control and what variables are determined by outside factors. Abstraction Reducing complexity to define main idea Choose a period in politics that was most like the current one by analyzing the essential characteristics of the current period. Algorithms &Procedures Series of ordered steps taken to solve a problem or achieve some end. Discuss the decision-making process for choosing a college, then create an algorithm that describes that process.The algorithm will be able to handle unknown variables, such as where friends are attending, availabilty of financial aid, and admission success, to come to an unambiguous decision. Automation Having computers or machines do repetitive or tedious tasks. Debate the merits of learning skills and information that are rarely necessary today because of automation. These skills might include long division,deriving square roots, spelling, statistical formulas, memorizing historic dates, etc. Simulation Representation or model of a process. Simulation also involves running experiments using models. Create a spreadsheet to simulate the “Birthday Problem” (How many people must be in a room for there to be at least a 50% chance that at least two have the same birthday?). Use the same model to answer the question for three people having the same birthday. Parallelization Organize resources to simultaneously carry out tasks to reach a common goal. Describe the sequence of activities by each of the armies leading to the Battle of Waterloo. Include both physical activities (e.g., recruit troops) and intellectual activities (e.g., pick troop positions). 国际教育技术协会(ISTE)和计算机科学教师协会(CSTA) Data Collection Data Analysis Data Representation Problem Decomposition Abstraction Algorithms &Procedures Automation Simulation Parallelization

CT Vocabulary and Progression Chart

Algorithms &Procedures Definition Series of ordered steps taken to solve a problem or achieve some end. Grades PK to 2 Create a set of directions from the school to the major landmarks in the neighborhood. Grades 3 to 5 Design a board game and write instructions to play. Test instructions on peers trying to play the game. Refine instructions with feedback from peers who played the game. Grades 6 to 8 Program a robot to find its way out of a maze such that given any maze, the robot could exit successfully within a specified time period. Grades 9 to 12 Discuss the decision-making process for choosing a college, then create an algorithm that describes that process. The algorithm will be able to handle unknown variables, such as where friends are attending, availabilty of financial aid, and admission success, to come to an unambiguous decision

across multiple disciplines

Great Principles of Computing,1991,2003,2007 Peter James Denning

2003年版

2007年版 Computation (meaning and limits of computation) Communication (reliable data transmission) Coordination (cooperation among networked entities) Recollection (storage and retrieval of information) Automation (meaning and limits of automation) Evaluation (performance prediction and capacity planning) Design (building reliable software systems) These categories resulted from a functional analysis of many computing technologies and applications: Computing systems are built from processing elements that process and store information (computation, recollection); Processing elements exchange information (communication); Processing elements cooperate toward common goals (coordination); Humans delegate tasks to systems of processing elements (automation); Humans predict the speed and capacity of systems (evaluation); and Humans decompose systems into processing elements and organize their construction (design).

Google Computational thinking (CT) involves a set of problem-solving skills and techniques that software engineers use to write programs that underlie the computer applications you use such as search, email, and maps. However, computational thinking is applicable to nearly any subject. Students who learn computational thinking across the curriculum begin to see a relationship between different subjects as well as between school and life outside of the classroom. Specific computational thinking techniques include: problem decomposition, pattern recognition, pattern generalization to define abstractions or models, algorithm design, and data analysis and visualization. (6)

The College Boardwww.csprinciples.org Computational Thinking Practices Connecting Computing Developing computational artifacts Abstracting Analyzing problems and artifacts Communicating Working effectively in teams

Big Ideas Creativity: Computing is a creative activity. Abstraction: Abstraction reduces information and detail to facilitate focus on relevant concepts. Data: Data and information facilitate the creation of knowledge. Algorithms: Algorithms are used to develop and express solutions to computational problems. Programming: Programming enables problem solving, human expression, and creation of knowledge. Internet: The Internet pervades modern computing. Impact: Computing has global impacts. Creativity Abstraction Data. Algorithms Programming Internet Impact

CT操作性定义-李波 2012年1月 CT及问题求解 模型：抽象和表示 算法 信息编码与数据组织 网络与协作 计算机应用 智能系统

1. CT与问题求解 什么是CT 日常生活中的CT 问题及求解过程 问题分解、递归、近似和启发式求解问题 2 1.CT与问题求解 什么是CT 日常生活中的CT 问题及求解过程 问题分解、递归、近似和启发式求解问题 2.模型：抽象和表示 抽象：仅仅保留适当的细节 模型和抽象 模型的类型 表示：从可选（alternative）选择 模型和表示 模块化、封装、组件（使用定义良好的交互组件组织一个大型的系统） OO四原则 三个分析类

3.3算法思维：简单排序算法（选择、插入、Bubble排序） 3.4算法能做什么不能做什么？ 3.算法 3.1 算法的定义 3.2算法表示 伪代码 流程图 算法构造:赋值、条件、循环、子例程 3.3算法思维：简单排序算法（选择、插入、Bubble排序） 3.4算法能做什么不能做什么？ 3.4.1可计算地不可解问题（Computationally unsolvable problems） 3.4.2易解VS不易解问题（Tractable vs. intractable problems） 3.4.3NP-完全和可计算难题（Computational hard problems） 3.4.4近似算法 3.4.5 时空复杂度

4.信息编码与数据组织 编码和计数 选择合适的数据编码和理解他们容量和上限 数据组织 数组vs列表 3.5递归思维 3.5.1递归算法（递归算法性质、递归和数学归纳、汉诺塔问题） 3.5.2递归结构(递归设计、树数据结构、树的递归遍历） 3.6算法策略 3.6.1 穷举法 3.6.2贪心算法（TSP的贪心策略） 3.6.3分治算法（MergeSort vs. QuickSort） 3.6.4动态规划（重叠子问题、Fibonacci数、生物信息学中的动态规划） 3.6.5随机（概率）算法（随机数生成、蒙特卡洛方法） 3.6.6启发式算法（病毒检测作为一个计算机不能求解的问题，启发式和反病毒软件） 4.信息编码与数据组织 编码和计数 选择合适的数据编码和理解他们容量和上限   数据组织 数组vs列表 栈,队列,树和图 数据库术语

5.网络与协作 社会网络与图论 基本图论 社会网络分析 加密 对称密钥 公开密钥（大素数发现，通过难解性实现信息安全，数字签名及数字认证） 协作系统 并发 并行 6.计算机应用 信息检索 穷尽式搜索 启发式搜索 启发式排名 计算机仿真 模型设计 模型执行 执行分析 7.智能系统 计算机辅助决策制定 决策支持 专家系统 进化计算 遗传算法 遗传程序设计 群集智能 蚁群算法 计算机能思维吗？ 图灵测试 CAPTCHAs（逆向图灵测试）

11个知识大类、36个小类（其中含18个知识点）、49个知识点 CT操作性定义-李波 2012年7月 11个知识大类、36个小类（其中含18个知识点）、49个知识点 Computational models and constraints on computation Abstractions (levels of) Representation, approximation, and dealing with errors Processing techniques and their limitations Information, Knowledge, and Machine Learning Algorithmic thinking and problem analysis Data structures and algorithms Flow of control Transformation and Patterns Communication and coordination The human element 11个知识大类、36个小类（其中含18个知识点）、49个知识点

Algorithmic thinking and problem analysis Problem decomposition divide and conquer levels of abstractions Reasoning correctness, logics, invariants, verification, debugging Time and space constraints Abstractions (levels of) What to model salients, constraints, pitfalls in assumptions and in approximations How to model it what type multidisciplinary models How to implement the model solve analytically simulate kinds of simulation visualize the results Representation, approximation, and dealing with errors Data types of data to be represented representation techniques and formats, and their limitations Behavior

Processing techniques and their limitations Linearization Kinds of simulation Granularity in spatio-temporal sampling Computational models and constraints on computation Models of computations... automata and grammars computation graphs dataflow and Petri Nets ATN Scaling - constraints and tradeoffs in time, space, power, ... Fault tolerance, reliability Complexity, intractability, undecidability Data structures and algorithms (the usual and growing collections) Graphs and networks physical virtual social hypertext Transformation and Patterns Transformation mapping between representations examples: rule-based systems... Patterns defining -> searching vs. discovering/recognizing examples: machine learning... Language models augmented transition network

Information, Knowledge, and Machine Learning data models query languages issues - data integrity, ... Knowledge representaton logical reasoning and cognition examples - natural language processing, ... Machine learning supervised and unsupervised learning examples - data mining, robotics, ... Communication and coordination Abstraction levels and protocols Centralized/distributed Models such as synchronous/asynchronous broadcast/P2P client‐server shared memory/message‐passing blackboard architecture cloud Error handling concurrency control problems [Denning] and deadlock

Flow of control Sequential Conditional Iteration Recursion Parallelism co-routines threads and processes multi-processing multi-core distributed Non-deterministic computation The human element Why the human element matters What aspects to consider perception cognition interaction social dynamics

CT操作性定义-2012年7月 Algorithmic thinking and problem analysis CSTA(9) Denning(7) Google(6) 李波1月（7） College Board(7) Data Collection Data Analysis Data Representation Problem Decomposition Abstraction Algorithms &Procedures Automation Simulation Parallelization Computation Communication Coordination Recollection Evaluation Design problem decomposition pattern recognition, pattern generalization to define abstractions or models, algorithm design data analysis visualization. CT及问题求解 模型：抽象和表示 算法 信息编码与数据组织 网络与协作 计算机应用 智能系统 Creativity Data. Algorithms Programming Internet Impact Algorithmic thinking and problem analysis Abstractions (levels of) Representation, approximation, and dealing with errors Processing techniques and their limitations Computational models and constraints on computation Data structures and algorithms Transformation and Patterns Information, Knowledge, and Machine Learning Communication and coordination Flow of control The human element CT操作性定义-2012年7月

请批评