《算法设计与分析》课程教学改革探讨

郭良敏

摘要：《算法设计与分析》课程是计算机相关专业硕士研究生的专业基础课程，该文基于该课程的特点和教学中存在的问题，从教学内容、教学方法、实践以及课程考核四方面进行一些讨论。

关键词：算法设计与分析；教学内容；教学方法；实践；考核

中图分类号：G64 文献标识码：A 文章编号：1009-3044（2016）35-0120-02

Discussion about Algorithm Design and Analysis Teaching Reform

GUO Liang-min

（School of Mathematics and Computer Science， Anhui Normal University， Wuhu 241000， China）

Abstract： The course of algorithm design and analysis is a basic specialty course for graduated students majored in computer science and related fields. According to the course features and the existing problems in teaching， the teaching content， teaching method， practice and course assessment are discussed in the paper.

Key words： Algorithm design and analysis； Teaching content； Teaching method； Practice； Assessment

《算法设计与分析》课程是计算机相关专业重要的一门专业基础课程，要求学生能通过对本课程的学习，理解主要算法的基本思想，掌握算法的设计方法和分析方法，并能将所学算法应用到实际问题中，从而解决遇到的实际问题。

该课程具有内容抽象、知识范围广、实践性强等特点，因此，学生的学习难度大，学习兴趣不高。教师在课程内容的选择上与前沿科学研究的联系不是很紧密，教学方法和考核方式也相对单一。针对上述问题，本文主要从教学内容、方法、实践和考核四方面展开讨论。

1 教学内容的整合

教学内容除了包含经典算法[1]（递归、分治法、动态规划、贪心算法、回溯法、分支限界法）的设计理论外，我们还应将随机算法、近似算法、现代启发式算法、并行算法、分布式算法等与前沿联系紧密的内容融入教学中。教学的重点是经典算法的原理，要让学生理解，并且可以具体实现；难点是如何灵活运用合适的算法去解决遇到的实际问题，即培养学生对所学算法的实际应用能力。

另外，需要将新的相关科研动向融入教学中[2]，尤其是在讲解现代启发式算法、并行算法、分布式算法等时，增强学生的学习兴趣，让学生感到学有所用，从而提高教学效果，最终达到使学生可以用基本理论去解决实际问题的目标。

具体的教学内容安排如下：第一部分是算法概述，包括基本概念、描述算法与算法设计、算法分析的基本原则、复杂性分析；第二部分是分治与递归，包括递归概念和分治法的思想、二分搜索技术、矩阵的快速乘法、合并排序、快速排序、线性时间选择、最接近点对问题；第三部分是动态规划，包括矩阵连乘问题、动态规划算法的基本要素、最长公共子序列问题、0-1背包问题、作业调度问题、图像压缩问题；第四部分贪心算法，包括活动安排问题、贪心算法的基本要素、最优装载、哈夫曼编码、最小生成树、单源最短路径；第五部分是回溯法，包括回溯法的算法框架、装载问题、批处理作业调度、0-1背包问题、n皇后问题、图的m着色问题、旅行售货员问题、圆排列问题；第六部分是分支限界，包括分支限界法的算法框架、单源最短路径问题、装载问题、0-1背包问题、批处理作业调度、旅行售货员问题；第七部分是随机算法，包括数值计算问题的随机算法、舍伍德算法、拉斯维加斯算法、蒙特卡罗算法；第八部分是近似算法，包括NP完全性理论、顶点覆盖问题、旅行售货员问题；第九部分是分布式算法，包括分布式系统、分布式计算模型、分布式算法的设计基础、遍历算法、选举算法、容错技术；第十部分是现代启发式算法，包括启发式算法的基本概念、模拟退火算法、遗传算法、蚁群算法、人工神经网络算法；第十一部分是并行算法，包括并行计算机、并行算法的基本概念、非数值计算问题的并行算法、数值计算问题的并行算法。

2 改革教学方法

一是采用以“幻灯片+黑板+计算机”的授课模式，即以电子教案幻灯片、板书和算法的动态演示作为教学内容的展现方式。用幻灯片主要展示静态的文字，如定义、基本框架或步骤，板书主要用于分析算法的原理和效率，方便与学生进行交流，算法的动态演示可以更直观地展示算法的执行过程，从而让学生更容易地去掌握和理解算法的原理和执行步骤。

二是对同一问题，如背包问题、皇后问题、作业调度问题、资源分配问题等，有不同的算法可以求解。对于这类问题的讲解，我们应该以问题为主线，分析和比较不同算法的特点和效率[4]，并让学生编写程序实现，理论联系实际，通过不同程序的运行结果，从而更容易地理解对同一的问题的不同实现算法。

三是我们主要采用启发式的教学方式，即变填鸭式的教学为双向互动式的教学，采取以探究解决实际应用问题为主的引导式教学，启发学生在理解问题的基础上，进行新的算法思路的探索与讨论，引导学生深入思考，培养学生的自我创新能力。

四是对于非经典的算法可先通过简单的、有趣的实例来说明，便于学生了解算法的大致思想，然后再通过阅读相关科技文献的方法加深对算法的理解。这样不仅可以让学生较容易地掌握相关算法，还可以让其了解相关领域的研究状况。

3 强化实践环节

将算法转换成实际的程序来获得实际问题的解，这是我们学习算法的最终目的，通过多动手编程，可以让学生加深对理论知识的理解。考虑到学生水平的参差不齐，特别是动手编程的能力，我们给予实验内容多种不同的选择方案[3]，不同的选择方案对应着不同的实现难度，例如，可将实验内容按难易程度分为基础型、拔高型、挑战型。对于基础型的实验一般较容易，要求学生必须完成，对于拔高型和挑战型的实验，学生可以根据自身的能力进行选做，对于选做的学生，我们可以依据他们的完成情况在最终的考核成绩上予以体现。

4 优化考核方式

考核方式应该多样化，更应该注重评判学生平时课堂上的积极性，作业的完成效果，学生的创新能力，即注重对学生的过程性考核。利用过程性考核和最终的理论测试考核相结合的方式来综合评价学生。例如，过程性考核和理论测试考核各占50%，其中，在过程性考核中，平时课堂上的积极性（由到课率、回答问题情况，参与讨论情况决定）占50%，作业的完成效果（由作业完成的时间质量和内容质量，以及拔高型和挑战型作业的完成质量决定）占40%，学生的创新能力（由学生参与课题的情况及已获得的成果，特别是与本课程相关的成果决定）占10%。

5 结束语

本文主要从《算法设计与分析》课程的教学内容、教学方法等方面阐述了一些想法。但要更好地提高教学效果，还需教师在教学过程中不断地进行经验总结，根据实际情况对内容、方法等做出较为及时地调整。

参考文献：

[1] 王晓东. 计算机算法设计与分析（第3版）[M]. 电子工业出版社， 2007.

[2] 刘文萍， 陈世红， 郭小平. 教师领导力在计算机专业研究生创新能力培养中的应用[J].计算机教育， 2013， 23： 42-45.

[3] 陈宝平. 《算法设计与分析》课程教学的探索与实践[J]. 现代计算机， 2012： 37-40.

[4] 孙亞红. 《算法设计与分析》课程教学中计算思维的培养研究[J]. 电脑知识与技术， 2012，8（16）：3910-3911.