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

黄成

（中南林业科技大学涉外学院，湖南 长沙 410201）

软件工程专业是一个强调程序设计实践能力和编程动手能力的专业。《算法分析与设计》是专业内的一门重要的专业基础课，通常是有了基本编程和数据结构基础的大二下期或是大三上期开课。作为《高级语言程序设计》和《数据结构》课程之后续课程，这门课的理论性和实践性都很强。而根据尼克劳斯·威茨在他的著作《算法+数据结构=程序》一书中提出的理念：程序的编辑其本质就是数据结构加算法的综合应用。所以培养应用型人才就是在培养实际运用算法和数据结构解决问题的能力。这个应该成为《算法分析与设计》课程教学的核心任务。

由于算法本身特点不能局限于某种具体的程序语言，所以部分教学内容具有一定的难度。教授课程的老师如果将代码完整的展现给学生，就会纠结于代码的组成和实现，不利于学生理解算法原理和思维逻辑；而不写完整的代码，使用伪代码讲述算法，对于学生来说就成了“听起来很重要，条理梳理明确了，方法讲解明白了，但是自己运用起来就不知道从哪里下手、怎么下手，编程实现很困难”。这其实就是学生解决实际问题的能力并没有本质上的提高，知其然不知其所以然。这样的情况应该予以改变。

一、算法教学中的问题

梳理笔者多年算法课程的教学，发现传统的课程教学中存在以下的问题：（1）本课程要求学生的编程基础扎实。而部分同学在前导课程中学习并不理想，导致课程实践的时候想法思想和代码不能无缝衔接，无法顺利实现自己的设计，从而影响后续课程的学习积极性。（2）课堂讲述因课时的影响，只能偏重理论教学，实践教学薄弱乃至空白。一般算法实践课时仅占总课时的百分之二十不到，有的专业还不到这个比例。这个情况导致学生为了应付考试和学分，只顾死记硬背理论内容，缺乏上机操作的锻炼，不善于应用算法思想解决实际问题。（3）教学内容涉及面广且知识点众多，加上综合应用性强，所以它不能像其他的课程一样依靠记忆背诵就可以学好，更多的是依赖于理解算法的思想和数学知识的相结合达到灵活运用程度。软件工程的部分同学数学知识基础薄弱，对于理论知识抽象且繁杂的时候，越学到后面越不能理解，越学越觉得枯燥难懂，没有兴趣继续学习。算法的含义是一系列按机械步骤解决问题的明确指令，也就是说对于符合一定规范的输入能够在有限时间内以一定的机械步骤获得要求的输出。虽然这标志着绝大多数算法最终靠计算机来执行，并强调解题步骤的机械性，但是算法概念本身并不依赖这样的假设[1]。算法不只是为了写出良好的计算机程序而准备的，是为了培养人们的分析能力和向“计算机”描述知识而准备的。所以局限于某一特定的语言编程中，无助于学生真正的掌握算法的思维。所以算法强调以伪代码描述，而非程序代码。但是伪代码不是程序，不能运行看结果。这样导致没有理解算法思想的学生无法也没有兴趣将理论应用至实际问题当中。所以激发学生应用的兴趣和能力，也就成了算法课程急待解决的问题。

而想要达到这一目标，需要激发学生面对问题主动思考的热情和积极性，鼓励他们自主动手解题、勇于动手解题。探究式的教学方法正是为了这样的目标而出现的。通过探究式教学启发学生思考，带领他们体会算法的核心思想，领悟不同的算法解决不同的问题的选择，学习遇到实际问题时分析问题性质、设计适合的解决方案的办法，从而培养他们举一反三的探索问题、解决问题的能力。

笔者经过教学实践总结了一些经验，本文拟从教学内容、教学方式等几方面来进行探讨。

二、教学内容的改革

当前算法设计与分析的教材五花八门，总结其所涉及的知识点主要是三大部分：首先是算法分析基础，其中包括算法问题求解基础和算法效率分析基础。其次是算法设计策略，包括蛮力法、分治法、减治法、变治法、时空权衡、动态规划、贪婪技术、迭代改进等[2]。第三部分是算法能力的极限和超越能力的极限，核心是求解困难问题。

知识点的第一部分是全体算法求解思路的核心，是总纲但也是理解的难点。原来算法课程是立足理论，主要进行概念的教授。学生没有接触过实际工程项目，对项目的效率分析没有直接的感受，无法明确了解算法效率的意义。仅仅停留在理论明白的层面上，对实际应用的时候没有起到指导性的作用。对于应用型的大学生来说应立足于用、理解思想精髓为上。所以在这里减少理论讲述，以具体实际经典算法为案例结合后面的课程创设探究的情境[2]。先建立感性认识，让学生在后期的算法实践中感受和认知。第二部分内容繁多，涉及的编程技巧众多，授课课时压力很大。但可以结合第一部分内容所形成的情景，选择其中较贴近生活的典型事例，以此引导学生采用书本多种算法思路分析求解问题。从而从实际问题的求解方式的对比，来体会效率的意义和算法思维的精髓。例如：排序算法在求解序列相关问题时可以使用的排序方法有合并排序，快速排序等。都是针对排序问题的算法，但是按情景设定的区别，各自都有不同的适用场景。如求无序序列数据中间的极值时宜使用合并排序算法，仅仅求取最大或最小值时无需全部归并，只要找最大的和最小的归并即可。求无序序列数据区间情况的时候用快速排序算法，在只求无序数列排序后的部分区间内数据的时候，可以增加门阀值作为快排分裂点以提高效率，且同时可以进行数据压缩的操作讲解。这样可以告诉学生算法不是模板，不需要完全照搬算法的原始设计。这些都可以在课堂上引导学生通过分组讨论的形式分辨算法思维和效率的高低，从而得到直观贴切的解题感受形成课程报告。而不再局限于某个章节或是某类方法的讲授。第三部分求解困难问题部分，可以结合前面的实践成果来讨论求解的条件和场景，也可以作为学生课后扩展的练习。针对学时有限的软件工程专业的本科生来说，在总数56学时中包含了众多的知识点。因而在内容的选择上要依据容量适中、前后内容衔接紧密的原则，尽量减少在相似内容上的讲述时间，用解题思路的演变和对应的实现方法贯穿整个教学活动。

三、教学方式的改变

原本的算法课程大都是理论讲述，各章节的内容较为分散，没有有机的结合[3]。雷同的解题情景在不同的算法章节中重复出现，如称金币或式金块，旅行者问题、二叉树查找问题。虽然是经典的事例，但是算法思维随着情景的改变而改变的思路、情景的对比讨论、算法之间的耦合都没有。而且与生活事例交集不大，形成学生无法对比联系，无法认同这些理论的价值，在实际使用时常常无法应用，从而降低了他们学习的兴趣。所以变原来按部就班地依照算法大类章节讲述方法为以案例驱动的探究式教学。以实际生活中的事例为场景，按照情景的变化综合性的跨算法大类讲授算法的实现，会极大的调动学生的积极性，提高他们的主观能动，开拓他们的思维，提升实际算法思维的使用。如同二叉树剪枝操作。是十分有必要使用的算法，但是因涉及算法能力的优化内容，教材安排在后续的章节中，在课时的压力下大多情况是不会教授的。在教授过程中可以提出案例“查询公司在某个范围的时间内，售卖价格大于门阀值，库存小于门阀值”，在这里加入二叉树剪枝操作的讲解。传统的做法一般是在数据采集完成后，用于降低程序的计算复杂度时，减少处理数据的分支数据的。但是在大数据环境下一般是在对采集的数据进行价值化处理的数据挖掘时期决策树使用的。一个是减少程序的计算量，一个是筛选数据形成有效分类。这样既述说了使用的适用场景，也联系了现下最流行的技术应用，十分吸引学生的注意力，提高了学生的学习兴趣。

这个教学体系主要以实际事例为引导，贯穿各个算法的思维演变和方法的变化，可以适用于所有计算机相关专业的算法分析与设计课程。

虽然是通过教学实践总结了一个体系，但是尚存在诸多不足。作为一种新的教学思路，所提出的方法能否解决当下课程的问题？是否是最有效的解决方案？能否满足学校培养方案和社会用人需求之间的完美统一？是值得讨论的。一家之言，希望能够抛砖引玉获得大家的指正。