算法设计与分析课程教学方法探讨

封富君　李新社　姚俊萍

[摘 要]算法设计与分析是计算机专业的一门核心课程，具有较强的理论性和实践性。结合该课程的教学经验，对教学内容设置进行探讨，同时提出几种适合于该课程的教学方法，使课程教学达到了较好的教学效果。

[关键词]算法 教学方法 教学实践

[中图分类号] G642 [文献标识码] A [文章编号] 2095-3437（2014）18-0149-02

算法设计与分析课程是计算机专业为本科生开设的一门必修专业课，主要通过对一些有代表性的算法进行系统学习，使学生掌握算法的设计思想，培养算法设计与分析的能力，提高学生算法编程的实践能力、知识综合运用能力和解决实际问题的创新能力。

算法设计与分析课程是理论与实践并重的课程，但是在教学过程中笔者发现，大部分学生将其视为理论课，对算法思想虽然理解了，但是不能灵活运用，在编程实践过程中，缺乏解决实际问题的能力。因此，如何提高教学效果，不仅让学生增加理论知识，同时培养学生的实践能力，是本课程教学中需要探索的问题，同时也对授课老师提出了挑战。本文结合算法设计与分析课程的讲授经验，对教学内容设置和教学方法进行探索。

一、目前课程教学中存在的问题

1.算法思想死记硬背，不能举一反三

在教学过程中，发现学生不能真正理解算法的设计思想，而是死记硬背，不能实现举一反三的教学效果。出现这种情况的原因，一方面是没有激发学生的学习兴趣以及自主学习的积极性，另一方面是采用的教学方法不灵活，达不到让学生理解知识的教学目的。因此，该课程教学方法的运用应该考虑如何提高学生学习的兴趣，既要有教学方法的多样性，又要适合该课程的教学。

2.重理论轻实践

算法设计与分析课程往往以理论教授为主，实践环节比较薄弱，因此学生有重理论轻实践的倾向。很多学生虽然理解了算法的设计思想，但是在编程实现算法的过程中总是不能达到满意的结果，究其原因，是由于动手编程的机会太少，实践能力较弱。

课程中所涉及的经典算法都是与实际应用联系紧密的，如果在教学过程中让学生了解相关算法的实际应用，增强学生提高实践能力的意识，培养学生的实际编程能力，对学生以后进行计算机科学研究具有重要的作用。在教学过程中应该多增加一些上机实践课，使学生在实践的过程中加深对算法思想的理解，增强解决实际问题的能力。

二、课程内容设置

算法设计与分析课程在教学内容的选择上应该结合学生的知识背景和接受能力，以典型算法的设计思想为主线，既要掌握算法设计的理论知识，又要提高解决问题的实践能力，同时激发学生自主学习的积极性，使所学内容不局限于书本，而是与实际应用相联系。因此在课程内容设置上应该注意以下几个方面：

1.以算法的基本思想作为主线，并紧紧围绕这条主线，通过具体实例让学生真正理解算法的思想及其分析问题的方法，在解决问题的过程中加深对知识的理解和应用，并培养学生解决问题的综合实践能力。每个典型算法的讲解过程是类似的，以讲解贪心算法为例，采用问题驱动式方法启发学员思考并回答以下问题：

（1）贪心算法的起源是怎样的？为什么会提出这种算法？用于解决哪些问题？

（2）贪心算法的基本思想是什么？需要满足的两个要素（贪心选择性质和最优子结构性质）如何理解？

（3）以最小生成树问题为例，该问题是否适合用贪心算法解决，如何进行分析？

（4）Prim算法和Kruskal算法的基本思想是什么？二者有何区别，分别适合于解决哪类无向连通带权图？

（5）Prim算法和Kruskal算法的时间复杂度如何分析？请进行比较。

（6）分组编程实现Prim算法和Kruskal算法，并研讨交流。

如果学生可以把以上所有问题都能够正确的回答出来，说明对该算法的讲解达到了教学目的。由于课程学时的限制，不可能把所有的实例都讲到，因此，在教学过程中，选择典型例题进行讲解，并让学生自学一部分内容，往往可以达到举一反三的效果。

2.介绍一些经典问题的算法研究新进展，让学生了解该领域的前沿，为以后的科学研究方向奠定基础。例如，最短路径问题的Dijkstra算法目前出现很多的改进，让学生通过查找文献资料了解相关的研究进展，并编程实现感兴趣的改进算法，培养学生解决问题的科学探索精神。

3.在讲解算法的过程中注重与实际的具体应用相联系，让学生认识到学习算法的目的就是为了解决实际的问题，达到理论与实际相联系的目的。例如，在讲解最小生成树和最短路径时，让学生知道该算法的设计可以解决城市交通问题或计算机网络路由问题；回溯法可以应用在电路板排列和图的着色问题中等。

三、课堂教学方法

1.引入趣味问题，提高学习兴趣

通过一些大家比较感兴趣的谜题、故事或生活中的常见问题等，引导学生进入课堂的教学内容，同时提高学生的学习兴趣。例如，汉诺塔问题可以用递归算法解决；棋盘覆盖问题可以用分治法解决；背包问题可以用贪心法解决；0 / 1背包问题可以用动态规划法解决；n后问题可以用回溯法解决等等。这些趣味问题，提高了学生学习算法的热情以及分析问题和解决问题的能力。

2.采用比较教学，加强算法理解

课程中涉及一些基本的算法，包括分治法、动态规划法、贪心法、回溯法、分支界限法和随机化法。不同算法的设计思想不同，解决问题的类型不同，算法设计时需要考虑的代码细节也不同，学生在刚开始学习不同算法时往往容易混淆，如果在教学过程中进行不断的比较学习就可以加深学生对不同算法的理解，如表1所示。

3.制作动画演示，提高教学效果

在课程教学中，通过制作动画演示，把抽象和难以理解的内容直观形象的展现给学生，这样可以在有限的学时内，既将算法执行的步骤一步步的展现给学生，也加深了学生对算法的理解，同时提高了教学效果。

在算法设计与分析课程中，易于用动画演示的算法有：汉诺塔问题的递归算法、二分搜索算法、快速排序算法、合并排序算法、单源最短路径Dijkstra算法、最小生成树Prim算法和Kruskal算法、n后问题和0 / 1背包问题的回溯算法。通过以上实例和算法的动画演示，在教学过程中，取得了很好的教学效果。

4.加强上机实验，培养动手能力

上机实验教学应该考虑以下几个问题：

（1）实验题目的选择不宜过难，要根据学生的知识水平和目前的实际能力，由易到难的选取一些题目，一方面调动了学生的积极性，另一方面也发挥了学生的主观能动性。

（2）实验内容的安排依照教学内容而定，选取一些趣味习题，且面向实际应用，例如：航线选择问题、钱币变换问题、最大覆盖问题、字典序编码问题、田忌赛马问题、任务调度问题、购物问题、士兵队列问题等，这些学生日常生活中常见的问题会引起学生编程的兴趣。

（3）为了使学生更好的理解算法思想，可以布置上机大作业，让学生分组完成不同题目的实验内容，上交实验报告，并在课堂中进行汇报，与其他学生分享自己的收获与经验。例如，实验内容可以是0 / 1背包问题的算法设计与分析，或单源最短路径问题的算法设计与分析等，要求用两种算法设计并编程实现，并比较不同算法的效率。通过学生提交的大作业情况，以及课堂汇报，可以看出学生基本上都能按照要求完成，并出现了很多新的想法，学生的自信心和创造力得到了激发，达到了较好的教学效果。

（4）对于动手能力较强的学生，可以再增加一些有难度的问题，激发学生的创新能力。让学生阅读一些有关算法的文献，了解当前的算法发展，并编程实现。

四、结束语

为了帮助学生更好的理解算法的思想，同时培养解决问题和分析问题的能力，笔者采取了多样的教学手段，如引入趣味问题、采用比较教学、制作动画演示和加强上机实验，在教学中取得了令人满意的教学效果。算法设计与分析课程对教师也提出了挑战，教师不仅应该具有算法的理论知识，还应该具备实践经验，在教学过程中，转变传统的教学观念，采用多样的教学方法，充分调动学生的积极性，鼓励创新，培养学生分析问题和解决问题的能力，使该课程的教学逐步趋于完善。

[ 参 考 文 献 ]

[1] 王晓东.计算机算法设计与分析（第4版）[M].北京：电子工业出版社，2012.

[2] Thomas H.Cormen，潘金贵等，译.算法导论（第2版）[M].北京：机械工业出版社，2008.

[责任编辑：钟 岚]