摘要：“算法设计与分析”是工程硕士研究生的一门核心课程，本文结合算法设计与分析课程的特点，对该课程的教学内容、教学方法与教学手段等三方面的改革做了一些有益的探讨。
关键词：算法设计；算法分析；教学方法
中图分类号：G642文献标识码：A
1引言
“算法设计与分析”是计算机专业高年级学生与研究生的重要专业课，同时还是一门与计算机有关的非计算机专业如管理信息、系统工程、应用数学与计算数学的专业课。本课程与前驱课程“离散数学”、“程序设计”、“计算方法”、“数据结构”等联系紧密，而且实践性很强，各种经典的算法思想如动态规划法、回溯法等，从一系列经典问题的解决方案中提炼出来后，再应用于实际问题的解决。但是我们在教学过程中发现，大部分学生把该课程看成单纯的理论课学习，对算法设计思想死记硬背，而不是灵活运用，不能对一种设计方法举一反三。这就要求教师思考如何把其与程序设计教学相结合，而不是将孤立的算法设计思想传授给学生。
2教学内容
工程硕士研究生的算法设计与分析主要目的是讲授计算机应用中常常遇到的系统软件或应用软件开发中的具有广泛工程背景的典型非数值计算问题的解法，讲授设计与分析各种算法的基本原理思想、方法与技术，重点阐述算法设计的典型方法，分析不同算法的时间和空间复杂度，建立计算机与应用问题之间的桥梁，从而使学生在选择或者设计算法时可以对其进行时空耗费分析，并使所设计的算法时空复杂性最优，进而为其编写出高效程序、开发出优秀软件系统奠定基础。通过本课程的学习，学生应基本掌握递归、分治法、动态规划、贪心算法、回溯法、分支限界法等经典算法的设计和分析方法，学习为解决应用中的非数值计算问题建立计算机解题模型的设计和分析算法的理论基础，并掌握对求解典型问题必要的算法设计技术和编程技巧。
计算机科学的特点决定了它的内容和手段始终处在不断革新和变化的过程中。根据工程硕士研究生大多有一定的工程经验，有一些工程需求。因此，本课程的授课内容除了讲授经典算法设计理论外，应结合教师科研实际，逐步引入并行算法、现代启发式搜索算法等先进内容，尽量反映本学科领域最新的学术和科技成果，使学生既能夯实基础，也能扩大眼界。另外，算法的应用领域很广，基本上只要有计算机的地方就会有算法。我们在教学过程中还介绍了计算机其他领域方面的算法，如数据压缩算法、并行算法、神经网络等等。虽然只能粗略的介绍其中很小的一部分，但是可以用很浅显的例子进行说明，让学生了解各个领域算法的大致思想，拓宽他们的专业知识面。
研究新动向融会进去，从而使学生可以用基本理论去解决遇到的新问题，增强学习兴趣，使其感到学有所用，也是如何在有限的教学时间内讲清基本理论知识，同时把本课程教学改革的关键所在。目前，计算机专业学生使用的“算法设计与分析”教材内容较多，而工程硕士研究生学时有限，这就要求我们在教学中力求做到抓住关键，突出重点，解决难点，我们要把主要时间花在讲解重要概念、基本设计思想和基本方法上，引导学生掌握课程内容的内在关联性，比较不同算法特点，举一反三，比如背包问题，在讲课中用图解法、递推法等多种方式，让学生由浅入深逐渐理解动态规划算法原理。在规定的课时内，既完成教学任务，也同时提高教学效果。在具体操作上，我们以一些基本算法设计技术内容为主线，以其基本设计思想的具体应用及分析为重点，讲清楚算法设计及分析问题。另外，为了激发学生的学习兴趣，密切关注计算机算法的业内发展，充分利用互联网信息资源，跟踪计算机科学的最新进展，将新知识信息融入教学之中。
3教学方法
教学方法从传统的“粉笔+黑板”模式为主过渡到“计算机+大屏幕”为主的授课模式。授课的电子教案开始时以静态文字为主的PowerPoint幻灯片方式提供，现在则在教案中穿插曲可动态演示算法的多媒体课件，在大屏幕上展示抽象算法的执行过程，辅之以板书交流，从而大大增加了从教师到学生传递的信息量和信息种类，有助于建立从感性到理性的深入理解及相关技术掌握运用。
(1) 启发式教学
抽象、理论、分析是计算机科学与技术学科的三种基本形态。在基础课的教学中应将上述三种基本形态贯穿于教学的始终，融合新概念将各分支学科的内在联系串联起来。在计算机专业课教学中针对不同教学内容采取多样化教学方式，以启发式教学为主，辅以其他教学方法。
启发式教学是从介绍典型应用问题入手，将计算机算法的构建过程展现出来，同时提出新的算法设计问题，以便让学生进行思考和研究。变单向传输式教学为双向互动式教学， 变以强调抽象算法设计为主的理论讲授为探究解决应用问题为主的设计引导式讲授。对一组相关的算法，分析、阐明不同算法的优、缺点，启发学生在能够解决问题的前提下探索新的设计思路，培养学生的创新思维，诱导学生深入思考，实现教与学的互动，激发学生的创造性，达到创新能力培养和提高教学效果的目的。为此，我们在课前应充分备课，一方面吃透算法设计与分析的基本理论知识，另一方面则要多了解其最新应用发展状况。另外，在讲课方式上，采取“系统讲解基本理论思想、反复强调重点难点、启发性讲解引申知识内容”的方式，启发并引导学生主动探索知识，既注意了基础的特点，同时又给学生提供了一个发散的思维空间。
(2) 理论联系实际
计算机科学非常强调理论联系实际，算法本身相对来说比较枯燥，特别是对于工程硕士研究生，他们更注重应用，如果能与实际应用联系起来，可以使学生学起来更有兴趣。在教学中，算法设计技术、算法分析技术、基本设计思想及其应用是我们教学的重点及难点，讲课过程中，我们要把基本算法设计方法的思想及应用结合起来讲授，由简单应用到解决复杂问题，使学生循序渐进接受算法基本思想，从而掌握所学知识及相应的思维方法。同时在此过程中，不失时机提出一些问题来引导学生积极思考。如贪心算法的思想很简单，也可以用于处理最优化问题，但是由于用此方法解决问题时优化测度要根据具体的问题自己选取，故用此方法设计算法时对于解决不同问题其具体实现方式也是不同的。以找硬币为例，希望找的硬币个数最少，如果硬币面值为：1分、5分和11分，要找给顾客为15分，对贪心算法而言，则需要1枚11分，4枚1分，共用5枚硬币；而用动态规划法求解，得出只用3枚5分硬币就可以了。从这个小例子可以看出，贪心算法虽然好用，但对于有些问题采用贪心算法不一定能得到最优解。为了让学生对算法设计有较完整的认识，我们引导学生思考对于同一问题时，选择不同算法会有什么样的结果，如调度问题、0/1背包问题、城市交通问题、场地租用问题等等。算法课不再是纸上谈兵，而是实际中的运用，这种教学方式让学生带着问题学习，可以提高他们学习的兴趣，更重要的是可以培养他们发现问题、分析问题及解决问题的意识和能力，通过对不同的学生提出不同难度级别的问题，配合给出不同级别的提示来调动不同学生的主动性。
(3) 强化讨论教学环节
针对理论课教学中一些尚未理解透彻、容易出错的问题，在教学中进行分析讨论。选题要有代表性，不选难题繁题，但是要有讨论引申之内容。通过一题多解和分析，加深学生对基本理论知识的理解而起到举一反三、触类旁通的作用，有助于学生结合实际进行具体应用。讨论问题的同时，学生又会提出新问题，从而在讨论问题、解决问题的过程中，使学生独立思考能力得到培养和锻炼。在讲授递归方程解法时，以汉诺塔问题的递归方程为例，可以采用三种解法中任一个求解。同时可以联系时间复杂性分析其时间耗费，从而引导学生思考三种求解方法各自的适用范围及其优缺点。
4教学手段
将传统教学方法与现代化教学手段相结合，也是我们教学改革的举措之一。为了在有限的教学时间内，增加单位时间的信息含量，将有限精力与时间用于剖析课程内容的重点难点。把抽象难于理解的内容直观形象地展现。在该课程教学中，引入多媒体教学手段，制作课件，开展计算机辅助教学。计算机辅助教学的特点是将算法设计中较抽象的设计思想以动画形式演示出来，既可以节省教师在课堂上的板书时间，也可以将算法设计的一系列步骤直观展示在学生面前。如利用贪心法解决单源的最短路径问题时，利用课件可以让学生更清楚了解求解指定顶点到其他顶点最短路径的过程以及最终求解结果，更好掌握贪心算法的设计思想。课堂教学充分采用多媒体教学手段，使学生学得直观、学得轻松、学得活跃，并提高课时利用率，增加课堂信息量，可以更好地发挥学生的能动性，从而提高学生学习兴趣。
另外，我们开设“算法设计与分析”课程网站，在网站上配套电子教案、作业及其他课程资源，也是将传统教学方法与现代化教学手段相结合的举措之一。此外，可以把讲课内容制作成电子课件在校园网上发布，对工程硕士研究生有时可能因为工作原因不能到学校上课，或者学生没听懂，可以上网察看，方便学生自学、复习。
此外，我们也改进了考核方式，将传统、单一的闭卷考核方式，改变为对平时课堂学习、课外设计(课外作业)、
期末算法设计与分析笔试与交报告等多环节考核相结合的考核方式，逐渐加大对算法设计和程序开发能力的考核力度，激发学生自主学习、自主训练的兴趣和热情，避免产生“高分低能”的现象。
参考文献：
[1] 王晓东. 算法设计与分析[M]. 北京:清华大学出版社,2003.
[2] 苏德富. 计算机算法设计与分析[M]. 北京:电子工业出版社,2000.
[3] 陈国良. 并行算法实践[M]. 北京:高等教育出版社,2002.
[4] 陈莉. 计算机专业基础课教学改革探索[J]. 高等理科教育,2004,(2):51-55．
First Step towards the Teaching Reform of Algorithm Design and Analysis
ZHENG Hong, SHAO Zhi-qing, FU Hai-bo
(College of Information Science and Engineering, East China University of Science and Technology, Shanghai 200237)
Abstract: Algorithm design and analysis course is a core course for engineering graduate students．This paper integrate with algorithm design and analysis course"s characteristics，make beneficial discuss in the Reform of teaching method, teaching content and teaching instrument．
Key words: Algorithm Design, Algorithm Analysis, Teaching Reform