算法分析与设计课程教学改革和实践文档.pdf

“算法分析与设计”课程教学改革和实践 “算法分析与设计”是一门理论性与实践性兼顾的课程,是计算机科学与技术学科的核心课程之一,也是一门与计算机有关的非计算机专业如管理信息、信息与计算科学的专业课。1通过对计算机算法系统的学习与研究,理解和掌握算法设计的主要方法,培养对算法的计算复杂性进行正确分析的能力,为独立地设计算法和对给定算法进行复杂性分析奠定坚实的理论基础。如何上好“算法分析与设计”课程,给广大教师带来了新的挑战和考验。我们在讲授该课程时发现,学生普遍认为学习该课程比较吃力,其原因主要是:首先,它需要学生具有扎实的离散数学、程序设计、数据结构等前驱课程的基础;2,3其次,它也不像很多其他课程大部分依靠记忆,而更多的是依靠理解,并且要求能够灵活应用。因此,这是一门理论知识和独立分析及解决问题能力并重的课程。本文以“算法分析与设计”这门课程为主要研究对象,结合教学实践经验,就算法分析与设计在本科教学中的教学内容、教学方式、实验环节、考核方法等进行了探讨。一、目前算法教学中存在的问题 目前,算法分析与设计课程教学过程中,存在着一些矛盾和问题。1.教学内容繁多、涉及面广,但课时有限 在“算法分析与设计”课程中,教学内容非常丰富,其中包括一些非常经典的算法设计策略,如分治法、贪心法、动态规范法等,还包括一些求解困难问题的高级算法设计策略,如随机化算法、近似算法等。而在教学计划中,课程的教学课时是有限的,要将这些算法设计的策略全部讲透彻非常困难。2.课程教学内容难以跟上当今科技发展步伐 计算机科学的特点决定了它的内容和手段始终处在不断革新和变化的过程中。算法分析方法和设计策略也是日新月异,而传统教材上出现的例子大多是一些经典的例子,在教学内容的改革步伐上很难跟上算法设计方法的发展。3.课程考核方式限制了教学效果 以往的考核方式以期末考试成绩为主,再加权平时成绩和实验成绩。这种考核方式基本能考核出学生对知识的掌握程度,但很难考核学生对知识的应用能力,从而没有达到让学生灵活运用算法设计的思想来解决实际问题的目的。二、教学内容的改革 在教学内容的选择上,总的原则是:内容难度适中,结合实际问题和相关课程的知识讲解算法设计技巧及算法分析方法,使学生既能理解,又能拓展创新。4 现有教材定位往往偏高,注重理论讲解高深,适合研究生、重点院校本科生使用,这样的教材往往导致学生对算法设计课程产生畏惧心理。5本课程的授课内容除了讲授经典算法设计理论外,还结合教师科研实际,逐步引入并行算法、现代启发式搜索算法等先进内容,尽量反映本学科领域最新的学术和科技成果,使学生既能夯实基础,也能扩大眼界。在算法设计策略举例时,为了让学生较好地掌握各种方法之间的联系,应选用同一个例子而采用多种方法来解决。如在讲解贪心法、动态规划法、回溯法和分枝限界法时都采用了 0/1 背包问题,这样可以引导学生掌握课程内容的内在关联性,比较不同算法特点,举一反三。三、教学方法的改革 1.启发式教学 在教学过程中,我们始终贯彻“授人以鱼,不如授人以渔”的思想。在传授知识的同时,还要传教自己如何理解、掌握这些知识的方法体会。3在课堂上,我们主要从经典应用问题入手,在讲解过程中,不仅介绍单个具体问题的解决方法,而且将自己对这一类问题的思考方式表述出来,让学生知道怎么去考虑一个问题。同时提出新的算法设计改进问题,以便让学生进行思考和研究。变单向传输式教学为双向互动式教学,变以强调抽象算法设计为主的理论讲授为探究解决应用问题为主的设计引导式讲授,启发学生在能够解决问题的前提下探索新的设计思路,培养学生的创新思维,诱导学生深入思考,实现教与学的互动,启发学生的创造性,达到创新能力培养和提高教学效果的目的。2.引入参与式教学,强化讨论教学环节 我们将若干名学生分成一个小组,让他们自己选择教师指定的题目,给他们充足的时间进行精心准备,让他们就此在课堂上为其他同学讲解。选题要有代表性,不选难题繁题,但是要有讨论引申之处。讨论问题的同时,学生又会提出新的问题,从而在讨论问题、解决问题的过程中使学生独立思考能力得到培养和锻炼。3.理论联系实际 算法本身相对来说比较枯燥,如果能拓展教材中的内容,在加强理论说明的同时,与实际应用联系起来,可以使学生学起来更有兴趣。如在讲授哈夫曼算法时,我们由最优二叉树引出哈夫曼树的构造方法,然后通过验证它的贪心选择性质和最优子结构性质,从理论上证明哈夫曼编码是平均码长最短的整数码。又如,在讲解找硬币问题时,希望找的硬币个数最少,如果硬币面值为:1 分、5 分和 11 分,要找给顾客15 分,对贪心算法而言,则需要 1 枚 11 分,4 枚 1 分,共计 5 枚硬币;而用动态规划法求解,得出只用 3 枚 5 分硬币就可以了。由此可以看出,贪心法虽然设计思路容易理解、求解问题简单,但对于有些问题采用贪心法不一定能得到最优解。通过引导学生思考对于同一个问题选择不同算法会有什么样的结果,可以提高他们的学习兴趣,培养他们发现问题、分析问题及解决问题的意识和能力。四、教学手段的改革 现代教学和传统教学手段各有利弊,我们应根据教学内容,扬长避短,充分利用各自优势,将它们有机结合起来。为了在有限的教学时间内增加单位时间的信息含量,将有限精力与时间用于剖析课程内容的重点难点,应引入多媒体教学手段。利用多媒体教学课件,采用直观教学方法,动态模拟算法的执行过程,可以促进学生对算法的理解。但是对于算法复杂性分析和算法解决问题的推导过程,我们仍采用传统的黑板板书教学方式。因此,学生经历了板书从无到有,思路从疑惑到逐渐清晰的过程,而教师的板书和讲解过程,就是一个展示思维与学生交流和沟通的过程。此外,我们还充分利用网络资源,将教学课件和学习资料发布到网上,方便学生查看,通过网络答疑,及时解答学生在学习中遇到的问题。五、实验环节的改革 本门课程理论性较强,同时实践性也很强。本科生学习算法的主要目的是:能将所学算法灵活运用到实际问题中。目前,一些高校只安排了课程教学,没有安排实验学时,而我们的课程课时调整后,已基本保持了课堂授课学时与实验学时比例为 3:1(如 24 学时的课堂授课配设了 8 学时的上机实验)。在实验课的教学过程中,还应注意:学生的接收能力、理解能力、编程能力以及创新能力各不相同,需因材施教,区别对待。因此,可以设置难易程度不同的实验项目供学生选择,或设置必做题和附加选做题。我们设计了三个不同层次的要求:一是基本验证型对课堂上讲授的经典问题,采用不同算法实现,输入大量数据,测试程序运行时间,与理论结果进行比较;二是拓展型设计一个实际问题,能够应用所学算法或经过变换解决,如旅行售货员问题的算法可以应用到物流配送线路选择等实际应用问题;三是综合型提出一个综合性问题,利用所学的知识设计出新的算法,并用实验模拟验证。其中,最低要求必须完成第一层次的实验。实践证明,这样可以激发学生学习的积极性,提高学习的兴趣,并充分发挥学生的主观能动性。六、考核方式的改革 不仅教学内容、教学方法和手段与课程的教学效果紧缩相关,课程的考核方法对于教学的效果也有很大的关系。考核的方式不同,学生在学习过程中的学习重点也会不同。在传统的考核方式中,期末的理论考试往往占很大比重,一般在70%以上,而平时成绩和实验成绩只有 30%左右。就算法这门课程,我们提出了如表 1 的考核内容及所占总评成绩的比重,适当降低了期末理论考试的比重,提高实验成绩所占的比重,并考虑到学生在讨论课中的表现。这样更注重考核学生学习过程中的表现情况,有利于促进学生积极主动学习,培养创新能力。七、改革的效果 对于本次“算法分析与设计”课程教学的改革,笔者所在北京信息科技大学理学院在信息与计算科学专业先后三个年级约 150 人中进行了实践,实践后达到了以下的效果:(1)通过本课程的学习,学生不仅掌握了书本上的理论,更重要的是掌握了算法设计的思想,锻炼了开发程序的能力,并能将书本上的理论初步应用到实际问题的解决。(2)进一步激发了学生学习算法课程的兴趣,增强了学生学习的主动参与性,减少了学生对该课程感到枯燥无味的感觉。(3)学生先后参加了多届北京市 ACM、数学建模等竞赛活动,其中有一队学生获得了 2009 年数学建模竞赛全国二等奖。不少学生都表示,在进行竞赛活动以及毕业找工作笔试面试时都用到了算法课程的内容,它能够帮助活跃思维,充分调动主观能动性。八、结束语 高等教育的改革和探索是没有止境的。本文就“算法分析与设计”这门课程提出了教学内容、教学方法和手段、实践环节以及考核方法等方面的改革措施。这些措施还需要在今后的教学过程中不断完善,使算法课程的教学质量提高到新的水平。