《算法设计与分析》启发式实验教学方法探讨

刘少兵+周娅+缪裕青

（桂林电子科技大学 计算机与信息安全学院，广西 桂林 541004）

摘要：《算法设计与分析》课程是计算机软件类专业的一门核心课程，旨在培养学生用算法解决实际工程问题的能力，实验部分更突出强调学生实际动手能力的培养。提出教学内容革新：以启发式实际问题为主，增加综合实验和选做实验，增加以小组形式完成的实验项目；提出实验指导书撰写思路上的革新：从问题→模型→算法→程序的思路撰写实验指导书；提出了在教学形式上革新：制作6个常用算法的微课视频供学生参考等。通过这些方法来切实提高学生的实际动手能力。

关键词：算法；实验教学改革；启发式问题设计

中图分类号：G642.41 文献标志码：A 文章编号：1674-9324（2017）18-0172-02

《算法设计与分析》课程是我校的省级精品课程。这门课程的理论课的师资力量雄厚，然而该课程的实验教学师资、教学水平相对薄弱，实验内容近些年没有更新和补充，因此，对《算法设计与分析》实验进行革新，丰富区精品课程的薄弱部分、培养学生用算法解决问题的实践动手能力具有很现实的意义。然而经过近3年的教学实践，却发现如下问题：（1）学生对算法知识的理解和掌握不够；（2）不能按要求完成实验内容。过半数的学生不能按时独立完成实验，收获较小；（3）实验抄袭现象严重，导致教学目的失败。本文主要讨论实验教学部分，希望能够给同行提供一点借鉴之处。

一、实验教学内容上的改革

本课题组认为，对待《算法设计与分析》这门特别强调学生的动手能力的课程，要有更高的要求：学生应该具备解决综合问题的编程能力。而限于实验学时有限，学生很难在规定的2个学时内完成实验内容，从而使教师不能客观地评价学生。这样导致很多实验内容显得知识点单一，考核内容单一，不能充分调动学生的学习积极性，学生最后的动手能力不能得到充分的挖掘和开发。这里举例说明，下面是我院《算法设计与分析》实验指导书中贪心算法一章中要求完成的实验内容：

实验内容：（1）编程实现背包问题贪心算法。

（2）背包问题的实验数据如表1：N=8，M=110，即8种物品，最大负载110。

应该说上面的实验题基本满足了对贪心算法的学习和实践编程要求。不足之处也是显而易见的：一是考核的知识点单一；二是考核的题目太模型化；三是不适合小组形式合作完成，如果学生不能完成，必然导致抄袭过关；四是题目太少，一人做出，全班做出的局面很常见。为了较好地解决上述不足，课题组提出每次实验的内容至少包含一道综合实验题，一个综合题包括2—3个模块，由一个小组（建议每个小组2—3人）来共同完成。比如可以引入“数列极差问题”作为一道综合实验题。问题要求：在黑板上写了N个正整数组成的一个数列，进行如下操作：每次擦去其中的两个数a和b，然后在数列中加入一个数a×b+1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的为max，最小的为min，则该数列的极差定义为M=max-min。这个实验选题就比以前的题目要好，一是它主体还是用贪心算法，但又和霍夫曼树构造类似；二是用到了两个独立的求最大、最小值，都需要用到贪心算法。这样把一个大的问题分成2个小的模块，该题可以由2个同学协作完成，一人完成一个模块，由于绝对工作量的减少，学生能够在实验时间完成；团队合作，使学生的自信心会明显增强。既培养了大学生之间的协作能力，又有效地降低了学生大面积抄袭行为。这里可能有的任课老师会提出，到哪里去找那么多综合性强但难度又不是很大的题目来让学生来完成呢？笔者认为可以这样来解决：一是合理利用网络资源；二是任课老师将实际项目、毕设、课设或工作等拆解而来；三是最重要的一点，就是需要任课老师多花点时间和精力在教学上，这是业界良心。

二、实验指导书撰写组织思路：从问题→模型→算法→程序

目前的实验指导书不完整，内容少，启发性的东西较少，学生难以完成，做完后收获不能达到预期。撰写指导书，从问题→模型→算法→程序，让学生容易接受和掌握，并能由点及面，解决一类相似问题。比如，在讲分治算法时，会重新学习几种常见的通用排序算法：SORT（A）：（1）If small，just return A.（2）Split A into A1 and A2.（3）S1 is Sort（A1）.（4）S2 is Sort（A2）.（5）Return combine（S1，S2）.

在排序的基础上，得出找一个随机集合中第k小的元素算法：kth（A，k）：（1）Sort A.（2）return the kth value in A.

然后進行如下启发式问题设计：Consider A containing the values 1，2，…，10.

（1）对该特殊数组排序后，第k小的元素位置？

（2）进行一次划分后的数组如下：Charles Hoot 5/30/12 7：16 PM（3）如果我们在找第4小的元素，那么它会在哪个部分？划分元素的前面还是后面？（4）如果有n个元素的集合，我们要找到第k小的元素，所有查找比较次数？（5）给出各种算法所花的时间，完成表格。

在设计以上启发式问题之后，然后学生理解了该怎么做，也真正理解了分治算法的本质，也有信心写出代码，不至于导致实验培养目的失效（限于篇幅，只设计了几个启发式问题，实际的时候一个算法实验至少设计6—10个启发式问题以上较好）。

三、实验教学形式的革新

目前随着网络资源丰富，教师的权威性在学生眼里大幅降低，教师所讲的内容学生都会从网络中去求证或者比对。这本无可厚非，也是学生寻求真知灼见的好方面，但问题是学生的学习时间也有限，在查找一些没有太多实际意义的小问题上花了太多时间，这是消极影响。既然这样，还不如我们任课教师有的放矢，针对自己学生实际水平制作微课视频，有针对性地讲清楚几个常用算法——穷举算法、分治算法、贪心算法、动态规划、回溯算法、分支限界算法、随机算法等。《算法设计与分析》实验通常涉及到后面的6个算法，因而建议实验教师录制6个常用算法微课视频供学生碎片时间里学习，为顺利和有效地完成实验做准备。

四、结论

增加启发式问题是学生深入学习理解算法的关键，也能够增加算法的印象和完成实验的信心，适当增加综合性实验和小组合作实验，能够为学生在实际工作中解决复杂工程问题和团队协作能力打下基础；提供6个常用算法的微课视频是理论教学的良好补充。当然，每门课程都有各自的特点，因材施教，因课施教，是不断摸索和积累的过程。

参考文献：

[1]刘少兵，等.《程序设计与问题求解》理论教学方法研讨[J].科学时代，2010，（22）：106-107.

[2]缪裕清，等.《程序设计与问题求解》实验教学方法探讨[J].教育教学论坛，2015，（20）：158-159.

收稿日期：2016-11-30

基金项目：2015年广西高等教育本科教学改革工程项目，（项目编号2015JGB211）；本文受国家级实验教学示范中心——桂林电子科技大学计算机实验教学中心项目资助，项目号：ZJW43010

作者简介：刘少兵（1973-），男，湖北荆州人，讲师，硕士，主要研究方向：算法优化与算法理论、网络底层通信协议。