“算法设计与分析”课程教学中若干实践与思考

石润华 仲红

摘要：“算法设计与分析”是计算机专业的核心课程。该文分别从培养目标、学习兴趣、积极思考、教学方式、理论与实验、科研与教学等多方面探讨该课程的教学实践，并引出若干思考。这对提高这门课程的教学效果与教学质量有着重要意义。

关键词：算法设计；算法分析；教学研究；教学实践

中图分类号：G642文献标识码：A文章编号：1009-3044(2012)01-0246-03

Several Teaching Practices and Thoughts on Algorithms Design and Analysis

SHI Run-hua, ZHONG Hong

（School of Computer Science and Technology, Anhui University, Hefei 230039, China）

Abstract: Algorithms Design and Analysis is one of core courses in Computer Science and Technology. This paper discussed its several teaching practices from Training Objects, Interest of Study, Active Thoughts, Teaching Method, Theory and Experiment, Scientific Research and Teaching, respectively, and then presented several thoughts. It is significant to improve the teaching effect and quality of Algorithms Design and Analysis for these practices and thoughts.

Key words: algorithm design, algorithm analysis, teaching research, teaching practice

“算法设计与分析”是计算机科学与技术学科中核心课程之一，主要研究一些基本算法的设计策略及算法分析的方法。算法（Algorithm）一词来自19世纪一位波斯数学家，它就是计算的步骤和法则，也就是一系列的将输入转换为输出的计算步骤[1]。也可以简单理解为算法是一序列解决问题的清晰指令，也就是说，能够对一定规模的输入，在有限时间内获得所要求的输出。算法作为计算机软件技术中的重要组成部分，其发展对提高计算机的使用效率以及拓宽其应用领域起着重要的作用[2]。目前，在一些211或985高校，算法是本科生的必修课程，也是研究生的核心课程。因为它的重要性，以及有着相当的难度和深度，通常作为计算机领域博士生入学的必考内容之一。

尽管“算法设计与分析”课程在计算机科学中有着非常重要的地位，但学习起来并不像那些仅仅需要死记硬背的课程，学好算法不仅仅要求能理解人家已有的对具体问题的求解策略（算法），还要能够能动地利用已学过的算法策略去解析新的问题。理解算法是一回事，运用它去解决问题是另一回事。特别对于一些数学基础薄弱，缺少抽象思维能力的学生来说，能理解算法就已经很不容易了，更何况要利用它去解决问题、分析问题。这使得他们在学习过程很吃力，很难学好它，从而排斥乃至抵制学习算法。此时，教就显得很重要，教得好能提高学生的学习兴趣，正确指引他们学习的方向，逐步培养他们解决问题、分析问题的能力；教不好可能适得其反，反而使得他们感到枯燥无味。

目前，在教授“算法设计与分析”课程中，存在如下共性问题[3,4]：培养目标单一，教学内容固化，教学方法僵化。结果势必是：学生学得很吃力，老师教得也很累。笔者及同课题组多位同事，多年从事不同专业不同层次的与算法相关的教学工作，在教学过程中不断学习，在学习过程中用心积累，在积累过程中不断完善。特别地，针对以上存在的具体问题，不断思考，努力创新，进行了若干实践，取得了不错的效果。

1若干实践与思考

经过多年的实践教学，我们认为以下几点值得同行们借鉴和思考。

1.1培养目标的多样化

算法始终贯穿整个计算机的发展历程。甚至有学者提出“计算机科学就是算法的研究”。理论上，只要是研究算法的内容都可以作为“算法设计与分析”课程的授课内容，因而该课程所覆盖的内容非常广：既有一些基础算法的设计策略及相应的分析方法，例如分治算法、贪心算法、动态规划算法、回溯法、分支限界法，又有一些特殊算法，例如图论算法、几何算法、组合算法、密码算法、遗传算法、蚁群算法等。另外针对不同的计算模型，算法研究的内容也不尽相同，例如有并行算法、分布式算法、概率算法、量子算法、云计算乃至普适计算环境下的算法。正因为算法所涉及的内容很广，所以不可能在有限的时间内向学生传授所有的东西，只能根据具体的培养目标选择相应的教学内容。

为了克服培养目标单一，以免教学内容固化，我们构建了多级培养目标。首先我们构建了一个总体目标：“通过系统学习，使得学生掌握算法设计与算法分析的常用方法；培养学生由具体到抽象的逻辑思维能力，培养他们计算的思维、计算的习惯”。进而，针对不同的专业不同的层次，我们制定了相应的分级培养目标。分级培养目标更具体，但都要为总体目标服务。正是因为分级目标的不同，导致了所选用的教材及所授课的内容也不一样。

对于非本专业的本科层次，例如信息管理、数学、电子与信息等专业，学习该课程的目的主要在于理解和认识，因而其分级培养目标为：“使得学生能够理解一些基本算法设计的思想，及相应的时空复杂性，帮助他们进一步认识和理解计算机，掌握计算的规律，初步培养他们计算的思维和习惯，能够从计算的视角去观察世界”。也即，侧重点是算法设计。我们选用自编教材，总学时36，所涉及的主要内容是一些基础算法设计的方法，例如分治、贪心、动态规划、回溯、分支限界，以及一些常用的算法，例如查找、排序、选择、匹配等。

对于本专业的本科层次，包括计算机科学与技术，软件工程，网络工程三个本科专业，其分级培养目标为：“通过对计算机算法系统的学习，掌握算法设计的主要方法，培养学生分析算法复杂度的初步能力，锻炼其逻辑思维能力和想象力，并使之了解算法理论的发展。为独立设计算法和对算法进行复杂性分析奠定坚实的基础”。对此，我们的教学侧重点是算法设计，兼顾算法分析。我们选用王晓东编著《计算机算法设计与分析》教材。通过大量具体实例，重点学习分治、动态规划、贪心、回溯、分之限界、概率等算法的设计思想、求解步骤、分析方法。此外，我们也适当增加了一些算法复杂性分析的方法的内容。所用学时54+24，增加了24个机时的实验课，实验课采用自编讲义。

对于本专业研究生层次，已经具备一定的计算机科学与技术素养，而且其中相当一部分学生因本科期间修过算法相关课程，已经具备一定的算法设计与分析的能力，但也有少数学生在本科阶段没有系统接受过算法课程的学习。因而我们的侧重点是算法分析，兼顾算法设计，并拓展算法研究内容，要求他们掌握一些常用的算法分析的方法，所选用的教材是中文版《算法导论》（潘金贵译）。它的主要内容是研究计算机应用中常常遇到的实际问题的解法，研究设计和分析各种算法的基本原理、方法和技术。与本科层次相比，增加了一些算法分析的高级方法，以及针对于一些高级数据结构的算法。总学时72。其分级培养目标是：“掌握算法设计与算法分析的常用方法，以便运用这些方法去独立设计解决各类实际问题的算法；利用已有的算法去解决计算机科学与工程领域中较为复杂的实际问题；对已有的算法进行改进，使之能更快、更有效地解决问题”。

另外，对于本专业的博士层次，也开设了算法相关的选修课程，例如，智能计算、自然计算、量子计算等课程。在我们的教学体系中，宏观上有一个粗线条的总体培养目标，具体到不同对象，又有不同的分级培养目标。分级培养目标更具体，形成阶梯之势，都为总体目标服务。

1.2激发学生的兴趣

在我们的教学过程中，始终把激发学生的学习兴趣放在首要位置。但怎样能激发大学生的学习兴趣呢？实际上，这不仅仅是这门课程需要思考的问题，也是整个大学教育都需要思考的问题[5,6]。显然，为了激发大学生的学习热情，仅仅采用小学、中学时的那种“增强科学的神秘感，展示技术的力量”的方法行不通。那种因为我不知道所以要学的方式很难再驱使大学生。经过我们的调查发现，多数学生对学习失去兴趣，主要原因有二：一是缺少专业理想（进而缺少学习动力）；二是因不知而不学（即对所学的科目缺乏了解，缺少积累，更不知道学有什么用，从而失去学习兴趣）。

因此为了激发他们的学习兴趣，需要引导他们，树立远大的专业理想，继而对所在学科、所学内容，能从宏观上把握、认识、了解、喜爱、乃至着迷。在教授专业知识的同时，我们也很注重以下几点：

帮助学生树立远大的专业理想。在科学探索上，人类有两大永恒的主题：一是探索外太空；二是探索生命的奥秘。而计算机科学与技术给这两大领域的探索带来了很大的变化，获得了一些了不起的成就。启示学生应该多思考“怎样利用计算机来涉及这两大主题，怎样使自己融入其中，乃至做出推动整个人类文明进步的工作，在人类的文明史上留下自己的烙印”。

简要介绍计算机的发展历程，展望未来的计算技术与未来的世界。理解什么是计算，拓展计算的范畴。实际上，计算无处不在。但怎样用计算机来计算？也即“怎样抽象模型，形式定义，设计合适的数据结构，加上具体的算法策略，最后程序实现，得到想要的结果”，这一过程实质上是一种在计算机中模拟具体物理实在（或系统）的动态过程，从而更好地探询这些复杂系统的内在规律。对于千千万万的具体问题，我们应该从哪里着手？怎样深入分析乃至实施最终的计算？或许“算法设计与分析”中将会有答案。它能指引我们用更好的方法求解具体问题，并且能够培养我们计算的思维和习惯。

系统概述地介绍“算法设计与分析”的主要内容，以及它在整个计算机科学与技术中的地位。偶尔介绍一些算法在计算机科学中扮演重要角色的例子。例如，密码破译中算法与高性能计算机之间的博弈。在授课之初，就应该让学生明确“算法设计与分析”所覆盖的主要知识和技能。为什么要学习该门课程？学习该课程后，我们能做些什么？应该怎样学？”。

1.3引导学生积极思考

在教学过程中，引导学生积极思考，也至关重要，能使学习由被动变主动。经过多年实践教学，我们认为“多提问，提好问”是引导学生积极思考的重要措施。但问的问题不能很随意，需要经过精心设计。为了让学生积极思考，教师在教学之余需要多设计问题，设计好问题。问题设计得好不好，有没有吸引力尤为关键。笔者每章每节均会留下一些问题，让学生思考，当然也有课堂提问，鼓励学生及时作答。结果最为明显的效果是“主动与我互动的学生多了，学生间的交流与讨论也多了，认真听课的多了，作业完成的质量提高了，学习的氛围让我更满意了”。例如，讲授分治算法的某些实例时，分的阶段多为二分（均分），此时若引入：“能否三分或多分？若多分结果（或复杂性）又如何？”，“用分治算法求解具体实例时，怎样改进算法所需的时间复杂性？”；在学习自然归并排序时，笔者经常提出“是否存在自然冒泡排序？或在插入排序（或折半插入排序）中，是否可以一次插入多个有序的数？是否也能改进其时间复杂度”；学完矩阵连乘问题（动态规划算法求解）时，喜欢提出“矩阵连乘的每一种计算方式对应着一种计算成本（也即一个整数），若有n个矩阵连乘，则至少对应着Ω(2n)个整数，该问题实质上是要从Ω(2n)个数中选择最小数（对应最佳成本）。那么是否意味着存在比最坏时间为线性还要优的选择算法？”；“在概率算法中，学习计算π值的随机算法后，能否设计计算线段长度（等于 2或其它无理数）的随机算法？”。

另外，给学生推荐一些好的课外读物也有积极的作用。我们推荐的课外读物不仅是一些教辅读物，还有一些有关计算机、算法乃至其它自然科学的人物传记、科学史话、科幻预言等。例如《宇宙、量子和人脑》、《宇宙的起源》、《揭开生命的奥秘》等书或视频。

总之，课堂教学固然很重要，但课堂之外的工作也非常重要，其中多设计问题，设计好问题很关键。它能引导学生积极思考，变被动学习为主动学习。

1.4教学方式多样化

在传统教学中，那种填鸭式的教学方式，只会使学习“算法”相关的课程变得枯燥，学生只能被动接受，缺少主动思考，更谈不上所谓的创新能力的培养。教的根本是学，因而教学方式要能适应学生的需要。所学的内容日新月异，所采用的教学方式当然也要与时俱进。

在我们的教学过程中，鼓励教学方式的多样化：以多媒体和板书为主，结合其它教学方式。多媒体课件的开发应用，极大地丰富了教学手段。但开发、设计出具有个性化的课件需要花费教师大量的课外时间。尤其是动与静的结合，具体与抽象的变换，需要精心设计。另外，多媒体教学也有局限性，很难满足“内容的有限与思想的无限”之间的矛盾。而教是一个动态的过程。为了体现及时性，必要的板书尤为重要。实际上，板书更自由，跨度广，前后关联更紧密。此外，启发式教、自主式学、分组讨论等其它教学形式也是必要的补充。

1.5理论与实验相辅相成

在“算法设计与分析”课程的理论教学的同时，我们也很重视相应的实验教学。理论与实验相辅相成，相得益彰。实验能对理论加以验证，进而能加深对理论的理解，反过来，理论又能指导实验。

针对不同的专业不同的层次，我们设计了不同的实验内容，分别以实验课和课外作业的形式开展。在所有实验教学及作业中，我们设计了四类实验：验证类、基础类、综合类、设计类。前三类均由老师给定相应的实验内容，后一类实验内容由学生独立设计、开展、实施、验证。整个实验进程由浅及深，内容覆盖面广，涉及算法设计、算法实现、算法改进等内容。整个实验（特别是后一类实验）的开展，取得了不错的成效。加深了学生对理论知识的把握和更深层次的感悟。使学生在学习过程中更能发挥主动性、能动性。主导自己的学习目的，修正自己的学习行为，更新自己的学习内容乃至学习方式。

1.6科研与教学并重

教学不能游离于科研之外，教学与科研并重，相互促进，有益补充。良好的科研会使老师对某一专业研究有较深的理解，能更好地把所学知识融入其中（也即学有何用），从而对教的内容、方式、方法有更深的理解、更好的感悟。例如，笔者在教学的同时，坚持科研工作。研究方向为信息安全，重点研究密码算法，这为我的教学工作提供了很多素材，特别是使我对算法有着更深层次的理解。能够适时地把所研究的密码算法乃至信息领域最新的理论和实验成果介绍给学生，让他们明白学以致用的地方，激发他们学习专业知识的兴趣，培养崇尚科学的品质。

有了自己的科研方向及积累，结合学生已掌握的知识结构，就可以指导学生完成一些创新项目或参加一些全国或国际上的竞赛。例如，全国信息安全大赛、国际ACM大赛。这势必又能提高学生的学习兴趣，进而帮助自己的教学工作更全面的开展。

另外，老师在科研上的出色工作，必定帮助他在学生中树立更高的威信。反过来，老师的威信一定程度上能够促使学生认真学习。

2结束语

“算法设计与分析”是一门理论性与实践性兼顾的课程，是计算机科学技术中面向设计、处于核心地位的教育课程。笔者多年从事本科、研究生“算法设计与分析”课程的教学工作，在培养目标、学习兴趣、积极思考、教学方式、理论与实验、科研与教学等多方面，进行了有益的尝试，取得了一些积极的成效。今后还希望在网站资源、考核方式、培养兴趣小组等方面继续尝试和探讨。

参考文献:

[1]卢开澄,谭明术.计算机算法设计与分析[M].北京,中国铁道出版社,1998.

[2]刘波.“算法设计与分析”教学探讨[J].高等理科教育,2007(4):78-80.

[3]戴群.“算法设计与分析”本科课程教学研究[J].计算机教育,2009(18):70-72.

[4]张铭,耿国华,陈卫卫,胡学钢.数据结构与算法课程教学实施方案[J].中国大学教学,2011(3):56-60.

[5]魏青.《C语言》教学中学生学习兴趣的培养[J].电脑知识与技术,2010,6(21):5806-5807.

[6]杜丙新,秦国防.基于兴趣驱动的数据结构课程教学探索[J].电脑知识与技术,2011,7(21):5171-5172, 5174.