离散数学教学中采取的三点技巧.pdf

第3卷 第 9期 2 0 1 1 年 9月 当 代 教 育 理 论 与 实 践 Th e o a n d Pr a c t i c e o f Co n t e mp o r a r y E d u c a t io n VO 1 3 No 9 Se p 2 0 1 1 离散数 学教 学 中采取 的三点 技巧 匡能晖 胡 国辉 湖南科技大学 a 数学与计算科学学院 b 图书馆 湖南 湘潭 4 1 1 2 0 1 摘 要 离散数学课程是计算机专业核心基础课 离散数学课程学习的好坏直接影响其后续课程的学习 如数据结构 编译理论 算法分析和 自动机理论等 因此提高离散数学课程的教学质量 具有重要的实际意义 根据多年的离散数学教 学实践 谈谈在离散数学教学中采取的三点技巧 关键词 离散数学 教学 技巧 中图分类号 G 6 4 2 0 文献标识码 A 文章编号 1 6 7 4 5 8 8 4 2 0 1 1 0 9 0 0 7 1 一 O 3 离散数学课程主要介绍离散数学的各个分支的基本 概念 基本理论和基本方法 该课程所提供的训练十分有 益于学生概括抽象能力 逻辑思维能力 归纳演绎能力 的 提高 十分有益于学生严谨 完整和规范的科学态度的培 养 离散数学作为计算机专业的核心课程 它为后续课程 提供了必要的数学基础 这些后续课程主要有 数据结构 编译理论 算法分析和自动机理论等 离散数学在计算机 科学与技术中的地位如同微积分在物理学和工程技术 中 的地位一样 为计算机科学与技术 的发展奠定了重要的数 学基础 它对学生后续课 程的学 习和毕业 以后 的科学研 究 和实践都有重要意义 因此提高离散数学课程 的教学质 量 具有重要的实际意义 目前已有许多学者研究如何更 有效地进行离散数学教学改革 下面根据多年的离散数学 教学实践 谈谈在离散数学教学中采取的三点技巧 一 技巧一 对症下药 从实际教学中 我们发现不同届的学生对于同样的知 识点往往犯有类似的错误 为了避免类似 的错误再度发 生 需要认真分析出现错误的原因 找到问题的症结所在 对症下药 从而降低本届学生犯类似错误的概率 例如 从过去实践教学中得知 学生在根据 H u f f m a n算法求叶带 权为的最优2叉树的构造过程中 容易出现同样的错误 比 如当所 得新 的分 支点上 的权 与其它树 叶 的权 相 同时 下 一 步构造时思路不清晰 最终所构造的最优 2叉树少了一些 树 叶 原因是 将所 得新 的分 支点上 的权 当做 某片树 叶 的权 来构造 就遗漏了一些树叶 基于此种情况 进行对症下 药 在本届学生中采取改进的教学方法 举例说明如下 例 1 求叶带权为 1 1 2 2 3 4 5 8的最优 2叉树 分析 根据 H u ff m a n算法 令点集 E 1 1 2 2 3 4 5 8 在点集 E中选 择权 最小 的两个 点作 为 儿子 产 生父 亲 父亲的权等于这两个儿子的权之和 在点集 E中删除 两个儿子 增加父亲 形成新的点集 重新操作 直到点集 只剩下一个点为止 此点作为树根画出相应的后代得到的 2叉树为最优 2叉树 具体步骤如下 1 1 2 2 3 4 5 8 在所 选取 权最 小 的两个 数下 面加 下划 线 后 面 类似 2 2 2 3 4 5 8 上一步加下划线的两个数相加得到新的分支点的权 为2 并在上端用着重号标注 表明与树叶的权加 以区别 然后再选取权最小 的两个数在下面加下划线 后面过程 类似 4 2 3 4 5 6 4 5 4 5 8 8 5 5 8 8 1 0 8 1 6 1 O 2 6 注 1 在第 步中也可以选取第二个和第三个 2 得到 不同的最优 2叉树 所以最优 2叉树不是唯一的 注 2 上面的改进步骤具有的优点是 第一 用序列号 标明步骤 思路清晰 第二 在每次所选取权最小的两个数 下面加下划线 不会遗漏树叶 第三 在所得到新的分支点 的权的上端用着重号标注 将分支点的权与树叶的权严格 区分 这是以前学生所犯错误的根本原因所在 大大降 低了犯类似错误的概率 按上述步骤得到的最优2叉树为图 1 所示 收稿 日期 2 0 1 1 0 5 1 4 基金项 目 2 0 0 9年湖南科 技大学 教学研究 与改革重点资助项 目 G 3 0 9 3 7 作者简介 匡能 晖 1 9 7 3一 男 湖南邵东人 硕士 讲师 主要从事离散数学教学研究 71 万方数据 2 6 S 图 l b c d 图 2 二技巧二 高屋建瓴 众所周知 不同的教材对一些相同的内容采取不同的 处理方法 教师应该参考多本书籍 选取一种学生最容易 理解的方式进行讲解 教师不要局限于书本的内容 改进 对书本 内容 的处理方法 达到一种高屋建瓴的水平 比 如 刘爱民所著的 离散数学 我校选用的教材 介绍边带 权图中从固定点到其它任意点的最短路径 的 D i j k s t r a算 法 比较抽象 学生不易理解其基本思想 并且其所介绍的 以表格的形式简化整个求解过程 只能得到从固定点到其 它任意点的一条最短路径 下面举例说明 通过对现有的 处理方法的改进 可以得到从 固定点到其它任意点的所有 的最短路径 例 2 求图2中顶点 a到 e的最短路径 分析 虽然从图中直接观察容易得到顶点 a到 e的最 短路径 但是应该将求最短路径的 D i j k s t r a算法的基本思 想介绍给学生 便于进行编程 由计算机处理 D i j k s t r a算 法的基本思想是 若 t o M u H 是从 tt 到 的最短路 径 则 t t 0 一 是从 到 的最短路径 D i j k s t r a 算法依赖 于 系列 的迭代 通过在 每次迭代 中 添加一个顶点来构造出特殊顶点的集合 在每次迭代 中完 成一个标记过程 现给出算法细节 首先用 0标记初始点 a 用 标记其余顶点 用记号 L o a 0和 表示在没有发生任何迭代之前的这些标记 下标 0表示 第 0次迭代 设 S 表示在标记过程第 k次迭代之后 的特殊顶点的集合 先令 S a 而 S 是通过将不属于 S 的带最小标记的顶点u添加到S 里得到 一旦将 t t 添 加到 中 就更新所有不属于S 的顶点的标记 设 是不 属于 5 的一个顶点 为了更新 口的标记 注意以下事实 从 a到 的只包含 S 中顶点 的最短路径 或者是从 a到 v 的只 7 2 包含 Js 中顶点 即不包括 在内的特殊顶点 的最短路 径 或者是在第 k一1阶段从 a到u的最短路径加上边 n 无向图 或 有向图 换言之 即L k mi n L 一 M 其中 表示在第 k 次迭代之后顶点 的更新标记 表示边 无 向图 或 有向图 上的权 上述标记过程可以表格形式进行 下面给出本例的表 格形式 注3 每次迭代后所确定的一个特殊顶点用方框 固定 表示 各次迭代后不属于 S 的顶点的标记 中斜线后 面的字母表示从初始点到 的最短路径中 的前一点 如 果斜线后面的字母不止一个 说明所要求的最短路径可能 有 多条 从上表利用反向搜索法 即从初始点a 到e 的最短路径 中e的前一点有 b 或 d b 的前一点有 a 或 c d的前一点有 b 或 c c的前一点有 a 容易得到下图 图 3 从而可得顶点 口到 e的所 有 的最短 路径共 5条 a b e a c h e a b d e a c b d e a c d e 另外 由此易得从顶点a到d的所有 的最短路径共3 条 a b d a c b d a c d 类似可得从顶点a 到c 的 所有的最短路径共 1条 a c 从顶点 a到 b的所有的最短路 径共 2条 a b a c b 注 4 这样介绍 D i j k s t r a 算法 浅显易懂 并且改进了 刘爱民所著的 离散数学 对这个知识点的处理方法 特别 万方数据 是通过此法可求得从 固定点到其它任意点的所有的最短 路径 三技巧三 言简意赅 熟知 给定 的某二 元关 系 它 不一 定具 有某 种 性 质 如自反性 对称性或传递性 而我们又希望它具有这些 性质 就需要在关系 R中增加一些有序对构成一个新的关 系 使其具有所需要的性质 但是又希望新的关系不要变 得过大 即增加的有序对应可能的少 通过这样的过程产 生新的集合 就是所谓 的关系的闭包运算 其中主要有三 种闭包 自反闭包 r 对称闭包 和传递闭包 t R 学生感到最难的是传递闭包的计算 不是少添加 了一些 边 就是添加了一些不必要的边 在教学 中 采用言简意赅 的语言归纳总结求关系的传递闭包的方法 利用关系图检查 顶点 是否可达顶点 v j 1 若顶点 可达顶点 看 是否可直达 若 不可直达 v i 则添加直达边 2 其余情况 均不要添加边 简言之 若可达且不可直达 则添加直达边 注 5 若存在从顶点 到顶点 的通路 则称 可达顶 点 若存在边 则称 可直达 显然 可直达 必可达 但是可达不一定可直达 注6 需要检查每一个顶点是否可达每一个顶点 在可 达的情况下 是否可直达 包括 自己是否可达 自己 自己是 否可 直达 自己 注7 运用言简意赅 的语言 学生对所学知识易于理 解 印象深刻 这样就可正确地求得关系的传递闭包 举例说明如下 例3 设A a b C d 其上的二元关系 的关系图 如图 4所示 求传递闭包 t R 图 4 分析 1 首先检查 a点 a可达 n 因a b c a 但不可直达 因无边 故需要添加直达边 同理 a 可 达 b 且 a可直达 b 故不要加边 a可达c 但 a 不可直达c 故需要添加直达边 a可达 d 但 a不可直达 d 故需要添加直达边 2 检查 b点 b 可达a 但b 不可直达a 故需要添加直达边 b 可达 b 但 b 不可直达 b 故需要 添加 直达边 b 可达 C 且 b可直 达 c 故不要加边 b 可达 d 但 b 不 可直达 d 故需要 添加 直达边 3 检查 c 点 C 可达 a 且 c 可直达 a 故不要加边 c 可达 b 但c 不可直达b 故需要添加直达边 c 可达C 但 C 不可直达 c 故需要添加直达边 c 可达 d 且 c 可直达 d 故不要加边 4 检查 d点 d均不可 达 a b c d 故不要加边 综上所述 可得 R 四 结论 离散数学教学教无定法 只要有利于学生接受的 容 易理解的教学方法都可以尝试 此文总结的三点技巧只起 到抛砖引玉的作用 与同行共享 为了提高离散数学教学 质量 需要我们不断地探索 寻求最佳教学方案 参考文献 1 屈婉玲 王元元 傅 彦 等 离散数学 课程教学实 施方案 J J 中国大学教学 2 0 1 1 1 3 9 4 1 2 李超 良 刘跃华 现代教 育教 学手段 改革 以 离散 数学 教学为例 J 当代教 育论坛 教 学版 2 0 1 0 1 2 4 1 4 2 3 刘光洁 谈谈 离散数学的教学 J 计算机教育 2 0 0 7 6 6 2 6 4 责任编校龙四清 73 万方数据 离散数学教学中采取的三点技巧离散数学教学中采取的三点技巧 作者 匡能晖 胡国辉 作者单位 匡能晖 湖南科技大学数学与计算科学学院 湖南湘潭 411201 胡国辉 湖南科技大学图书馆 湖 南湘潭 411201 刊名 当代教育理论与实践 英文刊名 年 卷 期 2011 03 9 被引用次数 2次 参考文献 3条