算法设计与分析课程教学改革探索

□南京理工大学 孙廷凯 於东军余立功 刘传才 金忠

算法设计与分析课程教学改革探索

□南京理工大学 孙廷凯 於东军余立功 刘传才 金忠

本文从算法设计与分析的课程特点出发，结合课程教学组的教学实践经验，在教学内容、教学方法、教学手段和考核方法等几方面进行了探讨，总结了几点教学改革经验。教学实践表明，这些教学经验在教学中收到了良好效果。

算法设计策略；问题分析；多方位考核

算法设计与分析课程（下文简称“算法课程”）是计算机专业的一门重要的专业基础课，基于现代计算机技术的算法研究从其萌芽阶段到成为一门独立的学科分支，是和计算机科学及其软硬件技术的发展紧密相关、互相促进的。著名的超级计算机“深蓝”击败国际象棋世界冠军卡斯帕罗夫就是一个家喻户晓的例子。学习算法课程，有助于学生日后在实际生产或科研工作中，面对复杂的应用问题时，能够根据问题本身的性质，利用已学习的算法设计技巧，编写出优质高效的程序来解决实际问题，或者针对已有的算法，分析其时间和空间复杂度，进行适当的算法优化，从而对问题的解决带来质的提升。

随着信息技术的发展，算法课程日益成为计算机科学技术中处于核心地位的一门专业基础课，同时，也是电子信息等其他理工科专业学生必需掌握的。许多高校的计算机相关专业都将算法从数据结构中独立出来，将其列为必修课，并给予越来越多的重视。

算法课程是我校的软件工程专业、计算机科学与技术专业的主干课程之一。一方面，它与数据结构、程序设计等课程，构成了这两个本科专业学生课程体系的重要组成部分，并在教学过程中，逐渐建立了一支算法课程教学团队。另一方面，国内高校盛行的大学生数学建模大赛和著名国际赛事ACM竞赛的蓬勃开展，也对本课程的建设起到了积极的推动作用[1]。然而，在实际操作中，学生们普遍反映本课程学习吃力。究其原因主要是：首先，它需要学生具有扎实的先修课程基础；其次，它也不像很多其它课程那样大部分依靠记忆，而是更多地依靠理解，并且要求能够灵活应用；第三，教学内容繁多、涉及面广，但课时有限；第四，传统的课程教学内容过多侧重于理论，忽视应用案例和实践教学，难以跟上当今科技发展步伐。因此，如何上好算法课程，给本课程的教学团队带来了挑战和考验。在教学实践中，我们努力尝试了一些教学改革举措，得到了一些成功的经验。本文拟从教学内容、教学方法、教学手段、考核方式等几方面分别进行探讨。

一、教学内容的选择

建立科学合理的教学内容体系，对于丰富充实教学内容、提高教学效果起着不容置疑的重要作用。一方面，算法设计与分析所涉及的内容非常广泛，与先修课程离散数学、数据结构的某些经典内容有交叉（如图的最短路径算法、排序算法）而又各有侧重，选择恰当的内容有助于算法课程在整个专业课程体系中的准确定位[2]，加上有针对性的讲解，可以让学生既学习到算法设计的思想和分析方法，又不至于让学生觉得“已经学过，没意思”。而教学的困难则在于：先修课程的某些经典内容恰恰是阐述某类算法设计思想的最佳案例，因此常常有学生发问：算法与数据结构两门课程是什么关系？我们认为：二者本身密不可分，在数据结构课程里，重点是静态的数据结构定义，辅助以动态的有关算法使之“活”起来；而在算法课程里，算法设计思想是核心，而数据结构成为算法的基石。在教学实践中，我们也身体力行了这一点，努力让学生对经典内容不但知其然，更知其所以然，从算法设计思想的角度，使学生将经典内容理解得更加深刻。另一方面，算法设计与分析本身是一门年轻的学科，正在不断地发展之中，教学内容需要与时俱进，不断注入新鲜血液和活力，让学生在学习知识的时候，思想深处受到鼓舞，进而激发他们进一步探索学习的愿望。

算法课程通常应包括如下几个方面[3]：一是算法的基本概念、算法的数学基础和复杂度分析方法；二是迄今人们所设计和归纳的几大类经典算法策略，包括分治策略、动态规划策略、贪心策略、图搜索算法、回溯策略、分支限界策略等；三是可计算性理论和问题复杂性方面的研究，如计算模型、NP完全问题等；四是近年来发展起来的随机算法、近似算法、智能优化算法（如启发式搜索、遗传算法、人工免疫算法等）等最新研究进展。其中，前三个方面是重点内容，第四方面可做有选择、有重点的讲解。

目前，国内外关于算法设计与分析的教材很多，但水平不一。国内教材内容选题较为陈旧，分别定位于不同层次本科院校和不同专业，而采用合适的国外教材是快速改革优化教学内容的合理途径之一。国外教材内容大多从ABC起步，内容浩繁（如T.Cormen的《算法导论》，潘金贵等译），但并不适合用做教材。结合我校实际情况，我们选择了M.Alsuwaiyel所著《算法设计技巧与分析》（吴伟昶等译）为基础（其特点是内容丰富、难度适中、加强数学基础、用伪代码描述算法思想），T.Cormen的《算法导论》（其特点是许多经典算法和重要知识点独立成章，讲解细致）为主要参考，以王晓东编著《计算机算法设计与分析》（其特点是应用案例丰富、C语言直接描述便于实现）、吕国英的《算法设计与分析》（其特点是由浅入深、同类算法策略中有更细微的区别策略）为参考的教学内容选择方案，辅之以教师所关注的最新科研进展成果。上述方案较好地兼顾了经典内容的知识性、理论方面的严谨性、应用案例的趣味性、“时尚元素”的现代性等因素。

二、教学方法的改革

从算法设计本身而言，其目的是实际问题求解，而实现过程是：根据问题本身固有的性质，选择合适的算法设计策略，通过一系列算法过程，使问题得到解决。不难看出，分析问题性质是基础，求解过程是关键，也是算法最注重的，而算法策略是某一类算法过程的思想总结。俗话说，条条大路通罗马。同一个问题也应有多种求解策略，而其时间和空间复杂度各有千秋。在教学实践中，我们始终从这一原则出发，不是急于灌输给学生一套算法过程，而是从分析问题性质入手，通过不同的求解过程，实现算法设计、分析、优化的统一。

1.从朴素思想到止于至善

算法思想是前人智慧的总结，简单灌输给学生固然快捷，然而，授人以鱼，不如授人以渔，简单灌输会让学生失去探索的乐趣，失去思维能力提升的宝贵机会，这样做的后果是学生面对新问题时，依然不知道从何下手。因此，面对一个待求解的问题，我们首先让学生利用自己脑海中固有的朴素思想给出求解思路，再分析其利弊（主要是时间和空间复杂度，以及是否利用了充分问题的性质特点），然后，启发学生分析问题本身的性质，利用已有的数据结构知识，勾画出更为高效的算法的“梗概草图”，最后，加以细化，设计出具体算法过程，这样，算法复杂度分析也会迎刃而解。兹举两例说明之。

介绍算法概念时，以二分查找为例，启发学生“基于朴素思想的顺序查找没有充分利用数据有序的固有特点”，而利用中间元素（由于数据有序，刚好居于中值附近）做阈值，不断抛弃大约一半元素，不断缩小问题规模，可迅速定位找到该元素，加以细化，不难写出具体算法。由于该算法利用了数据本身的有序性，求解隐含利用了树结构，不难得到其复杂度为O（logn），比顺序查找的复杂度O（n）低。通过这个简单而又熟悉的例子引起学生的兴趣。而再次启发学生“是否还有别的方法抛弃元素，减小复杂度？”从而为本课程的随机化方法埋下伏笔，这无形中提高了学生带着问题学习的求知欲。

介绍基本数据结构“堆”（在数据结构课中未重点讲解）时，关于堆的建立过程，学生会提出一种朴素的思想，即从空树开始，逐个插入每个结点，调整建堆。我们提醒学生这种方法虽然可行，优点是简单、直观，但实例板书演示发现，每次插入新结点，可能导致彻底打破原堆的结构，结点交换次数过多，造成时间浪费。于是启发学生：如何尽量减少结点交换次数？而启发讨论的结果使算法过程逐渐明晰，得到一种“先建立树，再逐个调整子树成堆”的方法。思想明晰之后，再运用数学知识分析后不难知道，后一种方法更为高效。在这个过程中，学生们真切地在脑海中感受到了“从朴素思想入手——分析问题性质——提出新的求解思路”的一个思维自我提升的过程。使算法设计——分析——优化的过程再次完美统一，此间，教师可不失时机地教育学生“大学之道……在亲民，在止于至善”的理念，让学生在学习知识的同时受到教育思想的熏陶。

在各种算法设计策略的教学中，我们基本都采用了这种教学方法。从中可以看出，这种循序渐进的启发引导式方法，可以帮助学生从分析问题本身性质入手，从基于朴素思想的算法中寻找算法提升的空间，启发学生运用已有的数据结构知识设计出高效的算法，可一揽子实现“算法设计—算法分析—算法优化”的过程，有助于学生解决问题能力的自我提升。

2.从举一反三到触类旁通

面对具体应用问题，既可以根据问题的性质特点采用不同的算法设计策略，在同一种算法策略内部，不同的问题求解方法之间也有具体而微小的差别，这一切都依赖于对问题性质的分析认识程度有多深。在教学中，我们根据这个特点，也采取了有针对性的教学方法。举例来说，利用分治策略求解问题时，需要将规模为n的原问题分解为若干个规模较小的子问题，但如何分割是值得深入思考的。既可以是2个大小相等的子问题（如归并排序），也可以是2个大小不等的子问题（如快速排序），或者是若干个大小不等的子问题（如求数组的最大最小元素），或者是不断抛弃部分元素减小问题规模（如线性选择第k小元素，类似于二分查找），或者是将原问题通过某种变换分解得到若干个子问题（如棋盘覆盖问题）。这样，学生学习之后，会觉得策略不是死的，而是可以具体情况具体分析、可以灵活运用的。此外，为了让学生较好地掌握各种方法之间的联系，我们选用同一个例子而采用多种方法来解决。如在讲解贪心法、动态规划法、回溯法和分枝限界法时，都采用了0/1背包问题，这样，可以引导学生掌握课程内容的内在关联性[4]，帮助他们站在更高的起点和视角审视学过的知识，避免只见树木不见森林。

3．从学会到会学

有的算法策略实现过程的相似性较高，不同的算法策略之间也有内在的联系。我们在有些章节中（如回溯策略），教师精讲一种算法之后，对于其他算法过程，选择一二先让学生自学，然后鼓励学生上台试讲。我们认为，从被动听课到听懂，再到给别人讲明白，实际上是对算法的理解逐渐深刻的过程，同时也是对学生口头表达能力的一种锻炼。在结束几章的授课之后，让学生思考这些章节的算法策略之间的内在联系（如分治策略、动态规划策略、贪心策略之间的对比和联系）并走上讲台与大家交流，对于能够积极主动思考的学生而言，无疑是一种锻炼和尝试，而对于一般学生也是一种激励和促进，这种方式本身也有利于督促学生回顾整理并深入思考已学过的知识，让他们在“埋头拉车”的时候，不要忘记“抬头看路”，进而实现从“学会到会学”的飞跃。

三、教学手段的改革

将传统教学手段与现代技术相结合，是本课程的主要特点之一。我们在教学过程中，将多媒体教学课件、板书和网络教学方式相结合，充分利用多媒体课件多样化的表现形式，利用丰富的网络教学资源，构筑算法课程的现代教学模式。采用的教学手段包括以下几种。

1．多媒体教学和板书相结合

紧扣教学大纲，以教科书和教参为主要依据，精心选择内容制作多媒体课件，课件每个学期都有更新，加入最新内容或对旧内容的新理解。其优点是课程容量大，动态直观，节约了板书的时间。对于一些概念性强、演示性强的章节（如回溯策略、分支限界策略），宜多采取多媒体教学方式，其间辅以研究背景和名人小传轶闻，以增强课堂的趣味性。对于一些算法，可利用电脑软件计算平台现场演示其效果。对于算法复杂性分析和算法解决问题的推导过程，我们仍采用传统的黑板板书教学方式。由此，学生经历了板书从无到有，思路从疑惑到逐渐清晰的过程，而教师的板书和讲解过程，就是一个展示思维与学生交流和沟通的过程。

2．网络教学方式的运用

网络教学在时间和空间上将传统教学进行了全方位的延伸，填补了过去传统教学许多力不能及的地方。一方面，教师可以从网络上获知最新的研究成果(如NP理论、旅行商问题、蚁群算法的最新进展)、一些“高而可攀”的教学研究成果（如递归算法的非递归实现、最短路径算法的最新研究成果）、在线算法论坛资源并将其推荐给学生。另一方面，利用网络实现了师生信息交互，主要方式包括建立课程QQ讨论群，建立课程网站将课件代码上网，在线问答，建立在线作业代码提交和批改系统等，将师生交流从课堂上拓展到随时随地的网络沟通。

四、考核方式的改革

在传统的考核方式下，期末闭卷考试成绩占大部分，平时成绩占小部分，这在一定程度上制约着教学效果，导致一些学生考前突击复习，仅仅靠记忆获取高分，这也会导致考核成绩的不公平。我们尝试改变这种现状，加大了平时成绩的权重，将平时成绩从考勤、作业两方面拓展为包括课程设计、在线作业、研究小论文、课堂表现等都纳入到考核体系中。学生的代码原创性、研究选题新颖性、课堂参与的积极性都是考量指标，通过这种方式，将积极爱好思考的优秀学生与其他学生区别开来，从多方位考核学生的表现。实践表明，这样做更能准确地反映学生平时的学习程度。另一方面，我们将考核与教改有机结合，在期末考试时增加一道主观题，选题范围可以是论述本课程的内容体系结构，或者是对某些算法策略之间内在关系的深层思考，或者是对本课程的教学提出宝贵意见或建议，这些题目均无固定答案，学生可见仁见智自由发挥，从而促使他们思考学习的内容，思考教学过程与学习过程本身存在的有待改进之处。实践表明，这种为学生着想，以学生为中心的做法受到普遍欢迎，学生对我们的教学改革实践也表现出普遍认可，同时还提出了很多合理化建议。

针对算法课程特点和我校的实际情况，为了提高学生的学习积极性，增强教学效果，我们在教学内容、教学方法、教学手段与考核方法等几方面积极开展了教学改革研究和实践，根据课程特点倡导并实践了新的教学方法，通过利用丰富的网络教学资源，将传统的课堂讲授模式和考核方式拓展为全方位的教学与考核模式。实践结果表明，新的教学方法和教学实践受到了学生的普遍认可，取得了令人满意的效果。

[1]吴英杰，王一蕾，傅仰耿，等．依托程序设计竞赛，推进“算法与数据结构”课程实践教学改革[J]．计算机教育，2010（4）：53-55．

[2]於东军,李勇智．算法设计与分析教学改革初探[J]．中国轻工教育，2005（3）：52-54．

[3]陈蕾，张怡婷，许建．基于创新能力培养的算法设计与分析课程教学改革[J]．计算机教育，2010（10）：27-29．

[4]李涵．“算法分析与设计”课程教学改革和实践[J]．中国电力教育,2010（16）：74-75．

G642

项目名称：南京理工大学高等教育教学改革研究重点课题（计算机专业基础课程探究式教学的研究与实践）项目号：2011-362-A5；项目名称：南京理工大学高等教育教学改革研究课题（程序设计类课程体系与ICPC竞赛教学模式研究）项目号：2011-362-B21；项目名称：南京理工大学高等教育教学改革研究课题（本科生导师制教育管理模式创新研究）项目号：2011-362-C28。