前言Foreword


本书以计算思维为主线介绍计算机科学的入门知识，主要针对一年级本科生的“计算机科学导论”“大学计算机基础”“计算概论”课程。本书的撰写考虑了全球发展趋势与中国的实际情况，具备下述4个特点。
(1) 强调计算思维。本书试图突出计算机科学最本质的特征: 计算机科学是研究计算过程的科学，计算过程是通过操作数字符号变换信息的过程。最本质的解决问题方法是计算思维，包括逻辑思维、算法思维、系统思维和网络思维。
(2) 强调基础知识。本书并不追求覆盖众多新概念，而是突出计算机科学不过时的最基础的入门知识点，并将它们组织成对计算思维的10个理解: 自动执行、正确性、通用性、构造性、复杂度、抽象化、模块化、无缝衔接、连通性、协议栈。
(3) 鼓励主动学习。本书的设计鼓励学生主动学习，但教师讲解与课堂互动有利于揭示要点难点、提高学习效率。本书还提供了动手动脑的课程实验，对应于逻辑、算法、系统和网络4部分内容。
(4) 鼓励胜任力教育。本书参考了ACM/IEEECS在2021年发布的《计算课程体系规范》（CC2020）。为了实践CC2020倡导的胜任力教育理念，本书实践了“高德纳测试”，并花了不少篇幅讲解计算机领域的真实创新故事，让同学们了解前人如何通过计算思维认识世界、提出问题、解决问题。
一、 致谢
本书的构思、写作、实践优化持续了10年，主要的难点是如何体现计算思维。作者要感谢北京大学李晓明教授，他多年来一直鼓励和敦促我们写一本计算机科学导论教科书。感谢时任美国国家科学基金会副主任的周以真（Jeannette Wing）博士，她多次与我们讨论了计算思维要点。感谢加州大学伯克利分校的Richard Karp教授，他多次与我们讨论计算透镜思想与计算过程要点。感谢中国科技大学陈国良教授与合肥工业大学李廉教授，以及教育部大学计算机基础课程教学指导委员会。这些老师花了很多精力在中国推动计算思维改革，为本书提供了很多同行经验。感谢北京大学的张铭教授向我们解读ACM/IEEECS《计算课程体系规范》，她是CC2020的15 位指导委员会成员之一。
特别感谢中国科学院大学的同学们，他们是本书的第一批读者，也是本书作为教科书的计算机科学导论课程的第一批实践者。感谢中国科学院计算技术研究所的博士生朝鲁、李春典、赵永威、李振营、俞子舒、李奉治、郭泓锐，他们担任了课程的助教并帮助撰写了课程实验内容。感谢中国科学院大学的李思悦、吕星宇、董可昕同学，他们为本书的创造性学习内容提供了案例。
本书引用了业界的大量素材，在此一并致谢。我们要感谢开源社区，尤其是LAMP（Linux、Apache、MySQL、PHP/Perl/Python）社区。感谢学术社区，尤其是ACM、IEEECS、CCF。ACM（Association for Computing Machinery）与IEEECS（IEEE Computer Society）是全球最大的计算机科学技术领域的国际学术社区。CCF（中国计算机学会）有10万多名会员，是全球第二大的计算机学会。它们的旗舰杂志分别是Communications of the ACM、IEEE Computer以及《中国计算机学会通讯》。
我们还要感谢众多的公司和机构，本书合理使用了它们的素材（例如公司名称、技术和产品名称、logo），这些名称和标志都是这些公司的知识产权。这些公司包括亚马逊、AMD、苹果、AT&T、百度、思科、Docker、Meta、通用电气、谷歌、红帽、华为、IBM、英特尔、联想、领英、龙芯、微软、甲骨文、曙光、腾讯、W3C、小米等。南京信息高铁研究院提供了算力资源。
特别致谢斯坦福大学计算机系荣休教授(Professor Emeritus)高德纳老师（Donald Knuth），他长期关心中国计算机教育。这位85岁高龄的码农今天还在科教一线精力充沛地工作，撰写教科书、设计算法、编程序、写论文。他在2020年再次强调: “我是否理解某项知识的终极测试，是看我能否向计算机讲解清楚。”本书将他的观点称为“高德纳测试”，用于指导教学。
二、 课程网站
本书包含课件、实验课件、部分习题答案、程序源码和其他教学工具，可扫描如下二维码查看。
配套资源信息
三、 说明
书中标注有三个星号（）的是进阶内容。

徐志伟孙晓明2023年秋于北京中关村◆计算机科学导论——以计算思维为舟学习目标和学习方法
我们使用“本课程”指称使用本书作为教科书或参考书的“计算机科学导论”或“大学计算机基础”课程。本课程面向所有专业的一年级本科生，以计算思维为主线，学习计算机科学的最基础的入门知识。那么，什么是计算思维？什么是计算机科学的最基础的入门知识？如何知道是否掌握了这些知识？
计算机科学不仅提供一种科技工具、一套知识体系，更重要的是提供了一种从信息变换角度有效地解决问题的思维方式，这就是作为计算机科学主线的计算思维Wing J. Computational thinking［J］. Communications of ACM. 2006,49 (3): 3335. 。计算思维也是计算机专业人士解决问题的思维方式，其要点是精准地描述计算过程，并使用计算过程认识世界、改造世界、定义问题、解决问题。
一、 教学目标
本课程针对所有专业的一年级本科生，在一学期学完计算机科学导论，达成3个目标。
(1) 掌握基本词汇。掌握计算机科学的基本词汇，能够与计算机同行进行入门级的交流。例如，访问网站时输入的“http://cs101.ucas.edu.cn/中文”是什么意思？ 什么是计算机的“冯·诺依曼模型”？
(2) 理解基础知识点。能够用至少一个实例描述下列基本概念的要点: 抽象计算机、真实计算机、计算机应用、数字符号、抽象、算法、作品、指数增长、计算的极限、智能。在此基础上，领悟对计算思维的10个理解。
(3) 提升胜任力。提升《计算课程体系规范》(CC2020)倡导的胜任力ACM, IEEECS. Computing Curricula 2020: Paradigms for Global Computing Education. https://www.acm.org/binaries/content/assets/education/curricularecommendations/cc2020.pdf.。课程专门安排了让同学们融会贯通基础知识点、创造性实现个人作品的实验。
1. 基本词汇
(1) 数（number）也称为数值（value）。计算机科学将所有事物表示为数并对其操作，从输入数值产生输出数值。
(2) 数位（digit）是表示数值的基本数字。我们最熟悉的是十进制数位（decimal digit）。例如，十进制数279有三个十进制数位，分别是2、7、9三个数字，它们合起来代表二百七十九这个数值。
(3) 比特（bit或binary digit）是二进制数位，即取值为0或1的数位。例如，二进制数1110有4比特，分别是1、1、1、0。二进制数1110等价的十进制数是14。
(4) 数字符号（digital symbol）是可由一个或多个比特表示的记号，用于表示一个抽象或具体的事物。每个数字符号本质上都会表示为一个二进制数。
(5) 字（word）。计算机处理数值的基本单位，所需比特数称为字长（word length）。例如，在64位计算机中，一次加法是64比特的加法。
(6) 字节（byte）特指8比特构成的数字符号。
(7) 字符（character）是一类特殊的数字符号，表示某种文明的文本（text）。本书重点关注两类字符集: 表示英文文本的ASCII字符集，包含A、b、7、$等字符；以及表示全球文本的Unicode字符集，包含A、⊙、、中、￥等字符。
(8) 算法（algorithm）是一组有穷的规则，给出求解问题的数字符号操作步骤序列。
(9) 程序（program）是算法的编程语言表示，也就是说，程序是采用某种计算机语言表示的算法。代码（code）是指一部分程序，可大到包括整个程序。软件（software）包括程序及说明程序的文档。
(10) 数据（data）是一组数字符号。当程序或数据被持续存放在计算机中时，它们被称为文件（file）。持续存储是指，当计算机断电后，文件不会丢失。
(11) 数据类型（data type）是特定类型的数据在计算机中的表示及其操作规则。本书主要关注5种数据类型: 布尔值、整数、字符、数组、切片。
(12) 控制抽象（control abstraction）说明多个操作的顺序。本书主要关注5种控制抽象: 运算优先级、串行顺序、条件判断、循环、函数调用（包括递归调用）。
(13) 计算机（computer）包括抽象计算机（如图灵机）和真实计算机（如笔记本计算机）。
(14) 系统（system）主要是指计算机（如笔记本计算机）。也用于指称计算机应用系统（如微信系统）、计算机的部件子系统或由多台计算机组成的计算机网络系统。
◆计算机科学导论——以计算思维为舟学习目标和学习方法2. 基础知识点集合
美国科学院和工程院设立的“计算机科学基础问题委员会”在2004年撰写了《计算机科学基础报告》National Research Council Committee on Fundamentals of Computer Science. Computer Science: Reflections on the Field［M］. The National Academies Press, Washington D.C., 2004. ，归纳了计算机科学的基础知识点集合，如下框所示。本课程以此报告为基础，添加了计算机领域概貌介绍和创新故事等内容。《计算机科学基础报告》的基础知识点
计算机科学是研究计算机及其能干什么的一门学科。它研究“抽象计算机的能力与局限，真实计算机的构造与特征，以及用于求解问题的无数计算机应用”。
报告还总结了计算机科学具有的一些本质特点。
(1) 计算机科学涉及符号及其操作。
(2) 计算机科学关注多种抽象的创造和操作。
(3) 计算机科学创造并研究算法。
(4) 计算机科学创造各种人工制品，尤其是不受物理定律限制的作品。
(5) 计算机科学利用并应对指数增长。
(6) 计算机科学探索计算能力的基本极限。
(7) 计算机科学关注与人类智能相关的复杂的、解析的、理性的活动。

本课程设计的一个考虑是: 针对大学所有专业的一年级本科生，包括没有任何计算机编程经验的学生，在一学期学完计算机科学导论。因此，不能简单地罗列讨论一个面面俱到的知识点集合，而应该系统地取舍和组织内容。
例如，本书使用了抽象栈（a stack of abstraction layers）概念（表1），帮助同学们融会贯通计算思维知识点。不只是停留在如何设计算法解决排序问题或斐波那契数列问题，而是贯穿从算法到电路实现的全栈，下沉到如何用高级语言程序和汇编语言指令实现循环，直到布尔电路层面。这使得同学们从单纯的计算机用户变成了计算机设计者，有利于提升技能到创造层次。这就像语文课要求同学们不只是能够读文章，还能够写文章。为了避免烦琐细节，组合电路和时序电路层面只考虑加法。掌握了做加法的原理，就可推广到做减法、乘法、除法，乃至实现各种组合电路和时序电路。表1抽象栈概念示意
3. 胜任力本位教育
ACM与IEEECS在2021年联合发布了《计算课程体系规范》。它由全球20多个计算机学会（包括中国计算机学会）的专家共同制定。这个规范有两个当代特色值得重视。
(1) 教育理念从知识本位教育（knowledgebased education）转向胜任力本位教育（competencybased education），其中:
胜任力=知识+技能+品行
Competency=Knowledge+Skills+Dispositions
(2) 认知技能采纳了教育学中的布鲁姆教育目标六等级（Blooms Taxonomy），即记忆、理解、应用、分析、评估和创造，如图1所示。
图1布鲁姆教育目标六等级(2001年修订版)
本课程倡导将布鲁姆教育目标从记忆等级提升到创造等级，品行方面鼓励想象力。
参考胜任力本位教育理念，本课程的教育目标还可归纳为表2所示。其中，期望同学们对基础知识点的掌握50%达到创造等级，25%达到理解等级。品行不是简单的“如何做人”，而是鼓励计算思维的想象力、热情与责任心。在此基础上领悟对计算思维的10个理解。表2本课程的教育目标胜任力(Competency)知识(Knowledge)技能(Skills)品行(Dispositions)针对问题求解和创造性表达的胜任力抽象计算机、真实计算机、计算机应用、数字符号、抽象、算法、人工制品、指数增长、计算能力的基本极限、人类智能相关的活动50% 创造
(Create)
25% 理解
(Understand)
25% 记忆
(Remember)想象力
(Imagination)
热情
(Passion)
责任心
(Responsibility)二、 教学方法〖*2〗1. 知行合一的主动学习方法本课程融合了当代计算机科学教育理念，提倡知行合一的主动学习方法。本书在阐述狭义的计算机科学知识之外，还用不少篇幅讲述创新故事，并通过动手动脑的课程实验，鼓励同学们创造性地学习。这种方法有利于提升同学们的学习主动性，有利于实践胜任力本位教育。这种主动学习方法不同于高中学习，对本科一年级同学具有一定挑战性，需要教学团队实践“有温度的”教学。本书的内容组织考虑了教学的主动性与温度。
通过知行合一的主动学习方式，同学们能够达到表3的学习目标。可以看出，它们覆盖了《计算机科学基础报告》的基本要点。续表表3学完本书后同学们能够达到的学习目标《计算机科学基础报告》
的基本要点知行合一的学习目标举例抽象计算机实现二进制串行加法器的图灵机真实计算机在笔记本计算机上编写执行简单程序解决问题计算机应用信息隐藏应用程序数字符号从比特、字节、数、字符、图像到网页的各种数字符号；从加、减、乘、除到赋值语句的各种操作符号抽象布尔变量、整数、字符、数组、切片等数据抽象；顺序、条件判断、循环、函数调用、递归等控制抽象；组合电路、时序电路、指令流水线等硬件抽象；指令、进程、程序等软件抽象算法高德纳算法定义；分治算法、动态规划算法、快速排序算法人工制品动态网页个人作品指数增长“P与NP”的基本概念；摩尔定律计算能力的基本极限图灵可计算性，邱奇图灵命题，停机问题；哥德尔不完备定理人类智能相关的活动布尔逻辑，演绎推理2. 高德纳测试
在2020年2月的一次科技媒体访谈中，高德纳老师提出了一个终极测试。他说: “我是否理解某项知识的终极测试，是看我能否向计算机讲解清楚。”为了避免断章取义，我们列出完整的英文原文段落: The ultimate test of whether I understand something is if I can explain it to a computer. I can say something to you and youll nod your head, but Im not sure that I explained it well. But the computer doesnt nod its head. It repeats back exactly what I tell it. In most of life, you can bluff, but not with computers.DAgostino S. The Computer Scientist Who Cant Stop Telling Stories. Quanta Magazine. 2020,(4). https://www.quantamagazine.org/computerscientistdonaldknuthcantstoptellingstories20200416.
本书将他的观点称为高德纳测试（Knuths Test）。这是将布鲁姆教育目标贯彻到计算机教育的一个绝妙测试，为同学们提供了一个实用的教育学工具，可用于检测自己是否掌握了某项知识或能力: 看自己能否向计算机讲清楚。
如何向计算机讲清楚一项知识或能力呢？本质上是通过比特精准的计算过程。下面列出3种具体途径。
(1) 计算机程序。将该项知识或能力具象为计算机程序，在计算机上正确地执行程序，提供典型的输入数据，返回期望的结果。例如，某位同学测试自己是否掌握“个人作品”相关知识和能力，一个途径是该同学开发一个动态网页，在计算机上运行起来，体现创造性表达。在此过程中，如果同学误解了网页相关的HTML、CSS或JavaScript知识，程序往往会出现期望之外的行为，计算机会报错。
(2) 思想实验（thought experiment）。与计算机程序途径很像，只是“计算机”变成了同学自己的大脑（或“心”）。同学自己通过“心算”，当然也可以辅之以纸和笔，在自己心中执行任意一个具体的计算过程。例如，测试是否掌握了“递归”概念，即递归函数调用，可在自己心中执行任意一个具体的递归计算过程，例如快速排序。这个途径的要点是，“心”必须装扮成一台计算机，每一步只能执行明确的步骤，响应明确的指令，使用精准的输入，产生精准的输出结果。
(3) 结对实验（pairing experiment）。与计算机程序途径很像，只是“计算机”变成了另一个同学或助教。这个途径的要点是，另一个同学必须装扮成一台计算机，每一步只能执行明确的步骤。有时，一个同学也可以扮演这两个角色: 本人和“另一个同学”。
高德纳测试可用于测试布鲁姆教育目标六等级的各个等级。下面列出对应“记忆”“理解”“创造”3个等级的教学建议和高德纳测试，并举例说明。注意，这些等级总地来讲是逐渐包含关系，高等级包含了低等级的教学要求。
(1) 记忆等级: 这是最低等级。针对每个概念或方法，每个同学能够较为精准地重述，并举一个教科书或课堂讲授提到过的实例说明。
高德纳测试例子: 可通过习题、考题、实验重现该概念或方法，并通过比特精准的计算过程，测试出重现结果是否与正确答案契合。
(2) 理解等级: 针对每个概念或方法，每个同学能够较为精准地解释它，动手动脑阐述一个具体实例，并能够举一反三，应用到讲过的问题实例的变种。
高德纳测试例子: 本书要求同学们使用图灵机实现加法器；在此过程中，同学们应该理解了使用图灵机求解问题的入门知识，从而能够自行实现本书没有阐述过的图灵机减法器。
(3) 创造等级: 掌握了课程相关的胜任力，即“知识+技能+品行”，并能够应用到新场景，定义新问题、自学新知识、提出新观点、实现新作品。这里的关键是“新”，是教科书或课堂讲授没有提到过的。
高德纳测试例子: 本课程的个人作品实验体现了高德纳测试。同学们需要无中生有地创造、构思并设计作品，在计算机上实现为动态网页，分享给全班同学。同学们需要将Go语言编程知识迁移到网页设计的新场景中，自学个人作品需要的网页设计和编程的新知识。教学团队会介绍少量入门网页编程知识，并提供动态网页实例库和答疑帮助。
三、 一年级本科生创造性学习实例
下面列举中国科学院大学的一年级本科生创造性学习的3个真实例子，进一步显示布鲁姆教育目标的“创造”等级和高德纳测试。这些实例都是同学们自己想象出来的。
【实例1】吕星宇的“活体U盘”。
本课程的信息隐藏实验要求将一个英文文本文件隐藏到一个图像文件中。在完成信息隐藏实验的实践中，中国科学院大学计算机专业的吕星宇同学发现: 中文文本文件也可以被隐藏和复原！他的好奇心和探索导致他提出了一个“活体U盘”的想法。这已经属于“创造”等级的学习了。他的这个想法大体上可以使用思想实验的途径通过高德纳测试。
(1) 吕星宇发给教师的邮件(部分内容)。
（接上封邮件）老师好，在您的启发下我突然又想到一个问题，就是生物的DNA是一串“嘌呤嘧啶对”，每个“嘌呤嘧啶对”有4种不同的取法，如果分别标记成0、1、2、3的话，那么DNA就可以等效地用一串四进制数表示了，这样的话，也可以把这个大数隐藏到文件里面，这是不是对生物信息的隐藏？……我是不是也可以把我想要隐藏的信息通过修改DNA中的“冗余片段”实现隐藏？更进一步地，我让这个DNA控制发育成一个生命体，比如小白鼠，看起来它跟其他的小白鼠没什么不一样，但它却成了一个“活体U盘”，无时无刻不携带着一段有用的信息！甚至可以通过克隆这只小白鼠实现信息的克隆与传递。
也就是说，我既可以把一只小白鼠隐藏到《蒙娜丽莎》里面，也可以把《蒙娜丽莎》隐藏到小白鼠里面？
(2) 教师的回复(事实上，吕星宇的想法已经不限于DNA存储的范围)。
星宇，你提出了一个很妙的想法。已经有一些初步进展了，同行称为“DNA存储”。如你有兴趣，请搜索“DNA存储”，或读一下《国家科学评论》的最新综述:
DNA Storage: Research Landscape and Future Prospects
https://doi.org/10.1093/nsr/nwaa007
【实例2】李思悦的“猫猫指挥家”。
中国科学院大学物理专业的李思悦同学花了3天创建了个人作品“猫猫指挥家”（图2）。其中，大概50%的时间用于构思、设计，50%的时间用于编码。
李思悦仅用155行代码就实现了“猫猫指挥家”动态网页。3个可爱的小猫组成敲锣、打鼓、敲击三角铁的小乐队，玩家担任指挥，可单击某只小猫感受单独效果，也可输入一段由1、2、3组成的数字串乐谱演奏一段打击乐。她通过主动学习，掌握了必要的动态网页知识和创造性表达能力，达到了布鲁姆教育目标中的“创造”等级。这个作品显然可以采用程序运行途径通过高德纳测试。当然，创造性表达的程度涉及主观判断。
图2李思悦同学的个人作品“猫猫指挥家”截图，课程网站有完整作品
【实例3】董可昕的“绮”。
中国科学院大学生物专业的董可昕同学创造了个人作品“绮”，一个人眼色彩辨别力测试小游戏（图3）。她用简洁的代码实现了动态网页，通过闯关游戏测试玩家的人眼色彩辨别力，体现了创造性表达。
“绮”是一个简洁、独立完整、有趣、有温度的个人作品。
(1) 简洁: 整个动态网页“绮 2.0”包含172行HTML/CSS/JavaScript代码，包括必要的重复代码。“绮 3.0”包含215行代码，增加了三级难度功能。
(2) 自包含: 整个动态网页软件是董可昕同学自己编写的，有一定深度。
(3) 有趣: 这是一个有趣的攻关小游戏，可在计算机和手机上玩，可能需调整风格。
(4) 有温度: 与用户交互有温度。例如:
① ……小鼹鼠……别气馁，再玩一次吧～
② 时间到啦！60秒内您共通过15关，您的色彩辨别力大约相当于一只西伯利亚哈士奇……别气馁，再玩一次吧～
③ ……您的色彩辨别力和小海豹一样优秀！再玩一次吧～
④ ……您的色彩辨别力和小蜻蜓一样敏锐～棒棒哒～再玩一次吧～
⑤ ……您的色彩辨别力如猫头鹰一样敏锐！再玩一次吧～
⑥ ……明察秋毫！您就是苍鹰本鹰！再玩一次吧～
(5) 有致谢: 尽管整个动态网页软件是自己编写的，董可昕同学致谢了对她的创作工作有帮助的老师和同学，以及用到的一个网络背景资源。
(6) 有记录: 董可昕同学维护了一个《个人网页日记》。
教师也指出了可能改进的方向。作品展现的识别能力真的与自然契合吗，确实反映了小鼹鼠、哈士奇、……、苍鹰的眼力吗？作品是一个艺术品，创造性表达是重点，可以夸张或偏离。董可昕同学有兴趣、有时间的话，可考虑以作品为基础做本科研究工作，较为真实地反映自然，这样一来，作品就变成了一件有实用价值的软件，可以开源贡献给世界。
图3董可昕同学的个人作品“绮3.0”截图，课程网站有完整作品