数学之美与离散数学教学 史哲文，曹晓东（大连理工大学 软件学院，辽宁 大连 116620）摘 要：离散数学是计算机专业的核心专业课之一，但学生往往无法构建其与后续课程的联系，无法感知其应用。文章结合具体教学实践，从3个方面提出改革方案：在应用案例部分将离散数学应用引入教学，实现其与后续课程的无缝衔接；在编程实现环节设计多个难度不同的编程案例供学生选择，以提高学生的实际动手能力及协作能力；在教材环节综合课本与智能课件，展现数学模型及算法。关键词：离散数学；案例教学；课程衔接；实验教学：1672-5913（2014）12-0064-040 引 言从蜂巢形状的正六边形分布，到符合斐波纳契数列的植物花瓣数目，数学渗透在自然界的各个方面，以简洁、直观的方式展示着数学之美。在计算机、网络及通信系统发展的今天，数学，尤其是离散数学，作为这些学科的理论基础，正以自己独特的魅力改变着人们的生活。在网络检索、大数据分析、图像视频处理、信息加密等各个与计算机相关的热门应用中，离散数学模型提供了必要的理论和解决方案的支撑。在我国目前的高等教育体系中，离散数学是计算机科学与技术相关专业的核心课程之一，但大部分学生仅仅认识到离散数学的理论公式部分，看不到其在实际中的应用价值以及与计算机其他学科之间的关系，容易造成学生学习兴趣不高、主动性差、学了就忘，无法构建整个计算机学科的知识架构体系，影响到后续课程的学习。因此，在离散数学的授课中应该做到理论和实践相结合，使学生看到离散模型在计算机领域解决实际问题的威力和魅力，对离散数学课程的认识跳出“纯理论”误区。笔者结合国内外高校已有的教学方法1-2和自身的教学经验，对课程教学进行了一定的改进。在教学过程中，我们一方面依据离散模型和相应的数学方法，引入计算机领域的实际问题，激发学生的学习热情；另一方面将相关理论与后续专业课程，如数据结构、操作系统、数据库等相联系，真正实现先修课程的学习价值以及其与后续课程的无缝衔接，帮助学生构建自己的知识架构。课堂之外丰富上机练习环节，各章编程不断线，在锻炼学生动手能力的同时，加深他们对知识点的理解。同时，笔者进行教材建设和构建智能课件，直观展示数学模型及算法。总之，通过离散数学的学习，要真正提高学生的抽象思维能力、形式化描述能力、逻辑推理能力、概括能力以及对计算机专业课的学习热情，深刻领略数学之美。1 案例教学及课程衔接离散数学在本科计算机专业的授课内容一般分为4个部分：数理逻辑、集合论、代数系统和图论。这4部分表面看互相独立，实际上却又紧密连接。数理逻辑描述了一个符号化体系，该体系可以描述集合论中的所有概念。集合论中又有3个小模块：集合、关系和函数。关系是集合中笛卡尔乘积的子集，函数是关系的子集，代数系统是定义函数的运算，图论是一类特殊的代数系统。虽然互相联系，但这来自wwW.lw5U.coM4部分的表现形式都是概念、定理多，抽象程度高。因此，案例的引入至关重要，而在案例的选择中，针对学生实际情况，尽量选择趣味性题目或与计算机领域相关的问题。下面介绍各个章节所选择使用的案例以及与后续课程的关联方案。1.1 数理逻辑数理逻辑是用数学方法研究思维规律的一门学科，它首先描述了一个符号化的形式体系，进而在该体系的基础上研究判定与推理。应用1：布尔运算与信息检索3分析：在信息爆炸的今天，像百度、Google等搜索引擎的应用也越来越普遍。各种搜索引擎的算法和效果虽然各有不同，但其基本原理都相似。最简单的索引结构是用一个非常长的二进制数表示一个关键字/词是否出现在每个网页里，有多少网页，就有多少位二进制数。1表示相应网页有这个关键字，0表示没有。假定“康托尔”对应的二进制数是00100010011，“集合论”对应的二进制数为01100010100。当要找到包含“康托尔”和“集合论”的网页时，只需要将两个二进制数的对应位进行布尔运算里的“与”运算即可，可以得到结果00100010000，说明第3个和第7个网页满足要求。应用2：基于布尔运算的信息加密分析：用布尔运算可以构造一个简单的加密解密系统，假定原文对应的二进制串为00100010011，再任意给定同样长度的密钥，设为01111011011。将两个串对应位进行异或运算，结果为01011001000。这个信息可以作为密文传输，到了接收方以后，再与密钥进行异或运算，就能够还原出原串00100010011。应用3：数字电路分析：在数字电路中，有与门、或门、非门3个门电路分别对应布尔运算中的与（）、或（）、非（？）运算，而这3种运算又是功能完备的。因此，在解决实际问题时来自wWW，首先用命题逻辑将其表达出来，利用等价变换使之仅含有逻辑联结词？、，然后选用逻辑部件组成逻辑电路。应用4：逻辑难题分析：逻辑难题可以提高学生的学习兴趣。例如，一个岛上居住着两类人骑士和流氓。骑士说的都是实话，而流氓只会说谎。你碰到两个人A和B，如果A说“B是骑士”，B说“我们两个不是一类人”，请判断A、B是流氓还是骑士。对于这类问题，一般需要先进行符号化，然后再利用符号化之后的式子进行推导。应用5：8条推理规则构建推理系统分析：现实生活中的许多推理问题都可以利用8条规则进行推理解决，其中也有非常形象的知识点，例如：“A或B盗窃了货物；若A作案，则作案时间不在营业时间；若B提供的证据正确，则货柜没有上锁；若B提供的证据不正确，则作案时间应在营业时间且货柜上锁。推理谁是作案者”。1.2 集合论在集合论的3个部分中，“关系”与后续课程数据库的联系最为紧密。另外，无穷集合领域基数也是一类较难理解的知识点。应用1：基于表模型的数据库为何称为关系数据库？表为什么可以称为关系？分析：关系的定义为“笛卡尔乘积的子集”，对于一个具有n列的表而言，构造n个集合A1，A2，An，其中Ai（i=1，2，3，n）为该表在第i个属性上取值的集合，见表1，该表的每一行都是笛卡尔乘积A1A2An的元素，该表是这n个集合笛卡尔乘积的子集，因此，表实际上对应着关系，表中的每一行都反映了对应元素间的联系。分析：为了解决数据冗余的问题，数据库中的信息并不是放在一张表中，在查询时经常涉及多张表。上述查询通过对于两个表进行等值连接，也就是班级名字相等，找到学生和对应的班主任。这与关系的合成运算定义吻合，对应的班级名字就是起到连接作用的个体。应用3：希尔伯特旅馆问题。设一家有无限个房间的旅馆，所有的房间都客满了。这时又来了一位新客人，想订个房间。那么该如何为该客人安排房间呢？分析：把1号房间的旅客移到2号房间，2号房间的旅客移到3号房间，如此调换，新的客人就被安排进了被腾空的1号房间。这个问题表明，在无穷集合领域，局部和全体是可以一一对应的。1.3 关系代数关系代数是离散数学中最抽象的部分，因为它研究的是抽象代数系统，相当于对实际模型的二次抽象。在这一部分的讲解过程中，需要对部分知识点进行实例化。例如，命题和逻辑连接词与、或、非、异或、单条件、双条件可构成代数系统，集合和集合中的交、并、差、补、对称差分运算也可以构成代数系统。同理，关系、函数都对应代数系统。代数系统实例化除了深化对基础概念的理解，同样也有利于加深学生对同态、同构的掌握程度。如用集合代替命题，用集合的补、交、并、对称差分运算取代数理逻辑中的非、与、或、异或运算，运算性质可完全平移。1.4 图 论在离散数学中，图论以节点和边构成的图模型为研究对象，这部分内容应用丰富，但难度也比较大，是后续课程，如数据结构、操作系统、数据库等的基础，以下着重列举图论的3个应用。应用1：一笔画问题分析：欧拉对于哥尼斯堡七桥问题的解决标志着图论的起源，而该问题又与一笔画问题相一致：在一个连通图上，如果所有节点都是偶数度节点或只有两个节点是奇数度节点，则可以无重复地一笔画完。基于问题的启发式教学可用在该案例的教学中。应用2：测试图中有无回路分析：操作系统中判断进程占有系统资源是否出现死锁的检测算法以及数据库管理系统中判断事务之间是否循环等待的死锁检测算法，其基础都是图论中测试图中是否有回路的算法。对这些应用的引入有利于课程之间的无缝衔接。应用3：腾讯应用“圈子”的思考分析：2012年3月，腾讯推出了一款应用“圈子”，可以在QQ用户中自动寻找某个用户的好友并进行分组、标注姓名。该应用实际上是基于QQ的好友关系建立起一个图模型，并对该模型进行信息挖掘得到需要的结果。该例子能让学生在应用中看到图论的价值。2 上机实验设置为了进一步提高学生的兴趣以及动手能力，我们在授课过程中根据课程知识点的设置，为学生设计了多个可供选择的课外编程练习。实验1：布尔检索练习。通过Google（）进行检索，利用布尔运算组合出多个检索条件。实验2：主析取和主合取范式自动生成器。编程实现，输入任何一个合法的合式公式，输出该公式对应的主析取和主合取范式。实验3：编程实现任意集合的交运算以及并运算。实验4：关系性质自动判别器。编程实现，输入任何一个关系矩阵，输出该关系满足的性质，包括自反性、反自反性、对称性、反对称性和可传递性。实验5：编程求解关系的自反闭包、对称闭包和可传递闭包。实验6：对于开源工具GraphThing的代码研究及扩充功能。GraphThing是一个开源图形工具，可以用来对图模型进行创建、操纵并执行某些算法，如最短路径算法、图的遍历、最小生成树、最大流等。上述题目的难度等级从简到难依次是实验1、3、4、5、2、6。对于较难的题目，特别是实验6，学生可选择组队合作解决。3 教材选择国内外出版的离散数学书籍各有侧重点。以国外教材为例，Kenneth H. Rosen所著的Discrete Mathematics and Its Applications4偏重于应用，采用700多个不同的例子来导入应用，但对数学概念、模型和定理阐述得较少。国内教材结构明确，但主要强调数学概念和模型，抽象程度高，实例少。有鉴于此，笔者编写了离散数学及算法（第二版）5教材，配套有算法实现部分以及多媒体课件，更容易帮助学生将抽象思维转换为具体实现。在讲解的过程中插入实际应用实例并与后续课程衔接。另外，智能多媒体课件的开发应用将案例拆以交互式动画的方式演示，更加形象、直观地展现数学之美。4 结 语应用数学之美不在于虚华的外表和神秘的符号，而体现在数学模型的多样性、解决问题的实用性和覆盖领域的广泛性上，离散数学便具有如此特性。离散数学不是一门纯理论课程，而是一门结合了理论性、实用性和趣味性于一体的专业课程，在整个计算机专业课程体系中起到了重要的支撑作用。如何利用多种教学手段，结合应用实例，将离散数学所彰显出来的这种数学之美展现给学生，激发学生的学习兴趣和热情，培养学生实际生活中利用离散模型解决问题的能力，是离散数学的教学重点和难点。笔者从应用点选择、编程实验环节、教材建设3个方面加以改进，将理论知识、应用案例、实践环节以形象的方式揉合在授课过程中，在对学生的授课过程中取得了明显的效果。第一作者简介：史哲文，女，讲师，研究方向为智能计算和复杂网络， zhewen.shi。参考文献：1 屈婉玲， 王元元， 傅彦， 等.“离散数学”课程教学实施方案J. 中国大学教学， 2011（1）： 41-43.2 师雪霖， 尤枫， 颜可庆.离散数学教学练习计算机实践的探索J. 计算机教育， 2008（20）： 113-115.3 吴军. 数学之美M. 北京： 人民邮电出版社， 2012： 81-87.4 Rosen K H.