“算法设计与分析”教学模式探讨

徐晓华 何 萍 陈 崚 胡孔法

摘要:本文提出在教学过程中采用结合学习兴趣、当堂练习、因材施教和多维教学的四位一体的教学模式,提高“算法设计与分析”课程的教学质量,并对其考核方式提出了建议。

关键词:算法设计与分析;计算机专业;教学

中图分类号:G642 文献标识码:A

1引言

“算法设计与分析”是计算机科学与技术专业的一门核心高阶课程。在学习该课程之前,学生们已经掌握了基本的数据结构知识,能熟练运用一门或多门编程语言,并具备了一定的编程经验。但是如何利用这些已学过的知识,对不同的实际问题设计出有效的算法,就是本门课程所要达到的教学目标。

笔者在“算法设计与分析”教学中,不断探索和总结教学经验,在教学过程中采用学习兴趣、当堂练习、因材施教和多维教学四位一体的教学模式,从而有利于学生对教学内容的吸收和掌握,取得了良好的教学效果。

2四位一体的教学模式

“算法设计与分析”作为一门理论与实践紧密结合的课程,要让学生把两方面都学好具有一定的难度。在教学过程中,教师应该从学习兴趣、当堂练习、因材施教和多维教学四个方面将教学模式有机地协调为一个整体,使学生在享受学习的过程中提高自己的算法设计和分析能力。

2.1引导学生的学习兴趣,激发学习主动性

如果学生对一门课程完全没有兴趣,无论教师把教案备得如何深入浅出,学生也对之置若罔闻。反之,如果学生对算法或程序设计感兴趣,即使没有老师教他,也不代表他不能自学成才。因此作为一名负责任的任课教师,首当其冲要做好的工作就是培养学生对本门课程的兴趣。

“算法设计与分析”,顾名思义分为算法设计与算法分析两大部分,但实际上,教师在教学时常常主要偏重于算法设计这一方面,而对算法分析轻描淡写、一笔带过。原因很简单,因为算法分析涉及算法复杂性理论、艰涩难懂,当前大多数不喜欢数学的学生对此完全没有兴趣、也接受不了。但是这些理论是涉及算法设计和算法评价的根本因素,作为教师必须要向学生传达算法复杂性理论的重要性。对此,我们可以在介绍理论的过程中穿插一些大师的生平故事甚至传闻轶事,降低学生对枯燥理论的反感程度。例如,我们可以结合算法复杂度理论,讲算法设计大师Donald E. Knuth的求学经历,所著著作TAOCP以及对TeX的贡献等。借由学生对伟大人物的欣赏和崇拜之情,激发他们对所教内容的学习热情。

相比之下,“算法设计与分析”的另一方面——实践,对于培养学生兴趣则要容易得多,有时甚至无需培养。因为学生在自己动手做实验的同时,本身就有莫大的成就感来促成其学习兴趣的产生。但是,我们还是要采取适当的手段来帮助那些连上机也不愿意的学生产生学习兴趣。其中,最简单的方法就是把漂亮的吸引人的程序设计成果,尤其是时下流行的实际应用演示给学生们看。例如,我们在讲动态规划的时候,可以在NCBI网站上,演示如何用Blast程序从庞大的数据库中快速地搜索出与给定基因序列相似的所有序列;或者在讲最短路径地时候,先演示一下如何在Google Maps中计算从源点到目的地的最短路径。此外,考虑到现在的学生好胜心较强,我们还可以配套开设ACM程序设计实验课,让学生把已学的算法知识用于挑战解决一些具有一定难度的ACM题目,从而起到加强锻炼学生的编程能力和提高学生的学习热情的目的。例如,北京大学的ACM/ICPC Judge Online就是一个很好的ACM在线题库,教师可以鼓励或组织学生在线练习、提交程序,系统则会自动判断程序是否正确。

在讲解具体的算法设计方法时,教师还应注意教学内容的及时更新,并有意识地培养学生对算法思想的应用能力。所谓教学内容的更新,是指不能总是停留在对经典算法的讲解层面上,而是要结合当前涌现的一些新算法(比如Blast,PageRank等算法),让学生深刻地感受到这些设计方法是具有普适性,是所有算法(无论是新的还是老的)的灵魂,而不仅仅限于那些老生常谈的经典算法。例如,在讲二分查找算法时,教师就可以用2006年Joshua Bloch发现大量的二分查找的实现中都有bug的实例,来让学生们了解算法的发展同样也是与时俱进的。而所谓培养学生对算法思想的应用能力,是指要锻炼学生有运用旧方法来解决新问题的灵活应变能力,而不仅仅是就事论事,这需要大量的练习来完成这一目标。教师也可以参考Ron Shamir的“分子生物学中的算法”这一课程,适当地讲解一些将算法的基本设计方法应用到实际生物信息学的例子,让学生有感性的认识。

教师通过培养学生兴趣和提高他们对算法的感性认识来提高教学质量,与公司通过产品推介来吸引买家,本质上是相通的。学生对课程产生了自主学习的兴趣,那么教学工作的开展就会事半功倍,就好比用户本身对公司的产品产生了购买欲望,那么销售工作的开展自然也是顺水推舟。

2.2通过当堂练习,及时反映存在问题

“算法设计与分析”这门课程不但包括对学生理论知识的灌输,而且还包括对学生的算法实现能力的培养。因为对于学生而言,理解是一回事,实现是另一回事。理解的只是一个大概、一个总貌,而实现却需要考虑方方面面、各个细节。只有当学生能够熟练地把算法在计算机上编写出来、运行无误,才能说他是真正理解了,而不仅仅是纸上谈兵。然而目前由于教学时间的限制,教师大多把上机练习安排为学生自己练习理论课上的内容或者是课后作业。在实践中,我们发现花适量的时间让学生做一定的课上练习,是非常必要也是非常重要的,原因主要有二:

(1) 真实反映学生掌握情况。与课后练习相比,当堂练习更能够真实地反映学生对测试内容的掌握情况和熟悉程度。因为在课后作业中,经常出现一些偷懒的学生通过抄袭来完成自己的作业现象,如果教师单以课后作业的完成情况来判断学生对知识的掌握程度,得到的结果可能会过于乐观。而当堂练习则可较好地弥补这一缺陷,教师通过在课上当场布置一个或多个作业,让学生们写在纸上很快地交上来,基于这种作业完成情况的评价会更加真实反映学生究竟在哪些方面存在着共同的问题或个别的问题,然后教师可逐个针对解决。

(2) 凸显差距,激发竞争氛围。在当堂练习过程中,教师可以挑选一个或两个优秀的学生在黑板上来做练习题。当前的大学生有着强烈的表现欲望,渴望得到别人的关注,教师可以利用大学生的这一心理特点,在课上有意地营造适当的竞争气氛、调动学生的积极性。与此同时,通过学生在黑板上做演示,也能让一些后进的同学真实地感受到自己和别人的差距,在好胜心理的驱使下,有可能会成为其奋起直追的学习动力。

考虑到课堂时间有限的因素,教师在事先设计当堂练习的时候,应注意将练习的难度设置为比一般课后作业的难度相对稍低一些,例如以填空方式或者只要求写算法思想等等。

2.3设计递进式难度课后习题,因材施教

尽管“算法设计与分析”这门课程是针对已经接受了三年或更多计算机专业教育的学生所开设的,我们仍然不能忽视学生之间还是存在着一定的基本功或能力参差不齐的状况。因此,我们建议教师在设计课后习题时,应根据学生能力的不同,将作业的完成要求相应地划分成若干个由易入难的不同等级。例如,有的学生本身对以前学过的课程就一知半解,那么教师就应将习题的最低难度设为能够重新掌握以前的基础知识;相反地,同时也有些学生早已超前学过了很多算法知识、具有很强编程能力,那么此时,教师就应该将习题难度的上限设置得更具挑战性一点,防止优秀学生因自满而止步不前。

设计这种进阶式的训练,有利于帮助学生认清自己当前的能力水平,了解与其他同学的差距,从而更好地制定自己的阶段性学习计划。教师在布置这些进阶训练以及讲解的过程中,则宜采取表扬先进、鼓励后进的方式来调动学生积极性,形成良好的互动。

2.4灵活使用多种教学手段

传统教学方法的好处在于条理清楚、思路清晰,学生在教师写板书的同时可以进行思考并比较结果是否正确。而现代的多媒体教学方法的好处则在于节约时间,借助于一目了然的图形化演示使一些课程难点更容易为学生所理解,而且课件可以让学生在课后继续学习。我们在“算法设计与分析”这门课程中,采取了将传统教学方法与现代教学方法相结合的手段:将前者用于对课程节奏的把握和算法基本思想的阐述,而将后者用于对算法基本过程的演示和相应例子的评讲。例如,在讲解算法的分而治之这一章,教师可以用传统教学方法将其基本思想写(或画)在黑板上,以供学生随时参考;与此同时,也采用多媒体教学方式来逐步演示分而治之算法在归并排序上的应用。此外,网上有很多现成的在线教学资源也可以为教师所充分利用。例如在讲解贪婪法时,教师可以直接用网上现成的applet程序,为学生演示Dijkstra算法如何计算从源点到其它各顶点的最短距离。

3科学合理的考核方式

目前对“算法设计与分析”课程的考核方式主要是由平时考核和期末考核两部分组成,期末考核基本上采取单一的理论考试形式。我们认为,教师们可以考虑将该课程的期末考试分成两部分来考核,一部分是理论考试,另一部分则是上机考试。其中理论考试侧重于对算法理论和算法思想的考核,而上机考试则侧重于对编程能力的考核。例如,上机考试可采用像ACM程序设计比赛一样的规则,要求学生在规定时间内尽可能多地完成指定的测试题目,或直接用北大的在线提交系统进行评分。这样一方面兼顾了不同学生的不同特长——即有的学生数学推理能力强,但有的学生却动手能力强,另一方面也间接鼓励了学生平时要多动手编程,更深刻地理解算法思想,而不仅仅是死记硬背。

4结束语

“算法设计与分析”课程是一门非常重要的计算机专业课程,具有理论和实践并重的特点,如何利用学生已有的知识和经验,使其快速掌握一些经典算法的设计思想,进而能够动手实践解决一些编程问题,是我们在教学中关注的重点。教师只有在教学过程中不停地总结教学经验,坚持不懈地学习新的知识,深刻掌握“算法设计与分析”的核心思想,提高自身能力,才能让学生学到真正收益终身的算法设计思想和方法。

参考文献:

[1]Amy N. Langville, Carl D. Meyer. Google's PageRank and Beyond: The Science of Search Engine Rankings[M]. Princeton University Press, 2006.

[2]Donald Ervin Knuth. The Art of Computer Programming[M]. Addison-Wesley,1997.

[3]Donald Ervin Knuth. The TeXbook[M]. Addison-Wesley,1986.

Discussion on The Teaching Mode of “Algorithm Design and Analysis”

XU Xiao-hua, HE Ping, CHEN Ling, HU Kong-fa

(Department of Computer Science, Yangzhou University, Yangzhou 225009, China)

Abstract: This paper proposes a four-in-one teaching mode, which integrates inspiring students learning interest, quizzing on class, teaching according to the student's ability and combining different teaching tools to improve the quality of teaching “Algorithm design and analysis” course. Besides, some useful suggestions on the form of examination are also provided.

Key words: algorithm design and analysis; computer science, teaching