离散数学中的分层次实验教学研究

摘 要： 从离散数学的实验教学现状出发，分析了进行分层次实践教学的必要性，研究了分层次教学的原则、实验设计原则、实验设计思路，实验设计内容，实验具体实施和考核方案，最后进行了成果分析。实践教学证明，在离散数学课程中进行分层次教学有利于培养学生的动手能力和创新精神。

关键词： 实践教学； 教学原则； 分层次教学； 团队协作； 实验体系

中图分类号：G420 文献标志码：A 文章编号：1006-8228（2014）09-73-03

Study on layered experimental teaching in discrete mathematics

Chen Yegang

（School of Computer Engineering， Yangtze Normal University， Fuling， Chongqing 408000， China）

Abstract： Starting from present situation of the "discrete mathematics" experimental teaching， the necessity of layered teaching is analyzed. Research teaching principle， the principle of experimental design， experimental design， experimental design， experimental implementation and evaluation scheme are studied. The result analysis is conducted. The practice shows that teaching at different levels can improve students" practical ability and innovative spirit in the "discrete mathematics".

Key words： practical teaching； teaching principles； layered teaching； teaching team； experimental system

0 引言

离散数学作为现代数学的重要分支，主要研究离散量的结构及其相互关系[1]。离散数学作为计算机科学与技术专业的核心基础课程，对于学生知识、能力和综合素质的培养起到承前启后的作用。它不但为程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析等课程的学习提供必须的数学基础，而且有助于培养学生具有严谨的科学研究的作风，提高学生的理论素质和分析和解决问题的能力。

由于离散数学高度抽象、概念多，理论性很强，在大多数的本科教学中崇尚理论教学，基本不开设实验课，故造成学生学得枯燥，老师教得辛苦，学生解决实际问题能力不高。为了提高学生的动手能力，在教学中加强实践环节是很有必要的。

本文分析了离散数学课程的教学现状，对分层次教学的必要性进行了探讨，提出了实验设计的原则、思路和内容，对实验进行实施，并对实验教学成果进行了分析。

1 实践教学现状

以“服务社会，面向地方”培养应用型本科人才为目标，越来越多的高校在离散数学中增加了实验教学，并取得了不错的教学效果，但在教学与实践的过程也显现出一些问题。

⑴ 离散数学内容丰富，定义和定理较多，方法性较强，由于内容多且各成一体，让学生觉得各部分间联系不大，又由于繁多的定理和定义抽象难懂，增加了记忆的难度。

⑵ 实践教学方式、方法单调。由于受课时的影响，实践教学主要是通过实验课来实现，一学期实验课时一般在17学时左右，一般实验课都是验证性实验，很少有创新项目。

⑶ 有的高校实验安排没有层次感，内容单调和分散，不能满足不同学生的需求，有些高校开设了分层次实验教学，把实验分为验证型实验，应用型实验，综合型实验和创新型实验，但实验与工程的结合性不强。

⑷ 由于离散数学的学习群体一般是高等院校的学生，其实践教学未考虑本科和专科学生的接受能力和不同专业的侧重点。比如软件工程专业的离散数学课重点放在图论、集合与逻辑，而网络工程专业重点放在代数系统。

⑸ 实验课成绩在该学科期末中所占比例不大，一般占20%左右，因此学生对其重视程度不够。同时由于信息获取的渠道较多，因此，考试时学生存在上网抄袭别人劳动成果的情况。

2 开设分层次实验的必要性

分层教学是面向全体因材施教的一种教学模式，它强调“教师的教要适应学生的学”，“因材施教，分层提高，让尖子冒出来，使多数迈大步，叫后进生不落伍，达到班级整体优化”。其核心是重视学生的个体差异，使学生体验成功的喜悦，从而激发学生的学习兴趣[2-4]。

为了增强学生毕业后的竞争力与国际接轨，许多高校纷纷设立了不同类型的实验班、提高班（如“元培班”（北大），“钱学森班”（清华））并为其配备本校的教学名师，优质的教学科研资源（如购买国外数据库），目的是培养创新型人才。

我校从2010年9月开始招收计算机的服务外包实验班（安博教育集团与HP集团与我校联办），到现在为止已有三届学生，对入选学生的要求是英语和数学成绩必须达到120分（高考成绩），为其提供联合培养、到企业参与核心项目，为每个学生配备一个教师进行全程跟踪，通过前二届的学生就业情况看，相对于普通班比，其首次就业率达到90%以上（50%考研）。

实验班的学生基础好，学习积极性高，在老师的严格要求下，动手能力得到了大幅度提高。针对不同水平的学生情况，本人在离散数学的教学中，为了培养学生的创新能力、动手能力和实践能力，基于近15年的教学经验和科研积淀，精心设计了实验内容并建立了科学的考核机制。

离散数学的实验设计基于其课程体系，面向实际应用，针对计算机程序设计大赛，在实验过程让学生协作工作，让每个学生的特长得以体现，以培养学生的创新精神和团队的协作意识。

3 实验设计

3.1 分层教学的原则[5]

根据个体差异，在实验设计中按如下原则。

⑴ 水平相近原则：将学习状况相近，智力水平相同的学生为“同一层”。

⑵ 动态变化原则：分层是动态的，进步的学生“升级”，退步的学生“降级”。

⑶ 化整为零原则：教学内容进行适度合并或者分解，对学生“放”“扶”并重。

⑷ 适度控制原则：学生水平不一，因此教师要善于激励、引导、精讲、反思，做好分类指导。

⑸ 激励为主原则：对学生的评价以纵向性为主。及时表扬、激励进步大的学生并调高学生层次，鞭策后退学生，使所有学生随时都处于最佳的学习状态。

3.2 实验设计原则

实验体系的设计按如下原则。

⑴ 实验项目是课堂内容的扩展，计算机科学与技术专业中不同的方向其内容应有相应的区别，如我校的软件工程方向主要重点在集合、图论和组合数学；网络工程方向重点在代数系统和数论；物联网方向主要在逻辑和代数系统。因此，实验的设计与授课内容相符，可使得学生更好地解决实际问题。

⑵ 结合当前的研究和项目，拓宽学生的视野，将离散数学与程序设计相结合，同时注重算法的分析，设计高效且代价花费小的程序。将教学重点分解成模块序列，对每个模块进行一个程序设计项目，如数理逻辑中的合取范式和析取范式作为一个模块，将真值表、合式公式、范式结合为一个实验项目。

⑶ 将离散数学的教学与计算机程序设计大赛相结合，蓝桥杯和ACM竞赛中图论和搜索算法、网络流等都与离散数学教学密切相关。

⑷ 补充必要的一些知识，使学生更能品尝成功的喜悦。

3.3 思路设计

离散数学涵盖数理逻辑、集合论、代数系统和图论四大部分，这四大部分相互联系又各自独立，根据分层次试验教学的目的和原则，对软件工程方向的学生要求从四个部分来阐述试验设计的思路。

3.3.1 数理逻辑

基础实验是根据软件工程方向的特点，将真值与范式，合式公式、等价证明，永真式，永假式和可满足式等命题公式用C程序设计语言求解，使学生理解连接词，掌握真值表和等价证明。提高实验是利用知名的定理证明器PVS，如使用BDDs（二分决策图）简化命题（单词学习propositional simplification，命题简化，Propositional Logic命题逻辑），为了效率缓存自动改写。用户定义的步骤可以联合这些原语推理来产生高层的证明策略。在实验教学方面，要补充定理证明工具的使用和程序验证理论。

3.3.2 集合论

集合包括并、差、交、补、异或五种运算和计数，在二元关系中笛卡尔积，关系的性质、运算和闭包，以及等价、相容、序关系，它们在数据结构、数据库和算法分析与设计中具有广泛的运用，基础实验的部分主要掌握Warshall算法，以及自反、对称、传递闭包的编程。提高实验部分的要求是单向陷门函数的编写，以及编程实现在简单文本中的信息检索。在实验教学上要补充关系数据库的相关知识及开发，以及与集合相关的并查集、二项堆和斐波那契堆。

3.3.3 代数系统

代数系统包括半群，群，环，域，格以及布尔代数，基础实验部分用C程序判定群，半群，环，域，格等。提高实验部分，会要求学生熟练使用Maple代数运算软件，理解代数系统在网络安全方面的应用。在实验教学上要补充的是Maple代数运算软件的使用和DSA算法。

3.3.4 图论

图论是一个古老而又运用广泛的分支，包括传统的问题，如：最短路径，最优路径，关键路径，最小生成树，哈夫曼树，欧拉问题，哈密顿回路问题，二分图，图的着色问题等，也包括现代的网络流问题。基础实验部分用C编写最短路径，最优路径，关键路径，最小生成树，哈夫曼树，欧拉问题，哈密顿回路问题，二分图，最大匹配和着色。提高实验部分安排平面图的判断，树在网络布线和物流方面的运用和最佳网络流的实验。在实验教学上补充特定网络介数和核数。

3.4 内容设计

离散数学实验教学按分层次教学要求，将实验首先分为验证型实验，应用型实验，综合型实验和创新型实验，然后根据不同学生的不同层次，又将每种类型分为基础实验和提高实验两部分。下面就以图论为例进行说明。

3.4.1 验证性实验

基础实验有深度优先搜索算法，广度优先搜索算法，最小生成树，最小生成树算法；提高实验有关键路径，拓扑排序，最短路径，图的着色问题。

3.4.2 应用型实验

基础实验有双向广度搜索算法，欧拉回路，哈密尔顿回路，最优路径；提高实验有中国邮路问题，货郎担货问题，二部图的最大匹配。

3.4.3 综合型实验

基础实验有求图中任意两点的最短距离的Floyd算法以及Fleury和Hierholzer算法；提高实验有有向欧拉图，有约束容量的中国邮递员问题，TSP的近似算法。

3.4.4 创新型实验

基础实验有哈弗曼树，一般图的最大匹配，最大流最小截集的Ford，Fulkerson，Dinits算法；提高实验有向图的中国邮递员问题，TPS的分支限界法，可靠网络的设计。

4 实验实施和考核

由于离散数学的内容设计较为复杂，因此学生不同，分配的实验不同，其考核方法也不相同，下面仅以应用型实验中的基础实验欧拉回路加以说明。

4.1 设置情景

一位邮递员从自己所在的邮局去投递，然后回到邮局，要求他必须经过他所管辖的每条街一次，输出行程最短的路线图。

4.2 功能分析

把投递区的街道用边表示，街道的长度用权表示，街道的交叉口用点表示，则投递区构成一个连通无向图。为了实现上述功能，分三步进行。

Step 1 判定此图是否是欧拉图。

Step 2 如果是欧拉图，用Fleury算法输出即可。

Step 3 如果不是欧拉图，用最小对集法构建欧拉图，再用Step 2方法输出。

4.3 模块算法

4.3.1 欧拉图的判定算法

⑴ 给定一个图，用并查集判定是否是连通图，如是转⑵；

⑵ 分别求出每个节点的度数，若均为偶数，则转4.3.2算法，否则转4.3.3算法；

⑶ 输出此图不连通。

4.3.2 Fleury算法[6]输出欧拉回路的算法

任取v0∈V（G），令P0=v0；

设Pi=v0e1v1e2…ei vi已经行遍，按下面方法从中选取ei+1：

⑴ ei+1与vi相关联；

⑵ 除非无别的边可供行遍，否则ei+1不应该为Gi=G-{e1，e2，…，ei}中的桥（所谓桥是一条删除后使连通图不再连通的边）；

⑶ 当⑵不能再进行时，算法停止。

4.3.3 最小对集法[2，7，8]添加边使非欧拉图变成欧拉图

其算法如下：

⑴ 求出图G所有顶点之间的最短路径和距离；

⑵ 以G的所有奇次顶点为顶点集，做一完备图，边上的权为两端点在原图G中的最短距离，将此完备图的加权图记为G1；

⑶ 求G1的最小权理想匹配M，得到奇次顶点的最佳匹配对；

⑷ 在G中沿配对顶点之间的最短路径添加重复边得到欧拉图G’；

⑸ 利用Fleury算法输出欧拉图G’的路径。

4.3.4 功能实现

数据输入：

边数5，点数6

相关联的点 1 2

1 3

2 5

4 2

3 2

4 5

运行结果：

存在欧拉回路 1，3，2，4，5，2，1

4.3.5 考核方式

为了尊重学生的劳动成果，基础性实验由老师评分，评分细则：难度不同的基础实验，视完成的情况给分，若完成指定的功能，按对应的标准给分，难度越大，分数愈高；若在完成指定功能的基础上，还添加扩展功能，有创意，并且成功实现，给与一定的加分；未完成或有错误，酌情给分。

对于提高性实验考核由团队实现，每个难度不同的课程设计，视完成的情况给分，若完成指定的功能，按对应的标准给分，难度越大，分数愈高；若在完成指定功能的基础上，还添加扩展功能，有创意，并且成功实现，给与一定的加分；未完成或有错误，酌情给分。同学加入一个团队，其考核通过答辩的方式进行，所有学生作为评委，但须每个团队通过协商后给出一个分数，取平均分即可。

最后总的实验成绩分数是由基础实验占70%，提高实验占30%而得。

5 成果分析

对学生进行分层次实验教学，把抽象的理论和复杂的证明化解为解决实际生活的许多问题，使不同层次学生都有收获，同时让学生融入团队，培养其协作精神。这样的实验教学对学生参加计算机程序设计大赛也有很好的作用。在2010级，本人所辅导的学生参加ACM竞赛获得重庆市二等奖，2011级参加蓝桥杯获得重庆市两个一等奖，2012级的学生参加蓝桥杯获得了重庆市高校第一名和一个国家二等奖和两个国家三等奖，2013年辅导的学生参加蓝桥杯获得重庆市高校第一名。实践教学证明，在离散数学中进行分层次教学对于提高学生的动手能力和创新能力都有重要的作用。

6 结束语

在离散数学中引入实践教学内容，将复杂枯燥的算法和定义、定理的证明通过计算机编程来实现，使学生体验到成功的喜悦。根据不同学生的实际情况，将实验分为基础性实验和提高性实验，让不同层次的学生都有收获。对考核方式做了调整，期末理论占40%，实践占60%，让学生既要学习理论又要结合实际。经过实践证明，该方法是可行的，但是也存在一些局限，如基础性实验和提高性实验的划分标准不一等。实际教学中为了让学生适应性更强，还需要我们对学生因材施教，因地制宜。

参考文献：

[1] Kenneth H. Rosen，Discrete Mathematics and Its Applications[M].

NewYork：McGraw-Hill Companies，Inc，2011.

[2] 王志伟.离散数学教学中培养学生建模能力的探讨[J].广东技术师范

学院学报，2014.3：99-103

[3] 徐洁磐.应用型计算机本科中离散数学课程目标定位与课程改革的

探讨[J].计算机教育，2010.5：86-91

[4] 常亮，徐周波，古天龙，董荣胜.离散数学教学中的计算思维培养[J].计

算机教育，2011.14：102-107

[5] 徐文仲，任永泰，汤岩.提高离散数学课程课堂教学有效性方法的研

究与实践[J].东北农业大学学报（社会科学版），2010.4：55-60

[6] 温雪莲，苏庆，黄剑锋.浅谈在“离散数学”教学中培养学生的数学思

维与应用能力[J].广东工业大学学报（社会科学版），2009.S1：122-128

[7] 李国庆，张火林.《离散数学》课程教学优化策略研究[C].第二届亚太

地区信息论学术会议论文集（上册）[C]，2011：300-312

[8] 刘宝宏.非计算机专业离散数学课程教学改革的经验与体会[C].

Proceedings of 2010 Third International Conference on Education Technology and Training（Volume 7）[C]，2010：197-203