基于竞赛模式的“算法分析与设计”教学探索与实践

杨春明 陈念年

摘要:本文分析了程序设计竞赛的特点及算法分析与设计课程教学中存在的问题,利用程序在线评测平台,提出了基于程序设计竞赛的教学模式,并在教学中进行了实践。

关键词:程序设计竞赛;在线评测;计算机算法;教学改革

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

1程序设计竞赛

近年来,针对大学生的程序设计竞赛开展得越来越多,比较常见的有ACM-ICPC、TopCoder、百度之星、Google挑战赛等。其中ACM-ICPC (ACM International Collegiate Programming Contest)即ACM国际大学生程序设计竞赛,是历史最悠久、规模最大的竞赛。

由于程序设计竞赛具有开放性、综合性和评判的客观性特征,可以有效检验参赛选手综合应用知识分析和解决问题的能力,因此它不仅培养参赛选手的创造力和团队合作精神,而且也检测选手们在压力下进行创新思维和理性实践的能力。通过参与比赛,学生提高了利用计算机求解问题和程序设计的能力,形成积极向上的自主学习氛围。

在程序设计竞赛中,在线评测系统是开展竞赛的核心。它是一个在线程序与算法设计的练习和竞赛平台,提供大量程序和算法设计的题目,供学生练习或竞赛,学生可以使用自己熟悉的语言提交程序代码,系统编译提交代码,如果没有错误,则生成可执行文件,并利用系统的测试用例来测试,如果输出结果正确,则返回程序消耗的内存空间和时间。对于竞赛题目,系统可以从程序正确性、运行总时间、消耗内存空间、返回结果等方面来考察学生提交的代码,且支持多种语言。系统可以实现在制定的时间段提供竞赛的功能,根据学生解题数目和时间进行排名,也可以批量导出学生代码,进行分析。在线评测系统除了能用于程序设计竞赛外,还可以广泛用于辅助程序设计类课程的教学,为学生提供一个开放的、自主学习的实验环境。

2基于竞赛模式的算法分析与教学设计

2.1 “算法分析与设计”课程的特点

计算机专业要培养具备较强程序设计能力的程序员,需要掌握高级程序设计语言及数据结构、算法设计策略及设计模式、软件体系结构及开发方法等知识。“算法分析与设计”是面向设计的核心课程,主要通过介绍常见的算法设计策略及复杂性分析方法,培养学生分析和解决问题的能力,为开发高效的软件系统奠定坚实的基础。该课程理论与实践并重,内容具有综合性、广泛性和系统性,是一门集应用性、创造性及实践性融为一体的课程。主要内容包括算法效率分析基础、分治法、贪心法、动态规划、分支限界、回溯、近似算法、概率算法等常见的算法设计策略,也覆盖了排序、搜索、图论、几何、组合、数值计算等问题,这也是程序设计竞赛中常见的核心问题。因此,该课程在强调算法的设计思想和方法的同时,需要更加注重算法的应用和实现,教会学生如何利用计算机创造性地解决问题,培养学生独立分析和解决问题的能力。

目前,该课程的教学方法还是以传统的讲解为主,教师通常只是将已有的经典算法在已有的数学模型和数据结构上片面地解释给学生;在实践环节只是盲目的验证算法,而对该算法的运行效率、测试数据规模以及实际的应用场景则很少考虑。学生的学习则主要以理解和记忆为主,没有“理解”和“消化”,不能灵活运用算法;在实践环节,学生代码抄袭严重,很难达到训练的效果。这种教学模式下,学生缺乏问题抽象能力,在遇到实际问题时无从下手,思维创新能力和实践能力难以得到有效的提高。

针对以上问题,笔者利用程序设计竞赛模式和在线评测系统的特点,来弥补课程教学中的不足,探讨“算法分析与设计”的课程教学改革,培养高水平的创新型IT人才。

2.2基于程序设计竞赛的算法分析与设计教学模式

程序设计竞赛具有一定的时效性、开放性和评判的客观性,学生通过竞赛可以有效提高问题求解和程序设计能力。“算法分析与设计”课程通过介绍一些具体问题(如排序问题、检索问题、路径问题、组合问题等)的解决策略,让学生掌握算法的设计策略和分析方法。把这些问题编制成在线评测系统上的竞赛题目,在指定的时间内以竞赛方式开展实验或考核,让学生提交解决问题的程序代码,最后再导出学生代码进行分析。为了避免学生大规模的代码抄袭,可以使用代码甄别系统,该系统可判断代码的雷同率,有效分析学生代码的抄袭程度。教学基本模式(图1)以“竞赛题目”为中心,通过课堂教学和课后实践两个环节,让学生掌握算法分析方法和常见的算法设计方法,并应用到实际问题中,训练学生的程序设计能力。

竞赛题目的设计是课程教学的核心。题目设计应注意难度适中、内容新颖、能有效激发学生的学习兴趣,更重要的是要融入一种或多种算法设计策略,创造一种与现实应用紧密结合的环境;同时提供具有一定规模的一组或多组测试数据,以测试算法的效率。另外,设计题目时还应考虑学生水平的差异,对于能力强的学生,在完成基本要求的基础上,再增加一些有难度的问题,并引导学生自主研究新的问题解决方法,激发学生的创新能力。在具体实施时,考虑提供多个难易程度不一样的题目,如可分为基本算法的验证、基本应用、综合应用三个层次,一些为必选,一些为可选,让学生选择完成,因材施教。如合并排序、快速排序可作为基本算法的验证,最近点对和凸包问题可作为分治法的基本应用,而挑棒游戏可作为动态规划策略中求解有向图传递闭包的Warshall算法的综合应用。

课堂教学重点应放在指导学习方法,根据任务引导学生理解算法设计的基本策略与分析的基本思路;通过具体实例解析一些经典算法,让学生讨论算法在求解该任务时的效率,分析方法的优劣及适用场景;注意对问题进行归类,揭示算法设计策略的规律,使学生触类旁通;采用启发式提问,运用富有思考性的问题,引导学生自己去分析、解决问题。在题目求解方案找到后,适时地开展课堂讨论,引导学生对方案提出疑问,讨论算法的效率及实际应用场景,激发学生探求新的解决思路,让学生对各种方法加以评价;启发学生的思维,加深对问题的理解。

2.3基于程序设计竞赛的教学模式的优势

(1) 提供了开放的、自主学习的实验环境。通过网络使用,学生可以随时提交程序代码,并可在丰富的程序与算法设计题库中寻找合适的题目,训练程序设计能力。

(2) 有效训练了学生的程序设计能力,培养创新型IT人才。“算法分析与设计”的学习难点在于如何将常见的算法策略应用到实际环境中。通过三个层次(算法验证、基本应用、综合应用)的实践训练,让学生熟练掌握常见的算法设计策略,加深对各种算法设计策略的认识,理解算法的意义及精髓,达到学以致用。

(3) 形成良好的学习氛围,加强学生之间的交流。使用在线评测系统进行课程考核并举办程序与算法设计竞赛,以团队方式参与,可以形成良好的校园竞争和交流的学习氛围;学生有了在课余时间自主进行本学科知识钻研的机会和环境;也让学生体验团队协作的重要性,为软件项目团队化的合作要求做好准备。

3教学实践及实效

在笔者的教学实践中,采用了北京大学的POJ搭建了程序在线评测平台,并在近两年的算法分析与设计课程中利用该教学模式进行了改革,取得了很好的效果。为了更全面的训练学生的程序设计能力,课程考核采用了过程考核、课程报告、出勤三部分综合考查的考核方案,三部分分别占总成绩的70%、20%、10%。过程考核考察学生对算法设计策略的掌握程度,一共安排4次,每次以竞赛的方式进行,共计24道试题,每次选做3～5道,共计选做15道,每次考核中均有1～2道稍有难度的试题,内容覆盖了简单算法、分治法、减治法、变治法、时空权衡、动态规划、贪婪策略、回溯和分支限界等。课程报告考察学生综合应用算法分析和设计方法的能力,为9选1,根据所选题目撰写详细的解题报告。

在最近的一次教学中,笔者对教学班上66名同学进行了问卷调查,调查学生对教学改革的满意度、可取之处和不足。调查结果如表1、表2、表3所示:

从调查结果可以看出,学生的满意度很高,表明学生对此教学模式的认同度较高。从每次考核代码雷同甄别情况看,代码雷同率90%以上的低于10%,学生在POJ上做题的积极性也很高,常常会有1/3的非教学班同学参与每次考核。可见这种注重过程的考核方式在教学中取得了很好的教学效果。

4结论

基于在线评测系统的程序设计竞赛具开放性和评判客观性的特点,教师结合“算法分析与设计”课程的特点,将程序竞赛模式应用到课程的教学中,可以有效训练和考察学生的程序设计能力,还可以激发学生的学习兴趣。当然,在该教学模式的实践中,应注意每次考核或实验题目的选择要紧密结合课程知识点和实际应用;在实践过程中注重与学生的交流,激发学生学习热情,注重教学过程,促进学生掌握算法的精髓。

参考文献:

[1] 王卓威,尹宝林. 一个基于网络的程序自动评测系统[J]. 北京航空航天大学学报,2004,30(6):502-505.

[2] 武建华. 基于 ACM 模式的数据结构实践教学改革与探索[J]. 计算机教育,2007(12):114-116.

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

[4] Alex Aiken. A System for Detecting Software Plagiarism[EB/OL]. http://theory.stanford.edu/～aiken/moss/.

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

[6] 李文新,郭炜. 北京大学程序在线评测系统及其应用[J]. 吉林大学学报:信息科学版,2005,23(8):170-177.

The Teaching Exploration and Practice of Algorithm Analysis and Design base on Programming Contest

YANG Chun-ming, CHEN Nian-nian

(School of Computer Science and Technology, Southwest University of Science and Technology, Mianyang 621010, China)

Abstract: This paper analyzes the characteristics of program contest and the problem of algorithm analysis and design in teaching, and puts forwards a staged and validated teaching method base on programming contest.

Key words: programming contest; online judge; computer algorithm; teaching reform