“离散数学”课程教学中如何用好案例

　　摘要：本文用“成语接龙”游戏的例子, 阐述了在“离散数学”课程教学中如何用好案例, 分析了该案例的使用思路、方法及其在培养学生的思维能力与拓展学习中的作用。

　　关键词：离散数学; 教学案例; 计算思维;

　　0 引言

　　作为计算机类专业的基础核心课程, “离散数学”的重要性不言而喻。但是“离散数学”课程内容所固有的高度抽象性, 往往成为普通大学本科生畏惧和排斥学习的主要原因。

　　“离散数学”的研究对象是离散量、离散结构及其相互关系, 其主要的原理和方法又可以被计算机仿真模拟实现, 从而为有效地开展教学提供了良好的渠道。从这个意义上说, 知识传授已经不再是教学的主要目的, 思维方法以及由此带来的面对复杂问题时的思考方式才是课堂教学中需要传授的关键。

　　如何提高教学的趣味性, 吸引学生的持久关注和学习, 经常成为教师教学过程中的困惑。而良好的教学案例就成了提高教学关注度和参与度的有效手段。良好的课堂教学案例既是学科知识的有效载体, 也是实现教学目标的基础。但是, 正如北京大学王捍贫教授在一次关于“离散数学的困难性”的报告中所指出的那样, “教学案例的选取并不容易”, 不适当的案例往往带来更糟的结果。

　　笔者认为, 一个恰当的教学案例必须考虑以下4个重要因素: (1) 案例要有科学性, 并与课程教学内容直接关联, 学生主要使用本课程相关知识来描述和解决; (2) 案例要有趣味性, 或者从新的视角观察司空见惯的问题, 利于激发学生的学习兴趣; (3) 案例应贴近生活, 并且有明确的应用背景, 以减少学生的陌生感, 利于学习中的情感认同; (4) 案例中描述的问题要有挑战性, 但难度可控, 使学生能运用本课程的知识在很大程度上获得问题的解, 从而获得成就感。

　　本文拟从一个简单案例入手, 分析在“离散数学”课程教学中如何有效地使用案例, 使学生勇于面对困难问题, 提高思维能力。

　　“成语接龙”是一个喜闻乐见的游戏, 它要求使用成语连接, 上一个成语的最后一个字与下一句成语的第一个字相同。例如:

　　天长地久久别重逢逢凶化吉吉祥如意

　　意味深长长话短说说三道四四平八稳

　　很显然, 这个问题符合本文前面描述的几个特征。作为一个教学案例, 它是恰当的。

　　1 基本形式

　　读者自然会问, 任意给出一组成语 (如500个) , 是否能形成满足这样条件的一个成语接龙串呢?很显然, 这个问题可以描述为已知一个成语集合, 需要寻找文字先后连接的成语子集合。

　　为此, 可以考虑将每个成语看成一个节点, 如果满足某个成语的最后一个字是另一个成语第一个字的条件, 则在两个节点之间连上一条有向弧, 前者指向后者, 如图1所示。

　　因此, “成语接龙”问题就变成了有向图的连通性问题。例如, 从一个指定的节点A出发, 到另一个指定的节点B是否可以实现成语接龙?一些常见的算法可用于求解。

　　下面给出一个宽度优先的搜索算法。

　　Step 1:找出A的邻接节点集。

　　Step 2:标记邻接节点。

　　Step 3:判断B是否在邻接节点集中。若在, 则给出回溯路径, 算法结束;否则, 转到Step 4。

　　Step 4:找出Step 1的邻接节点集中各点的所有无标记邻接节点, 合并得到新的邻接节点集中, 转到Step 2。

　　Step 5:若不能得到新的邻接节点集, 则输出不存在A到B的成语接龙, 终止。

　　算法的实现与代码设计在“离散数学”课程的先修课程“程序设计与问题求解”等中已经解决, 本文不再赘述。

　　图1 成语连接关系

　　当然, “成语接龙”的问题可以有多种提法。假如要求找到从某个成语出发, 并经过接龙后最后一个成语仍然是自己, 从图上看就成了哈密顿 (或局部) 周游问题。一般而言这是没有快速算法可以求解的。

　　在教学中也可以作为挑战, 提出更多问题供学生做深层次探讨。例如, 如何找到至少包含k个成语的路径?如果同音字开头的成语也视为接龙有效, 应该如何处理?

　　2 提升形式

　　稍将问题简化。假如给定的不是汉语的成语, 而是一组英文单词。要求找到一种单词排列顺序, 使得前一个英语单词的最后一个字母是后一个单词的第一个字母 (注意不区分大小写) 。这样就把“成语接龙”游戏变成了“单词接龙”游戏。

　　表面上看, 问题并没有变得简单。但是考虑到英文单词只由26个字母 (仅考虑小写) 构成, 容易想到将26个字母作为节点, 若存在单词以某个节点M代表的字母开头, 以节点N代表的字母结尾, 则由M向N连一条有向弧 (代表该单词) , 如图2所示。

　　可以看到, 图2的节点数目比按照图1的方法已经大幅度减少了。但由此也带来了新的问题, 即图中出现了自环和平行边。

　　此时可以在有向弧集合中引入平行关系 (注意, 自环也可看成平行) 。可以验证该平行关系是等价关系, 从而使用等价类的方法建立单词等价类。利用等价类代表元, 可以实现将图2简化为简单图。

　　等价类的引进减少了节点之间连接边的数目, 在很大程度上降低了算法的复杂度, 有利于计算的实现。但是由于需要为每一条弧保留等价类, 因此存储空间增加了。

　　在图2的情况下, 问题就变成了从某一条弧出发, 是否可以找到一条路径到达另一条弧。

　　注意, 由于描述方式的不同, 问题的求解可类比于有向图中边的遍历, 与图1相比, 相当于从哈密顿路的求解变成了欧拉路的求解。

　　图2 单词接龙

　　3 案例使用的讨论

　　从上述案例可以看到, 实际问题的求解一般有4个步骤。

　　(1) 重述问题。就是将原始问题描述为数学上容易表达的形式, 忽略那些对问题及求解没有本质影响的部分, 必要的时候适当加以简化。

　　(2) 抽象化。这一过程将实际问题的相关概念抽象为数学概念, 厘清数学关系与限制约束条件。

　　(3) 数学模型刻画。用数学语言表达问题, 建立问题的数学模型。

　　(4) 求解。使用数学方法、算法技巧得到问题的解答。

　　从教学实际看, 上述案例由于趣味性强, 贴近生活, 在教学中很容易引起学生共鸣, 课堂参与度非常高。

　　教学过程中, 作为一种拓展方式, 就求解而言还可以引导学生建立二元关系, 借鉴复合闭包计算的思路设计相应算法, 计算出成语接龙串数目以及指定长度的接龙串。

　　上述案例综合应用了“离散数学”课程中多个模块的知识, 既可以作为课堂教学案例进行建模和问题分析, 也可以作为小班学习的讨论案例, 或者作为小组课外实践的应用系统开发项目。

　　4 结语

　　总体上说, 前面描述的过程是数学思维与计算思维能力综合运用的典范。通过问题重述, 以合适方式来陈述, 运用逻辑思维和形象思维准确把握问题的本质;通过抽象与简化, 实现复杂问题的分解;通过数学建模, 使问题形式简单, 表达清晰, 易于处理。而问题的求解过程, 既是数学方法如变换、归类、转化等思维方式的综合应用, 也是计算工具、计算策略的合理调配。

　　本文分析了良好的教学案例应具备的几个基本特征;以“成语接龙”游戏为例, 探讨了教学案例在“离散数学”课程教学中的重要作用, 展示了数学思维和计算思维能力培养在“离散数学”课程中如何有效实现。

　　(1) 典型的数学思维方式是, 通过假设、简化等环节将问题从复杂变得简单;通过分类将问题从困难变得容易;通过变换等手段将未解问题转换为已经解决的问题;再通过综合和推广得到更大问题的求解。

　　(2) 典型的计算思维方式是, 通过抽象、建模和化简寻求问题的适当描述和形式化, 形成实际问题的计算表示, 易于处理;通过编码实现, 完成问题求解的试错、调整和精化, 形成方法的评估, 实现算法应用范围的提升。

　　(3) 在“离散数学”课程的实际教学中, 如果基于问题驱动的良好教学素材得以有效融合, 有助于这两种思维能力的培养。

　　也应该注意到, 教学案例的选取和使用需要在教学研究与实践中长期积累, 应充分注意来源于科研、来源于实践、来源于生活的问题, 并加以适当改造, 才能符合教学的预期。这也是完善教学资源的有效手段, 值得教学工作者终身努力。

　　参考文献
　　[1]Jeannette M.Wing.Computational Thinking[J].Communications of the ACM.2006, 49 (3) :33-35.
　　[2]常亮, 徐周波, 古天龙, 等.离散数学教学中的计算思维培养[J].计算机教育, 2011 (14) :90-94.
　　[3]董荣胜.计算机科学导论:思想与方法 (第2版) [M].北京:高等教育出版社, 2013.
　　[4]王海艳, 陈志, 孙力娟.新型教学模式提升大学生计算思维能力研究[J].江苏高教, 2017 (6) :66-68.