基于ACM—ICPC的算法设计与分析课程改革

李华　赵建平　李奇　武岩

摘要：通过分析算法设计与分析课程的教学状况和教学形式，结合国内外教学模式的对比情况，提出有效的教学改革方法。该方法提倡理论与实践相结合，竞赛与考试改革相结合，教师讲解与课程讨论相结合，提供给学生一个综合的实践锻炼平台，并建立适合长春理工大学学生的测评系统和习题库，进行严格规范的训练，达到真正提高学生竞赛水平的目的。

关键词：ACM-ICPC；算法设计与分析；教学改革

文章编号：1672-5913（2013）07-0088-04

中图分类号：G642

0 引言

算法分析与设计课程是计算机科学与技术专业的专业基础课程。该课程要求学生具备良好的数学、数据结构和程序设计语言基础，是一门面向设计的计算机学科核心教育课程。该课程通过对算法设计策略的系统学习与研究，使学生理解和掌握算法设计的主要方法，培养学生对算法的计算复杂性进行正确分析的能力，为学生独立地设计算法和对给定算法进行复杂性分析奠定坚实的理论基础。这对从事计算机系统结构、系统软件和应用软件研究与开发等工作是非常重要的。

ACM国际大学生程序设计竞赛（ACM International Collegiate Programming Contest，简称ACM-ICPC或ICPC），是由美国计算机协会（ACM）主办的，是一项旨在展示大学生创新能力、团队精神以及编写程序、分析和解决问题能力的年度竞赛，是目前计算机行业唯一公认的高水平竞赛。

近几年，ACM国际大学生程序设计竞赛在全国范围内得到公认，尤其在研究生复试、知名企业面试常时采用ACM程序设计大赛的试题模式进行。各大高校也积极开展这方面的教育和培训。算法分析与设计课程作为程序设计类竞赛的理论基础课，其教学模式和教学方法改革也在不断的探讨中。学生普遍认为这门课程属于偏难理解、动手困难的课程。因此，如何更有效地提高大学生独立设计算法和分析算法的本领，提升实践能力，成为算法分析与设计课程改革的主要方向。

与其他课程不同的是算法设计问题千变万化，学生即使理解了知识点和设计策略仍需要结合大量有效的实践才能真正掌握算法。所以实践环节是至关重要的。针对这种状况，本文首先对目前一些高校的算法分析与设计课程的教学情况进行了分析和对比，然后提出一种基于ACM-ICPC模式的教学方法，旨在有效提高实践水平，促进教学效果和竞赛水平的提升。

1 国内外课程情况对比

1.1国内课程情况

目前，国内的计算机科学与技术专业基本都开设了算法分析与设计课程。近10年，该课程的网络资源变得越来越丰富。在国内的普通高校，该课程普遍的教学模式是一名教师授课、一名实验教师配合实验教学。通过对国内10所高校的课程情况进行调查，该课程的理论学时分配为32～48学时不等，课内实验学时一般为16学时。根据笔者多年教学经验来看，这种教学模式只能达到一般的教学要求，即介绍几种典型解决问题的策略，包括分治法、动态规划、贪心选择、回溯法、分支限界法、概率算法等。讲授内容通过对经典算法问题的分析，给出解决问题的最优算法和时间、空间复杂性、正确性证明。而实验题目一般是对应某种算法设计策略的练习。目前的实验环境可以检验结果的正确与否，对于时间复杂性等要求无法准确检验。同时，由于课内时间有限，使得综合性设计的题目比例偏少，这就只能靠学生的兴趣在课后进行更多的练习，也在一定程度上制约了动手能力的锻炼。

1.2国外课程情况

由于国内外教学体制的不同，我们无法准确的对比分析国内外的计算机算法课程，但是国外一些知名大学对算法导论类的课程教学模式是值得借鉴的，具体总结，主要有以下几方面。

1）课程主要由3部分构成：理论课、课程专题讨论、习题及作业课。

2）课堂讲授。由浅入深，推导出理论方法，传授算法设计技巧。

3）课程专题讨论。每周安排至少2小时的讨论。讨论内容是所学课堂知识的一个扩展。每次讨论设置一个专题，现场分发讨论题目，而且有些讨论的内容会直接出现在期末考试中，所以缺席讨论会对成绩造成重要的影响。

4）习题及作业课。重要的课程内容都有相关的作业。学生必须在规定的时间内独立完成文档。学校开放实验室，学生就可以自愿在指定的实验室和时间里集中完成作业，并得到助教的解答。此外我们还允许团队协作讨论作业，但学生必须独自完成在指定的时间内提交的文档，并能够在讨论课上对作业过程进行阐述。

显而易见，国外的课程教学安排更周密，详尽。从学生的角度来看，这种做法的优点是学生有自由的时间支配来完成实验以及作业，对学生给予更个性化的发展空间。

2 课程教学模式改革措施

按照上述分析，不难得出国内学生在遇到新问题的时候仍是束手无策的原因。笔者根据多年的教学经验，对算法分析与设计课程提出以下几点思考。

2.1引入信息学竞赛问题，采用启发式教学

例如，在介绍解动态规划算法设计策略的时候，教材中常用矩阵的连乘为例。该问题较为抽象，不易理解，而一般的信息学竞赛题目富含一个故事，所以我们可以先利用信息学竞赛题目的内容，通过故事引出一个问题，这样很容易唤起学生的兴趣，学生自然也就渴望了解问题的解决办法，主动探求知识了。与此同时，我们用启发式的教学方法，潜移默化的引出建立数学模型的过程，引出动态规划解决问题的基本思想和基本步骤。

例如，方块消除问题：N个带颜色的方格排成一列，相同颜色的方块连乘一个区域（即如果连个相邻方块颜色相同，则这两个方块属于同一区域）。游戏时，我们可以任选一个区域消去，并得到区域方块个数平方的分数。方块消除问题的两种情况如图1所示，方块消去之后将产生空列，此时其右边的所有方块就会向左移，直到所有方块连在一起，要求确定不同消除方案下的最高得分方案。

2.2结合课程需要，引入全新实践模式

算法分析与设计与其他程序设计类课程不同的一个重要特征是，要分析问题的复杂性，包含时间复杂度和空间复杂度两方面。而一般的程序设计实验环境，只能检验运行结果的正确与否，无法确切的让学生体会到运算时间的概念。从这个角度讲，算法问题的执行必须结合严谨的程序评判系统，而ACM-ICPC的在线判别系统OJ正具备这样的判别机制，将ACM-ICPC模式引入到算法设计与分析的课堂教学中来也是势在必行。

结合ACM-ICPC，学校建立了长春理工大学ACM-ICPC网站（网址为http：//acm.cust.edu.cn/），使课堂与实践紧密地结合。在教学过程中，竞赛的算法题目引入课堂，并把OJ系统作为实践教学、检验学生成绩的手段。课后作业让学生在规定的时间内把答案提交到OJ系统，成绩由系统自动评判，系统会列出运行每个学生程序的相关信息。教师根据系统信息了解学生的学习状况，同时还能进行运行时间的统计，给出公平、公正的成绩。这对于算法分析与设计来讲至关重要，同时提高了教学效率和教学质量。再者，很多算法问题既有趣，又有挑战性，极大地提高了学生的兴奋点。

2.3增加课程讨论，加强学生间交流

每学期提供给学生9～10个题目，定期开展课程讨论。课程讨论过程中由学生讲述算法设计思路，教师进行启发式引导，并进行讨论。经过一个学期的锻炼，学生的动手能力得到锻炼，思考问题更加缜密，团队协作能力也得到提升。

2.4开放实验室，适当增加学时

我们需要完善课程教学体系，采取措施鼓励教师开展多样化教学手段，把课程讨论、课程作业指导都纳入计算课程总学时中。教师从加强学习效果人手，同时又使学生有更多的自由支配空间。这种“自由式”的学习方式，在国外是普遍被采纳的，从实际效果看，好于灌输式的学习方式。中国学生从小适应教师灌输，紧跟教师的节奏进行被动式学习，导致自己缺乏主动思考问题的能力。若采用文章所述教学模式，学生的信心和主动性被明显带动加强。

2.5鼓励竞赛与课程成绩互补

我们把学生参加OJ系统练习题的数量考虑到参赛队员选拔指标及成绩考核中。由于每道题的完成情况在系统里都有记录，教师可以适当根据学生在系统中的习题完成情况，考查学生的平时成绩，同时课程组教师参与竞赛指导，对竞赛和课程教学都深入了解，有利于教学和竞赛的相互促进。目前教学手段多样化，很多课程都采用了多媒体授课。但是要因“课”而异。算法分析与设计课程的思路和思维方法很重要，学生必须有充分的思考时间，所以更适宜用传统的板书教学。国外著名的算法课程多是这样开展的，配以适当的投影，展示运行结果，笔者认为这是比较恰当的算法授课方式。我们还可以建立算法分析与设计课程网站，建立师生互动平台，进行课后学习指导，发布课件信息、复习资料等。

2.6考试改革

与外国学生相比，中国学生理论基础扎实，从教师和教材吸取的知识较多，对讲授的内容掌握牢靠；但创新能力较差，不善于发现问题、提出问题，缺乏实际解决问题的能力。这种现象的根源在于考试制度，包括考核形式与评分标准。目前，算法设计与分析课程的成绩大多按两部分计算：一部分是平时作业情况，占总成绩的20%～30%；另一部分是闭卷考试，占总成绩的70%～80%。这就导致学生对笔试的重视程度要高于实践环节。因此改革课程考核方式是值得尝试的。笔者认为按照前述课程安排，平时实践30%，作业报告20%，期末考试50%的比例是合理的。其中实践环节的考核，均在OJ系统上实现，充分体现考试的公平公正。

3 结语

经过一段时间，课程改革初见效果。学生参加ACM-ICPC竞赛的成绩逐年提高，除了连续3年获得省内、东北地区比赛一等奖外，还获得了全国大学生邀请赛及亚洲赛区银奖的好成绩。今后，我们将进一步探索算法分析与设计课程的教学模式改革，找出最能激发学生兴趣的切入点，进一步将课程教学与实践环节有机地结合在一起，逐步提高学生的创新能力、动手能力和团队协作能力。

（见习编辑：刘丽丽）