结合计算机应用的离散数学教学研究

2014-04-29张剑妹李艳玲吴海霞

数学学习与研究 2014年1期

关键词：离散数学计算机应用教学效率

张剑妹李艳玲吴海霞

【摘要】结合计算机专业的离散数学教学实践，对数理逻辑、集合论、代数系统和图论四个部分在计算机科学中的应用进行了深入探讨，并通过具体应用实例或练习阐述了如何将计算机应用与离散数学教学结合起来，以激发学生的学习兴趣，提高教学效率.

【关键词】离散数学；计算机应用；教学效率

【中图分类号】G642

【基金项目】山西省高等学校教学改革重点项目（项目编号：J2012102），长治学院教学研究项目（项目编号：2011205）.

离散数学是研究离散量的结构及相互关系的数学学科，是计算机等信息类专业的专业基础课.该课程的学习为数据结构、编译原理、操作系统、数据库原理和人工智能等后续课程的学习打下了坚实的数学基础，同时也有利于提高学生的抽象思维、逻辑思维和计算思维能力，为学生后续的学习和工作奠定了基础.鉴于离散数学在计算机科学中的重要性，中国计算机科学与技术学科教程2002和教育部高等学校计算机科学与技术教学指导委员会都将其列为计算机科学与技术学科教育的核心基础课程.

离散数学具有内容广、概念多、逻辑性与理论性强、高度抽象等特点，对计算机专业的学生来讲，他们更注重于计算机应用技能的获得，认识不到离散数学与其专业的相关性，把离散数学作为一门纯粹的数学课学习，导致一些学生失去学习热情，严重影响教学效果.另一方面，纯数学的教学方法也不能满足应用性人才培养的需求.为了解决这个问题，很多教师离散数学教学中增加相应实验内容，并且设计了切实可行的实验项目.但这些实验项目大多是对离散数学中的一些基本算法进行实现，其目的在于巩固学生所学的基本概念、原理和方法.笔者认为影响离散数学教学效率的一个最根本的原因是学生不明白离散数学与所学专业的关系，如何将离散数学与计算机应用相结合起来成为提高离散数学教学效率的重要环节.本文深入探讨了离散数学在计算机科学中的应用，并给出了必要的应用实例，旨在引导广大教师将更多的计算机应用相关的实例引入离散数学课堂教学中，使学生认识到离散数学的实用性，从而激发学生的学习兴趣，提高教学效率.

一、数理逻辑在计算机科学中的应用

数理逻辑是以数学的方法研究形式逻辑中的推理，一般包括命题逻辑和谓词逻辑两部分内容，它广泛地应用于人工智能、程序理论、数据库理论和计算机硬件电路设计等研究中.在课堂教学中，如果教师仅用这些概括性的结论强调数理逻辑在计算机科学中的应用，恐怕会适得其反，为了突出应用，吸引学生的注意力，教师可以把如下几个简单的应用实例引入课堂教学.

1.数理逻辑在硬件电路设计中的应用

数理逻辑中的逻辑演算是数字逻辑的基础，计算机系统中用高低电平来表示二进制数据中的1和0，计算机电路设计中用与、或、非门来实现数据的算术运算和逻辑运算.离散数学教学中我们引入一位全加器的设计作为数理逻辑在硬件电路设计中的应用实例.教师首先阐述逻辑电路设计的基本步骤（若还未开设数字逻辑课，教师可以详细讲解，否则，则是简单地复习已有知识），然后要求学生写出逻辑表达式.

假设Ai，Bi为两位操作数，Ci-1为低位的进位，Si为本位和，Ci为本位向高位的进位，根据加法的意义，学生很容易写出如下真值表：

当学生根据真值表写出逻辑表达式时，教师只要稍加引导，学生就会发现写出的逻辑表达式恰好是主析取范式，主析取范式与真值表的关系是书写逻辑表达式最直接的理论依据.既然学生已经发现了数理逻辑在硬件电路设计中的应用，是否继续画逻辑电路已无关紧要了.对有余力的同学，教师还可以给出一些具体要求，让学生设计一个表决器或者抢答器.

2.程序设计中的数理逻辑

数理逻辑可以用来验证程序的正确性，同时，学生在自觉不自觉中已经将数理逻辑应用到程序设计中.为了使问题更加清晰，教师可以将如下实例引入离散数学课堂教学中.例，在数组StArr中查找“Jon”，使用方法StArr.size（）和StArr[i].getName（）写出两个循环条件并证明这两个循环条件的等价性.学生很容易得出如下两个循环条件并使用德摩根律证明两个循环条件的等值性：

not （i>=StArr.size（） or StArr[i].getName（）=="Jon"

3.量词在SQL语句的应用

数理逻辑的谓词演算被引入到关系运算中，以此为基础形成的关系数据库查询语言叫关系演算语言，如ALPHA语言，QEB语言等，关系数据库的SQL查询语句中也允许用户使用全称量词和存在量词.教师可以有意识地让学生做SQL查询方面的训练.假如某学生管理数据库中有如下三个数据表：学生表S（S#，SNAME，SEX，AGE，DEP），课程名表C（C#，CNAME，TEACHER），学生选课表SC（S#，C#，GRADE）；要求学生用带量词的SQL语句完成如下查询并验证其查询结果是否正确.

①查询至少选修一门课的学生的姓名；

②查询选修全部课程的学生的姓名；

③查询没有学生选修的课程.

教师也可以给出相应的查询语句并让学生解释，使其体会到离散数学与计算机应用之间的关系.

二、集合论在计算机科学中的应用

集合论一般包括集合代数、二元关系和函数三部分内容.集合是具有共同性质的、可确定的、可分辨一组事物组成整体，二元关系是由二元组作为元素构成的集合，函数是特殊的二元关系.由此可见，二元关系和函数都是集合.集合是构造离散结构的基础，在数据库技术、数据结构、软件工程和程序设计中得到了广泛的应用.

1.集合在关系数据库查询中的应用

一个关系数据库表就是其行的集合，数据表中每个行就是由其数据项组成的一个n元组（表中有几列就是几元组），关系代数中选择运算和投影运算及为二元关系中的限制运算和像运算，笛卡尔积运算可以使用SQL语句中的多表连接查询来实现，SQL查询中还允许使用普通的并、交、差、补等运算.在教学中，我们针对学生管理数据库中的数据表设计了如下查询，要求学生用连接运算和集合运算完成，并鼓励学生在课外上机验证，以激发学生的学习兴趣.

例1 完成下列SQL查询.

① 检索数学系和计算机系的所有学生的姓名；

② 检索既选修C2和C3课程的学生的姓名；

③ 检索选修C2但不选修C3课程的学生的姓名；

④ 检索没有选修C2和C3课程的学生的姓名.

这个例子有助于学生很好的理解逻辑运算和集合运算之间的关系.如①的两种SQL查询语句分别如下：

I.SELECT S.SNAME FROM S WHERE DEP="数学系" and DEP="计算机系"

II.SELECT S.SNAME FROM S WHERE DEP="数学系"

UNIONSELECT S.SNAME FROM S WHERE DEP="计算机系"

例2 显示下列SQL语句的执行结果，分析该结果的正确性及其原因.

SELECT S.SNAME，C.CNAME FROM S，C

该例子的查询结果是表S和表C的笛卡尔积，无论学生与课程之间是否有选课关系，都会将学生名和课程名连接起来.

2.等价类在软件测试中的应用

软件测试是软件开发的最后一个阶段，其目的是通过运行程序，发现程序中潜在的错误.等价类划分是黑盒测试最常用的方法，其基本思想是把输入数据的可能取值划分为若干个等价类，使每个等价类中的数据可以发现程序中的一类错误，这样只需从每个等价类中选择一个数据作为测试用例就可测试出这类错误，而不需要穷举所有的数据.实际教学中，教师可以写出一个简单C语言程序要求学生使用等价类划分法设计测试用例，如用户登录系统、输入一个年月日计算这天为该年的第几天等程序.这样既有利于学生对等价关系、等价类、商集和划分等概念的理解，也有利于学生理解离散数学在计算机科学中的应用，从而激发学生的学习兴趣，变被动学习为主动学习.

三、代数系统在计算机科学中的应用

代数系统的研究方法和研究结果在构造可计算数学模型、研究计算复杂性、编码理论、程序设计语言的语义学等方面有着重要的意义.代数系统中的群论在计算机安全领域得到广泛关注，比如利用置换群实现秘钥交换.在讲解枯燥无味的群论时作者引入了如下应用实例.

计算机网络安全中常用的数据加密技术有对称加密和不对称加密.凯撒密码是一种古老的对称加密体制，其基本思想是通过把字母移动一定的位数来实现加密和解密.凯撒密码容易被破解，在实际应用中无法保证通信安全.为了使密码具有更高的安全性，出现了单字母替换密码.如，

明码表 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

密码表 Q W E R T Y U I O P A S D F G H J K L Z X C V B N M

即明文中的A替换成Q、B替换成W、C替换成E等，如果密码表是明码表的任意中重排，秘钥就会增加到26！种，破解非常困难.很显然，每个字母表就是一个置换，这样，在26个英文字母上的置换和置换的复合构成了置换群.

使用字母表替换密码，通信双方需要预先约定好共享的保密秘钥（即字母表）.若由于某种原因（如，原秘钥受到威胁）需要临时改变秘钥，秘钥交换就成为一个至关重要的问题.置换群可以实现用户的密钥交换，为了便于理解，假定通信双方之间传输的信息只有A，B，C三个字母，三个字母上有6个不同置换，这样用户A，B的公共信息为置换群G={σ1，σ2，σ3，σ4，σ5，σ6}.运算表如下：

（1）用户A从群G中构造一个序列SA={σ2，σ3，σ4，σ5}并向外界公布，用户B从群G中构造一个序列SB={σ1，σ4，σ5，σ6}也向外界公布；

（2）用户A在序列SA中选择一个私钥X，不妨设X-1=σ2σ3σ5=σ6，对SB中的元素进行共轭运算Xσ1X-1，Xσ4X-1，Xσ5X-1，Xσ6X-1，并把结果发给用户B，本例中运算结果为{σ1，σ2，σ5，σ6}；

（3）用户B在序列SB中选择一个私钥Y，不妨设Y=σ4σ5σ6=σ4，并对SA中的元素进行共轭运算Yσ2Y-1，Yσ3Y-1，Yσ4Y-1，Yσ5Y-1，并把结果发给用户A，本例中运算结果为{σ3，σ2，σ4，σ6}；

（4）用户A用自己的私钥X和用户B发给自己的信息可得：

X·YX-1Y-1=X·Y（σ2σ3σ5）Y-1=X·Yσ2Y-1·Yσ3Y-1·Yσ5Y-1=σ5σ3σ2σ6=σ6；

（5）用户B用自己的私钥Y和用户A发给自己的信息可得：

XYX-1·Y-1=X（σ4σ5σ6）X-1·Y-1=Xσ4X-1·Xσ5X-1·Xσ6X-1·Y-1=σ2σ5σ6σ4=σ6.

用户A和用户B即得公共会话密钥K=XYX-1Y-1=σ3=（1 3）（2 4）.

四、图论在计算机科学中的应用

图论是一个应用非常广泛的数学分支.在图论中用顶点表示事物，用顶点之间的边表示事物的联系，这样，图论就成为很自然的一种数据结构，这种数据结构为许多问题的解决提供了抽象和描述方法，广泛地应用在计算机科学中.从图的形式化定义看，图中的顶点组成一个集合，边是顶点集上的关系，这样，图论则是关系的图形化表示.在离散数学中，为了激发学生的学习兴趣，每个教师都会引入一些有趣的数学游戏和一些典型的应用，如关键路径问题和最短路径问题.除此之外，教师还可以引入一些计算机应用方面的实例，以突出图论在计算机科学中的重要性.

1.图在计算机网络设计中的应用

在计算机网络工程中，设计者总希望用尽可能少的网络布线连接网络站点，这样，就不可能通过站点之间的连线来确定它们是否连通.使用图可以有效地测试网络站点之间的连通性.网络结构可以用有向图表示，其中图中的节点表示网站，节点间的有向边表示网站之间的链接.教师可以给定一个网络结构图，要求学生使用有向图的邻接矩阵计算是否可以从一个网站导航到另一个网站.事实上，如果把网络节点之间的链接看成是一种关系的话，给定一组网络站点，根据网络站点之间的连接可以建立一个该节点集上的关系，这样利用关系的传递闭包也可以判断任意两个网络站点之间是否有网络连接.通过这个例子，不仅可以使学生理解图与计算机应用之间的关系，还可以使学生进一步理解关系与图之间的关系，加深学生对图的形式化定义的理解.

2.哈夫曼树在文本文件压缩中的应用

哈夫曼树是一种最优二元树，用哈夫曼树产生的二元前缀编码叫哈夫曼编码.在离散数学教材上，通常会以例题的形式给出哈夫曼编码在信息传输中的应用.事实上，这样的例子足以说明树在计算机科学中的应用，但是由于该例题的局限性，很多学生没有认识到树在计算机科学中的重要性.作者把这个例题稍做扩展后，将哈夫曼编码在文件压缩中的应用[10]引入到离散数学教学中.

压缩分为有损压缩和无损压缩.视频、音频等多媒体信息经常进行有损压缩，而本文只能采用无损压缩，基于哈夫曼编码的压缩是一种无损压缩.利用哈夫曼编码压缩文件的基本步骤如下：

（1）扫描原文件，统计各个字符出现的频率.每个西文字符占一个字节，而且最高位为0；对于中文字符，将一个字符分为两个字节，以字节为单位进行统计；

（2）利用统计结果构造哈夫曼树；

（3）利用构造好的哈夫曼树对各字符进行哈夫曼编码；

（4）再次扫描原始文件，利用生成的哈夫曼编码重新编码原始文件，即得到一个压缩文件.

五、结束语

通过将计算机应用与离散数学理论相结合的教学方法，使学生对离散数学与其专业的相关性有了充分的认识，激发了学生的学习兴趣，提高了学生的学习积极性，有效地提高了离散数学的教学效率.未来，我们将在离散数学教学中增加更多的实用性内容，以满足应用型人才培养的需求.

【参考文献】

[1]中国计算机科学与技术学科教程2002研究组.中国计算机科学与技术学科教程2002 [ M ].北京：清华大学出版社，2002.

[2]教育部高等学校计算机科学与技术教学指导委员会.高等学校计算机科学与技术专业核心课程教学实施方案[M].北京：高等教育出版社，2009.

[3] 徐凤生.离散数学及其应用[M].北京：机械工业出版社，2006.

[4] 蔺永政，王新红，李金屏.离散数学中实践教学的探讨[J].计算机教育，2006，10： 03-104.