作者：董荣胜
出版社：人民邮电出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
计算思维的结构试读：
前言
计算机在科学、经济、商业等各个领域的重要作用早已广为人知。然而现在，计算机科学不仅处于当今科学与技术的中心地位，而且正在改变着几乎所有的其他学科。在一定程度上，这是廉价计算处理能力迅速发展的结果，但是最根本的改变还是来自计算机科学的概念和工具在其他学科的成功应用。比如从数据的组织方式到问题的求解方式；通过对生命系统的计算机建模，计算机科学的方法正在改变生物学；类似地，它也正在改变天文学家、流行病学家和经济学家的研究方式。在这一过程中，计算机科学正从一个令人讨厌的工程学科变成一个富有创造性的科学学科。为了更好地进行问题求解、系统设计，以及理解人类行为，人们希望更多的研究者能在理解计算机科学的基础上，从计算的视角来重新审视自身学科的问题，最终产生一系列新的科学发现与技术创新。2008年美国NSF启动的CDI重大计划就是这个思路，而计算思维在这个重大计划中起着关键的作用。
计算机科学源于欧美，目前，美国的计算机科学处于世界领先地位。在美国，人们将计算思维能力的培养列为高校计算机科学专业的第一任务，目前这一任务正在从美国国家战略这个层面，由美国政府投入巨资向美国中小学延伸。
计算思维的结构是计算思维表述体系的一个关键问题，一个良好的结构会降低人们理解该领域的复杂程度，促进该领域的发展。一般认为，周以真给出的计算思维本质结构，Denning给出的“伟大的计算原理”结构框架，以及本书推荐的“计算机方法论”的结构框架是3种具有代表性的计算思维结构框架。
本书的结构建立在计算机方法论的结构框架之上，将原来计算学科的基本问题、计算学科的3个学科形态、计算学科的核心概念、计算学科中的数学方法、计算学科中的系统方法等内容作为本书的重要内容，对部分内容进行了删减、修改甚至重写，侧重以“一般（类）问题求解能否自动有效进行”为核心的计算思维习惯的训练和养成，力求通俗易懂。增加“跨学科的计算问题案例”一章，将原来“社会与职业问题”中的职业化本质、道德选择，以及有效的检举等内容纳入其中。
本书是中国大学MOOC“计算思维的结构”课程的配套教材，书中内容力争做到计算思维课程表述的最小集，相关的习题和答案、程序、PPT文档、微视频，以及补充资料（如课程评估方面的BLOOM分类法、SOLO分类法，难度、复杂度与能力）等均放在课程网站上，供大家参考。
本书是陈国良院士领导下的教育部“以计算思维为切入点的大学计算机课程改革项目”的成果之一，本书的出版得到了国家自然科学基金项目（61363070）和2014年教育部高教司——微软公司校企合作专业综合改革项目的资助，以及教育部高等学校大学计算机课程教学指导委员会各位同仁的帮助和支持，在此一并表示感谢！作者2017年5月第1章 绪论
伟大的计算原理是美国ACM前主席Denning教授，2003年在Communications of the ACM上发表的《伟大的计算原理》（Great Principles of Computing）一文中提出的一个旨在弘扬计算机科学的概念框架。
Denning认为，计算（Computing）是一门关于信息处理的科学，现在大量的事实表明，它是一门人工科学，又是一门自然科学。如果我们将不同学科领域存在的问题当作一个计算问题，从计算的角度揭开这些问题的神秘面纱，就有可能推动这些领域的发展，比如生命科学、化学、金融学，甚至法律。而计算原理正是推动这些发展的关键。以前，我们对计算的描述，往往侧重其核心的技术，比如编程、计算机制图、网络、高性能计算等。而如果按“伟大的计算原理”描述计算，其好处如下。（1）提供理解物理、社会或者其他现象的新方式。（2）指出解决问题的新途径。（3）强调创造知识，而不是使用信息。（4）提高创造和创新能力。（5）为计算机科学课程的教学提供新的方法，激发同学们的兴趣和爱好。
Denning分析了计算技术，以确定它们所依据的原理，在《伟大的计算原理》一文中将计算的原理划分为五个类别：计算（Computation）、通信（Communication）、协作（Coordination）、自动化（Automation）、记忆（Recollection）；2009年6月Denning又在Communications of the ACM上发表了论文《超越计算思维》（Beyond Computational Thinking），增加了评估（Evaluation）和设计（Design）两个类别，总共有7个类别。
计算原理的类别就像是一个计算知识领域的窗口。每个窗口都有各自的视角，从不同窗口看，会发现一些相同的素材。比如，可以从协作的角度来了解网络协议，也可以从通信的角度了解网络协议，还可以从记忆的角度来了解网络协议。Denning相信，这7个类别现在是完整的，并具有持久的影响力。
我国教育部高等学校大学计算机课程教学指导委员会在综合考虑周以真教授和Denning教授研究成果的基础上，在《大学计算机基础课程教学基本要求》（高等教育出版社，2016年1月出版）中给出了计算思维表述体系，如表1.1所示。表中增加了周以真教授非常强调的重要学科原理，即“抽象原理”，给出了相应的42个核心概念，对掌握的重点也做了相应的说明。表1.1 计算思维表述体系1.1 计算思维概述
关于计算思维，周以真教授发表了2篇重要论文，分别为2006年发表在Communicationsof the ACM上的《计算思维》（Computational Thinking）和2008年发表在英国皇家学会《哲学汇刊》（Philosophical Transactions of the Royal Society）上的《计算思维和关于计算的思维》（Computational Thinking and Thinking about Computing）。在第1篇论文中，周以真给出了计算思维的一个总的定义，并对计算思维具体是什么、其特征是什么进行了描述。第2篇论文探讨了计算思维的本质。
计算思维的提出，对美国教育界和科学界均产生了重要影响，并促成了美国国家科学基金（NSF）两个重大计划CPATH和CDI的产生。
2007年，美国NSF启动了旨在振兴美国计算教育的国家计划——CPATH（CISE Pathways to Revitalized Undergraduate Computing Education），该计划旨在通过“计算思维”从根本上改变美国大学计算教育的现状。
2008年，美国NSF又启动了一个涉及所有学科的以计算思维为核心的国家重大科学研究计划CDI（Cyber-Enable Discovery and Innovation），计划将计算思维拓展到美国的各个研究领域。美国NSF希望通过CDI等研究计划，使人们在科学与工程领域以及社会经济技术等领域的思维范式发生根本性的改变。基金会确信，这种思维范式的改变将会为美国产生更多新的财富，并最终提高美国人民的生活质量。
2011年，NSF又启动了CE21（The Computing Education for the 21st Century）计划，该计划建立在CPATH成功的基础上，其目的是提高K-14（中小学和大学一、二年级）老师与学生的计算思维能力。
2015年12月10日，经美国参众两院投票通过，美国总统在白宫签署了名为“让每个学生取得成功的法案（Every Student Succeeds Act，ESSA）”，将以计算思维培养为核心的计算机科学提高到与数学、英语等同的重要地位，并投入巨资在美国国内广泛推行。
计算思维的提出，同样引起了中国计算机界的重视。2010年7月19日至20日，C9高校联盟（包括北京大学、清华大学、浙江大学、复旦大学、上海交通大学、南京大学、中国科技大学、哈尔滨工业大学、西安交通大学）在西安交通大学举办了首届“九校联盟（C9）计算机基础课程研讨会”。陈国良院士在会议上做了“计算思维能力培养研究”的报告。
会议研讨了国内外计算机基础教学的现状和发展趋势，并就如何增强大学生计算思维能力的培养，进行了充分的交流和认真的讨论，2010年9月在《中国大学教学》杂志上发表了影响深远的《九校联盟（C9）计算机基础教学发展战略联合声明》，旗帜鲜明地把“计算思维能力的培养”列为计算机基础教育的核心任务。2012年5月，教育部高教司在合肥工业大学召开了“大学计算机”课程改革研讨会，会上明确了大学计算机课程要像大学数学、大学物理一样，成为大学的基础性课程。这是教育部对非计算机专业大学计算机课程的新要求。
针对国内外计算机教育发展的新动向，2012年春节刚过，教育部高等学校计算机科学与技术专业教学指导委员会、中国计算机学会教育专业委员会、全国高等学校计算机教育研究会召开了一次主任（理事长）扩大会议，就计算思维能力的培养进行了研究。认为“随着信息化的全面深入，无处不在、无事不用的计算使计算思维成为人们认识和解决问题的重要基本能力之一。一个人若不具备计算思维的能力，将在从业竞争中处于劣势；一个国家若不使广大受教育者得到计算思维能力的培养，将在激烈竞争的国际环境中处于落后地位。计算思维，不仅是计算机专业人员应该具备的能力，而且也是所有受教育者应该具备的能力。计算思维，也不简单类比于数学思维、艺术思维等人们可能追求的素质，它蕴含着一整套解决一般（类）问题的方法与技术。因此，作为教育部计算机教育的咨询与指导机构和计算机教育专业社团，我们有责任来推动计算思维观念的普及，促进在教育过程中对学生计算思维能力的培养，为提高我国在未来国际环境中的竞争力做出贡献。”会议发表了“积极研究和推进计算思维能力的培养”报告。
在对计算思维进行了长达5年的跟踪研究和教学实践的基础上，教育部高教司在2012年设立了“以计算思维为切入点的大学计算机课程改革项目”。2013年5月，教育部高等学校大学计算机课程教学指导委员会的新老两届主任和副主任共聚深圳，就进一步推动项目进展，在高校计算机教育中加强计算思维的研究和教育进行了深入的讨论，并在深圳发表旨在大力推进以计算思维为切入点的计算机教学改革的宣言，即“计算思维教学改革宣言”。
宣言开篇写道：一个古老而又年轻的概念，计算思维的概念，正在科技界和教育界萌发、激荡和蔓延。所到之处，彻底更新和改变了现在被广泛认同的一些理论和认识。一种新的关于计算和计算机科学的观点正在以雷霆万钧之势荡涤着旧有的传统，焕发出面向新时代和新技术的崭新面貌。从事计算机科学、思维科学、教育科学、社会科学、人文科学等各方面的专家，围绕着不同的要求和目的被吸引到这一领域里来。这种共同的兴趣正酝酿着新的重大的理论革命和技术飞跃，一种全新的对计算机科学的理解和应用的时代已经展现在我们的面前。
现在，人们已经认识到计算思维的重要性了，文化正在改变。中国一些学者甚至进一步地指出，计算思维的培育是教育改革，乃至科技改革的一个重要突破口，或者说，是中国科教战线的“诺曼底”。
为了充分地理解计算思维，下面，我们分别介绍计算思维的定义、计算思维的特征、计算思维的本质、计算思维的结构等内容。
周以真教授在《计算思维》中给出了计算思维一个总的定义，该定义被国际学术界广泛采用。计算思维是运用计算机科学的基础概念进行问题求解、系统设计以及人类行为理解等涵盖计算机科学之广度的一系列思维活动。为便于理解，文中又给出了计算思维更详细的7种描述和6大特征，如表1.2和表1.3所示。表1.2 计算思维的7种描述表1.3 计算思维的6大特征
计算思维吸取了问题解决所采用的一般数学思维方法，现实世界中巨大复杂系统的设计与评估的一般工程思维方法，以及复杂性、智能、心理、人类行为的理解等的一般科学思维方法。
计算思维建立在计算过程的能力和限制之上，由机器或人执行。计算方法和模型使我们敢于去处理那些原本无法由个人独立完成的问题求解和系统设计。
计算思维最根本的内容，即其本质（Essence）是抽象（Abstraction）和自动化（Automation）。计算思维中的抽象完全超越物理的时空观，并完全用符号来表示，其中，数字抽象只是一类特例。
与数学和物理科学相比，计算思维中的抽象显得更为丰富，也更为复杂。数学抽象的重大特点是抛开现实事物的物理、化学和生物学等特性，仅保留其量的关系和空间的形式，而计算思维中的抽象却不仅仅如此。
计算思维中的抽象最终是要能够机械地一步一步自动执行。为了确保机械的自动化，就需要在抽象的过程中进行精确和严格的符号标记和建模，同时也要求计算机系统或软件系统生产厂家能够向公众提供各种不同抽象层次之间的翻译工具。
抽象层次是计算思维中的一个重要概念，它使我们可以根据不同的抽象层次，进而有选择地忽视某些细节，最终控制系统的复杂性；在分析问题时，计算思维要求我们将注意力集中在感兴趣的抽象层次，或其上下层；另外，对各抽象层次之间的关系人们也应该有一个初步的了解。
计算思维提出后，不少国家，如美国、英国，以及中国的学术组织举办过一系列的学术研讨。其中，2010年，在美国NSF的资助下，美国国家研究委员会（NRC）召开了一系列会议，给出了《关于计算思维的本质和适用范围的工作报告》（Report of a workshop on the scope and nature of computational thinking），报告给出了“计算思维”的五个公开问题（Open Questions）：计算思维的结构问题、计算思维者的识别问题、计算思维与技术之间的关系问题、计算思维的教学方法问题与计算思维相关的计算社团的角色问题。其中，第一个问题，也即“计算思维的结构问题”是最重要的核心问题，下面做简单介绍。
在NRC的研讨会上，关于计算思维的本质和所应用的领域范围，与会者（包括来自美国科学院、美国工程院和美国医学院的国家顾问）提出了许多不同的观点。
虽然与会人员没有明确表示不同意与自己不同的计算思维观点，但是几乎每一个人都在坚持他们自己的观点，强调计算思维在某个特别方面的作用或者是对某个个体的重要特性。因此，为了达成一致，与会人员提出了计算思维的结构问题，该问题涉及计算思维的核心是什么，计算思维的组成元素是什么，不同元素之间的逻辑关系是什么等内容。
与会人员认为，一个符合逻辑的计算思维结构有助于计算思维的应用和发展。这个问题将引发后续关于计算思维本质的结构、伟大计算原理的结构框架以及计算机方法论的结构框架等3种具有代表性的计算思维结构的讨论，这种讨论会进一步加深人们对计算思维的理解。1.2 计算思维的结构
根据周以真的定义，计算思维是运用计算机科学的基础概念进行问题求解、系统设计以及人类行为理解等涵盖计算机科学之广度的一系列思维活动。
这样，问题来了，这里指的计算机科学的基础概念是什么，其中最为核心的基础概念又是什么？如果回答是“算法”，则有可能将我们又带回传统计算机科学认识的老路，也即计算机科学=程序设计。
美国ACM前主席Denning在《超越计算思维》一文中就是根据这个问题，对周以真教授提出的计算思维给了如下两个否定：（1）计算思维不是计算机科学独有的特征；（2）计算思维不能充分地代表计算机科学的特征。
Denning认为，他提出的“伟大的计算原理”能够做到这两点。
近年来，我国教育部高等学校计算机类教学指导委员会力推学生系统能力的培养，也从一个侧面对计算思维的作用隐含地提出了不同意见。的确如此，尽管算法，或者更广泛地说程序设计，对于计算机科学而言非常重要，但只是其中实践方面的一个部分。
Denning认为，系统、模型、创新这些内容也是计算机科学实践方面的重要内容，并与程序设计具有同等的地位，过分地强调程序设计不利于计算机科学的发展。Denning担心，周以真提出的计算思维如果讲不清楚的话，就有可能将我们带回我们曾一直想逃避的老路上去，也即计算机科学=程序设计。
美国国家科学基金会注意到了关于“计算思维”认知的不同意见，2008年春，委托美国国家研究委员会对“计算思维的本质和适用范围”进行研讨，研讨会邀请了包括美国科学院、美国工程院和美国医学院的代表参会，参会人员对计算思维在各自领域的重要作用进行了肯定，2010年4月总结整理后的报告《关于计算思维的本质和适用范围的工作报告》由美国国家科学院出版社出版，报告认为计算思维认知的关键在于确定什么是计算思维的基本元素，元素之间的关系又是如何，从而引出了计算思维的结构问题。
一个领域的结构问题向来就是一个迷人的问题，如果这个结构能用公理系统来描述，就是最理想的了，现在我们知道，根据哥德尔定律，在一个足够复杂的系统中，建立一个绝对完备的系统是不现实的，但这不等于我们不追求这种系统，当然可以对完备性的要求适当地放宽，即使在完备性方面有点“不足”，也是令人神往的。
想必周以真教授也深知其中的道理。2008年7月，周以真教授又在英国著名期刊《英国皇家学会哲学学报》上发表论文《计算思维与关于计算的思维》，对计算思维的本质进行了讨论，给出了抽象（Abstraction）和自动化（Automation）的两个概念，明确了计算思维的本质是抽象和自动化，也就是计算思维中最重要的两个元素，在《关于计算思维的本质和适用范围的工作报告》推出后，周以真教授在其宣讲用的PPT文档中，用抽象（含抽象层次）和自动化构建了计算思维的结构图。
大家注意，Denning的两个“NO”不是说周以真提出的计算思维不好，而是说，Denning自己提出的“伟大的计算原理”更能充分地展示计算机科学的伟大。其实，周以真是从思维这个层面给出计算思维本质的结构，Denning是从原理出发给出计算思维的结构框架，显然，还可以从思想方法这个层面给出计算思维的结构框架，这就是本书推荐的一种有效的计算思维教学框架，也即“计算机方法论”的结构框架。本书认为，周以真给出的计算思维本质结构框架、Denning给出的“伟大的计算原理”结构框架，以及本书推荐的“计算机方法论”的结构框架是三种具有代表性的计算思维结构框架。下面分别简单介绍。
1．计算思维本质的结构框架
2006年3月，周以真发表《计算思维》一文，给出计算思维的定义，并对计算思维的特征进行了描述。2008年7月，周以真发表论文《计算思维与关于计算的思维》，指出计算思维的本质是抽象和自动化。2010年后，她给出了计算思维本质的结构框架图（见图1.1）。图1.1 计算思维本质的结构框架图
2．“伟大的计算原理”结构框架
2003年11月，Denning在《ACM通讯》杂志上发表文章《伟大的计算原理》，给出了最初的5个伟大原理：计算、通信、协作、自动化、记忆（见图1.2）。2009年6月，他又在《ACM通讯》杂志发表文章《超越计算思维》，增加了评估和设计两个伟大原理，将“抽象”原理放在设计原理之中，Denning认为，“伟大的计算原理”包含了周以真提出的“计算思维”的内容。2015年1月，Denning根据“伟大的计算原理”结构框架（见图1.2）撰写了名为“伟大的计算原理”的教材，并由麻省理工学院出版发行。图1.2 伟大的计算原理结构框架图
3．计算机方法论的结构框架
2001年7月，在上海召开的CC2001工作研讨会上，本书作者介绍了“计算机科学与技术方法论”，2002年9月出版教材《计算机科学与技术方法论》，并给出了计算机方法论的公理化描述。根据计算机方法论的结构框架，2007年9月撰写出版了教材《计算机科学导论：思想与方法》，2009年，由计算机方法论结构框架构建的“计算机科学导论”课程被评为国家级精品，2011年该教材入选国家“十二五”规划教材，2015年7月该教材第3版出版发行。本书也建立在计算机方法论的结构框架之上，结构基本一致，只是更强调计算思维习惯的养成，以及跨学科的交融（见图1.3）。图1.3 计算机方法论的结构框架图1.3 计算机方法论概述
计算机方法论（Methodology of Computer Science，MCS）是一个具体的科学技术方法论，它将一般科学技术方法论中最基本的C（Cognition，认知）和P（Practice，实践）两个元组改为更具体的A（Abstraction，抽象）、T（Theory，理论）、D（Design，设计），因此，它是一个五元组，即：
MCS=
其中：（1）Q是一个包含子集A、T、D的集合。（2）A是计算学科中所有属于“抽象”概念的集合。（3）T是计算学科中所有属于“理论”概念的集合。（4）D是计算学科中所有属于“设计”概念的集合。（5）F表示由Q到它自身的一个关系。
认知与实践以及其相互关系是一般技术方法论研究的核心内容。计算机方法论研究的核心内容，其实也就是一般技术方法论研究的核心内容，只不过具体化为计算学科的抽象（感性认识）、理论（理性认识）和设计（实践）3个过程及其内在联系所要研究的内容。
由于“科学研究从问题开始”与“认识以实践为基础”是从不同角度得出的不同命题，而其本质是一致的。因此，我们可以将科学问题从抽象、理论和设计3个过程中提取出来，构成与3个过程具有相同地位的重要内容。
计算机方法论遵循一般科学技术方法论的普遍原理，但是，它又不同于一般科学技术方法论。
一般科学技术方法论在学科认识中具有一般性的指导意义；而计算机方法论直接面对和服务于计算学科的认识过程，它是我们认知计算学科的工具。就某种意义而言，计算机方法论的建立正是计算学科成熟的标志之一。
计算机方法论的研究不仅具有理论意义，也具有现实意义，它能促进计算学科的发展，有助于计算学科的建设与人才培养。下面，从五个方面来概括它的意义。（1）有助于我们正确理解计算学科中所蕴含的科学思维方法。
抽象、理论和设计是计算机方法论中最基本的3个概念。3个学科形态的划分，反映了人们的认识从感性认识（抽象）到理性认识（理论），再回到实践（设计）中来的科学思维方法，并有助于我们从方法论的高度来认知计算学科。（2）有助于总结和提升计算学科所积累的各种方法与经验。
计算学科自20世纪40年代诞生以来，科学家们在不到百年的时间里取得了大量的里程碑式的科学成果，使该学科得到了迅猛的发展。这些成果所包含的研究方法更是一份宝贵的财富。
然而就大多数研究者而言，研究成果是他们自觉追求的目标，而方法则是为取得成果而采取的手段。一旦研究工作获得成功，大多数研究者对于自己的科研成果的价值甚为清楚，而对获得成果所使用的方法却重视不够，一般很少有人自觉地将自己的研究方法加以系统的总结和提升，使它们成为具有普遍意义的思想工具。
计算机方法论的任务就是要系统地总结和提升这些方法，使它们成为具有普遍意义的思想工具，从而被计算领域的工作者所掌握，以便使我们更好地从事该领域的工作。（3）有助于促进计算学科的发展。
从计算学科的发展来看，计算学科的每一个重要进展几乎都与研究方法的改进密切地联系着，计算学科每个领域的发展总是与那一时期的研究方法的发展水平相适应。
例如，在20世纪50年代，程序设计受当时技术的限制，如果说程序设计采用了一定的方法的话，那就是技巧；60年代末期由于软件危机以及硬件的发展，出现了规范化的程序设计；70年代末期，形成了以结构化方法为主的系统开发方法；80年代人们发现，由于行业间语言的障碍，要弄清用户的需求有困难，于是提出了原型化的思想方法；90年代开始，随着人们认识的进一步深化，提出了目前占主导地位的面向对象的思想方法。
新的思想方法是不会凭空产生的，它是对已有方法进行改进的结果，从以上研究方法的发展来看，它符合实践、认识、再实践、再认识的一般规律。也就是说，它需要我们对现有方法进行深入研究，在肯定它们具有认识功能的同时，又注意到它们的局限性，要根据研究对象的特点与需要，对研究方法进行改进，实现方法上的突破，从而促进学科的发展。（4）有助于确立正确的思想原则，把握正确的研究方向。
恩格斯在其著作《自然辩证法》中说过：不管自然科学家采取什么样的态度，他们还是得受哲学的支配。问题只在于他们是愿意受某种坏的时髦的哲学来支配他们，还是愿意受一种建立在通晓历史及其成就的基础上的理论思维的支配。一个研究者如果不具备正确的理论思维形式，不以正确的思想方法作指导，在具体的研究实践中可能会常常碰壁，甚至对理应到手的研究成果也可能会视而不见、置若罔闻。
计算机方法论是在一般科学技术方法论的指导下建立的，它吸收了其他学科已有的方法论成果，遵守共同的方法论原则。同时，它又是解决计算学科特殊矛盾所需的、有着计算学科特点的、相对独立的方法论，它直接面对和服务于计算学科的认识过程，使人们对计算学科的认识逻辑化、程序化、理性化和具体化，它有助于我们在计算学科的研究中确立正确的思想原则，把握正确的研究方向。（5）有助于计算学科的建设和人才培养。
如何进行计算学科的建设，是一个长期以来争论的问题。计算机方法论从计算学科的基本问题，学科的抽象、理论和设计3个过程，学科的核心概念，数学方法，系统科学方法，形式化技术，以及社会和职业的问题等方面出发，深刻地揭示了计算学科的本质，有助于我们对计算学科的认识，从而有助于计算学科的建设。
计算专业的学生如能在大学的学习中系统地接受学科方法论的指导，以了解、懂得研究工作的一般程序、操作技术与正确的思维方法，无疑有助于自己的成长。习题1
1.1 美国ACM前主席Denning在《超越计算思维》一文中对周以真教授提出的计算思维给了哪两个否定？（ ）
A．计算思维不是计算机科学独有的特征
B．计算思维没有解决“计算机科学=程序设计”这个认知上的误区
C．计算思维不能充分地代表计算机科学的特征
D．计算思维没有体现计算机科学特有的设计和评估两个特征
1.2 美国ACM前主席Denning给出的两个否定，不是说周以真提出的计算思维不好，而是说，Denning自己提出的“伟大的计算原理”更能充分地展示计算机科学的伟大。其实，周以真是从_____这个层面给出计算思维本质的结构，Denning是从_____出发给出计算思维的结构框架，显然，还可以从_____这个层面给出计算思维的结构框架。（ ）
A．思想方法、原理、思维
B．原理、思想方法、思维
C．思维、原理、思想方法
D．原理、思维、思想方法
1.3 2010年，在美国NSF的资助下，美国国家研究委员会（NRC）召开了一系列会议，给出了《关于计算思维的本质和适用范围的工作报告》（Report of a workshop on the scope and nature of computational thinking），报告给出了“计算思维”的五个公开问题（Open Questions）。其中最重要的核心问题是______。（ ）
A．计算思维相关的计算社团的角色问题
B．计算思维的结构问题
C．计算思维者的识别问题
D．计算思维与技术之间的关系问题
1.4 计算思维的结构问题涉及以下哪两个方面。（ ）
A．计算思维与技术的关系
B．计算思维的组成元素
C．计算思维不同元素之间的逻辑关系
D．计算思维者的识别问题
1.5 下面不属于计算思维特征的是______。（ ）
A．是思想，不是人造品（ ）（ ）B．计算机的，不是人的思维
C．根本的，不是刻板的技能
D．概念化，不是程序化
1.6 计算机方法论中最基本的三个概念是______。（ ）
A．计算、抽象、设计
B．抽象、自动化、评估
C．抽象、理论、设计
D．计算、自动化、设计
1.7 为什么说不重视计算思维的结构问题，就有可能回到传统计算机科学认识的老路，即计算机科学=程序设计？第2章 计算学科的基本问题
计算学科的问题无非就是计算问题，从大的方面来说，分为可计算问题与不可计算问题。可计算问题是指存在算法可解的问题，不可计算问题是指不存在算法可解的问题。
为便于理解，下面分别以汉诺（Hanoi，又译为梵天）塔问题和停机问题来介绍可计算问题与不可计算问题。2.1 汉诺塔问题
相传，印度教的天神汉诺在创造地球时建了一座神庙，神庙里竖有3根宝石柱子，柱子由一个铜座支撑。汉诺将64个直径大小不一的金盘子，按照从大到小的顺序依次套放在第一根柱子上，形成一座金塔（见图2.1），即所谓的汉诺塔（又称河内塔）。天神让庙里的僧侣们将第一根柱子上的64个盘子借助第二根柱子全部移到第三根柱子上，即将整个塔迁移，同时定下3条规则：（1）每次只能移动一个盘子。（2）盘子只能在3根柱子上来回移动，不能放在他处。（3）在移动过程中，3根柱子上的盘子必须始终保持大盘在下，小盘在上。
天神说：“当这64个盘子全部移到第三根柱子上时，世界末日就要到了。”这就是著名的汉诺塔问题。图2.1 汉诺塔
用计算机求解一个实际问题，首先要从这个实际问题中抽象出一个数学模型，然后设计一个求解该数学模型的算法。从实际问题中抽象出一个数学模型的实质，其实就是要用数学的方法抽取其主要的、本质的内容，最终实现对该问题的正确认识。
汉诺塔问题是一个典型的用递归方法来求解的问题。递归是计算学科中的一个重要概念。所谓递归，就是将一个较大的问题归约为一个或多个子问题的求解方法。当然，要求这些子问题比原问题简单一些，且在结构上与原问题相同。
根据递归方法，可以将64个盘子的汉诺塔问题转化为求解63个盘子的汉诺塔问题，如果63个盘子的汉诺塔问题能够解决，则可以先将63个盘子移动到第二根柱子上，再将最后一个盘子直接移动到第三根柱子上，最后又一次将63个盘子从第二根柱子移动到第三根柱子上，这样则可以解决64个盘子的汉诺塔问题。依次类推，63个盘子的汉诺塔求解问题可以转化为62个盘子的汉诺塔求解问题，62个盘子的汉诺塔求解问题又可以转化为61个盘子的汉诺塔求解问题，直到1个盘子的汉诺塔求解问题。再由1个盘子的汉诺塔的求解求出2个盘子的汉诺塔，直到解出64个盘子的汉诺塔问题。
现在的问题是当n=64时，即有64个盘子时，需要移动多少次盘子？要用多少时间？按照上面的算法，n个盘子的汉诺塔问题需要移动的盘子数是n-1个盘子的汉诺塔问题需要移动的盘子数的2倍加1。于是
因此，要完成汉诺塔的搬迁，需要移动盘子的次数为64
2-1=18 446 744 073 709 551 615
如果每秒移动一次，一年有31 536 000 s，则僧侣们一刻不停地来回搬动，也需要花费大约5 849亿年的时间。这个时间大大超过了科学家们推测的地球的寿命（大约100亿年，已存活46亿年）。
假定计算机以每秒1 000万个盘子的速度进行搬迁，也需要花费大约58 490年的时间。
就这个例子，读者可以了解到理论上可以计算的问题，实际上并不一定能行，这属于算法复杂性方面的研究内容。
下面用Raptor代码对该问题的求解算法进行描述，如图2.2和图2.3所示。图2.2 汉诺塔问题的main子图图2.3 汉诺塔问题的move子程序2.2 算法复杂性中的难解性问题
算法复杂性包括算法的空间以及时间两方面的复杂度问题，汉诺塔问题主要讲的是算法的时间复杂度。n
关于汉诺塔问题算法的时间复杂度，可以用一个指数函数O(2)来表示，显然，当n很大（如10 000）时，计算机是无法处理的。相2反，当算法的时间复杂度的表示函数是一个多项式，如O(n)时，则可以处理。因此，一个问题求解算法的时间复杂度大于多项式（如指数函数）时，算法的执行时间将随n的增加而急剧增长，以致即使是中等规模的问题也无法求解，于是这一类问题被称为难解性问题。人工智能领域中的状态图搜索问题（解空间的表示或状态空间搜索问题）就是一类典型的难解性问题。
在计算复杂性理论中，将所有可以在多项式时间内求解的问题称为P类问题，而将所有在多项式时间内可以验证的问题称为NP类问题。由于P类问题采用的是确定性算法，NP类问题采用的是非确定性算法，而确定性算法是非确定性算法的一种特例，因此，可以断定P⊆NP。2.3 证比求易算法
为了更好地理解计算复杂性的有关概念，我国学者洪加威曾经讲了一个被人称为“证比求易算法”的童话，用来帮助读者理解计算复杂性的有关概念，大致内容如下。
从前，有一个酷爱数学的年轻国王艾述向邻国一位聪明美丽的公主秋碧贞楠求婚。公主出了这样一道题：求出48 770 428 433 377 171的一个真因子。若国王能在一天之内求出答案，公主便接受他的求婚。
国王回去后立即开始逐个数地进行计算，他从早到晚，共算了3万多个数，最终还是没有结果。国王向公主求情，公主将答案相告：223 092 827是它的一个真因子。国王很快就验证了这个数确能除尽48 770 428 433 377 171。公主说：“我再给你一次机会，如果还求不出，将来你只好做我的证婚人了。”
国王立即回国，并向时任宰相的大数学家孔唤石求教，大数学家在仔细地思考后认为这个数为17位，则最小的一个真因子不会超过9位，于是他给国王出了一个主意：按自然数的顺序给全国的老百姓每人编一个号发下去，等公主给出数目后，立即将它们通报全国，让每个老百姓用自己的编号去除这个数，除尽了立即上报，赏金万两。最后，国王用这个办法求婚成功。
在“证比求易算法”的故事中，国王最先使用的是一种顺序算法，其复杂性表现在时间方面，后面由宰相提出的是一种并行算法，其复杂性表现在空间方面。直觉上，我们认为顺序算法解决不了的问题完全可以用并行算法来解决，甚至会想，并行计算机系统求解问题的速度将随着处理器数目的不断增加而不断提高，从而解决难解性问题，其实这是一种误解。当将一个问题分解到多个处理器上解决时，由于算法中不可避免地存在必须串行执行的操作，因而大大地限制了并行计算机系统的加速能力。下面用阿姆达尔（G.Amdahl）定律来说明这个问题。
设f为求解某个问题的计算存在的必须串行执行的操作占整个计算的百分比，p为处理器的数目，S为并行计算机系统最大的加速能p力（单位：倍），则
设f=1%，p→∞，则S=100。这说明在并行计算机系统中即使有p无穷多个处理器，若串行执行操作占全部操作的1%，则其解题速度与单处理器的计算机相比最多也只能提高100倍。因此，对难解性问题而言，单纯地提高计算机系统的速度是远远不够的，而降低算法复杂度的数量级才是最关键的问题。2.4 P=NP？
在“证比求易算法”中，对公主给出的数进行验证，显然是在多项式时间内可以解决的问题，因此，这类问题属于NP类问题。现在，P=NP是否成立的问题是计算学科和当代数学研究中最大的悬而未决的问题之一。2000年5月，美国克莱数学研究所（The Clay Institute of Mathematics）提供100万美元求解这一问题。解决这一问题有重要的意义，若回答P=NP，对人类实践则有深远的影响，它不仅将动摇当今以电子技术为基础的密码学理论基础，同时也将为人们有效解决数学和其他科学与工程学科中的难解问题提供了可能；若回答P≠NP，则有可能找到一种崭新的证明方法，进一步丰富和发展计算机科学和数学的新理论。
若P=NP，则所有在多项式时间内可验证的问题都将是在多项式时间内可求解（或可判定）的问题。大多数人不相信P=NP，因为人们已经投入了大量的精力为NP中的某些问题寻找多项式时间算法，但没有成功。然而，要证明P≠NP，目前还无法做到这一点。
针对P=NP是否成立的问题，库克（S.A.Cook）等人于20世纪70年代初取得了重大的进展，他们认为NP类中的某些问题的复杂性与整个类的复杂性有关，当这些问题中的任何一个存在多项式时间算法时，所有NP问题都是在多项式时间内可解的，这些问题被称为NP完全性问题。
NP完全性（NPC）问题是计算复杂性理论中最有研究价值的问题，这类问题在下述意义下具有同等的难度：要么每个NP完全性问题都存在多项式时间的算法（即通常所指的有效算法）；要么所有NP完全性问题都不存在多项式时间的算法。尽管学术界目前还不能证明其中任一个结果的正确性，但普遍认为第二种可能性更接近于事实。
NP完全性问题在理论和实践两方面都具有重要的研究意义。历史上第一个NP完全性问题是库克于1971年提出的可满足性问题。
可满足性问题就是判定一个布尔公式是否是可满足的。它可以形式化地表示为：
SAT={<φ>|φ是可满足的布尔公式}
关于可满足性问题和NP问题的联系，库克给出并证明了这样的定理：
SAT∈P当且仅当P=NP
库克因其在计算复杂性理论方面（主要是在NP完全性理论方面）的奠基性工作，于1982年获ACM图灵奖。
在库克工作的影响下，卡普（R.Karp）随后证明了21个有关组合优化的问题，也是NP完全性问题，从而加强和发展了NP完全性理论。卡普由于在计算复杂性理论、算法设计与分析、随机化算法等方面的创造性贡献，于1985年获ACM图灵奖。
计算复杂性理论有一个非常实用的结论，那就是，若采用某种特定的方法（步骤），你无法控制这个问题的复杂性，其实，他人按这种方法也没有办法控制这个问题的复杂性。因此，问题的解决不在于问题的本身，而在于方法的改变。
现在，在计算科学、数学、逻辑学以及运筹学等领域中已发现数万个NPC问题。其中有代表性的有哈密尔顿回路问题、旅行商问题（也称货郎担问题）、划分问题、带优先级次序的处理机调度问题、顶点覆盖问题等（见图2.4）。图2.4 P、NP、NPC的关系图2.5 RSA公开密钥密码系统
计算复杂性理论在密码学研究领域起了十分重要的作用，它给密码研究人员指出了寻找难计算问题的方向，并促使研究人员在该领域取得了革命性的成果。公开密钥密码系统就是其中的典型例子。
第一个实用的在非保护信道中建立共享密钥的方法是1976年由迪菲（Whitfield Diffie）与赫尔曼（Martin Hellman）建立的密钥交换方法（Diffie-Hellman key exchange，DH）。迪菲与赫尔曼为解决密钥管理的问题，在《密码学中的新方向》（New Directions in Cryptography）一文中给出了一种密钥交换协议。该协议允许在不安全的媒体上保证通信双方交换信息的安全。在迪菲与赫尔曼等人工作的基础上，很快出现了非对称密钥密码系统，其原理是将加密密钥和解密密钥分离，公开加密密钥，保存解密密钥。用公开密钥加密数据，数据以密文形式传播，只有拥有解密密钥才能解密。
目前，使用最为广泛的是1978年由李维斯特（R.L.Rivest）、萨莫尔（A.Shamir）和阿德曼（L.M.Adleman）在A Method for Obtaining Digital Signatures and Public-Key Cryptosystems一文中给出的RSA公开密钥密码系统，它通过RSA公钥算法，利用相应的“整数对”作为公钥和密钥对数据进行加密和解密。这三位科学家因在公开密钥算法上所做出的杰出贡献而荣获2002年图灵奖。
1．RSA公开密钥密码系统的形式化描述
RSA=
其中：（1）p，q，n，m，e，d，k，c∈Z*，Z*={1，2，3，…}。（2）p、q为不同质数，n=p×q。（3）(e，n)：公钥。(d，n)：私钥。（4）m：原始报文，m 2．构建一个RSA公开密钥密码系统的步骤（1）选择两个不同的质数p、q。（2）求e，使得e与(p-1)(q-1)互质，且0 3．在RSA公开密钥密码系统中的加密和解密e（1）对原始报文m加密，加密后的报文c=m(modn)。d（2）根据加密后的报文c，求原始报文m=c(modn)。 在RSA公钥密码系统中，(e，n)是公钥，(d，n)是私钥，p和q用来构建加密系统，由加密系统的构造者所有，不对外公开。k(p-1)(q-1) 命题∀k(m(modn))=1和∃k(ed=k(p-1)(q-1)+1)都可以用严密的数学方法证明，本书不作证明，但用例子做出验证。例2.1验证k(p-1)(q-1)了命题∀k(m(modn))=1，例2.2中在求d的同时验证了∃k(ed=k(p-1)(q-1)+1)。 例2.1 若p=3，q=11，n=3×11=33。 设m=2（m m(mod n)=2(mod 33)20 =2(mod 33) =1 048 576(mod 33) =1 设m=2（m m(mod n)=2(mod 33)40 =2(mod 33) =1 099 511 627 776(mod 33) =1 设m=2（m m(mod n)=2(mod 33)60 =2(mod 33) =1 152 921 504 606 846 976(mod 33) =1k(p-1)(q-1) 依次类推，对所有的k，(m(modn))=1成立。d 证明c(modn)=m。ded 证明：c(modn)=(m(modn))(modn)ed =(m)(modn)ed =m(modn)k−−(p1)(q1)+1 =m(modn)k−−(p1)(q1) =m×m(modn) =m×1 =m 例2.2 设p=3，q=11，n=3×11=33，构建一个RSA公开密钥密码系统，并对报文9加密和解密。 构建RSA公开密钥密码系统的步骤如下。（1）求e。 当p=3，q=11时，(p-1)×(q-1)=(3-1)×(11-1)=20 根据RSA公钥密码系统的构建，e必须与(p-1)×(q-1)互质，即与20互质。 设e=2，20 mod 2=0 设e=3，20 mod 3=2 由上可知，3与20互质，因此，e=3。（2）求d。 存在k使得ed=k(p-1)(q-1)+1，因此，必定存在一个k使得 d=(k(p-1)(q-1)+1)/e 将e=3，p=3，q=11代入上式，有d=(20k+1)/3 当k=1时，d=21/3=7 根据题意，知d为整数，因此，d=7。 因此，该RSA公钥密码系统的公钥为(3，33)，私钥为(7，33)。 用公钥(3，33)对m=9进行加密：e3 c=m(mod n)=9(mod 33) =729(mod 33) =3 收到加密报文3，用私钥(7，33)进行解密：d7 c(modn)=3(mod 33) =2187(mod 33) =9 例2.3 设p=223 092 827，q=218 610 473，n=487 704 284 333 771 171，构建一个RSA公钥密码系统（本题p、q、n的值来自“证比求易算法”）。 构建RSA公开密钥密码系统的步骤如下。（1）求e。 p=223 092 827，q=218 610 473，则(p-1)×(q-1)=(223 092 827-1)×(218 610 473-1) =48 770 427 991 673 872 根据RSA公钥密码系统的构建，e必须与48 770 427 991 673 872互质。 设e=2，48 770 427 991 673 872 mod 2=0 设e=3，48 770 427 991 673 872 mod 3=1 由上可知，3与48 770 427 991 673 872互质，因此，e=3。（2）求d。 存在k使得ed=k(p-1)(q-1)+1，因此，必定存在一个k使得 d=(k(p-1)(q-1)+1)/e 将e=3，p=223 092 827，q=218 610 473代入上式 d=(48 770 427 991 673 872k+1)/3 当k=1时，d=48 770 427 991 673 873/3 当k=2时，d=97 540 855 983 347 745/3 =32 513 618 661 115 915 根据题意，知d为整数，因此，d=32 513 618 661 115 915。 因此，该RSA公钥密码系统的公钥为(3，487 704 284 333 771 171)，私钥为 (32 513 618 661 115 915，487 704 284 333 771 171) 在RSA公开密钥密码系统中，加密密钥（e，n）与加密报文c均通过公开途径传送，对于巨大的质数p和q，计算n=p×q非常简单，而相对的逆运算就费时了。这种“单向性”的函数称为单向函数。任何单向函数都可以作为某种公开密钥密码系统的基础，而单向函数的安全性也就是这种公开密钥密码系统的安全性。公开密钥密码系统不仅可以用于信息的保密通信，还能用于信息发送者的身份验证和数字签名，这些内容本书就不再介绍了。2.6 停机问题 停机问题（Halting Problem）是1936年图灵（A.M.Turing）在其著名论文《论可计算数及其在判定问题上的应用》（On Computable Numbers，with an Application to the Entscheidungsproblem）中提出，并用形式化方法给予证明的一个不可计算问题。 该问题针对任意给定的图灵机和输入，寻找一个一般的算法（或图灵机），用于判定给定的图灵机在接收了初始输入后能否到达终止状态，即停机状态。若能找到这样的算法，我们说停机问题可解；否则，不可解。换句话说，就是我们能不能找到这样一个测试程序，它能判断出任意的程序在接收了某个输入并执行后能不能终止。若能，则停机问题可解；否则，不可解。 有编程经历的人都会遇到判断一个程序是否是进入死循环的情况，并且往往能判定该程序在某种情况下是否能够终止。 例2.4 很明显，这个程序可以终止。但是将程序中while语句的条件“(i<10)”改为“(i>0)”时，循环将会一直运行下去，无法终止。程序简单的时候，我们很容易做出判断；当例子复杂的时候，会遇到较大的困难。而在某些情况下，其实是无法预测的。 用计算机的程序来证明停机问题的不可解或许会更有趣，本书不介绍图灵的严格证明，而采用J.Glenn Brookshear在其著作《计算机科学概论》（Computer Science：An Overview）中给出的一个证明。 在证明之前，先介绍一个概念：哥德尔数。 在计算机理论的研究中，可以将无符号数分配给任何用特定语言编写的程序，这样的无符号数就称为哥德尔数。这种分配使得程序可以作为单一的数据项输入给其他程序。 首先，将程序中要使用的符号用哥德尔数进行对应。 int 对应1 x 对应2 + 对应3 - 对应4 … while 对应A if 对应B … 语句则根据以上符号的对应关系来确定。比如语句int x，int对应1，x对应2，所以int x对应12（十六进制），这样int x的哥德尔数也可以用二进制数00010010表示。 同理，可以用这样的方法表示其他语句和程序段，这样就可以将程序转化为歌德尔数并作为单一的数据项输入给其他程序。特别是，当一个程序以自身（转化为哥德尔数）为输入，该程序能够终止，那么这个程序就是一个自终止的程序，否则就不是。下面举例说明。 例2.5
试读结束[说明：试读内容隐藏了图片]