计算机科学导论的高德纳测试教学法

0 引 言

随着人类进入信息社会，大学计算机基础（又名计算机科学导论、计算概论等）已经成为很多中外大学的基础性必修课。教育界近年来重视通过“计算思维”改革课程教学[1-5]，以建立新的时代意识：农业社会必教语文，工业社会必教数学，信息社会必教计算。

一直以来，计算思维教学面临落地难题，文献[3]中提出了5个具体的落地问题。自2010年以来，通过调研国内外20余所大学的经验，并经过9年以计算思维为主线设计计算机科学导论课程的教学实践，初步回答以下5个计算思维落地问题。

（1）计算思维有哪些基本的组成部分？

（2）这些基本的组成部分的特征和表现是什么？

（3）这些组成部分如何在计算机课程中讲授？

（4）计算思维的培养能否像知识点或者技能点那样进行建构？

（5）培养计算思维的课程体系和课程要求应该是什么样的？

中国科学院大学的计算机导论课程确定了对计算思维的10个理解[4-5]，回答了问题1—2。教学实践表明，问题3—5都有正面回答，其核心是一种“知行合一”教学方法，要点是落实到可操作性层面，让教学团队和学生能够“动手动脑动心”地实践。

借鉴图灵测试将机器智能理念落地的成功经验，可以将知行合一理念具体落地为高德纳测试教学法。

1 高德纳的大师观点

“理解某项科学知识的终极测试，是向计算机解释清楚”，高德纳的这个观点为计算机科学导论教学如何实践知行合一提供了根本指引，它倡导一种教学方法，激励学生将知识点向计算机讲清楚。该方法也提供一种客观测试，度量学生对知识点的掌握是否达到了布鲁姆教学目标的“理解”层级。

为什么将这句话称为大师观点呢？不仅因为高德纳是一位大师，还因为高德纳在近50年的时间里反复阐述这个对计算机学科极其重要的思维性观点。以下是3个例子。

在1974年图灵奖获奖演说中，高德纳首次提出了这一观点，以阐述文科和理科的异同。科学与艺术有什么区别？理学（Science）与文学（Art）为什么是不同的学科？因为“科学是我们理解得足够清楚以致能教会计算机的知识”[6]。

在1995年，高德纳再次重申：“我们足够理解以致能向计算机解释清楚的，是科学；我们从事的其他种种，是艺术”[7]。

最近一次是2020年，高德纳将他的观点进一步陈述为一种对教育效果的终极测试。他说：“我是否理解某项科学知识的终极测试，是看我能否向计算机解释清楚”[8]。

2 高德纳测试教学法

2.1 高德纳测试的设计考虑

高德纳观点是一种智慧，需要变换成为“高德纳测试”，一个像图灵测试那样的可操作过程，进而发展成为一种知行合一教学法。设计高德纳测试需要解决3方面的问题，分别对应于测试方法选择、测试效果和具体落地的挑战。

第一，如何“教会计算机”？如何“向计算机讲清楚”？高德纳指出：“计算机程序为我们提供了极其有用的测试工具，以测试我们对任何知识的理解深度”[6]。因此，最简单直接的办法是让学生编写程序在计算机上执行，以展示自己对科学知识的理解，该方法还可以有很多变种。例如，学生可请同学结伴手算，同学严格扮演比特精准的计算机角色；学生也可以像爱因斯坦那样做思维实验，自我扮演计算机角色。

第二，如何保证学生“理解了知识”？即使学生将某项知识向计算机讲清楚了，怎么保证学生就理解了知识，而不是诈唬混过的？高德纳认为计算机与人有本质不同，从度量教学效果看计算机更严谨。他对采访他的科技期刊记者说：“我可以对你解说某项知识，而你会点头，但我不确信我解释清楚了，但计算机不点头，它精确地重复我告诉它的知识。在人生中你可诈唬混过，但对计算机你无法诈唬”[8]。

第三，如何解决计算机科学导论课程的如下4个实际教学挑战？

（1）专业挑战。是否需要对计算机专业和非专业学生分别开不同的课？对他们的布鲁姆教学目标层级（即CC2020的技能层级）[9]是否应有不同要求？

（2）导论挑战。如何把握并反映导论课的要求？尤其是大部分修课学生“不识字”，从未写过计算机程序，也未读过别人写的程序。

（3）规模挑战。如何有效支持成百上千名学生？高德纳认为应该利用计算机实现自动化[6]。这当然包括自动批改习题和实验，还包括其他更深刻的教学环节与做法。10年前，我们征求Armando Fox教授对规模挑战的意见，他认为软件教育的未来形态是互联网服务（SaaS）。他们的这套教学方法在UC-Berkeley的软件工程导论课程中，已成功得到了规模化实践[10-11]。

（4）划水挑战。瞎蒙、搭便车、作弊等老问题，特别是选课学生人数较多的课程。

2.2 计算机科学导论的高德纳测试

具备操作性的高德纳测试定义涉及3个角色，如图1所示。

高德纳测试：

（1）测试目的：测试学生S是否理解了知识点K。

（2）测试过程：在测试时间区间[0，T]，计算机C向学生S提出与知识点K相关的问题集Q中的任意问题q，学生S向计算机C提交对q的解答a，计算机C判定解答a正确或错误。

（3）测试结果：如果学生S的解答正确率≥90%，则判定学生S理解了知识点K。

图1的高德纳测试简图需要如下7个注释，这些注释也表明了高德纳测试的实现难点。可以看出，高德纳测试是一个人机协同的过程。

（1）整体衔接难点。图1是针对单一知识点的。一个真实的高德纳测试往往涉及多个知识点。一门课程可有多个高德纳测试。如何设计它们，使其合理地分工衔接，形成一个整体的高德纳测试教学法实践？

（2）知识点刻画难点。教师（Lecturer L）以人能够理解的形式对学生讲授知识点K（Knowledge），如真值表；同时以计算机能够理解的形式告诉它知识点K。知识点K的这两个形式是什么？

（3）问题集生成难点。计算机（Computer C）自动产生反映知识点K的问题集Q（Questions），其中每个问题q应该以人能够理解的形式提供给学生。问题形式以及问题集Q的内容是什么？

（4）自动判题难点。学生（Student S）以计算机能够理解的形式告诉它对问题q的解答a，以便计算机能够自动判定解答a的正确性。对Q中所有问题的解答集记为A。解答形式是什么？

（5）题目数量选择难点。一次测试可有多个问题和解答，即在测试时间[0，T]之内，计算机可提出与知识点K相关的多个问题，并从学生中收到对应的多个解答。一次测试中，计算机需要评判多少道题？

（6）优化测试时间难点。一次测试的时间T可根据测试内容和类型调整，从几分钟到几周。中国科学院大学的课堂小测验只需要几分钟，每次家庭作业测试时间是1周，每次实验（大作业）是3周，期末考试是3小时。教学时间是宝贵资源，测试时间必然占据教学时间。如何优化测试时间？

（7）判定标准难点。90%正确率是中国科学院大学的计算机科学导论教学团队当前内部掌握的经验性判定标准。什么是合适的比例？选取满分100%或小于60%的正确率作为“学生理解了知识点”的判定标准，都不太合适。

2.3 应用高德纳测试

1）计算思维体现。

任何科学都有其精准性。计算机科学强调比特精准，即计算过程每一步的每一个比特都是正确的。教师通过讲授真值表知识帮助学生理解比特精准。真值表采用特殊的表格形式表示二值函数（布尔函数），是比特精准的基本体现。要求学生理解真值表每一个单元的0值或1值。

2）整体衔接。

知识点的内容由教学团队（图1中的教师）决定。具体的知识表示形式，参考了知识空间和学习空间理论[12]。

例如，课程在逻辑思维环节首次学习真值表。前置知识点包括简单命题、复合命题（也称为布尔表达式）。涉及的逻辑连接词，即布尔运算符，包括与（P∧Q）、或（P∨Q）、非（¬P）、蕴含（P→Q）、异或（P⊕Q）。后续知识点包括在程序设计环节的操作特定比特的编程知识，以及系统思维环节的全加器组合电路例子。教师在课堂讲授时应指出这些知识点的前后衔接呼应。

3）知识点及其问题集刻画。

如何刻画某个知识点及其问题集，有助于学生通过高德纳测试呢？

（1）知识点描述。遵循一种四要素模板方法，简称RPCC方法。这四要素是知识点的构造性定义规则（Rules）、重要性质（Properties）、教学难点（Cruxes）以及整体衔接要点（Cohesion）。后两者即教学难点与衔接要点，反映了教学团队的教学经验与教学特色。

（2）知识点概要。从教师提供的知识点描述，教师进一步构建出知识点概要（profile），它是一种形式化规约（specification）。概要是在TLA+和PlusCal基础上构建的[13-14]，具备更高的抽象层次以便于刻画知识点，但仍可被计算机自动地模型检测（model check）。

（3）动态题集。依据知识点概要，计算机在教师的指导下自动生成包含正确答案的动态题集。这类似监督学习中的训练集。学生提供的解答在本质上是规约或程序，能够被计算机自动地模型检测或自动执行。题目的形式需要避免高德纳指出的“点头”（nod）和“诈唬”（bluff）两个缺点，尤其是减小选择题中瞎蒙的作用。每个学生的题目应当不同且难度相当，以应对划水挑战。

3 真值表实例

3.1 知识点描述四要素

1）真值表的定义规则。

给定任意命题公式，也称为布尔表达式，其真值表由若干行和列构成，含一个表头行。每个真值表单元对应特定的列与非表头行，每个单元只能取值0或1。

以P∧Q的真值表为例（见表1），它一共有3列，包含两个简单命题和一个复合命题，其间用一条双线区分开。两个简单命题的取值可有4种组合，因此表身行号对应十进制的0、1、2、3。复合命题P∧Q的取值由逻辑与运算决定，除了第3行单元（标粗）外，其他单元取值为0。

2）重要性质。

在入门课中值得指出定义型性质和导出型性质。

（1）定义型性质：P∧Q、P∧Q∧P是两个不同的复合命题，但它们具有同样的真值表，因此是等价命题。

（2）导出型性质：两个简单命题一个复合命题的不同真值表一共有

=16个。

3）教学难点。

计算机科学导论教学主要有两类难点，一是根据历年教学经验总结出的学生容易混淆出错的故障点（bugs）。教师须指出或澄清，并让学生有机会练习。二是教师有意引入错误（称为炸弹bombs），让学生改正，以加深对知识点的理解。例如，学生对包含蕴含运算符（→）的命题容易犯错。除了用“P→Q等价于P∨Q”澄清外，还可设计如下炸弹作业题：请改正下面真值表（见表2）中的全部错误。

4）整体衔接要点。

上面真值表用法是给定命题公式，列出其真值。另一个用途是给定真值，求出对应的命题公式。一个例子是全加器组合电路设计。在讲真值表时，只需指出“真值表可用于设计组合电路”，给出全加器输出变量S与Cout的真值（见表3）；后面讲解组合电路时，再推导出S与Cout的命题公式。

3.2 真值表的概要

以下概要形式化地规约了任意命题P的真值表，包括精确地定义RPCC四元素描述。概要包括3部分：概要签名（第1行），定义变量的变量段（第2~6行），以及刻画规则、性质、难点、衔接的性质段（第7~26行）。注释以#开头。

1 profile TruthTable (p)

2  # 使用GetVars获取p中所有简单命题

3  vars = GetVars(p)

4  n = Len(vars)

5  #定义table的初始值， 2^n+1行，n+1列

6  table = {row in 0..2^n: {col in 0..n: ""}}

7 {

8  # 真值表的定义规则

9  # 表头包含所有简单命题和该复合命题

10  table [0] = vars \o [p]

11  # 依次列出简单命题取0、1值的所有组合

12  for i, values in {1..n -> {0, 1}}

13  #Eval计算vars取值为values时p的值

14  table [i+1] = values \o Eval(p, vars, values)

15  # 重要性质

16  # 真值表相同的命题是等价命题

17  Equals(x, y) =

18  TruthTable(x).vars == TruthTable(y).vars&&

19  TruthTable(x).table[1:]== TruthTable(y).table[1:]

20  # 教学难点

21  assert Equals("P→Q", "~P∨Q")

22  #整体衔接要点

23  # 真值表概要可被组合电路概要导入

24  # imported by [CombinationalCircuit]

25  #组合电路概要有与的推导

26 }

4 教学效果

高德纳测试教学法已经在中国科学院大学计算机科学导论课程教学中实践了3年，其知行合一方法体现为多类实践。本节简要讨论真值表之外的3个实例（见表4），它们在知识点类别、思维类别、实践类别、布鲁姆层级方面具备代表性。

（1）简化版快速排序。这个编程实验让学生实现一个fastsort算法，它与quicksort算法的唯一区别是固定标杆（pivot），而不是随机选择标杆。知识点是快排特有的通过比较操作划分数据的方式，以及递归与切片编程知识。虽然70%的学生没有任何编程经验，但是99%的学生都以满分通过了高德纳测试。

（2）串行减法器时序电路。在课堂讲授串行加法器时序电路的基础上，期末闭卷考试要求学生设计一个减法器，考查举一反三的创造性学习能力。此题成绩满足考试区分度要求。

（3）动态网页个人作品。该实验是课程的最后一个实验，要求每个学生设计实现一个动态网页作品，并体现自己的创造性表达能力和兴趣。在此过程中，学生须自学必需的HTML/CSS/JavaScript知识。令人惊喜的是，非计算机专业学生创造出了更多的优秀作品。目前还不能向计算机讲清楚“创造性”，只能由教学团队评判。

从课程总成绩看，高德纳测试教学法适合所有专业的一年级本科生，他们与计算机专业学生的成绩差别并不大（见表5）。

5 结 语

高德纳测试教学法是一种知行合一方法，有利于学生“动手动脑动心”地掌握计算机科学导论的知识，达到布鲁姆教学目标的“理解”及以上的层级。应用该方法要求教师构建课程知识图谱，以自然语言描述和形式化概要的方式刻画知识点，并指导计算机自动构建动态题集。学生提交的解答被教学平台识别为程序或规约，能够被计算机自动执行或模型检测，进而评判正确性，从而实现“向计算机讲清楚知识点”的目的。

如何设计出高德纳测试，能够检验个性化变形后题目的公平性、限制每次测试的题目数量、判定解答的创造性？这些工作目前是由教学团队人工把握的。未来一个研究方向是如何设计出更加自动并智能的高德纳测试。

参考文献：

[1] Wing J M. Computational thinking[J]. Communications of the ACM, 2006, 49(3): 33-35.

[2] 陈国良, 董荣胜. 计算思维与大学计算机基础教育[J]. 中国大学教学, 2011, 1(7): 11.

[3] 李廉. 计算思维——概念与挑战[J]. 中国大学教学, 2012, 1(7): l2.

[4] 徐志伟, 孙晓明. 计算机科学导论[M]. 北京: 清华大学出版社, 2018.

[5] Xu Z, Zhang J. Computational thinking: A perspective on computer science[M]. berlin: Springer, 2021.

[6] Knuth D E. Computer programming as an art[J] . Communications of the ACM, 1974, 17(12): 667-673.

[7] Knuth D E. Foreword to A=B[M]. massachusetts: A K Peters, 1995.

[8] Susan D’Agostino. The computer scientist who can’t stop telling stories[EB/OL]. [2023-01-01]. https: //www. quantamagazine. org/computer-scientist-donald-knuth-cant-stop-telling-stories-20200416/.

[9] 张铭, 陈娟. ACM/IEEE CC2020胜任力模型对中国计算机教育发展的影响[J]. 计算机教育, 2023(4): 3-9.

[10] Fox A. From MOOCs to SPOCs: Curricular technology transfer for the 21st century [J]. ACMUbiquity, 2014(June): 1-13.

[11] Fox A, Patterson D A. Engineering software as a service: An agile approach using cloud computing [M]. 2nd Ed. 2021. http: //www. saasbook. info/. ISBN: 978-1735233802.

[12] Falmagne J C, Doignon J P. Learning spaces: Interdisciplinary applied mathematics[M]. berlin: Springer Science & Business Media, 2010.

[13] Lamport L. Specifying systems: The TLA+ language and tools for hardware and software engineers[M]. boston: Addison-Wesley. 2002.

[14] Lamport L. The PlusCal algorithm language[C]//International Colloquium on Theoretical Aspects of Computing. Berlin: Springer , 2009: 36-60.

基金项目：教育部101计划项目（教高厅函[2022]13号）。

第一作者简介：徐志伟，男，中国科学院研究员，研究方向为分布式系统、计算思维教育，zxu@ict.ac.cn。

引文格式：徐志伟，李振营，俞子舒，等. 计算机科学导论的高德纳测试教学法[J].计算机教育,2023(4)：21-25.

转自：“计算机教育”微信公众号

如有侵权，请联系本站删除！