“算法设计与分析”本科课程教学研究

戴 群

摘要:“算法设计与分析”不仅是计算机科学与技术学科的核心课程之一,也被很多高校的电子信息及数学等专业列为专业必修课程。本文从教材选择、兴趣培养、理论教学、科研方法及实践能力培养等方面探讨有效教学的方法,旨在提高教学质量。

关键词:算法设计与分析;教学研究;教学质量

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

1引言

“算法设计与分析”是计算机科学与技术学科的核心课程之一,受到越来越多的重视。对于一个计算机专业的学生,学好算法课是必要且是必须的。“算法设计与分析”这门课程的主要目的不仅是讲授计算领域中不同问题的标准算法,更重要的是分析其算法复杂度,并且在诸多可行算法中选择一种时间或者空间效率最高的方法。美国著名算法大师Donld Knuth认为“计算机科学就是算法的研究”,他主持设计的TeX排版系统被誉为是“不存在Bug的系统”,这是以大师严密的算法设计基础为保证的。前微软高级副总裁李开复博士认为“计算机科学实质是人工智能”,而人工智能则是模拟人类思维的一种算法科学。计算机算法的应用已经遍及人类社会的各个领域,包括计算机软硬件机器学习、电信及互联网、一般制造业、经济与金融业等。算法技术不仅在计算机领域,而且在其它理工及社会科学领域都有极其广泛的应用。任何问题的求解,都离不开一般性的算法设计原则,在笔者执教的学校,数学和信息安全两个非计算机专业已将该课程列为必修课程。因此,提高“算法设计与分析”课程教学水平有着极其深远的意义和重要的作用。

2教材选择

近年来,国内引进了一些优秀的国外教材,其中的《算法导论》是国际上被引用频率最高而且知名度也最高的专著,但是由于它篇幅过长,在国外多用于两个学期的教学课程,因此难以将该教材系统地用于学时有限的本科教学;《算法设计与分析》是美国工程院院士UIIman等三位大师合著的优秀教材,该书的目的是将算法领域的基础研究结果进行综合,重点在于对算法思想过程的理解,而不是算法的实现细节和具体的编程技巧。但是该书内容和习题难度都较大,因此更适合作为研究生教材。国内的专家王晓东和周培德所编写的教材也很优秀。这些教材都被我们重点推荐给学生作为参考书。

出于上述考虑,我们最终选择了沙特学者M.H.Alsuwaiyel所著的《算法设计技巧与分析》作为教材,该书基本覆盖了传统算法设计的主要内容,此外还包含了概率算法和近似算法等一些基本内容,这些内容在传统教材中并不多见,是一些高端算法经常使用的方法。虽然该书不是欧美传统名校教材,但作者在南加州大学攻读获得硕士和博士学位,因此该书吸收了欧美优秀教材的风格,且文笔简洁流畅。该书的内容及习题难度适中,便于课堂教学及自学,是一本适合本科教学的好书。

如果一个本科生能够学好本教材,并在后面的硕士阶段,学好UIIman的《算法设计与分析》,之后再将《算法导论》学习好,则必将打下坚实的算法理论基础,为终身的职业生涯所受用。

3兴趣培养

本课程的教学对象是大学理工科三年级学生,要求他们不仅具备数学分析、概率及线性代数的基础,而且具备离散数学和数据结构等计算机专业基础知识。很多学生刚学过数据结构,翻开算法教材,有似曾相识的感觉。教材中确实有部分章节如数据结构,排序算法,图的遍历等取材于数据结构课程。因此会有些学生学习热情不高,认为是在学习重复的课程。

针对这一情况,首先我们会教育学生两课程的目的是不一样的。数据结构的目的是教会学生如果对现实世界中的事物及对其信息处理过程建立数据模型;而算法设计课程的重点是算法的效率问题,其主题是算法的空间和时间复杂度,主要论述如何运用算法技术改进已有一些算法的效率,或者对复杂问题进行求解。

近年来,计算机硬件和软件技术发展迅速,CPU、外存、内存的性能在持续提高,价格却大幅度下跌。因此有很多人认为,软件的效率已经不再重要了,只要提高计算机系统的配置就足够了。这种观点显然是错误的。

我们在第一节的绪论课中引用《算法导论》的例子,深入浅出地阐明了算法效率的重要性。设有两个排序算法:其一是插入排序,时间复杂度为c1 n*n, c1是一个不依赖于n的常数;其二是归并排序,时间复杂度为c2 nlog n,c2是一个不依赖于n的常数,一般情况下c1< c2。n是待排序数列的长度。对于这两个实质上属于不同数量级的算法,很多人并未真正感觉到log n比n优化多少,甚至当n较小时,插入排序比归并排序还要快速一些。但是我们必须认识到,当n逐渐增大到一定数值以后,无论c1比c2小多少,归并排序均比插入排序快速。在大规模数据集上排序结果的对比,则效果更为显著。假若在高性能计算机A(10亿指令/秒)上运行插入排序,而在低速计算机B(1千万指令/秒)上运行归并排序。此时硬件条件是机器A比机器B快了近100倍;软件先决条件是 c1值为2, c2值为50;数据集的规模n为100万。

计算得到:

机器A运行时间为2*(100万*100万)/10亿=2000秒

机器B运行时间为 50*100万*lg(100万)≈100秒

结果是惊人的,用了快100倍的机器处理相同的数据集,反而慢几乎20倍。如果数据集大10倍为1000万,那么机器A要算2.3天,机器B只要20分钟,这一差距是令人震惊的。

事实上,算法技术的发展没能跟上硬件的发展,其发展空间还很大,盲目崇尚硬件建设而忽视算法技术的观点是错误的。

在电信应用中,虽然硬件和软件技术发展很快,但是用户的需求更是呈爆炸式增长。一个国家网内就可能有成百万实时在线用户,每秒几十万次用户交互发生,夜间有成千万的话单记录要处理。当一台内存中存放近百万用户资料,则浪费16个字节就是浪费16M空间。如果记录的数据结构及处理算法设计不合理,则内存很容易不够用,大量工作任务会被抛弃。要在这样的平台软件上构建软件,必须对每个字节空间、每个计算机指令的使用优化到位。否则,即便有先进的计算机系统,一般的软件技术是无法承受高性能、高容量计算的需要的。算法技术能支持开发人员在软件设计阶段从理论层面保障系统的效率达到最优。

经首次引论性教学,绝大多数同学认识了算法课程重要性,明确了学习目的,获得了较好的教学效果。

4理论教学

课程教学组在教材内容上选择了以下内容:

(1) 算法分析基本概念,数学预备知识。这些都是本课程工具性方法。

(2) 堆和不相交理论。介绍了能有效实现优先队列的数据结构。

(3) 归纳法、分治、动态规划。介绍了计算机技术中十分重要的递归为主题的设计技术,递归要求能够将待解问题抽象为递推表达式,确定初试值和递推终止条件后就能将复杂问题化解为嵌套的简单问题。

(4) 贪心算法。介绍了如何求解最优化问题。

(5)NP完全问题。介绍不确定性图灵机在P时间内能解决的问题,这类论题对于培养学生将来思考问题复杂度是个导论。

(6) 回朔法。介绍有组织的穷尽搜索算法,对一些问题尤其是解空间很大的问题有效。我们介绍了3着色、8皇后等经典问题。

(7) 概率算法和近似算法。一般性介绍近20年来算法研究迅猛发展的领域,以扩展学生知识面,但不做考核要求。

其他内容如数据结构、图遍历等是数据结构和图论课的内容,本课程内不做讲解,供学生预习课程时选读;对于域指定问题的迭代改进和计算几何技术等高级课题,推荐学生根据兴趣自学。

近年,越来越多的国内高校主张双语教学。我们也有这样的规划,但是考虑课程有一定深度,三年级本科生英语运用还有限,为此达到最好的教学效果,在教学中先采用中文教学。但是我们鼓励学生同步阅读英文版教材,以更好地适应未来科研和国际化软件研发的需要。

5科研方法及实践能力培养

科研式教育并不是新生事物。在二十年前,我国清华大学、中国科技大学等名校就对高年级学生讲授研究生课程,并进行导师制研教结合型教学,使得很多学生读研时就能取得优秀的成果。作者所执教的是重点工科院校,有很多有利的因素便于我们展开科研式教学:一是有超过60%的学生主观上有本科毕业后继续深造的愿望;二是学校有丰富的图书馆资源,能全文检索CNKI、硕博士论文、IEEE、ACM、ELSERVIER、SPRINGER等中外优秀电子数据库。在教学中,作者也将在科研中读到的一些新颖实用且难度适中的论文摘录下来介绍给学生,并将自己研究生阶段的学习方法介绍给学生。除了阅读教材,我们还鼓励学生读一些高端的杂志,例如计算机学科领域的四大学报,ACM期刊,Software Experience and Practice,Information Processing Letter等刊物,从其中检索感兴趣的论题。读核心期刊有几点好处:这些刊物审稿严格,文章无论是学术性、前瞻性、理论正确性及写作水平都有保证;减少检索的开销。读者可以先在这些高水平杂志中找到自己感兴趣的主题后,再广泛检索与主题相关的其它刊物或会议文章。引导学有余力的本科生读高水平论文并不是过高要求,算法设计及数据结构教材中大部分章节内容其实也都是来源于前二十至五十年的国际知名算法学术期刊,其中选择ACM、IEEE及ISAM杂志内容的比例最高。现在的一些学术期刊中刊出的优秀算法,过几年就会被大量的引用或实际应用,也许再过十至二十年后就会被引入未来的教材之中。

我们认为,在本科高年级展开研究式教学对学生长远发展有好处。对打算深造的同学,可以潜移默化地引导他们思索自己未来的发展方向,有很多成功的学者就是在大学受到某门课程老师的影响而走上科研道路的。科学研究是一个漫长的过程,很多工科博士生学习到第三、四年后才开始发表一级论文,很多硕士生毕业前才急忙撰写可发表成果。而同时有些博士生入学两年就能取得丰硕的成果,很重要的因素是他们在本科高年级阶段就培养了研究型思维,为以后深造明确了方向并作好了理论准备。如果本科阶段就培养研究型学习方法,那么在日后深造过程中多出成果就是水到渠成的事。而如何培养学生良好的研究习惯,正是我们教师要不断探索的论题。

重视理论而实践不足,是我国高校普遍存在的问题。

在国际上,知名的软件鲜有来自中国人的原创。所以我们要更加重视培养学生实践能力。

实验环节,我们布置了基本的排序、递归、贪心、回溯等论题的实验,鼓励学生用不同的编程语言实现,不仅仅是单纯的算法实现,最好能够编制出实用美观的界面,将算法更友好地呈现出来。无论以后的工作或者深造,目标是可应用或者可发表的成果,都需要研发者具有较高的实践能力。我们认为实践与理论教育是并重的。

6结束语

通过四年的教学实践,学生对此课程实践的参与度越来越高。通过教育方法的不断改进,学生的课程成绩也一届好于一届。更为重要的是,通过启发引导式教育,很多同学开始萌发研究型思维,课余经常向老师提问,有的问题有较高难度,老师都要回去研究资料才能解答。在来自本校新入学的硕士生中,不少同学反映受益于此课,有些同学读研究生后不久就在一级学报上发表了算法类论文,这也正是我们当初所期待的。我们教师仍然要不断提高自身科研水平,并将研究成果及方法引进课堂,提高教学效果和质量。

教学中,还发现一个现象,数学系的学生比计算机系的考试成绩要高一些。最简单的因素,是他们理论思维能力更强,如何因材施教,改进教学方法及增强工科学生学习本课程能力,是我们课程教学组今后要探索与研究的方向。

参考文献:

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

[2] Thomas H.Cormen. 算法导论[M]. 北京:高等教育出版社,2002.

[3] Alfred V. Aho, John E. Hopcroft, Jeffery D. Ullman. 算法设计与分析(影印版)[M]. 北京:中国电力出版社,2005.