比较教学法在“算法分析与设计”课程教学中的应用

刘伟

【摘要】“算法分析与设计”是计算机类专业的核心专业课程之一。在“算法分析与设计”教学过程中引入比较教学法，从同一算法求解不同问题、不同算法求解同一问题、同一算法求解同一问题中不同实现方式等多个角度开展比较教学，让学生更好地归纳和整理所学知识，加深学生对知识的理解，建立相关知识之间的联系，有效改善教学效果。

【关键词】算法分析与设计  比较教学法  课程教学

【中图分类号】G642                              【文献标识码】A      【文章编号】2095-3089（2016）11-0111-02

一、引言

“算法分析与设计”是计算机科学与技术、软件工程、信息管理与信息系统、医学信息工程等计算机相关专业一门重要的专业课[1]，是计算机科学和计算机应用的核心课程之一。“算法分析与设计”是一门兼具理论性和实践性的课程，其中部分教学内容具有一定的难度，需要在教学过程中适当引入一些先进和高效的教学方法。

比较教学法是一种对具有可比性的教学内容通过横向和纵向比较，找出它们具有的相同点和不同点，让学生在对比分析中学习和掌握所学内容的教学方法，它通过在教学活动中比较两个或两个以上的认识对象，分析它们存在异同，达到辨识、了解和把握认识对象的目的[2-3]。比较教学法有助于加深学生对知识的理解，建立相关知识之间的联系，培养学生知识迁移应用和自主学习的能力。比较教学法在计算机类专业课程的教学中得到了较为广泛的应用[4-5]。通过多年的教学实践，我们发现比较教学法也可以很好地应用到“算法分析与设计”课程的教学过程中。

二、比较教学法的应用

在“算法分析与设计”课程中，可以从多个角度对教学内容进行比较，下面介绍几种较为典型的应用情况。

1.同一算法求解不同问题的比较

对于某一种算法通常会有大量的应用实例，例如我们在动态规划算法的教学过程中主要讲解五个实例，包括最长公共子序列、矩阵链连乘、01背包问题、数字三角形和最长递增子序列，通过使用动态规划法求解这些问题，对比分析这几个问题的解决步骤，很容易归纳总结出动态规划求解问题的基本步骤，即分析最优解结构、建立递归关系、计算最优值和构造最优解。动态规划算法在求解问题时通常需要采用表格来保存子问题的解，不同的问题其表格的构造存在不同，但是都蕴含了自底向上求解问题的思想，通过对比分析不同问题的递归关系和算法结构，便于总结和整理动态规划的特点，有助于学生更好地理解动态规划算法。同时，通过比较教学法，可以更加深入理解动态规划算法的基本步骤和原理，在比较分析的同时寻找这些问题的共同之处，更好地理解最优子结构和重叠子问题这两个动态规划的基本要素。

在开展“算法分析与设计”教学时，我们还发现对于一些具体问题，使用同一种算法思想从不同的角度考虑可以设计出不同的算法，例如在讲解分治算法时，快速排序和归并排序都基于递归和分治思想，但是这两种算法的实现过程完全不同，可以将二者结合一些经典的排序算法，例如冒泡排序、选择排序和插入排序等进行比较，对比项包括时间复杂度、空间复杂度、排序的稳定性等。通过比较，学生可以理解每一种排序算法的优缺点，便于根据待解决问题的特点选择合适的算法进行求解。

2.不同算法求解同一问题的比较

对于某些实际问题，有时候可以使用多种算法来求解，例如对于最长公共子序列问题，可以采用穷举搜索法、备忘录法、动态规划法等多种方法，且不同的方法具有不同的特点，其实现过程也不尽相同。因此，针对某一问题，在教学过程中对比分析不同算法的特点，有助于学生更好地理解和掌握相关算法的原理。

在“算法分析与设计”课程教学中，主要讲解分治算法、动态规划算法、贪心算法、回溯法和分支限界法这五大算法。对于某些具体问题而言，可以采用这些算法中的两种或多种来求解。以经典的背包问题为例，可以使用多种算法来求解背包问题，但是不同的算法在求解问题时存在较大的区别。例如采用最简单的不考虑跳跃点的动态规划法求解01背包问题时，要求物品的重量为整数，其适用性不强，可以通过跳跃点来改进;如果采用贪心算法，则不能求解01背包问题，因为得到的不一定是最优解，贪心算法可以用于处理连续背包问题，对于01背包问题而言不适用;采用回溯法来求解虽然时间复杂度不及动态规划，但是它是一种万能解题法;也可以使用分支限界法来求解01背包问题，与回溯法的相同点在于都需要使用剪枝函数来删除部分子树，区别在于分支限界法采用广度优先搜索来搜索问题的解空间，而回溯法采用的是深度优先搜索，因此在算法实现时回溯法和分支限界法需要使用不同的数据结构和代码结构。

3.同一算法求解同一问题中不同实现方式的比较

有时候针对某一问题采用同一算法有不同的具体实现方案，例如在讲解使用回溯法求解01背包问题时，重点在于教学生如何高效剪枝，在设计剪枝函数时引导学生主动思考，首先利用约束函数剪去左子树，但时间复杂度仍然很高，然后设计限界函数剪去右子树，最简单的限界函数是直接将剩余物品的总价值与当前获得的价值相加再与当前最优值比较，如果小于当前最优值，则剪去右子树，更好的限界函数是计算得到右子树的上界，如果将当前获得的价值与右子树价值的上界相加小于当前最优值，则剪去右子树，通过计算可以得到右子树的精确上界，进一步对算法进行优化。此外，在讲解回溯法时，通过比较教学法，在分析具体实例时可以让学生理解两种典型的解空间树的异同，遇到新的问题时根据问题的性质来确定是排列数还是子集树，对于不同的解空间树，有不同的算法框架。使用回溯法对解空间进行深度优先搜索时，可以采用递归回溯，也可以采用迭代回溯，通过对代码实例进行比较让学生更好地理解和掌握两种回溯方法的异同。

对于分支限界法，根据从活结点表中选择下一个扩展结点的不同方式也存在不同的分支界限法的实现方式，最常见的有队列式分支限界法和优先队列式分支限界法。在讲解装载问题等具体实例时，通过比较两种不同的实现方法可以加深对这两种实现方式的理解。

三、结语

比较教学法通过对比分析，寻找事物之间的联系，分析待比较对象之间存在的异同，采用求同比较、求异比较、相似比较等形式，让教学内容更加系统化、综合化和条理化。在“算法分析与设计”课程教学过程中，通过对某些教学内容采用比较教学法，有助于培养学生整理和总结所学知识的能力，让学生在面对新知识的学习时摆脱陌生感，增加学习的主动性，提高学习效率，优化学习效果。正确运用比较教学法可以让学生更为深刻、更为全面地理解和掌握所学知识，从而获得更好的教学效果。

参考文献：

[1] 王晓东. 算法分析与设计（第3版）[M]. 北京：清华大学出版社， 2014.

[2] 李运模. 比较教学法论略[J]. 中南民族学院学报：人文社会科学版，2000，20（3）：125-127.

[3] 肖敏. 比较教学法在现代设计方法课程教学中的应用[J]. 高教论坛，2006（6）：120-121.

[4] 徐钦桂，杨桃栏. 比较教学法在操作系统教学中的应用与实践 [J]. 计算机教育，2010（10）：95-99.

[5] 熊小兵. “汇编语言程序设计”的比较教学法 [J]. 计算机教育，2010（3）：147-149.