离散数学 课程教案 编号： 授课题目 5.4最短路径与关键路径 教学课型 理论课☑讨论课口实验课口 (1) 习题课口实践课口其它口 授课时间 月日 时 1 固定座位教室☑移动座位教室口 智慧型互动教室口 教学场所 实验（实训）室口校外实践基地口 户外口 其它口 教材简析： 本节内容为第五章第四节最短路径、关键路径与着色问题第一节课讲解，将图论知 识用于实际问题的解决，也是对所学知识综合掌握程度的一个检验，涉及到图的通路、 路径长度、边的赋权等知识，以及矩阵计算方法等，综合性较强，内容难度较大。但是 本节内容中最短路径算法是后续关键路径等问题解决的基础，有着十分重要意义，教学 过程中注重算法的介绍与应用，通过实例分析激发学生的探究欲望，实现教学大纲目标， 为下一步的学生打下坚实基础。 学情分析： 学生通过前段时间的学习，对图论相关理论知识已基本掌握，但对于图论的应用的 起源，应用的领域以及图论中涉及的算法还有许多未知，通过本节课内容学习，学生 方面可以对本课程学习的意义有更深的理解，同时对图论知识有一个概括和全面的认 知，对实际问题的解决有更多思路与方法。 当代大学生虽然心智比较成熟，但仍有部分大学生是比较自负和自私的，不懂得感 恩，人生观和价值观等有待更进一步的塑造，中国邮路问题是最短路径最具代表性的实 例，也是我们中国人在近代数学史上的骄傲，另外最短路径的求解和一带一路建设有- 个共同的本质，追求效益最大化，把握好契机，充分挖掘思政素材，开展合理的课程思 政，学生可以增强爱国主义情怀，体验一带一路精神，提升社会责任感和历史使命感。 考虑到少数计算机功底好的学生会尝试将算法在计算机软件中去实现，但在编码过 程中可能会遇到困难，为了帮助学生解决这些难题，可以将迪杰斯特拉算法的编码上传 到学习通平台，以供参考
离散数学 课程教案 编 号： 授 课 题 目 5.4 最短路径与关键路径 （1） 教学课型 理论课 讨论课□ 实验课□ 习题课□ 实践课□ 其 它□ 授课时间 月 日 学 时 1 教学场所 固定座位教室 移动座位教室□ 智慧型互动教室□ 实验(实训)室□ 校外实践基地□ 户外□ 其它□ 教材简析： 本节内容为第五章第四节-最短路径、关键路径与着色问题第一节课讲解，将图论知 识用于实际问题的解决，也是对所学知识综合掌握程度的一个检验，涉及到图的通路、 路径长度、边的赋权等知识，以及矩阵计算方法等，综合性较强，内容难度较大。但是 本节内容中最短路径算法是后续关键路径等问题解决的基础，有着十分重要意义，教学 过程中注重算法的介绍与应用，通过实例分析激发学生的探究欲望，实现教学大纲目标， 为下一步的学生打下坚实基础。 学情分析： 学生通过前段时间的学习，对图论相关理论知识已基本掌握，但对于图论的应用的 起源，应用的领域以及图论中涉及的算法还有许多未知，通过本节课内容学习，学生一 方面可以对本课程学习的意义有更深的理解，同时对图论知识有一个概括和全面的认 知，对实际问题的解决有更多思路与方法。 当代大学生虽然心智比较成熟，但仍有部分大学生是比较自负和自私的，不懂得感 恩，人生观和价值观等有待更进一步的塑造，中国邮路问题是最短路径最具代表性的实 例，也是我们中国人在近代数学史上的骄傲，另外最短路径的求解和一带一路建设有一 个共同的本质，追求效益最大化，把握好契机，充分挖掘思政素材，开展合理的课程思 政，学生可以增强爱国主义情怀，体验一带一路精神，提升社会责任感和历史使命感。 考虑到少数计算机功底好的学生会尝试将算法在计算机软件中去实现，但在编码过 程中可能会遇到困难，为了帮助学生解决这些难题，可以将迪杰斯特拉算法的编码上传 到学习通平台，以供参考
教学目标： 一、知识目标： 1、了解中国邮路问题，知道最短路径的起源与定义。 2、学习最短路径计算方法，利用迪杰斯特拉算法独立完成最短路径问题的求解。 3、理解最短路径算法迪杰斯特拉算法，能尝试利用计算机软件写出相应代码。 二、能力目标： 1、思考中国邮路问题的解决，提高探究能力。 2、利用迪杰斯特拉算法解决最短路径实际问题，增强知识应用能力和解决实际问题的 能力。 3、完成课堂练习，增强知识运用能力和合作学习能力。 三、情感与价值目标 1、学习最短路径的定义以及最短路径的实际应用领域，树立效益最大化意识，并学会 追求最高效益，有助于形成良好高效的职业素养。 2、学习迪杰斯特拉算法，运用该算法解决最短路径实际问题，加深对本课程学习意义 的理解。 3、了解中国邮路问题的命名来历，华为芯片事件，提高民族自豪感，增强爱国主义情 怀，塑造学生科技创新、科技自立、勇于探索的工匠精神。 4、拓展了解什么是中国一带一路，明确一带一路对中国乃至全世界的战略意义，体验 祖国的大国担当，提升民族危机意识与历史使命感，践行社会主义核心价值观。 教学重点、难点： 重点：理解迪杰斯特拉算法基本步骤，画出迭代过程表，找出最短路径。 难点：理解迪杰斯特拉算法迭代过程，尤其是如何确定永久标号。 课程思政： 1、课程思政素材 1)中国邮路问题百科知识；华为芯片事件资料： 2)视频资料：一带一路是什么？ 3)官方文字资料：一带一路的战略意义，一带一路体现的精神。 2、课程思政切入点： 1、新课引入环节：最短路径经典案例中国邮路问题的解决历程，华为芯片事件
教学目标： 一、知识目标： 1、 了解中国邮路问题，知道最短路径的起源与定义。 2、 学习最短路径计算方法，利用迪杰斯特拉算法独立完成最短路径问题的求解。 3、 理解最短路径算法迪杰斯特拉算法，能尝试利用计算机软件写出相应代码。 二、能力目标： 1、 思考中国邮路问题的解决，提高探究能力。 2、 利用迪杰斯特拉算法解决最短路径实际问题，增强知识应用能力和解决实际问题的 能力。 3、 完成课堂练习，增强知识运用能力和合作学习能力。 三、情感与价值目标 1、学习最短路径的定义以及最短路径的实际应用领域，树立效益最大化意识，并学会 追求最高效益，有助于形成良好高效的职业素养。 2、学习迪杰斯特拉算法，运用该算法解决最短路径实际问题，加深对本课程学习意义 的理解。 3、了解中国邮路问题的命名来历，华为芯片事件，提高民族自豪感，增强爱国主义情 怀，塑造学生科技创新、科技自立、勇于探索的工匠精神。 4、拓展了解什么是中国一带一路，明确一带一路对中国乃至全世界的战略意义，体验 祖国的大国担当，提升民族危机意识与历史使命感，践行社会主义核心价值观。 教学重点、难点： 重点：理解迪杰斯特拉算法基本步骤，画出迭代过程表，找出最短路径。 难点：理解迪杰斯特拉算法迭代过程，尤其是如何确定永久标号。 课程思政： 1、课程思政素材： 1）中国邮路问题百科知识；华为芯片事件资料； 2）视频资料：一带一路是什么？ 3）官方文字资料：一带一路的战略意义，一带一路体现的精神。 2、课程思政切入点： 1、新课引入环节：最短路径经典案例-中国邮路问题的解决历程，华为芯片事件
2、例题讲解环节：最短路径实际的应用。 3、课程思政目标 了解中国邮路问题的来由华为芯片事件，提高民族自豪感，增强爱国主义情怀，塑造学 生科技创新、科技自立、勇于探索的工匠精神 2)观看视频：一带一路是什么？感受中国的国际担当和“和平合作，开放包容，互学 互鉴，互利共赢”的丝路精神，践行社会主义核心价值观。 3)思考个人学习现状，树立努力完成好当下任务的决心与信心 4、课程思政实施思略： ②依托素材1)，采取探 究，启发，讨论等方法， 实现思政目标1) ③依托素材2)，采取讲授、 ①钻研教材 情感体验等方法，实现思政 洗定素材 思政素材 目标2) 确定目标 思政目标 方法选择 ④采取反思个人现状、行动 实践等方式，检验和巩固思 政效果，实现思政目标3) 教学方式和手段： 基于对教材内容的分析和学情的分析，在各教学环节中，紧靠教学内容，为实现教学目 标，充分发挥学生在学习中的主体地位，将采取以下教学方式和教学手段 教学方式：讲授、案例分析、启发、展示、探究，实践等方式相结合 教学手段：将现代化教学工具如手机，电脑，投影仪等，学习软件如学习通，微师等， 网络交流平台如QQ,微信等，传统教学工具如黑板，教材等紧密结合
2、例题讲解环节：最短路径实际的应用。 3、课程思政目标： 了解中国邮路问题的来由华为芯片事件，提高民族自豪感，增强爱国主义情怀，塑造学 生科技创新、科技自立、勇于探索的工匠精神。 2）观看视频：一带一路是什么？感受中国的国际担当和“和平合作，开放包容，互学 互鉴，互利共赢”的丝路精神，践行社会主义核心价值观。 3）思考个人学习现状，树立努力完成好当下任务的决心与信心。 4、课程思政实施思路： 教学方式和手段： 基于对教材内容的分析和学情的分析，在各教学环节中，紧靠教学内容，为实现教学目 标，充分发挥学生在学习中的主体地位，将采取以下教学方式和教学手段： 教学方式：讲授、案例分析、启发、展示、探究，实践等方式相结合。 教学手段：将现代化教学工具如手机，电脑，投影仪等，学习软件如学习通，微师等， 网络交流平台如 QQ,微信等，传统教学工具如黑板，教材等紧密结合。 ① 钻研教材 选定素材 确定目标 方法选择 ③依托素材 2），采取讲授、 情感体验等方法，实现思政 目标 2） 思政素材 思政目标 ②依托素材 1），采取探 究，启发，讨论等方法， 实现思政目标 1） ④采取反思个人现状、行动 实践等方式，检验和巩固思 政效果，实现思政目标 3）
教学过程设计： 主要教学环节： 最短路径定义 案例引入 巩固 (课程思政] Dijkstra算法 练习 小 3min 33min i Dijkstra算法应用 实例，课程思政 效益最优的思想意识渗透整个教学环节 具体教学过程： 教学组织 教师活动 学生活动 设计意图 采取任务驱动法，给出素例-中国邮路愿，引导学生 思考，探时问摆的解决，并引入新溪内容 一个邮递员送信，要走完他负责投递的全部街道， 完成任务后回到邮局，应按怎样的路线走 积极探究 鼓励学生思考，自由 他所走的路程才会最短呢？ 自由讨论 讨论，激发学生的学 体 仔细聆听 习欲，引入新课内 来例引入 情感体验 容，同时，学生深切 教 (3分钟) 体验到民族自豪感， 学 塑造学生科技创新、 过 科技自立、勇于探发 程 的工匠精神 引入思政材料，讲述故事： 中国邮路问题的名字来由一我国数学家管梅谷先生最 早解决上述问愿而得名。 分字华为故事。 结合图形洲授，板书，指导学生理解 1、承短略径相关定义
教学过程设计： 主要教学环节： 具体教学过程： 具 体 教 学 过 程 教学组织 教师活动 学生活动 设计意图 案例引入 （3 分钟） 采取任务驱动法，给出案例-中国邮路问题，引导学生 思考，探讨问题的解决，并引入新课内容 一个邮递员送信，要走完他负责投递的全部街道， 完成任务后回到邮局，应按怎样的路线走， 他所走的路程才会最短呢? 引入思政材料，讲述故事： 中国邮路问题的名字来由-我国数学家管梅谷先生最 早解决上述问题而得名。 分享华为故事。 积极探究 自由讨论 仔细聆听 情感体验 鼓励学生思考，自由 讨论，激发学生的学 习欲望，引入新课内 容。同时，学生深切 体验到民族自豪感， 塑造学生科技创新、 科技自立、勇于探索 的工匠精神 结合图形讲授，板书，指导学生理解： 1、最短路径相关定义 案例引入 (课程思政) 3min 新课 讲授 33min 最短路径定义 Dijkstra 算法 Dijkstra 算法应用 实例，课程思政 巩 固 练习 5min 课堂 小结 3min 课堂 思考 作业 布置 1min 效益最优的思想意识渗透整个教学环节
1.1定义1带权图G-<E,@>,其中：E一R e∈E,oe称作e的权。 -作以.记ag若不相邻.记仙=0 12定义2设L是G中的一条路径，L的所有边的聆所 采用数形结合的方 权之和称作L的权记作。亿。 领悟 法，学生能更直观的 13定义3山和，之间的最烟路径山和v之间权最识记 学习和理解相关定义 小的通路。 如：右图 Li-Vs w(L/-10. L2-%影，oLJ-l2, 通过答愿情况可及时 Ly-vovwws.o(LjJ=11. 了解学生对最短路径 相关定义的掌握情 新授知识 设置拾答题 况，以便发现问题， (33分钟) 上图中，到各自顶点的最短路径的长度为多少？即求 解决问愿：设置抢答 解最短路径问题。 题环节，形成竞争机 课外任务布置：查找相关资料或者参考学习通平台误 思考 制，提高学生的专注 外资源。了解最短路问题的常用算法：Dijkstra算法， 抢答 力和反应能：通过 Bellman-Ford算法，Floyd算法和SPFA算法等，了解 课外任务的设置，拓 各种算法的适用情况。 展学生的知识而，提 高自主学习能力 针对本节难点与重点内容，先指导学生阅读教材，然 后师生合作复述的方式，将算法关步臻进行板书 2、迪杰斯特拉D时ksta算法（标号法）介绍 2.1算法记号说明： 迪杰斯特拉算法实质上一种标号法，每一个顶点有 个标号，分为永久性标号和临时标号两种
具 体 教 学 过 程 新授知识 (33 分钟) 1.1 定义 1 带权图 G=<V,E,ω>, 其中 ω:E→R, e E , ω(e)称作 e 的权。 e=(vi ,vj ), 记 ω(e)=wij . 若 vi ,vj不相邻, 记 ωij =∞。 1.2 定义 2 设 L 是 G 中的一条路径, L 的所有边的 权之和称作 L 的权,记作 ω(L)。 1.3 定义 3 u 和 v 之间的最短路径: u 和 v 之间权最 小的通路。 如：右图中 L1=v0v1v3v5 , ω(L1 )=10, L2=v0v1v4v5 , ω(L2 )=12, L3=v0v2v4v5 , ω(L3 )=11. 设置抢答题： 上图中 v1 到各自顶点的最短路径的长度为多少？即求 解最短路径问题。 课外任务布置：查找相关资料或者参考学习通平台课 外资源。了解最短路问题的常用算法：Dijkstra 算法， Bellman-Ford 算法，Floyd 算法和 SPFA 算法等，了解 各种算法的适用情况。 针对本节难点与重点内容，先指导学生阅读教材，然 后师生合作复述的方式，将算法关键步骤进行板书 2、迪杰斯特拉 Dijkstra 算法（标号法）介绍 2.1 算法记号说明： 迪杰斯特拉算法实质上一种标号法，每一个顶点有一 个标号，分为永久性标号和临时标号两种。 聆听 领悟 识记 思考 抢答 采用数形结合的方 法，学生能更直观的 学习和理解相关定义 通过答题情况可及时 了解学生对最短路径 相关定义的掌握情 况，以便发现问题， 解决问题；设置抢答 题环节，形成竞争机 制，提高学生的专注 力和反应能力；通过 课外任务的设置，拓 展学生的知识面，提 高自主学习能力