翻转课堂在最小生成树问题教学中的实践

岳珂娟，洪 伟

（湖南第一师范学院 信息科学与工程学院，湖南 长沙 410205）

翻转课堂在最小生成树问题教学中的实践

岳珂娟，洪 伟

（湖南第一师范学院 信息科学与工程学院，湖南 长沙 410205）

最小生成树问题是算法分析与设计课程中的一个重要内容。由于其内容本身比较难，加上传统的教师“讲”，学生“听”为主的教学方式，使得学生学习的主动性比较差，也很难达到预期的教学效果。通过探索翻转课堂在最小生成树问题教学实践中的应用，基于翻转课堂的教学模式对教学内容进行重新设计和组织的教学改革效果表明，这种教学模式非常适合最小生成树问题的教学。

翻转课堂；最小生成树；自主学习

引言

最小生成树问题是贪心算法的一个经典例题，也是算法分析与设计这门课程中的一个重要的教学内容。传统的教学方法以教师“讲”，学生“听”为主，并通过上机实验和课后答疑来帮助学生加深对这个问题的理解。这样的教学方式不能调动学生学习的主动性，也很难达到预期的教学效果[1]。

我们将“翻转课堂”这种新的教学模式应用于最小生成树问题的教学实践，解决传统教学中面临的困难，在翻转课堂的框架内对教学内容进行重新设计，教学效果表明这种教学模式非常适合最小生成树问题的教学。

一、最小生成树问题教学中面临的困难

最小生成树问题的教学过程主要包含了以下个步骤：最小生成树问题的描述；最小生成树性质的证明；Prime算法和Kruskal算法的描述；Prime算法和Kruskal算法的实现，程序的编写。这样的教学效果往往很难达到教学的预期目标，主要原因包括以下几个：

（1）缺少课前预习的环节，学生仅靠课堂有限的几十分钟时间要吸收大量的新知识比较困难。即便教师下达了课前预习的指令，由于没有布置具体的预习任务，学生只是盲目地翻看一下教材，对知识点的理解仍然非常浅显。

（2）最小生成树算法本身比较难，仅依靠教材内容的学习难以还原算法的逻辑细节，所以大部分学生对算法的理解停留在死记硬背的阶段，知其然而不知其所以然。

（3）部分学校在开设算法分析与设计这门课程之前，已经开设了数据结构这门课程，从图论的角度讲解了最小生成树问题。在算法分析与设计这门课程中则要求学生从贪心法的角度理解这个问题，并且要分析算法的时间复杂度，学习的侧重点和学习目标有所不同，教学设计上也要有区别。

（4）传统的教学方式通常都是先讲解最小生成树算法的基本理论，然后讲解算法的实现，课堂教学后马上要求学生独立完成相应的算法实现代码[2]。学生和学生之间，缺乏互相讨论和学习的环节，导致实验课的效果并不好，部分同学会无法完成实验课的教学目标。

（5）以教师传授知识为主的传统教学方法，难以激发学生的自主学习性[3]，不利于知识面的拓展。学生学习完最小生成树算法之后，可能对Prime算法和Kruskal算法掌握得比较好，但是对于算法的发展和历史，以及求解最小生成树的其他方法一无所知，不利于学习兴趣的培养。

二、翻转课堂的教学模式

翻转课堂是指重新调整课堂内外的学习模式，将学习的决定权从教师转移给学生[4]。在这种教学模式下，教师的角色从“教”转变为“导”和“答”，学生的角色从“听”转变为“问”[5]。即学生在课前自主完成知识的学习，课堂则变成教师与学生之间，以及学生与学生之间互动的场所，包括答疑解惑、知识的运用等，从而达到更好的教学效果。

随着高校信息化建设的发展，大多数学校已经具备在线学习的平台，可以提供翻转课堂所需要的软硬件环境。同时网络的发展，尤其是学校图书馆科技文献资料的信息化建设，也为学生查阅资料和自主学习提供良好的技术支撑。通过以上对最小生成树问题教学中存在的问题，以及翻转课堂教学模式的分析，我们尝试利用翻转课堂的教学模式对最小生成树问题的教学过程进行重新设计，调动学生自主学习的积极性，探索以学生“问”为主的课堂教学方式。

三、翻转课堂的建设

（一）教学模式的总体设计

翻转课堂构建包括两个角色和三个阶段。两个角色分别是教师和学生，三个阶段分别是课前、课中和课后[6]。在课前，教师根据教学任务和教学目标，对教学内容进行知识点划分和归纳，以知识点为单元，制作教学视频或PPT，搜集相关的学习资源（包括数字图书、网络课程视频或学习资料），布置课前学习的任务。这些资源通过网络上传到校园学习平台，学生通过学习平台观看教学视频，完成相应的学习任务并反馈给教师。教学视频的主要目的是让学生自学课程内容的主要知识点，考虑到学生的自学能力有限，视频的内容要重点突出，讲解要简单清晰，每一段视频的时间一般不超过15分钟。课堂中，教师针对教学内容进行主题讲解，并针对学生的提问开展课堂讨论，最后通过提问引导学生进行扩展知识点的学习。课后，教师进行教学内容的总结分析、作业布置、在线答疑和成绩评定，学生完成课后作业，并通过实践练习巩固学习内容。具体的教学模式如图1所示。

图1 翻转课堂教学模式的总体设计

（二）基于翻转课堂的最小生成树问题的教学设计

将翻转课堂的教学模式应用在最小生成树问题的教学中，需要对课前、课中和课后的教学内容和教学形式进行更加详细的设计，包括知识点的归纳，学习任务的设置、课堂讲解内容的准备、课堂讨论的主题，实验教学的安排，以及考核评价的标准。同时，每一个环节，我们都为学有余力的学生提供了相应的学习资料并给予引导，以满足不同层次学生的学习要求。

1.课前组织

课前学习的主要目的是让学生能够快速进入教学内容的主题，并抓住学习的重点，理解最小生成树问题中主要的知识点。因此，我们在录制的教学视频中只体现三个内容，即算法的应用背景和问题的提出，Prim算法的描述和实现，Kruskal算法的描述和实现。布置的学习任务包括复习最小生成树相关的概念，掌握Prim算法和Kruskal算法的工作原理（包括图示、算法描述和代码实现）。为了掌握学习任务的完成情况，我们设置了选择题和判断题来检查和最小生成树有关的图论中的基本概念的学习情况，设置了问答题来检查学生对Prim算法和Kruskal算法的掌握情况。同时，我们提供包含全部知识点的PPT，帮助学生提前预习课堂上教师需要讲解的内容。除此以外，我们还为学习能力比较强的学生提供了经典的网络课程的视频或网站链接，包括清华大学严蔚敏老师的数据结构课程，北京大学张铭老师的数据结构与算法分析课程，麻省理工学院算法导论公开课。

2.课堂讲解

学生通过课前的学习一般能掌握50%～60%的教学内容，剩余的内容则需要教师利用课堂的教学时间进行重点讲解，让学生对贪心法求解最小生成树问题有一个全面和完整的理解。主题讲解包括如下几个内容：贪心法的基本概念，手工求最小生成树的例题（后面的定理证明会多次使用这个例题），证明最小生成树问题的最优子结构性质和贪心选择性质。其中最优子结构性质和贪心选择性质的证明是重点也是难点，对大部分学生来说，这两个性质的证明很难通过课前的学习自己掌握。教师的讲解，可以让学生充分的理解为什么最小生成树问题可以采用贪心法求得最优解。接下来是学习算法的描述和实现，由于算法的基本原理和实现方法已经在课前学习中完成，根据课前学习的反馈结果，这部分内容的学习可以采取教师讲解学生提问，或学生讲解教师提问的方式进行，对学习内容进行充分的讨论。在课堂教学的最后，我们以提问的方式引导学生进行知识的扩展学习，例如：是否可以用动态规划化法求解最小生成树问题、最小生成树是否唯一、最小生成树算法的历史、其他求最小生成树的方法。

3.课后总结

课后总结是课堂教学完成之后非常重要的一个环节，这个阶段教师可以结合最小生成树问题的教学要点和前期的教学反馈对学习内容进行一个提纲式的总结，并在总结的基础上引导学生对知识点做更高层次的提炼。比如：为什么可以用贪心法求解最小生成树问题，对照最小生成树问题的求解过程，描述贪心法的解题步骤。学生通过对这些问题的思考，可以进一步加深对贪心法求解最小生成树问题的理解。

4.作业布置

根据翻转课堂的教学模式和算法设计课的教学特点，学生的作业主要以两种形式体现。一种是在课前的自主学习中，以书面答题的方式完成；一种是在课后学习中以实践上机并撰写实验报告的方式体现。考虑到个别学生编程能力较差，无法独立完成整个算法的代码编写，我们在这次的实践教学中鼓励学生以小组为单位进行程序的编写。小组成员可以分工合作，并在编写代码的过程中进行讨论，共同完成上机实践的任务。小组的实验报告要体现每个学生在实验中承担的具体工作，并记录讨论的内容。

5.成绩考核

整个学习过程的考核由课前的任务完成情况（占30%）、课堂讨论情况（占20%）、课后作业的完成（占20%），以及实验的完成情况（占30%）四部分组成。其中实验的完成情况包括实验中参与的具体工作和完成质量，以及实验报告的质量。

四、教学效果分析

将翻转课堂的教学模式应用在最小生成树问题的教学中，教学效果最明显的变化就是学生由被动地接受知识转变为主动地学习知识。通过教师提供的教学视频、PPT、网络学习资源，学生在老师的指导下自主学习最小生成树问题的主要知识点。大部分学生可以很好地完成老师布置的课前学习任务，当老师在课堂上进行主题内容的讲解时，学生对新知识点的学习效率有了明显的提高。例如，以往的教学安排是先讲解完贪心法求解最小生成树问题的理论，然后讲解算法的代码实现，学生对前一个知识点还没有完全吸收，就要理解代码的编写方法就很困难。而采取了翻转课堂的教学模式之后，学生已经在课前学习中理解了算法的基本思想，并学习了代码实现的方法，课堂上通过老师的讲解以及同学之间的讨论可以快速地掌握这部分的学习内容。由于课前布置的任务已经要求学生掌握Prim算法和Kruskal算法的工作原理，教师在课堂内的讲解将重点放在了贪心选择性质的证明上，这样避免了和数据结构课程内容上的重复，让学生重新从算法的角度理解来最小生成树问题。

实验部分的教学由独立完成转变为可以小组合作完成，使得编程基础差的学生克服了畏难情绪。这部分学生和小组其他成员合作，不但可以较好地完成自己承担的那部分工作内容，还通过小组讨论掌握了整个算法的实现方法。

同时，我们在课前、课中和课后的每一个环节，都为学生提供了可以进行知识扩展的的学习资料和指导。学习能力较强的学生对这部分内容非常感兴趣，课后也和教师进行了讨论，对最小生成树问题的理解也更加深刻。

结语

本文对算法分析与设计这门课程中的最小生成树问题教学中面临的困难进行了详细的分析，将翻转课堂的教学模式应用在最小生成树问题的教学中。我们分课前、课中和课后三个阶段，对理论教学和实验教学进行了重新设计，在实际教学中取得了较好的教学效果。这种教学模式也可以推广到其他算法的教学中，为算法分析与设计这门课程的教学改革实践提供了一个非常有价值的参考依据。

参考文献：

[1]封富君,李新社,姚俊萍.算法设计与分析课程教学方法探讨[J].大学教育,2014(18):149-150.

[2]冯月华.《数据结构》课程改革下的一堂教学实例——最小生成树[J].陇东学院学报,2014(3):111-115.

[3]陈翔.面向不同层次学生的算法设计与分析课程教学改革探索[J].计算机教育,2014(18):19-22.

[4]吴一尘,张亮,赵文进.翻转课堂在数据结构课程中的应用[J].计算机教育,2016(2):55-57.

[5]赵兴龙.翻转课堂中知识内化过程及教学模式设计[J].现代远程教育研究,2014(2):55-61.

[6]丁智国.翻转课堂在软件体系结构课程教学中的实践[J].计算机教育,2017(3):68-71.

Practice of Flipped Classroom in the Teaching of Minimum Spanning Tree Problem

YUE Ke-juan,HONG Wei

(School ofInformation Science and Engineering,Hunan First Normal University,Changsha,Hunan 410205)

The minimum spanning tree problem is one of the important contents of algorithm analysis and design. The content is difficult,and the traditional teaching method focuses on“teaching and listening”,which cannot arouse the student’s learning initiative,so it is difficult to achieve the desired teaching effect.This paper explores the application of flipped classroom in the teaching practice of minimum spanning tree problem.Based on the flipped classroom,we redesign and organize the teaching contents,and the teaching effect shows that this teaching method is very suitable for the minimum spanning tree problem.

flipped classroom;minimum spanning tree;autonomous learning

G642

A

1674-831X（2017）03-0076-04

[责任编辑：胡 伟]

2017-02-24

湖南省哲学社会科学基金项目（16YBA094）；湖南省教育厅科学研究项目（15C0282）

岳珂娟（1977-），女，湖南邵阳人，湖南第一师范学院讲师，博士研究生，主要从事算法分析与设计研究；洪伟（1976-），女，湖南岳阳人，湖南第一师范学院讲师，主要从事算法分析与设计研究。