离散数学分层次实验教学设计应用(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算法

　　输出欧拉回路的算法任取v0∈V（G），令P0=v0;设Pi=v0e1v1e2…eivi已经行遍，按下面方法从中选取ei+1:⑴ ei+1与vi相关联；⑵ 除非无别的边可供行遍，否则ei+1不应该为Gi=G-{e1,e2,…，ei}中的桥（所谓桥是一条删除后使连通图不再连通的边）；⑶ 当⑵不能再进行时，算法停止。

　　4.3.3 最小对集法

　　添加边使非欧拉图变成欧拉图其算法如下：⑴ 求出图G所有顶点之间的最短路径和距离；⑵ 以G的所有奇次顶点为顶点集，做一完备图，边上的权为两端点在原图G中的最短距离，将此完备图的加权图记为G1;⑶ 求G1的最小权理想匹配M,得到奇次顶点的最佳匹配对；⑷ 在G中沿配对顶点之间的最短路径添加重复边得到欧拉图G';⑸ 利用Fleury算法输出欧拉图G'的路径。

　　4.3.4 功能实现

　　数据输入：边数5,点数6相关联的点 1 21 32 54 23 24 5运行结果：存在欧拉回路 1,3,2,4,5,2,14.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].