“算法分析与设计”任务驱动教学模式改革与实践

摘要:本文分析了“算法分析与设计”课程教学中存在的问题,利用“任务驱动”教学方法,引入ACM/ICPC在线评测平台,结合教学实践,从任务设计、课堂教学和课程考核等方面探讨了一种注重过程和实践的教学模式。

关键词:任务驱动;在线评测;代码雷同;教学改革

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

1引言

“算法分析与设计”是一门面向设计的专业核心课程,是计算机科学研究的重要领域之一,也是现代软件系统的核心问题。课程旨在培养学生分析问题和解决问题的能力,掌握算法设计及复杂性分析方法。课程理论与实践并重,内容具有综合性、广泛性和系统性,是一门集应用性、创造性及实践性融为一体的综合性课程。目前,该课程的教学方法还是以讲解为主,通常只将已有的经典算法在数学模型和数据结构上片面地解释给学生;在实践环节只盲目地验证算法,而对该算法的运行效率、测试数据的规模以及实际应用场景则很少考虑。学生的学习则主要以理解和记忆的继承式学习为主,虽然记住了大量的算法理论,但没有“理解”和“消化”,不能灵活运用算法;在实践环节学生代码抄袭严重,很难达到训练的效果。在这种教学模式下,学生缺乏问题抽象能力,在遇到实际问题时无从下手,思维创新能力和实践能力难以得到有效的提高。

针对以上问题,文献[1]从教学思想及教师角色的转变两个方面探讨了如何在课堂教学中训练学生的综合分析能力。文献[2～3]对教学内容的选择、以学生为中心教学方式的改变、实验与课程设计环节的加强、考核形式及评分标准的改革等方面做了探讨。笔者在长期的教学实践中,结合课程特点和实际教学,利用“任务驱动”教学方法,引入ACM/ICPC的在线评测系统,探讨了算法分析与设计的课程教学改革。

“任务驱动”是一种建立在建构主义学习理论基础上的一种教学方法,是建构主义理论在教育教学中的具体应用。这种教学方法主张教师将教学内容隐含在一个或几个有代表性的任务中,以完成任务作为教学活动的中心;学生在完成任务的动机驱动下,通过分析和讨论任务涉及的知识及需要解决的问题;在老师的指导下,通过对知识的主动学习和应用,自主探索来完成任务。该教学方法的显著特点是以训练学生能力为主,教师的主要功能是“促进学生学习,引导学生成功”,是基于探究学习和协作学习的一种教学模式。

2注重教学过程及考核的“任务驱动”教学模式实践

2.1 “任务驱动”教学基本模式

算法分析与设计的课程内容由一些具体问题构成(如排序问题、字符串处理问题、查找问题、图问题、组合问题、几何问题等),这些问题可看成是“任务驱动”教学法中的“任务”。在课程教学中,将具体的算法设计策略融入到这些“任务”中;课堂教学以任务为主,引导学生利用算法设计策略探索解决方案;在课后的实践环节,将结合实际应用且融入了知识点的任务放到ACM/ICPC在线评测系统上,让学生在课后根据任务描述,自主探索问题解决方案,并提交程序代码,在线评测系统根据任务设计时的测试数据来评价学生的解决方案;同时,为了避免学生抄袭代码,可以将学生代码导出后甄别代码雷同情况。

整个教学过程以“任务”为中心,通过课堂教学和课后实践两个环节的任务驱动,让学生在自主探索的过程中掌握算法分析方法和常见的算法设计策略,并应用到实际问题中,训练学生实践能力,以达到教学目标。

2.2面向应用的任务设计

任务设计是“任务驱动”教学实施的第一步,也是该方法的核心,要求教师将教学内容和教学目标隐含到具体的任务中。课堂教学和实践环节的任务设计有着各自的侧重点。

(1) 课堂教学中的任务设计

课堂教学环节的任务设计重点是把教学内容和教学目标融入到任务中,让学生在教师的引导下逐步探索该任务的解决方法,以此掌握某一类算法设计策略。课堂教学是一个逐步推进的过程,因此,课堂教学中的任务可设计成多个有递进关系的小任务,由易到难,循序渐进地完成,激发学生的学习兴趣。

例如,在讲到动态规划算法时,可根据动态规划求解的一般步骤来设计任务。动态规划是解决最优性问题一种重要算法设计策略,是通过寻找问题的递推关系来解决问题,教学的重点是让学生掌握寻找递推关系式的方法。递推关系表明了一些交叠子问题之间的关系,这些交叠的子问题可看成不同的阶段,递推关系式表明了阶段之间的关系。动态规划算法的求解步骤为划分阶段、找出阶段之间的递推关系及初始值、利用初始值求解递推关系式。因此,动态规划教学的任务设计按照求解步骤可分成多个由易到难的小任务,通过逐步解决这些任务来掌握动态规划算法的知识点。

动态规划算法中求解有向图传递闭包的Warshall算法的任务可设计为:

任务一:划分传递闭包的阶段?

任务二:根据题目要求确定阶段之间的递推关系及初始条件。

任务三:根据递推关系描述算法。

任务四:分析算法的效率,并讨论与遍历方法的效率比较。

(2) 实践环节的任务设计

实践环节的任务设计重点在综合应用课堂教学中讲授的算法策略,需要面向具体应用,且难度适中、内容典型新颖、能有效激发学生学习兴趣。这一环节的任务应注意创造一种与现实应用紧密结合的任务环境,可融入多种算法设计策略,还应考虑提供具有一定规模的测试数据,以测试不同算法的效率。

如Warshall算法实践环节的任务可设计为:

任务:挑棒游戏

有若干塑料游戏棒散倒在桌子上,玩家要试着把他们一根根取走而不移动其他游戏棒。我们只考虑一对游戏棒之间是不是通过一系列相互搭着的游戏棒相连接。给定N(N>1)根游戏棒的端点列表,请找出所有相连的游戏棒。注意,搭在一起的算相连,但能通过其他相连游戏棒间接相连的也算相连。测试数据给多组,每组测试数据的规模不定,这样可以比较出不同算法的效率。

该任务初一看跟Warshall算法没有联系,但仔细分析后发现,只要将游戏棒缩小成一个点,如果两根游戏棒的端点值一样,则可以看成这两个点之间有边相连;这样散倒在桌子上的游戏棒就变成了一个无向图,找出所有相连游戏棒的任务就变成了求出该无向图的传递闭包。该任务可以有效的训练了学生理解问题、分析问题、灵活利用所学算法策略求解问题的能力。

另外,实践环节任务的设计除了考虑综合应用外,还应考虑到学生之间水平的差异。一个教学班上学生的接受能力、理解能力和动手能力各不相同,应区别对待。对于能力强的学生,在完成基本要求的基础上,再增加一些有难度的问题,并引导学生自主研究新的解决问题的方法,激发学生的创新能力。在具体实施时,考虑提供多个难易程度不一样的任务,一些为必选,一些为可选,让学生选择完成,实现因材施教。

2.3以培养学生能力为中心的课堂教学

课程的目标是培养学生算法设计与分析的能力,只有学生去思考并实践了才能很好掌握这些技能。因此,在课堂教学中应改变以往上课时老师唱主角,将大量内容“灌输”给学生,而不重视学生反馈和实践的教学方式;重点应放在指导学习方法,根据任务引导学生理解算法设计的基本策略与分析的基本思路,通过具体实例解析一些经典算法,让学生讨论算法在求解该任务时的效率,分析方法的优劣及适用场景,当学生了解算法设计的基本方法后,把求知的钥匙交给学生。

在课堂教学中以学生为中心,注意对问题进行归类,揭示算法设计策略的规律,使学生触类旁通;这样,学生在碰到实际问题时就不至于茫然,有一套明确的解题思路。在引导学生探索任务求解方案时采用启发式提问,运用富有思考性的问题,引导学生积极思考,让学生自己去分析问题、解决问题。在任务求解方案找到后适时地开展课堂讨论,引导学生对方案提出疑问,讨论算法的效率及实际应用场景,激发学生针对一些问题探求新的解决思路,让学生对各种方法加以评价;这有助于启发学生的思维,加深对问题的理解。

2.4注重过程的考核及评分标准改革实践

课程考核是“任务驱动”教学法实施的评价阶段,主要评价学生是否完成了对课程知识点的掌握及灵活应用,也是课程教学的重要阶段。目前,该课程的考核基本上分为两个部分,一部分是平时成绩,占30%～40%,主要由作业和出勤组成;另一部分为期末考试,占60%～70%。这样的考核方式很难考察学生的实践能力,导致大部分学生只注重期末考试,而忽略学习过程,很难有效的提高学生的创新能力和实践能力。

算法分析与设计课程的考核应着重考核学生对常见算法设计策略的灵活应用及效率分析,而不是对算法的死记硬背。对此,在笔者的教学实践中,引入ACM/ICPC在线评测系统及代码雷同判断系统,对课程的考核方式及评分标准作了如下改革:

课程考核分为三部分,分别为课堂讨论考核(10%)、常见算法设计策略的应用(过程)考核(60%)、课程报告考核(30%)。

课堂讨论考核主要考核学生的学习积极性,包括对提问的回答、学生提问及讨论。在课堂教学过程中记录下每位学生的发言次数,到期末统计次数,给出相应的分数。

常见算法设计策略的应用(过程)考核主要考核学生的实践能力,在实践环节完成。这一部分的考核与课堂教学同步,在ACM/ICPC在线评测系统上进行;在评测系统上提供多道难易程度不一的问题(任务),让学生在规定时间(如两周)内求解并提交代码到系统上,要求通过任务的测试数据,完成不同的任务可获得不同的分数。为了避免代码抄袭,在一次考核完成后,从在线评测系统中提取学生代码,利用代码雷同判断系统判断代码的雷同率,如果代码雷同率较高(如90%),则可认定为抄袭,计0分。代码雷同判断是一个难度较大的工作,笔者这里采用的是Stanford大学的Moss系统,它提供了一个免费的使用接口,通过该接口,可判断你提交代码的雷同率[7]。

课程报告考核主要考核学生算法分析与设计的综合能力,在课程结束后进行。考核时给出多个具有一定综合性和多种测试数据的任务,让学生选择1～2个任务解决,并撰写报告。报告内容主要包括任务分析、算法设计、算法效率分析、算法实现、程序测试及讨论组成。根据学生撰写报告内容的质量来综合给分。

三个部分的考核综合考虑了学生学习过程、课程内容、教学目标和课程的特点,能有效激发学生的学习积极性,很好的训练学生的实践能力。在笔者多次的实践中,取得了较好的教学效果。

3小结

“任务驱动”教学法能有效的结合算法分析与设计的课程内容和教学目标,它使学生在任务的求解过程中掌握了课程的知识点,达到教学目标。文章针对当前算法分析与设计课程教学中存在的一些问题,利用“任务驱动”教学方法及ACM/ICPC在线评测系统,探索了一种注重过程和实践的“任务驱动”教学模式,并在笔者的课程教学中多次实践,取得了较好的效果。

参考文献:

[1] 王素立,白首华. 算法分析与设计教学方法[J]. 湘潭师范学院学报:自然科学版,2005(9):124-127.

[2] 刘波. “算法设计与分析”教学探讨[J]. 高等理科教育,2007(4):78-80.

[3] 孙红丽,叶斌. 浅谈算法设计与分析课程的教学改革[J]. 太原教育学院学报,2005(12):45-47.

[4] 侯海云,李兴保. 任务驱动教学理念新解[J]. 中国现代教育装备,2007(2):98-100.

[5] 曾希君.“任务驱动”教学法在计算机专业课教学中的应用探索[J]. 计算机教育,2007(9):7-9.

[6] Anany Levitin.. 算法设计与分析基础[M]. 2版. 潘彦,译. 北京:清华大学出版社,2007:217-219,223.