基于ACM—ICPC模式的算法分析与设计课程的建设与实践

刘晓璐

摘 要：针对算法分析与设计课程的教学实际，文章分析了该课程教学模式的局限性和传统的实践教学中存在的问题，提出将ACM-ICPC竞赛模式引入该课程教学的观点，开发了一个基于ACM-ICPC模式的程序测评系统，并应用在算法分析与设计课程的实践教学中，取得了良好的教学效果。

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

中图分类号：G642 文献标志码：B 文章编号：1673-8454（2015）10-0065-03

一、引言

算法分析与设计是面向设计的计算机专业核心课程，主要通过对经典算法的学习和研究，使学生掌握算法的设计策略和算法复杂度的分析方法，培养学生分析和解决实际问题的能力，为开发高效的软件系统奠定了坚实的基础。该课程教学内容繁多，涉及的知识面很广，主要内容包括算法分析方法、递归算法、分治算法、贪心算法、动态规划、回溯算法、分支限界、近似算法、概率算法等经典的算法，覆盖了多项式、数论、矩阵、集合、图论、几何、模式匹配等数值和非数值计算问题。

目前，各高校该课程分配的课时普遍较少，教学方法也都是以讲解为主，即使设置了实验课，在实践环节通常也只是一味地对算法进行验证，很少考虑到算法的运行效率分析、测试数据的规模以及实际的应用场景。学生对算法的学习主要以理解和记忆为主，缺乏对知识的重构和对算法的灵活运用，遇到实际问题便无从下手。而且，在传统实践教学中，学生抄袭代码的情况严重，不能有效提高学生的实践能力，无法体现实践教学的真正作用。在这种教学模式下，学生缺乏对实际问题进行抽象和分析的能力，思维创新和实践能力难以得到有效提高。本文结合我校实际教学情况，将ACM-ICPC竞赛模式与算法分析与设计课程的建设相结合，达到了良好的教学效果。

二、课程现状

算法分析与设计课程的建设在我校起步较晚，我校从2010年开始招收计算机科学与技术专业本科学生，从2012年开始为计算机科学与技术专业学生开设算法分析与设计课程。第一届课程只有理论课，学生缺少实践机会。该课程的开设是面向计算机科学与技术专业大三的学生，学生在学习该课程之前，已经学习了C/C++程序设计、数据结构、Java程序设计、高等数学和离散数学等课程，但是由于学生欠缺良好的计算思维，逻辑分析能力相对不足，编程实践能力仍然比较弱，学生在学习该课程时倍感吃力。

目前，我校在算法分析与设计课程信息化建设方面有许多不足，主要体现在以下几点：

（1）课程之间的联系不够紧密

算法分析与设计课程与其他课程的关系是很密切的，如数据结构，它们之间相互作用，从而提高计算机专业学生的实践能力，为学院培养高素质的应用型人才。由于这些课程的前后都没有很好地衔接，课程之间的重点和难点没有对应上，所以学生在上算法分析与设计课程时需要重新复习之前所学的课程，从而增加了学生学习的工作量。

（2）教学资源不足

当前课程并没有信息化系统的支持。学生只能通过网络搜索所需的资源，获取教师的PPT也只能通过教师，教学资源没有实现整合和共享。

（3）编程竞赛平台不多

程序设计能力的提升需要学生多思考多编程，而这方面实践能力的获取最有效的方式就是竞赛活动。在参加或举办程序设计类竞赛方面，学生只参与了国内的“蓝桥杯”这一个程序设计类竞赛，学院内部并没有开展此类竞赛活动。

三、ACM-ICPC模式下的课程建设

1.ACM-ICPC在课程中的作用

ACM国际大学生程序设计竞赛（ACM-ICPC）是由美国计算机协会（ACM）主办的，是一项旨在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的年度竞赛。经过40多年的发展，ACM-ICPC已经发展成为最具影响力的大学生计算机竞赛。竞赛时间为5个小时，重点考察选手的算法和程序设计能力。选手通过网络提交程序，评委负责将结果（正确或出错的类型）通过网络尽快返回给选手。

将ACM-ICPC竞赛模式引入算法分析与设计的教学中，可以激发学生的主动学习积极性，鼓励学生勤思考、多实践，相对于传统的实践教学具有以下几方面的优势：

（1）在网上进行实践教学，没有时间和空间的局限性。教师可以在测评系统中对同一个实验项目布置多个难度各异的题目，学生可以根据自己的掌握情况，从易到难选择合适的时间完成训练题目。学生完成编程提交代码后可以立刻得到评测结果，这样可以激发学生的学习热情。教师也可以分析学生提交程序是否正确或错误，并进行针对性的讲解。

（2）对创造校园的学术交流氛围有良好的促进作用。学生在课余时间通过在网上提交自己编写的程序源代码，自主进行算法和程序的交流，有利于培养学生的学术修养，实现学生与教师、学生与学生之间的交流和互动。

（3）减轻教师实践教学时的指导负担。传统的实践教学在机房进行，教师需要在整个机房进行巡视，为有疑问的同学进行解答。这让教师在实践教学中的指导负担非常繁重，教师的指导范围也不能全面覆盖整个班级，在一定程度上打击了学生的积极性。而ACM-ICPC竞赛模式的在线测评系统可以对学生提交的作业进行评测，大大减轻了教师的负担。

2.测评系统的设计与开发

我们将基于ACM-ICPC竞赛模式的在线测评技术引入算法分析与设计课程的教学中，开发了一个程序在线测评系统。该系统基于Java EE，是一个程序在线评判、程序设计竞赛和交流的平台，可不断扩展题库供学生进行程序设计练习，系统自动对提交的程序源代码进行编译、运行并评判程序的正确性。系统可供课程日常训练和网上实时竞赛使用，也具备站内交流和站内全文检索功能。考虑到后期改进和后续开发的需要，系统的开发采用的是目前主流的MVC架构，使用的是Struts框架。系统有两个版本的评判模块，一个基于纯Java，另一个基于C++，两者均可在Windows平台下运行。

学生在系统提交程序后，系统先将程序保存至数据库，再写入评判队列，由系统评判内核进行编译、运行并返回结果，返回的结果类型有AC、WA、RTE、TLE、PE、MLE、CE。每个题目可能有多个测试数据，内核在读取主系统传递给它的参数后，编译程序，生成可执行文件，之后对于每个测试数据运行一次“验证测试数据”的操作，只有当所有测试数据均验证无误，才返回AC，如果在某次验证返回错误，则返回相应的错误信息，在任何时候遇意外终止将返回RTE。评判内核的程序流程如图1所示。

系统用户分为四种：普通用户、高级用户、论坛版主及系统管理员。任何学生都可注册成为普通用户。普通用户可以做练习题，提交程序并得到系统的评判和结果反馈；可以根据程序提交情况参与用户排名；拥有并可使用自己的站内信箱；可以查看、保存和管理自己提交的源代码；可以在论坛发帖，参与问题讨论；可以参加程序设计竞赛，并查看比赛结果和统计数据。任何解答题目超过20道的普通用户，可自动升级为高级用户。高级用户拥有普通用户的所有权限，还可以上传题目和测试数据，并可对自己上传的题目进行管理、修改等。高级用户上传的题目，经管理员确认后，便可加入系统的正式题库，系统在题目信息中记录上传题目者的相关信息。论坛版主为系统管理员授予，拥有普通用户的所有权限，同时对相应的论坛板块拥有管理权。系统管理员管理系统的日常运行，拥有所有的管理权限，需要对题目和测试数据进行筛选，检查系统运行情况，组织程序设计竞赛。

3.课程设置

结合我校实际情况，我们在算法分析与设计课程的实践教学内容上设计了递归算法、分治算法、动态规划算法、贪心算法、回溯算法、分支界限算法共6个经典算法的实验项目。由于实践教学课时有限，传统的教学方式每个实验项目只能设计2-3道题目。引入ACM-ICPC模式之后，学生可以利用课余时间通过网络完成程序设计，每个实验项目题量增加到6-8个，题目难度各异，学生可以根据自己的知识掌握程度和能力选择合适的时间完成。较容易的题目可以先完成，具有一定的综合性、难度较大的题目，可以在有相当的训练量之后完成。

这种循序渐进的训练方式，更有利于学生对算法原理的理解和掌握，也更有利于形成由浅入深的思维模式，有效提高学生的分析问题、解决问题的能力。测评系统中的部分习题如表1所示。

课程的考核参考学生提交程序的次数、通过率、提交程序的难度等，作为学生平时成绩的考核依据，这样可以鼓励和督促学生积极参与实践。

四、课程建设实践成果

实施ACM-ICPC竞赛模式的程序在线测评系统以后，学生的学习积极性得到了较大的提高。学生对经典算法的掌握程度和实践能力也大大提高了。

学生在各种全国性考试和比赛中取得了较好的成绩。以我校参加“蓝桥杯”全国软件专业人才设计与创业大赛的情况为例，不仅在报名人数上大幅增长，获奖人数和获奖等级也有了明显的提高，具体如图2所示。

在课程的实践教学中，学生设计算法的训练量加大，平均每人每学期完成习题数量为34题，较实施前增长88.9%。学生的自主学习能力有所提高，教师在实验课上的空闲率由原来的0.4%增长到33.3%，学生对教师的依赖程度大大降低。

五、结语

基于ACM-ICPC模式的算法分析与设计课程将理论学习与实际操作相结合，注重培养和提高学生分析和解决实际问题的能力，以公平、公正、公开的竞争形式带动学生的自主学习，调动学生交流和研究的积极性，为课程的开展提供了良好的氛围。在后续的研究和开发中，我们将把基于ACM-ICPC模式的程序测评系统扩展到全系范围内的更多的程序设计类课程。

参考文献：

[1]龚宇平，梁丽.计算机专业大学生创新思维的培养[J].教育与职业，2014（8）.

[2]陆慧.应用型本科高校创新型人才培养存在的问题与对策[J].教育与职业，2013（35）.

[3]赵春风.基于J2EE技术ACM竞赛程序在线评测系统的设计与实现[D].厦门：厦门大学，2013.10.

[4]李华，赵建平，李奇等.基于ACM-ICPC的算法设计与分析课程改革[J].计算机教育，2013（7）.

[5]赵晖，付秀花.计算机语言程序设计课程的教学创新[J].教育与职业，2013（23）.

[6]王伟嘉，张洪萍，宁亚辉等.关于《数据结构》课程与ACM-ICPC竞赛结合的探讨[J].计算机工程与科学，2014（S1）.

[7]芶生平，杨鹏，汪小平等.以ACM/ICPC竞赛为载体 探索课程体系建设与创新人才培养新模式[J].中国大学教学，2010（7）.

[8]ZHU Jie-ao， SUN Mian， LIU Xue， LI Hao. Learning Software Engineering through Experience of ACM-ICPC Training and Practicing Exercises[C].Proceedings of 2010 Third International Conference on Education Technology and Training（Volume 1），2010.11.

（编辑：李晓萍）