计算机科学中的数学教育

摘要：本文提出了一种新的教学思路，即以“离散”作为计算机科学中数学教育的主线，强调针对离散数学的知识与技能培养。既采用系统化的离散数学课程教学，又将数学思想渗透到具体课程中。教学实践表明，这种以解决问题为导向的教学方案收效良好。

关键词：数学教育；计算机科学；离散数学；离散概率；组合数学

中图分类号：G642文献标识码：B

1引言

计算机科学(Computer Science，CS)这个概念若仅从字面上看，可将其理解为研究计算机理论的学科，但它的覆盖面绝不限于理论，这也是它与理论计算机科学(Theoretical Computer Science，TCS)的区别。ACM和IEEE联合制定的Computing Curricula的总结报告认为[1]，计算机科学不仅包括理论和算法，而且已经延展到智能系统、计算机视觉、生物信息学等领域研究的前沿。从某种意义上说，计算机科学为计算机学科提供思维的工具。

从历史发展上看，数学在计算机科学的诞生与发展过程中发挥了巨大的作用——不夸张的说，数学就是计算机科学的基石。事实上，早期的许多计算机科学系脱胎于数学系，而最早的计算机更是由Turing, John von Neumann等一大批数学家创建而成。时至今日，计算机科学的发展越发迅速，由此带动的计算机技术的发展更是给整个世界带来革命性的变化。在此背景下，学习哪些数学知识，以及如何学习它们才能促进对计算机科学的掌握，进而更好的利用它来解决实际问题，都是非常值得思考的问题。

2“离散”的数学

在计算机系统中，最基本的假设就是它以二进制来表示数据，即所有信息都要被转换成0和1的组合。由于早期电子器件功能上的局限性，只有采用二进制才能准确的表示信息，但计算机发展到现在，二进制已成为难以更改的标准。因此计算机自从诞生之日起，它就和连续型的数学划清了界限。当然，连续型的数学在计算机上只要被“翻译”成二进制，也就是连续量转变成离散量后，即可被计算机理解和操作。所以作为计算机科学基石的数学，更确切地讲，应该是离散数学。在ACM和IEEE联合制定的CC2005教学计划的CS部分(即CC2001)中[1]，离散数学的内容被称为Discrete Structures(简称DS)，它排在14个主要领域的首位，其重要性由此可见一斑。

CC2001所列DS的主要内容是：

DS1. Functions, Relations, and Sets；

DS2. Basic Logic；

DS3. Proof Techniques；

DS4. Basics of Counting；

DS5. Graphs and Trees；

DS6. Discrete Probability.

CC2001教学计划的目标就是服务于计算机科学，而这些精选的内容实际上也都是在计算机科学中应用广泛的数学知识。如数理逻辑(DS2)是计算机科学乃至整个计算机领域中最基础的知识；又如进行复杂的算法分析就必须掌握基本的计数原理(DS4)。

从我们的教学经验上来看，若要总体把握这些内容必须紧扣“离散”二字。突出“离散”并不是为了标新立异，而是它确与“连续”有所区别。处理离散问题有一些特殊之处，因而需要补充专门针对离散问题的知识与技能。

例如 的 记号问题，其结论在堆排序等许多算法的分析中都非常重要。此问题虽然不甚复杂，但其处理方式比较特殊，在教学中若不单独提出，学生难以自行证明。此外，如果再进一步讨论利用积分给出其上下界限，则可让学生获得处理这类问题一般性的方法。这种方法在微积分中不算很难的内容，但它在渐进分析中相当重要，学生对其若有一定量的训练，可为今后的学习带来相当大的便利。

又如考察树的计数时，需要具备组合数学中的生成函数等知识，这些在DS4(Basics of Counting)中都有体现。事实上，DS4不但提供了基本的组合知识，还给出了计数的一般性方法。在这些计数原则的指导下，既能快速得到结果，还能避免多算、少算等各种在计数中易犯的错误。基于对组合数学地位的正确认识，国外许多教材在内容的取舍上已经做出了表率。如Lovász等编写的Discrete Mathematics[2]就给组合数学分配了较大的篇幅，同时还就其在计算机科学中的应用给出许多实例。姚期智先生在清华开设“理论计算机科学”课程时，即将此书列为教材。

3按需定学，现学现用

虽然离散数学的范围看上去比传统数学要窄，但它包含的内容却相当丰富，甚至可以用“庞杂”来形容。而CC2001教学计划的安排充分体现了美国教育界“现学现用”的教学思想，精心挑选出在计算机科学中有着广泛应用的那些内容。于是，详细讲解这些知识并紧扣其在计算机科学中的应用，必将为学生在今后的学习中打下坚实的基础。

例如许多国外的离散数学教材中特别强调循环不变量(Loop Invariants)的使用[3, 4]，还以一些例子来证明某些程序的正确性。从我们的教学实践来看，学生在编写程序时总会给出一些解决方案，但他们认为自己“算法”的正确性是不言自明的。事实上，这些“新算法”大多是错的，这是由于他们对“证明”缺乏基本的理念。所以，要求学生进行断言式的程序正确性证明是相当困难的。如果从循环不变量这个概念入手，先利用它证明一些简单的程序段，尔后则可逐步加深学生对程序正确性的理解。在讲解快速排序算法的划分步骤时，我们特别突出了Hoare在设计此算法时所遵循的循环不变量，学生对此反响甚好。对于更复杂的算法，我们着重以归纳法来统一算法的设计思路[5]，并以此证明其正确性。这种由浅入深的教学方式改善了教学效果：不但加深了学生对程序正确性的理解，而且也提高了他们对算法的认识深度。

又如在程序设计时，若能使用所学到的数理逻辑知识，则可对程序进行精简。下面这段程序针对不同的条件执行相应的函数：

可利用数理逻辑的知识将其化简为效率更高的形式[6]：

我们在离散数学课程相关内容的教学中补充了这些不甚复杂的应用实例，不但引起了学生的兴趣，而且能让他们更加深入的理解所学内容。

4教学方案

针对教学实际情况，我们在离散数学课程中适当补充了离散概率和组合数学方面的知识，以期能为学生进一步学习计算机科学打下扎实、全面的基础，也收到了良好的效果。当然，我们在教学中对于我国离散数学中的“常规”部分如逻辑、代数和图论也给予了充分重视。

从目前的研究现状看，“随机”这个概念已经在计算机科学中占据了相当重要的地位。它在算法设计、密码学、计算理论、人工智能等领域中都有相当丰富的应用，CC2001特别列出了DS6即离散概率(Discrete probability)以突出其重要性。国内开设的概率论课程虽已包含了DS6的内容，但侧重于连续变量，并未系统讨论离散变量。此外，对离散概率的讲授若无一定的深度和广度，还会对研究生的后续课程如概率算法等的学习产生一定的障碍。所幸，概率论权威Feller的名著《概率论及其应用》[7]涵盖了这方面的基本内容。该书不仅包括了概率论的基本知识，更深入讨论了随机行走(Random walk)、马尔可夫链和博弈问题，这些内容都是概率算法和算法博弈论必备的基础知识。该书的最后一版虽于1970年出版，但时至今日依然是案头必备的参考书。MIT的David Karger教授的话[8]给出了最好的注解——This book is fairly old but adorns the shelves of most theoretical computer scientists.

不过在实际教学中，我们发现离散概率的内容相当难处理：一是此部分应用广泛，由于学时所限不可能讲授太多内容；二是思想过于深刻，学生难以理解；三是有些内容与概率论课程重复。事实上，国外的一些大学已经单独开设了“概率与计算”这门课程[9, 10]，而且此课程已有成熟的教材[11]。对于离散概率的内容，我们目前的处理方法是：系统复习、梳理离散变量的相关内容；讲解针对离散变量的基本处理技巧；选择了一些应用实例如Monte Carlo方法进行分析；更深入的内容则让学生自学或改为研究生阶段的课程。

需要特别指出的是，以组合数学作为线索，可以将DS4、DS5、DS6紧密结合起来，一方面组合与图论本身就具备密切的联系；另一方面以组合为基础的概率空间正是离散概率的要义所在。从实践的角度看，大多数算法都是组合优化算法或图论算法，还具有相当强的实际背景，学生看到自己能解决实际问题必然产生强烈的自豪感。这种激励提高了学生学习的积极性，而且也让他们获得了更多的思考乐趣。

此外，密码学已成为计算机科学中不可或缺的组成部分，而作为现代密码学的基础，数论知识的重要性更不言而喻。在教学中适当加入一些初等数论的知识也很必要，但内容的取舍需要视情况而定。由于离散数学的学时有限，内容过多是教学的主要难题。此难题不仅存在于数论部分内容的选择，在抽象代数部分体现的尤为明显。我们认为，对于大多数学生来说，学习计算机科学应主要学习如何解决问题(How to solve it)，换言之，计算机科学是关于算法的科学。关于这一点，著名计算机科学家Knuth早已有过明确定义——Computer science is the study of algorithms[12]。解决问题也即寻求问题的算法不仅实用，也相对易于理解。因此，CC2001中对于DS的内容选择是合适的，我们应以这些内容为主。而在后续的课程的教学中，教师可以列出一些面向计算机科学的数论和代数参考书，如文献[13]就是一部相当优秀的著作。这种讲授方式不仅节约了时间，而且有利于不同研究方向的学生进行自由选择。

5结论

离散数学是计算机科学的基石，掌握并运用它是进行计算机科学的学习和研究的必要条件。许多著名的计算机科学家如Knuth, Hoare, Karp等都出身于数学专业，这说明数学方面的各种积累确实对计算机科学的学习和研究能起到积极的促进作用。为此，我们认真消化CC2001中关于DS部分的课程大纲并结合教学实践，一方面通过系统的离散数学课程让学生掌握必备的基础知识，另一方面结合多样的应用实例将数学的思想渗透到专业课程的教学中。这种理论与实践结合的教学方法不仅可以加深对数学理论的理解，更重要的是它能极大的促进对计算机科学的学习。教学实践表明，我们的方案不仅节约了宝贵的教学时间，还取得了相当好的效果。

当然，重视“离散”并不意味着在了解、掌握和应用计算机的学习过程中可以置“连续”于不顾。恰恰相反，这些“连续”的数学如微积分、线性代数等课程，在培养学生的数学思维能力以及运用数学知识解决问题的意识方面，具有无可替代的基础作用。此外，在数学基础课程的教学过程中，若能经常借助计算机开展数学实验，更可收到“学用相长”的效果。

由于计算机科学仍在不断发展，与其相关的数学教育问题还会遇到新的问题，这些都有待于我们在将来的教学中不断探索、不断创新。

参考文献：

[1] Computing Curricula 2005 [EB/OL]. http://www.acm.org/education/curricula.html.

[2] L. Lovász, J. Pelikán, K. Vesztergombi. Discrete Mathematics [M]. Springer-Verlag, New York, 2003.

[3] Susanna S. Epp. Discrete Mathematics with Applications (3rd Edition)[M]. Brooks Cole,2003.

[4] Kenneth H. Rosen. 袁崇义译. 离散数学及其应用(第5版)[M]. 北京:机械工业出版社,2007.

[5] Udi Manber. Algorithms: A Creative Approach[M]. Addison Wesley,1989.

[6] 谢勰. 程序设计中的逻辑分解技术[J]. 西安邮电学院学报,2007,12(3):98-100.

[7] William Feller. 胡迪鹤译. 概率论及其应用[M]. 北京:人民邮电出版社,2006.

[8] David Karger. Randomized Algorithms Syllabus, MIT Course [EB/OL].

http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-856JRandomized-AlgorithmsFall2002/Syllabus/index.htm

[9] Probability and Computing, CMU Course 15-359 [EB/OL].http://www.cs.cmu.edu/~15359/

[10] Probabilistic Methods in Computer Science, Brown Course CS 155 [EB/OL].

http://www.cs.brown.edu/courses/cs155/

[11] Michael Mitzenmacher, Eli Upfal. 史道济 等译. 概率与计算[M]. 北京:机械工业出版社,2007.

[12] Donald E. Knuth. Computer Science and its Relation to Mathematics [J]. American Mathematical Monthly, 1974, 81(4): 323-343.

[13] Victor Shoup. A Computational Introduction to Number Theory and Algebra [M]. Cambridge University Press, 2005.

推荐访问:计算机科学 数学 教育