本科算法课程建设的一些实践与思考

2009-06-15韩军许可

计算机教育 2009年7期

关键词：课程建设算法实践

韩　军　许　可

文章编号：1672-5913(2009)07-0064-04

摘要：本文介绍了北京航空航天大学计算机学院本科算法课程建设的现状，分析了目前教学中存在的问题，总结了教学方法上的实践经验，并对算法课程的建设提出了一些思考。

关键词：算法；课程建设；实践

中图分类号：G642

文献标识码：B

1算法课程建设的现状

1.1课程的定位

《算法与数据结构(2)》主要讲述基本的算法设计方法以及对算法的时间、空间和其他方面进行度量分析。

算法，是程序设计的灵魂。著名的PASCAL之父、结构化程序设计的首创者、1984年“图灵奖”获得者尼克劳斯·沃斯曾说过：“数据结构+算法=程序”。这一公式在结构化程序设计已相当成熟的今天仍被视为经典。由此可见，算法在计算机科学中具有不可替代的重要地位。

据统计，美国2007年综合排名前50位的大学，欧洲名校如牛津、剑桥等均开设了算法课作为计算机专业的必修课。不仅如此，美国、欧洲一些普通高校的计算机专业也均开设了算法课。中国国家211工程重点建设的100所高等院校中有多于半数院校的计算机专业开设了算法课，国内的一流高校也将算法设计与分析作为计算机专业本科生培养的重要环节。

算法课程是高等学校计算机专业重要的专业基础课程之一，是计算机程序设计的重要理论和实践基础，是目前国内计算机专业研究生招生考试的首选专业基础课程，其独特的应用价值也使其成为信息类专业的重要课程之一。

算法课的先导课为离散数学、程序设计语言基础和数据结构。

1.2课程的目标

开设算法课的目标在于使学生通过该课程的学习，能够运用课程所讲授的概念和方法更好地进行算法设计，能够对已有的算法和新设计的算法进行一般的效能和性能上的分析，并进一步提高程序设计的能力。学好该课程的主要目的是打好专业基础，提高计算机理论和应用水平。

因此，我们要求学生能够掌握各种基本的算法设计方法(包括归结法、分而治之法、贪心法、动态规划和概率法等)，并能够掌握基本的算法分析方法(算法的时间复杂度与空间复杂度分析)，并在学习已有知识的基础上，加强思考和实践。

1.3课程的主要讲授内容

根据北航学生的实际情况，算法课程目前分为18学时，以课堂讲授为主，辅以参考资料阅读以及每章的课后作业和练习题。授课内容分为七章，分别为：算法分析的基础知识、归结法和分而治之法、贪心算法、动态规划算法、概率算法、下界分析和求解NP完全问题的算法设计。重点讲授内容包括：算法的控制结构、算法的复杂性分析、归结法和分而治之法、贪心算法的基本思想及特点、设计动态规划算法需要具有的前提及一般设计思路、主要的下界计算方法、回溯法和局部搜索算法等。

1.4课程的授课效果

通过课堂上学生的听课情况、对问题的反应程度以及对小测验的完成情况，我们可以看出部分学生对该课的兴趣和重视程度较高、预习工作做得较好，能将老师当堂所讲的内容消化和掌握；大多数学生能够在课堂上对老师所讲解的内容加以理解，并能在课后加以复习并掌握；一些学生尽管没有在课堂上对内容理解和消化，但仍能通过下课向老师提问或课后发Email给老师的方式向老师询问未理解的问题来加以反馈。

从课后作业的完成质量以及期末考试的卷面成绩来看，绝大多数学生能在学完算法课之后对计算机算法有一定的理解，并具备一定的算法设计与分析能力，达到该课程的基本要求，甚至有一些学生就此对算法产生了较浓厚的兴趣，并能在以后的学习时间里继续深入学习算法。课程达到了较好的授课效果。

1.5教学过程中发现的问题

在教学过程中，学生普遍暴露出不愿深入思考、不爱动手实践的问题。尽管这些原则在平时的授课过程中再三地被强调，但能按照老师建议去做的人并不多，仅限于少数对算法有较大兴趣的学生。

从试卷情况来看，一些同学仍然缺乏将算法思想应用于同类问题求解中的能力，出现了同类问题不知道用同类算法求解的情况。究其原因在于未能将算法思想深入理解，做过的习题较少，对于同类问题无从下手。为应付考试而死记硬背某些算法，这是学习算法的大忌。

另外，部分学生对先导知识的掌握还有欠扎实，对基础知识和概念的掌握程度成了一些算法内容理解的瓶颈。

2教学方法上的一些实践经验

2.1提高学生学习基础课程的兴趣

从一定角度讲，兴趣是最好的老师，因此我们在讲述课程的过程中会经常从学生们感兴趣的问题入手，为他们创造易于理解问题、加深记忆的活跃的课堂气氛和环境。

我们在介绍一个算法问题时，首先介绍问题的背景，如河内塔游戏、斐波那契数列等。在教学过程中，我们将本课程学科的发展历史、前沿知识和自己从事科研实践的体会与成果贯穿于教学中，例如蒙特卡洛概率算法与SAT问题等均是两位授课教师曾深入研究过的算法和问题。另外，我们还结合课程内容介绍了Google和Microsoft等知名IT公司的面试题目，激发学生对算法的兴趣，令学生积极思考并展开讨论。

算法本身的概念与理论是抽象的，但具体问题又是实际的、易懂的、有趣的。在教学过程中，只有通过具体问题，引申出求解该问题的有效算法，同时有效借助多媒体教学灵活而快捷的特点，将抽象的算法具体化讲解，才能提高学生学习基础课程的兴趣。在每个问题的讲解过程中，我们尽量采用图文并茂的方式，将问题刻画得清楚明了，实践证明，该方法取得了较好的效果。

2.2培养学生提出问题、分析问题和解决问题的能力

在教学中，采用启发和探索式的教学方法，注重培养学生提出问题、分析问题和解决问题的能力。在教学中，我们本着一系列连贯的思路讲授学习内容，例如：当初某个算法问题是怎样提出来的；求解该问题的方法和策略是如何形成的；如何应用这些方法和策略来解决实际问题；对这些方法和策略做进一步的比较、分析和评价。

2.3增强与学生的交流

轻松活跃的课堂气氛是激发学生听课兴趣，进而达到良好听课效果的重要保证。在教学过程中，我们本着以学生为中心的原则，注重与学生的交流。通常一个问题、一个提示会达到良好的授课效果，实践证明，这种方式是有效的。

为了对学生的基础知识掌握情况有全面的了解，我们会以调查问卷的方式获取每个学生的学习情况信息，通过一些简单易答的算法题，帮助学生巩固基础知识，使听课效果更佳。事实证明，通过调查问卷的开放性问题，我们了解了同学们大致的想法和对算法课的建议。另外，我们还鼓励学生课后通过Email等手段与老师展开交流，并听取学生的反馈意见，选取一些有代表性的问题在下一次课堂上讲述。

2.4注重平时的考核方式

算法课程的特点是逻辑思维性强。因此，必须通过典型例子强化一般性问题。同时，为避免同学中大量存在的“平时不学习，考试搞突击”现象的发生，我们注重对学生平时的考核，并主要采取课后作业的方式。为加强学生的动手实践能力，我们要求学生用某一种语言(C、C++、Java、Delphi等)对作业问题进行实现。通过适当调整课后作业在期末总成绩中的比重，督促鼓励同学自己动手进行编程实践，进而有效地指导基础理论知识的学习。从学生提交的课后作业程序来看，绝大多数同学理解了求解问题所使用的算法基本原理。

3算法课程建设的一些思考

3.1如何进一步提高学生学习算法的积极性

在教学过程中，我们本着培养学生学习算法兴趣的原则，在授课过程中采用引导和鼓励等方式，提高学生学习算法的积极性，并取得了较好的效果。

为了进一步提高学生学习算法的积极性，我们拟建设一个算法课程网站，并逐步向网站中添加在线求解问题(类似目前国内多所大学的ACM网站)和算法讨论区等诸多板块，加强与同学的交流。鼓励同学利用课余时间参加在线答题和算法讨论。

通过平时与学生的交流我们发现，学生更愿意将理论知识实际化，在现实生活中寻找所学知识的应用。例如，在一次与学生的交流中，我们谈到在商场购物打折优惠卷的优化使用问题，之后一位学生便自己编写了一个针对商场搞优惠活动时不同折扣、返卷及优惠卷使用规则的购物优化算法程序，并在某商场进行了现场的咨询服务。这种勤于思考和实践的表现受到了教师的表扬和鼓励，毫无疑问，这种学以致用的学习方式是非常有益的。

3.2是否需要介绍模拟退火和遗传算法等启发式算法

在以往的教学中，我们主要为学生讲述求解问题的精确算法，如贪心策略、动态规划等。但随着当前算法理论的深入研究，众多学者越来越关注和研究难问题及启发式算法。因此，为了鼓励和启发学生深入学习算法，我们正在考虑是否在以后的授课中加入对模拟退火和遗传算法等启发式算法的介绍，为学生以后对算法的深入研究起到抛砖引玉的作用。

3.3如何培养学生的研究能力

我们认为，北航的学生与国内其他一流高校的计算机专业学生相比，普遍动手能力强，但具有研究能力的拔尖学生少，去国外一流高校深造和顶尖研究单位工作的学生则更少。如何培养学生的研究能力，是我们目前面临的问题之一。我们认为，培养学生的研究兴趣，激发学生的研究热情，为学生营造良好的学术研究氛围，鼓励学生参加竞赛，与国际接轨，是培养研究型人才的重要手段。因此，在教学工作中，我们试图采取有力有效的方法带动学生参与学术研究和项目工作，如：

●在教学中布置一些研究性的题目并介绍相关的背景知识(如SAT问题的求解算法)；

●将学生分成若干小组，每组有一个负责人，要求学生利用互联网等手段去查找相关资料，以培养发现信息和处理信息的能力；

●鼓励学生提出自己的求解算法进行计算实验分析，最后撰写技术报告，并进行组内排名，从中挑一些优秀的算法参加国际算法竞赛。

3.4如何将教学与目前算法研究的发展相结合

近些年，算法的研究发展呈现了一些新特点，不完全算法的发展很快。国际算法竞赛的兴起亦对中国大学计算机专业的大学生产生了较深的影响。为了将教学与目前算法研究的发展相结合，除了在加强教师自身科研工作的同时，我们也在试着寻找当前科研工作在教学内容中的切入点。让学生在学习基础内容的同时，通过听取教师的切身体会和指导，把握学术研究的动态。

4结论

本文总结了北航计算机学院本科算法课程建设的现状和存在的问题，介绍了激发学生的学习兴趣和注重学生的能力培养等方面的一点经验，提出了在增加授课内容、培养研究型人才和进一步提高学生学习的积极性等方面的一些思考，并强调了将教学与目前算法研究的发展相结合的重要性，而未来我院本科算法课程的建设也请各位老师提出宝贵意见。

参考文献：

[1] Top 100 Universities:Top 100 Colleges and Universities[N/OL]. http://www.ulinks.com.

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

[3] Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein. Introduction to Algorithms (Second Edition). 北京:高等教育出版社,2002.

[4] 陈国龙,王晓东,傅清祥. “算法与数据结构”课程教学改革和实践[J]. 高等理科教育,2003,(03).

[5] 殷人昆,邓俊辉. 清华大学“数据结构”精品课程建设[J]. 计算机教育,2006,(05).

[6] 廖明宏,张岩,李秀坤,李治军. 哈尔滨工业大学“数据结构与算法” 精品课程介绍[J]. 计算机教育,2006,(05).

[7] 王绵森. 以现代教育理念为指导,加强精品课程建设——建设精品课程的几点体会[J]. 中国大学教学,2006,(05).

[8] 杨圣洪. 编程训练与课程学习的相互渗透[J]. 计算机教育,2006,(10).

[9] 吴英杰,王一蕾,王晓东. 面向问题求解的实践教学模式——“算法与数据结构”实践教学改革[J]. 计算机教育,2007,(07).

[10] 姜浩. 数据结构教学过程中应重视算法设计与分析能力的培养[J]. 计算机教育,2007,(16).

[11] 李军利,卜晓燕. 精品课程与精品课程网站的建设[J]. 教育与职业,2007,(14).