《算法设计与分析》的实践方法探索*

摘要：《算法设计与分析》是计算机科学与技术的专业课程，同时又是对《数据结构》、《离散数学》等课程的综合应用，是实践性较强的一门课程。现实中解决问题，需要经历分析问题、设计问题、实施问题和验证问题等几个过程。本文从教学方法、思路引导、问题剖析和对比、实现辅助和结果验证等方面，对《算法设计与分析》课程教学实践过程进行初步探索。

关键词：算法设计与分析；解题报告；实践教学

中图分类号：G642.0文献标识码：A文章编号：1671-0568（2010）35－0087－02

《算法设计与分析》是计算机科学的核心问题之一，也是计算机科学与技术专业本科及研究生的一门重要的专业基础课，是计算机软件开发人员的必修课。软件的效率和稳定性取决于软件中所采用的算法。对于一般程序员和计算机专业学生，学习算法设计与分析课程，可以开阔编程思路，有助于编写出高效程序，能较好地培养学生分析问题、解决问题和验证结果的方法。课程需要使用离散数学、面向对象程序设计、数据结构等先修课程的基础知识。本文结合《算法设计与分析》课程的实践，从教学方法、思路引导、问题剖析和对比、实现辅助和结果验证等方面，对教学实践过程进行初步探索。

一、实践教学改革的必要性

《算法设计与分析》课程的主要目的是讲授计算机应用中常常遇到的实际问题的解法，讲授设计与分析各种算法的基本原理、思想、方法与技术，从而使学生在选择或者设计算法时可以对其进行时空耗费分析，使算法的时空复杂性最优，进而为其编写出高效程序、开发出优秀软件系统奠定基础。[1]对该课程，如果仅通过被动听课，而不动手、不实践，会对问题解决思路和方法的理解有一定的困难，同时很难将已学课程的知识融会贯通，用来解决实际问题。久而久之，容易使学生对基础知识的应用感到模糊和困惑，不能很好地理解基础知识的重要性。

将课程理论与实践相结合，使学生通过本课程的学习，能够在实践操作中理解和巩固理论知识，调动主观能动性，培养学生的分析和解决问题能力，促进他们理解知识并应用于实际，从而提高综合素质。

二、改革内容

《算法设计与分析》课程在教学过程中往往会产生对目标问题的解决方案的讲解，基本上是分析其中的解决思路，给出基本的伪代码或者源代码，验证其正确性。整个讲解过程以教师为主，学生纯粹跟随教师的思路，学生缺乏学习过程中的主观能动性，很难提出自己的创意和思路。不能很好地引导学生分析问题、解决问题和验证问题，从而限制了他们的学习兴趣性，也不能很好地提高其综合能力。

笔者根据该课程的教学大纲以及教学内容，从教学方法、思路引导、问题剖析和对比、实现辅助和结果验证等方面进行教学方法改革，并收到良好效果，使学生能从宏观上把握所学问题解决的类型，以及各个类型解决的一般过程。对具体问题，则以提示、引导的方式来积极探讨解题思路，并在确定解题思路后，对具体问题以及相应的类型进行问题剖析，对相近问题对比其异同性。在实现过程中，由易到难，逐步分析，必要时提供解题框架，也可以通过填空和选择的方式辅助其完成编码实现。在结果验证方面，提供普通、边界和压力性能测试用例，确保问题的完整性和可靠性。

三、实施方法

1.改革教学方法，对问题进行分类

可将问题根据解题的方法不同分为递归与分治算法、动态规划算法、贪心算法、宽度和深度搜索法和分支限界法五个专题，对每个专题总结一些普适的方法和解题的过程，利用具体实例阐述各个专题的解题过程。对拟解决的题目，督促学生制作成解题报告，在课堂上，针对有创新性和特色的解题报告，进行讲解、分析和讨论，促进学生的交流，增强他们的自信心。

解题报告主要涵盖如下内容：

▲问题题目和问题描述；

▲问题分析，需要指出属于哪一类型题目，需要注意什么；

▲解题流程图，需要指出包和包、类和类、函数和函数之间的关系和作用；

▲实现代码，对关键代码和思路进行必要的说明；

▲测试用例，需要指出哪些用例是针对一般情况用例，哪些是分支边界测试用例，哪些是时间和空间的压力测试用例；

▲验证结果，分析结果的是否符合要求，该算法中是否还有可以改进和提高的可能，是否存在其它的方法。

2.思路引导

针对具体问题的解题思路，采用启发式、引导式、讨论式等先进的教学方法，让学生积极参与问题讨论，教师参与其中，仅进行必要的提示和引导，进而激发学生思考问题、学习计算机语言和方法的主动性。教师设计若干个主要讲授的问题和提示，按照“提出问题、分析问题和得出结论”的讲授层次，形成一环扣一环的讲授主线。要在提出问题的教学设计上下功夫，引人入胜，激发学生思考，引导他们的思路，产生互动效果。[2]

3.问题剖析和对比

问题剖析，主要通过问题的分析，提示问题中的注意点，让学生思考拟采用的解决方法，给出理由和解题的基本过程。要提示是否还有其它方法，分析这些方法的优缺点。比如Hanno塔问题，可以有递归和迭代方式；如单源点最短路径有宽度和深度搜索等。对于一些经典的算法，比如0～1、背包问题和旅行商售货问题，可以采用动画教学的方式，将问题的解决方法编写成分段代码，模拟运行展示给学生，通过直观的动画演示方式，使学生轻松地理解和接受算法思想。[3]

4.实现辅助

在上机实践课中，根据学生的层次和对计算机语言掌握的程度不同，定制不同的评分标准和不同的辅助策略。针对基础较好、实践能力较强的学生，在其已经清晰思路后，就可放手让其编写程序；针对问题框架不是很清晰、但对计算机语言有一定掌握的学生，可以给其制定基本的实现框架，让其在框架内完成实现；针对基础较差、语言掌握程度有限的学生，可以将基本的实现交给他们，让其实现某些关键函数。或者以填空和选择的方式完成程序，然后让他们对每个部分进行必要的单体测试和集成测试，最终完成所有代码。

5.结果验证

通过和学生讨论确定测试用例（case）和存根（stub），要求给出40%的一般用例，30%的分支边界用例，30%的压力和性能用例，通过完善的用例来验证算法的正确性和性能。

《算法设计与分析》课程教学过程中的改革实践，从多个方面加强了本课程的建设，探索出一种新的教学模式和教学思路。课堂采用“分析+讨论+实现+验证”的授课方法进行讲授，在突出在传授理论知识的同时，更强调实际技能和综合应用能力的培养，使学生通过本课程的学习，能够在实践中理解和丰富理论知识，调动主观能动性，培养分析、理解和实践能力，促进他们理解知识并应用于实际，从而提高学生综合解决问题的能力。

参考文献：

[1]肖小克,陈莉.《算法设计与分析》实践教学探讨[J].福建电脑,2009,(10).

[2]顿毅杰.CDIO模式下《算法设计与分析》课程教学方法探析[J].职业时空,2010,(3).

[3]夏梦.《算法设计与分析》的教学方法研究[J].科技教育,2009,(18).

[4]M.H.AlsuwAIyel.算法设计技巧与分析[M].北京:清华大学出版社,2004.

[5]王晓东.计算机算法设计与分析(第三版)[M].北京:电子工业出版社,2007.

推荐访问： 算法 探索 实践 方法 分析

---