计算机科学导论的高德纳测试教学法_徐志伟.pdf

21计 算 机 教 育Computer Education第 4 期2023 年 4 月 10 日中图分类号：G642基金项目：教育部 101 计划项目（教高厅函 202213 号）。第一作者简介：徐志伟，男，研究员，研究方向为分布式系统、计算思维教育，。0引 言随着人类进入信息社会，大学计算机基础（又名计算机科学导论、计算概论等）已经成为很多中外大学的基础性必修课。教育界近年来重视通过“计算思维”改革课程教学1-5，以建立新的时代意识：农业社会必教语文，工业社会必教数学，信息社会必教计算。一直以来，计算思维教学面临落地难题，文献 3 中提出了 5 个具体的落地问题。自 2010 年以来，通过调研国内外 20 余所大学的经验，并经过 9 年以计算思维为主线设计计算机科学导论课程的教学实践，初步回答以下 5 个计算思维落地问题。（1）计算思维有哪些基本的组成部分？（2）这些基本的组成部分的特征和表现是 什么？（3）这些组成部分如何在计算机课程中 讲授？（4）计算思维的培养能否像知识点或者技能点那样进行建构？（5）培养计算思维的课程体系和课程要求应该是什么样的？中国科学院大学的计算机导论课程确定了对计算思维的 10 个理解4-5，回答了问题 12。教计算机科学导论的高德纳测试教学法徐志伟1，2，李振营1，2，俞子舒1，2，翟 恋1，2（1.中国科学院 计算技术研究所，北京 100190；2.中国科学院大学 计算机科学与技术学院，北京 100049）摘 要：针对计算思维在计算机科学导论课程中难以落地的问题，从高德纳（Donald Knuth）的大师观点出发，提出一种名为高德纳测试的知行合一教学法，并给出涉及数学概念、算法程序、硬件、创造性表达的实例，以说明高德纳测试适用于逻辑思维、算法思维、系统思维、网络思维等计算思维知识点的教学。关键词：大学计算机基础；计算机科学导论；计算思维；高德纳测试；知行合一教学法文章编号：1672-5913(2023)04-0021-05学实践表明，问题 35 都有正面回答，其核心是一种“知行合一”教学方法，要点是落实到可操作性层面，让教学团队和学生能够“动手动脑动心”地实践。借鉴图灵测试将机器智能理念落地的成功经验，可以将知行合一理念具体落地为高德纳测试教学法。1高德纳的大师观点“理解某项科学知识的终极测试，是向计算机解释清楚”，高德纳的这个观点为计算机科学导论教学如何实践知行合一提供了根本指引，它倡导一种教学方法，激励学生将知识点向计算机讲清楚。该方法也提供一种客观测试，度量学生对知识点的掌握是否达到了布鲁姆教学目标的“理解”层级。为什么将这句话称为大师观点呢？不仅因为高德纳是一位大师，还因为高德纳在近 50 年的时间里反复阐述这个对计算机学科极其重要的思维性观点。以下是 3 个例子。在 1974 年图灵奖获奖演说中，高德纳首次提出了这一观点，以阐述文科和理科的异同。科学与艺术有什么区别？理学（Science）与文学（Art）为什么是不同的学科？因为“科学是我们DOI:10.16512/ki.jsjjy.2023.04.015202322计 算 机 教 育Computer Education理解得足够清楚以致能教会计算机的知识”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 所示。针对人 针对机 教师 L 计算机C学生 S 问题q 解答a 知识点 K Q 图 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 是针对单一知识点的。一个真实的高德纳测试往往涉及多个知识点。一门课程可有多个高德纳测试。如何设计它们，使其合理地分工衔接，形成一个整体的高德专题策划CC2020 前沿第 4 期23纳测试教学法实践？（2）知识点刻画难点。教师（Lecturer L）以人能够理解的形式对学生讲授知识点 K（Knowl-edge），如真值表；同时以计算机能够理解的形式告诉它知识点 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。例如，课程在逻辑思维环节首次学习真值表。前置知识点包括简单命题、复合命题（也称为布尔表达式）。涉及的逻辑连接词，即布尔运算符，包括与（PQ）、或（PQ）、非（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。202324计 算 机 教 育Computer Education以 P Q的真值表为例（见表 1），它一共有 3 列，包含两个简单命题和一个复合命题，其间用一条双线区分开。两个简单命题的取值可有4 种组合，因此表身行号对应十进制的 0、1、2、3。复合命题 P Q的取值由逻辑与运算决定，除了第 3 行单元（标粗）外，其他单元取值为 0。后面讲解组合电路时，再推导出 S 与 Cout的命题公式。表 1 复合命题 P Q的真值表及其注释表头行PQP Q00001010210031112）重要性质。在入门课中值得指出定义型性质和导出型 性质。（1）定义型性质：P Q、P Q P 是两个不同的复合命题，但它们具有同样的真值表，因此是等价命题。（2）导出型性质：两个简单命题一个复合命题的不同真值表一共有 222=16 个。3）教学难点。计算机科学导论教学主要有两类难点，一是根据历年教学经验总结出的学生容易混淆出错的故障点（bugs）。教师须指出或澄清，并让学生有机会练习。二是教师有意引入错误（称为炸弹 bombs），让学生改正，以加深对知识点的理解。例如，学生对包含蕴含运算符（）的命题容易犯错。除了用“P Q等价于 P Q”澄清外，还可设计如下炸弹作业题：请改正下面真值表（见表 2）中的全部错误。表 2 与蕴含相关的 4 类复合命题的真值表PQ本命题PQ逆命题QP否命题 P Q逆否命题 Q P0000000100001000001111114）整体衔接要点。上面真值表用法是给定命题公式，列出其真值。另一个用途是给定真值，求出对应的命题公式。一个例子是全加器组合电路设计。在讲真值表时，只需指出“真值表可用于设计组合电路”，给出全加器输出变量 S 与 Cout的真值（见表 3）；表 3 全加器的真值表CinXYSCout00000001100101001101100101010111001111113.2真值表的概要以下概要形式化地规约了任意命题 P 的真值表，包括精确地定义 RPCC 四元素描述。概要包括 3 部分：概要签名（第 1 行），定义变量的变量段（第 26 行），以及刻画规则、性质、难点、衔接的性质段（第 726 行）。注释以#开头。1 profile TruthTable(p)2#使用 GetVars 获取 p 中所有简单命题3 vars=GetVars(p)4 n=Len(vars)5#定义 table 的初始值，2n+1 行，n+1 列6 table=row in 0.2n:col in 0.n:7 8#真值表的定义规则9#表头包含所有简单命题和该复合命题10 table 0=vars o p11#依次列出简单命题取 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).table1:=TruthTable(y).table1:20#教学难点21 assert Equals(P Q,P Q)22#整体衔接要点23#真值表概要可被组合电路概要导入24#imported by CombinationalCircuit25#组合电路概要有与的推导26 专题策划CC2020 前沿第 4 期254教学效果高德纳测试教学法已经在中国科学院大学计算机科学导论课程教学中实践了 3 年，其知行合一方法体现为多类实践。本节简要讨论真值表之外的 3 个实例（见表 4），它们在知识点类别、思维类别、实践类别、布鲁姆层级方面具备代表性。在此过程中，学生须自学必需的 HTML/CSS/JavaScript 知识。令人惊喜的是，非计算机专业学生创造出了更多的优秀作品。目前还不能向计算机讲清楚“创造性”，只能由教学团队评判。从课程总成绩看，高德纳测试教学法适合所有专业的一年级本科生，他们与计算机专业学生的成绩差别并不大（见表 5）。表 4 4 个实例的代表性实例知识类别思维类别实践类别布鲁姆层级真值表数学逻辑作业理解简版快排软件算法、系统实验理解、应用减法器硬件系统闭卷考试举一反三应用动态网页服务网络实验创造性表达（1）简化版快速排序。这个编程实验让学生实现一个 fastsort 算法，它与 quicksort 算法的唯一区别是固定标杆（pivot），而不是随机选择标杆。知识点是快排特有的通过比较操作划分数据的方式，以及递归与切片编程知识。虽然 70%的学生没有任何编程经验，但是 99%的学生都以满分通过了高德纳测试。（2）串行减法器时序电路。在课堂讲授串行加法器时序电路的基础上，期末闭卷考试要求学生设计一个减法器，考查举一反三的创造性学习能力。此题成绩满足考试区分度要求。（3）动态网页个人作品。该实验是课程的最后一个实验，要求每个学生设计实现一个动态网页作品，并体现自己的创造性表达能力和兴趣。表 5 课程成绩累积分布函数 CDF专业类别成绩累积分布函数1009060计算机专业学生（110 名）0%27%99%所有专业学生（340 名）0%22%94%参考文献：1 Wing J M.Computational thinkingJ.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 scienceM.Berlin:Springer,2021.6 Knuth D E.Computer programming as an artJ.Communications of the ACM,1974,17(12):667-673.7 Knuth D E.Foreword to A=BM.Massachusetts:A K Peters,1995.8 Susan D Agostino.The computer scientist who can t stop telling storiesEB/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 mathematicsM.Berlin:Springer Science&Business Media,2010.13 Lamport L.Specifying systems:The TLA+language and tools for hardware and software engineersM.Boston:Addison-Wesley.2002.14 Lamport L.The PlusCal algorithm languageC/International Colloquium on Theoretical Aspects of Computing.Berlin:Springer,2009:36-60.（编辑：宋文婷）5结 语高德纳测试教学法是一种知行合一方法，有利于学生“动手动脑动心”地掌握计算机科学导论的知识，达到布鲁姆教学目标的“理解”及以上的层级。应用该方法要求教师构建课程知识图谱，以自然语言描述和形式化概要的方式刻画知识点，并指导计算机自动构建动态题集。学生提交的解答被教学平台识别为程序或规约，能够被计算机自动执行或模型检测，进而评判正确性，从而实现“向计算机讲清楚知识点”的目的。如何设计出高德纳测试，能够检验个性化变形后题目的公平性、限制每次测试的题目数量、判定解答的创造性？这些工作目前是由教学团队人工把握的。未来一个研究方向是如何设计出更加自动并智能的高德纳测试。