离散数学教学中的计算思维培养

　　摘要：作为一项重要的教育理念，计算思维得到了国内外科学界和教育界的广泛关注，相应地对计算机专业的人才培养提出了新的要求。本文分析了计算思维培养与离散数学教学之间的内在关系，在此基础上分别从课程引入和课程教学两个阶段探讨如何将离散数学教学与计算思维培养有机地结合起来。通过案例，着重论述了如何将抽象和自动化这两个核心思想贯穿于整个教学过程，以及如何根据所讲授的知识点适时地引入计算思维中其他基本概念和思维方法。
　　关键词：计算思维；离散数学；教学方法；抽象；自动化
　　
　　计算思维是卡内基梅隆大学计算机科学系主任Jeannette M. Wing教授在2006年提出的教育理念[1]，被认为是近十年来产生的最具有基础性、长期性的重要思想[2]。Wing教授认为计算思维不仅仅属于计算机科学家，还应该和阅读、写作和算术一样，成为21世纪每个人必须具备的基本技能。
　　计算思维的概念一经提出就引起了国内外科学界和教育界的广泛关注。科学界主要关注于计算思维如何深刻影响其他领域的思考方式，进而如何促进其他领域的创新能力。例如美国国家科学基金会于2008年启动了以计算思维为核心的重大基础研究计划“计算使能的科学发现与技术创新”，旨在通过计算思维领域的创新和进步来促进自然科学和工程技术领域产生革命性的成果。教育界主要关注于对计算思维能力的培养。例如ACM和IEEE-CS在修订后的计算机科学教程2008(Computer Science Curriculum 2008)[3]79-84中明确指出应该将计算思维作为计算机科学教学的重要组成部分。
　　计算思维对计算机专业的人才培养提出了新的要求。针对计算思维培养问题，文献[4]介绍了普渡大学开设计算思维导论课程取得的经验。文献[5]对以计算思维为基础和以学科思想与方法为基础的两类计算机导论课程进行了分析比较。文献[6]探讨了如何在程序设计课程中强化学生的计算思维能力。文献[7]和文献[8]分别探讨了如何在编译原理课程和人工智能课程中培养学生的计算思维能力。
　　离散数学是计算机专业的核心基础课程；该课程不仅为数据结构、编译原理、操作系统、数据库原理、人工智能等专业课程提供必须的基础知识，更是对培养学生的抽象思维能力和逻辑思维能力起着重要作用。因此，针对培养学生的计算思维能力这个新的目标，抓好离散数学课程的教学显得尤其重要。本文首先对计算思维培养与离散数学教学之间的内在关系进行分析，然后通过若干案例探讨如何在离散数学教学中加强对计算思维能力的培养。
　　1计算思维培养与离散数学教学
　　在探讨对计算思维能力的培养之前我们需要明确什么是计算思维。根据Cuny、Snyder和Wing等的定义[9]，计算思维是指对问题及其解决方案进行阐释进而将解决方案表示成可以被信息处理代理(information-processing agent)有效实现的形式的思维过程。从这个定义可以看出，计算思维最本质的内容是抽象和自动化；而这两个内容恰好反映了计算的根本问题，即什么能被有效地自动进行。
　　从外延的角度来看，计算思维运用计算机科学的基本概念来求解问题、设计系统和理解人类行为，包括了一系列广泛的计算机科学的思维方法[1]。例如，计算思维通过约简、嵌入、转化、仿真等方法，把一个看起来困难的问题重新阐释成一个我们知道如何解决的问题；计算思维采用抽象和分解来迎接庞杂的任务；计算思维选择合适的表示方式来陈述一个问题或者对问题的相关方面进行建模，从而使问题易于处理；计算思维通过冗余、容错、纠错等方法来预防、检测或者从最坏的情况恢复系统；计算思维在时间与空间，处理能力与存储容量等之间进行折中，计算思维进行递归思考等等。
　　根据Jeannette M. Wing等的设想[9]，一个人具备计算思维能力之后将体现在以下方面：给定一个问题，能够理解其哪些方面是可以计算的；能够对计算工具或技术与需要解决的问题之间的匹配程度进行评估，能够理解计算工具和技术所具有的能力和局限性；能够将计算工具和技术用于解决新的问题；能够识别出使用新的计算方式的机会；能够在任何领域应用诸如分而治之等计算策略。此外，对于科学家、工程师以及其他专业人士来说，具备计算思维能力之后还应该能够应用新的计算方法来解决具体的专业问题，能够对问题进行重新阐释从而可以采用计算策略，能够通过分析大型的数据从而得到新的科学发现，能够提出之前没有想过或者由于问题的规模不敢提出但采用计算的方式容易处理的问题，能够应用计算的术语对问题及其解决方案进行解释等等。
　　基于以上分析我们认为，为了培养学生的计算思维能力，最为关键的是抓住抽象和自动化这两个核心内容。而对于计算机专业的学生来说，抽象和自动化这两个核心内容更具体地体现为如何构建各种层次的计算环境以及如何在这种环境下进行问题求解。此外，我们还需要提炼出计算机学科的基本概念和思维方法，在教学过程中有意识地强化学生对这些基本概念和思维方法的理解和掌握。实际上，对计算机学科的基本概念和思维方法的梳理已经得到了国内外教育者的重视；在ACM和IEEE-CS联合攻关组制订的计算教程CC1991(Computing Curricula 1991)中已经提取出了计算机学科的12个核心概念[10]，包括：概念化和形式化模型、大问题的复杂性、抽象层次、折中和结论、一致性和完备性、效率、演化、按空间排序、按时间排序、重用、安全性、以及绑定等。这些概念反映了计算机学科最核心的思想、方法和原则，我们应该在教学过程中不断强化学生对这些概念的理解和掌握。
　　作为计算机专业课程体系中的核心课程，离散数学具有内容多、概念多、理论性强、高度抽象等特点，被普遍认为是一门既难教又难学的课程。首先，该课程由数理逻辑、集合论、代数结构、图论等多个彼此独立的数学分支组成；这些内容自成体系，很容易让学生觉得各部分内容联系不大，进而使得学生对课程学习的目的不明确。其次，该课程每部分都包含大量以字母、符号、图形等形式呈现出来的抽象概念，使得学生在短时间内难以适应由大量抽象概念建立起来的理论体系，往往会茫然不知所措。最后，学生在学习该课程时认识不到这门课程的重要性，觉得这门课程与计算机科学联系不起来，看不到离散数学知识在计算机科学中的具体应用，从而缺乏相应的学习兴趣。
　　计算思维为我们提供了一种重新审视离散数学的视角。从计算思维的角度来看，虽然离散数学由多个相对独立的内容组成，但这些内容的教学目的其实是高度统一的，即：训练学生运用离散结构构建问题的抽象模型并在其基础上构造算法和解决问题的能力；而根据上文的分析，这种能力恰好就是计算思维能力的核心所在。因此，一方面，离散数学课程为我们培养学生的计算思维能力提供了一个很好的平台。另一方面，我们可以从计算思维这个层面来梳理和组织离散数学的教学内容，从计算思维这个高度来进行离散数学教学。
　　2面向计算思维的离散数学教学
　　计算思维可以贯穿于离散数学课程的整个教学过程。下面分别从课程引入和课程教学两个阶段探讨如何将离散数学教学与计算思维培养有机地结合起来。
　　2.1从计算思维出发的课程引入
　　在引入离散数学课程之前，首先要向学生指明：对计算思维能力的培养和训练是计算机专业教学的核心所在；大家在经过四年的大学学习之后，不仅要掌握计算机专业的相关知识，更为重要的是能够应用这些知识构建出各种层次的计算环境并在这些计算环境下进行问题求解。在此基础上可以进一步向学生阐述：电子计算机本身是一个离散结构，只能处理离散的或者离散化了的数量关系；因此，无论是计算机科学本身，还是与计算机密切相关的现代科学研究领域，都面临着如何运用离散结构建立模型或者如何将已用连续数量关系建立起来的模型离散化，从而可以由计算机加以处理和实现。
　　
　　接下来，可以比较自然地引入离散数学课程，告诉学生该课程的目的是训练大家运用离散结构构建问题的抽象模型并在其基础上构造算法和解决问题的能力，而这种能力是计算机专业的学生具备计算思维能力的重要体现。
　　最后，还可以按照引入离散数学课程的常见方式，介绍该课程在ACM和IEEE-CS制定的计算机科学教程以及我国高等学校计算机科学与技术教学指导委员会制定的计算机专业规范中所处的核心地位；用一棵树形象地展示该课程在计算学科主要课程中处于树干位置的情形；以及分别列举出数理逻辑、集合论、代数结构、图论等内容在计算学科的相关课程和领域中的应用等等。
　　总的来说，从计算思维出发引入离散数学课程可以较好地达到以下目的。首先，能够让学生明白该课程的重要性，能够从整体上了解该课程在整个专业课程体系中所处的位置。其次，能够让学生明确学习该课程的目的，即训练运用离散结构构建问题的抽象模型并在其基础上构造算法和解决问题的能力；围绕这个学习目的，离散数学中的数理逻辑、集合论、代数结构、图论等内容形成了一个有机的体系。最后，能够纠正学生普遍存在的认为计算机专业就是学习编程的误解，让学生认识到通过离散数学等各门专业课程训练出来的计算思维能力才是大家应该具备的核心竞争力。在实现上述目标的基础上，一方面还可以让学生认识到离散数学课程为训练他们的计算思维能力提供和一个非常好的机会，从而激发他们对该课程的学习兴趣；另一方面还可以让他们提前认识到抽象和自动化将是贯穿该课程的两个主题，从而为接下来将要接触的大量抽象概念和符号做好心理准备。
　　2.2结合计算思维的课程教学
　　计算思维与离散数学课程教学的结合主要体现在两个方面：首先可以将抽象和自动化两个核心思想贯穿于整个教学过程，其次可以根据讲授的具体知识点适时地引入计算思维中其他基本概念和思维方法。下面分别从数理逻辑部分和图论部分挑选两个教学实例进行说明。
　　实例１：从计算思维的角度组织数理逻辑教学
　　对于数理逻辑部分，按照经典的教学方式，我们首先可以介绍莱布尼茨的理想，即把推理过程像数学一样利用公式来描述，建立直观而又精确的思维演算，从而得出正确的结论；形象地说，当两个人遇有争论时，双方可以拿起笔来说“让我们来算一下”，就可以很好地解决问题。为了实现这个理想，基本思路是首先引入一套符号体系，规定一些符号变换规则，然后借助这些符号和规则将逻辑推理过程在形式上变得像代数演算一样。
　　从计算思维的角度来看，上述基本思路的核心恰好就是抽象和自动化，即将双方争论的内容抽象成符号，将逻辑思维过程抽象成符号演算，进而可以借助工具实现逻辑推理。当学生建立起这种认识之后，我们比较自然地引入数理逻辑的基本概念，并且通过表1将离散数学中数理逻辑部分的学习内容展现出来，让学生对该部分的学习内容形成一个清晰、全面的认识。在接下来学习数理逻辑部分的每个章节时，我们可以反复呈现这张表，一方面可以帮助学生知道接下来的学习内容处于哪个位置，另一方面可以加深学生对抽象和自动化这两个核心思想的理解和掌握。
　　在表1列出的各个知识点中，对归结推理方法的教学往往被许多教材和老师忽略。但从计算思维的角度看，归结推理方法非常直观地体现了自动化这个核心思想，是离散数学中的一个重要知识点。学习了构造证明方法之后，学生一般会形成一个印象，觉得构造证明法使用起来简单方便，但使用过程中需要一定的观察能力或者需要一定的技巧。以学生的这种直观认识为基础，我们可以比较自然地引入归结推理方法，告诉学生这种方法容易用算法实现，易于在计算机上实现自动的推理证明。在接下来讲授了归结推理方法的基本原理之后，我们可以将这种方法以算法的形式呈现出来；在有条件的情况下，还可以让学生上机实现命题逻辑的归结推理算法等[11]。
　　在给出命题逻辑的归结推理算法之后，我们还可以对算法的可终止性、可靠性、完备性、复杂度等进行简单论述。与之相对应，在给出谓词逻辑的归结推理算法之后，可以告诉学生这个算法不一定会终止，即谓词逻辑本身是不可判定的。当学生理解了上述内容之后，我们可以进一步分析逻辑系统的表达能力与推理能力之间存在的矛盾关系，进而引入计算机科学中的“折中”这个核心概念，训练学生能够以解决问题为导向来选择合适的工具。
　　实例2：在欧拉图和哈密尔顿图教学中训练计算思维能力
　　对于图论部分，我们可以在一开始介绍图论的起源时就将计算思维的相关内容融入到课堂教学中。具体来说，在给出著名的哥尼斯堡七桥问题之后，可以向学生强调欧拉如何将桥的宽度、距离等无关的因素去掉，进而构建出一个抽象的以图的形式呈现的模型；接下来，可以让学生分析欧拉如何在图的基础上总结出三条判定规则，形成一套用来解决类似问题的可靠并且完备的理论；最后可以让学生体验如何应用欧拉建立的理论判断任何一个图中是否含有欧拉回路。上述三个阶段实际上体现了进行科学研究或者问题求解时采用的一般方法，同时也是计算思维的精髓所在。
　　在讲授完欧拉图的相关内容之后，可以类似地引入并讲授哈密尔顿图的相关内容，并且可以从问题的定义以及是否存在有效的判定方法等方面对这两个知识点进行比较和总结。在此基础上，我们可以通过一个单词排序问题来强化学生对计算思维能力的掌握。其中，对单词排序问题描述如下：假设有n个盘子，每个盘子上分别写着由小写字母组成的英文单词；需要给这些盘子安排一个合适的顺序，使得相邻两个盘子中前一个盘子上面单词的末字母与后一个盘子上面单词的首字母相同。针对这个问题，要求学生对其进行抽象后建立模型，并在此基础上给出该问题的解决方法，以及分析所给出的解决方法的复杂度。
　　对于上述单词排序问题，学生可能会给出两种抽象建模方法。第一种方法将每个单词作为图中的一个顶点；两个单词之间存在一条边当且仅当前一个单词的末字母与后一个单词的首字母相同。在此基础上，单词排序问题可以转换为寻找哈密尔顿路径的问题。第二种方法将26个小写字母作为图中的各个顶点；每个单词都对应于一条以其首字母为始点并且以其末字母为终点的边。在此基础上，单词排序问题可以转换为寻找欧拉路径的问题。对这两种方法进行分析后学生可以发现：第一种方法的复杂度为NP完全，而第二种方法的复杂度为多项式时间。总的来说，借助单词排序问题，不仅进一步训练了学生进行抽象建模和问题求解的能力，还将计算机科学中的复杂性、效率等核心概念融合进来，训练了学生对解决方案进行评估的能力。
　　限于篇幅，这里仅仅列举数理逻辑部分和图论部分的两个例子。其他典型例子还有：结合学生在小学和中学阶段学习的数学知识，对有理数四则混合运算、实数运算和复数运算等进行抽象后得到代数结构；利用等价关系对集合进行划分；利用偏序关系划分抽象层次等等。实际上，离散数学中基本上每个知识点都蕴含了抽象和自动化这两个核心思想以及计算思维中其他典型的基本概念和思维方法。将这些基本思想、概念和方法抽取出来并教授给学生，是我们授课教师的职责所在，但同时也对授课教师提出了挑战。要实现这个目标，要求授课教师不仅仅是照本宣科，不仅仅是以教会学生课本上的知识为目的，而是要能够从计算思维的高度来看待离散数学教学，要具备开阔的视野和广博的知识，要能够不断学习并且不断提升自己的知识和认知水平。
　　3结语
　　作为计算机专业的核心基础课程，离散数学中的许多知识点都为计算思维提供了很好的诠释和生动的案例。将离散数学教学与计算思维培养结合起来之后，一方面可以从计算思维的角度重新审视和组织离散数学的课堂教学，取得更好的教学效果；另一方面可以加强对计算思维能力的培养，使学生能够更好地应用计算思维来解决问题。
　　
　　计算思维的培养不是通过一两门课程的教学就能解决的问题，而是应该贯穿于所有专业课程的教学中。这就需要计算机专业的老师能够从计算思维的层面看待所教授的课程，能够对这些课程中含有的计算思维的基本概念、方法和思想进行提炼，以及能够从计算思维的角度对这些课程进行重新梳理和建设等。总的来说，计算思维对计算机专业的人才培养提出了新的要求，我们必须在专业课程的教学中加强对计算思维能力的培养。
　　参考文献：
　　[1] Jeannette M. Wing. Computational Thinking [J]. Communications of the