离散数学实践教学研究与实践

摘 要：本文从算法描述、实验课程体系建设、实际应用领域介绍以及实践教学模式等方面讨论了离散数学的实践教学。

关键词：离散数学；实验教学；实践能力

离散数学课程所涉及的概念、理论和方法，大量地应用在计算机科学体系中，数理逻辑是计算机中的逻辑学、逻辑电路、人工智能的基础课程，集合与关系是数据结构、数据库系统的理论基础，而代数系统则是现实世界的缩影，直接模拟了现实系统，图论知识更是直接应用在计算机网络、数据结构、编译原理等专业课程中。但传统教学中过于注重理论教学而忽略实践，学生普遍认为枯燥难懂，认为是纯粹的数学课程，对计算机编程用处不大。因此教师在授课过程中要注重理论联系实践，培养学生的专业素养，我们将从以下方面循序渐进加强教学理论与实践。

1 课程教学注重教学方法与教学实践的改革与创新

加强理论联系实际，从提高计算机编程思想的角度对学生展开教学，教师在讲解理论的同时，要注重其实际应用与算法描述。例如在讲解最短路径时，就要介绍Dijkstra算法，单源最短路径的基本思想如下：设S为最短距离已确定的顶点集(看作红点集)，V-S是最短距离尚未确定的顶点集(看作蓝点集)。

① 初始化：只有源点s的最短距离是已知的(SD(s)=0)，故红点集S={s}，蓝点集为空。

② 重复以下工作，按路径长度递增次序产生各顶点最短路径：在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集，以保证算法按路径长度递增的次序产生各顶点的最短路径。当蓝点集中仅剩下最短距离为∞ 的蓝点，或者所有蓝点已扩充到红点集时，s到所有顶点的最短路径就求出来了。

我们通过实例给学生模拟算法执行过程，验证算法的正确性，但细心的学生会发现前面加进去的点并不一定是后期考察路径的必经点，例如有三个点A，B，C，AB、BC、AC间权值分别为1，2，4，如果设A为源点，则第一次加进来的点是B，到C的最短路径应该是A-B-C，如果BC权值为4，则到C的最短路径应该是A-C，这里就要注意红点集加入的点不是其他点必经点，这是因为集合元素是无序的，不是联结已有的点作为最后点的路径的。

我们给出求解的动画演示过程，加深学生的认识，实际多应用在交通网络中路径的查询中，两地之间是否有路径以及如果有多条路径时找最短路径等，最后再对算法进行扩展解决单目标最短路径问题、单顶点对间最短路径问题等，扩展学生对算法的理解等。

在讲解逻辑推理时，建议学生使用Prolog语言可以轻松实现命题和联结词表示以及逻辑推理，代数系统则是无处不再，自动售货机、电梯系统、自动取款机等都是一个代数系统，有自己的运算关系，鼓励学生定义一些运算，完成一个具有输入输出的可交互的系统。

2 建设完善实验课程体系，加强学生实验实践能力

挖掘课程内容，建设完善的实验课程体系，实验课程的主要目的是，培养学生的数学建模能力、算法设计能力、编写程序能力和应用创新能力，使学生养成良好的数学素质。学生可以有选择地做。

(1) 基础实验如表1所示，基础实验设计一些离散数学基本问题，要求学生利用所学基础知识，完成相应的算法设计和程序实现。如在集合论部分，设计有限集基本运算算法设计实验，要求学生利用熟悉的程序设计语言完成有限集合的数据结构、集合间的交、并、差、迪卡尔积、子集判断等基本运算。学生可以在每部分中自由选部分题，完成一定的基础实验。这样的设计使得学生学会基本操作，巩固程序设计基本调试方法的掌握。

(2) 综合性实验如表2所示，设计一些比较复杂的离散数学问题，要求学生综合运用各章知识或多学科知识，完成问题的分解与求解、综合和整体实现。例数理逻辑部分的命题真值表计算实验中，要求学生设计实现命题数据结构、五种基本逻辑运算的代数运算转换、表达式求值等；学生需要综合运用命题逻辑、数据结构等知识，完成实验各个环节，实现运算结果的显示。可由几个同学组成一个学习小组完成实验。

(3) 设计性实验如表3所示。这一层次要求较高，对那些学有余力、兴趣浓厚的学生，给出一些难度较高的课题，要求他们自行设计问题描述模型和实验方案，开发实现小型应用软件。例如，要求学生针对某景区内景点的分布情况，设计可满足旅游者不同需求(如费用最省、线路最短、重复较少、景点最全等各种要求)的实用小软件。教师检查实验现象和实验结果。学生对实际程序的运行结果应能进行分析并提出改进方法，每完成一个实验，都要求写一份实验报告，挑选出好的作品，做成精品演示系统。

3 发现实际应用点，扩大学生知识面

让学生了解离散数学在现实生活中的主要应用，有意识地引导学生运用所学理论去分析问题、解决问题，从而让学生充分感受到离散数学这门课程的魅力和实用价值。部分实际应用如表3所示。鼓励学生按照如下流程操作：发现问题，然后构思一个可能求解该问题的算法过程，再设计算法并将其表达为一道可执行程序，最后精确地评价这个程序，考查其作为一种工具去求解其它问题的潜能，锻炼学生数学建模能力，提高分析问题，解决问题的能力。

4 建设开放式教学环境，丰富网络教学资源

充分利用网络学堂、课程学习网站等丰富的教学资源，构建了开放式的教学环境，我们开发了离散数学教学网站，模块包括：实验发布、实验申请、已审核实验、成果展示、精品展示、在线解答(前台如图1所示，后台如图2所示)、资料下载等模块，实验项目可选或自拟，增强了师生间互动，也为学生个性化学习提供了良好的条件。

学生可以在任何时间远程登陆，发表咨询，下载资料，参与实验项目，申请实验项目，获得批准后，我们开放实验室免费提供设备，实验项目结题后提交成果，我们从中提炼出精品，做成精品演示系统，学生还可以对已有成果做深入研究。

总之，鼓励学生吃透书本，挖掘理论的应用领域，鼓励学生改进算法、挖掘应用点，从抽象的理论到实际应用，再扩大应用，抽象到一般情况，让学生感觉到学习离散数学的重要性，理论与实践相结合，互相促进，切实提高大家学习离散数学的兴趣，能够达到学生积极主动为了实现应用而吃透理论，发挥主观能动性。采用项目训练为主的教学理念，切实提高学生的实际动手能力、创新能力和自学能力。

参考文献：

[1] 耿素云，屈婉玲. 离散数学[M]. 北京:高等教育出版社.

Abstract：The paper will discuss algorithm description of important theory suitable for practical contents in textbook， construction of the course experimental system， the domain of practical application and the practice teaching mode， which is devoted to strengthen practical teaching， raise learning interest， foster students' practice and Innovation ability.

Key words：Discrete Mathematics; Experimental Teaching; innovation ability.