基于ACM-ICPC 模式的《算法设计与分析》课程改革与实践

韩丽霞，毕方明

（中国矿业大学计算机科学与技术学院，徐州221116）

0 引言

《算法设计与分析》课程是计算机科学专业的一门专业主干课程，该课程主要讲授经典的算法（包括递归与分治算法、动态规划算法、贪心算法、回溯算法、分支界限算法）的基本原理、实现方法和应用实例。通过该课程的学习，使学生熟悉算法复杂性分析理论和评价算法性能的标准，掌握基本的算法设计方法，培养学生的问题抽象和建模能力，能够针对具体的问题能进行特性分析，进而提出有效的解决方法，为学生进一步分析和解决计算机科学与技术领域的复杂工程问题奠定良好的基础。

ACM 国际大学生程序设计竞赛（简称ACM-ICPC）是由国际计算机协会（ACM）主办的最具影响力的大学生程序设计竞赛，被誉为计算机领域的奥林匹克竞赛。其中，ACM 对算法知识点的考核包括分治算法、动态规划、贪心算法、排序算法、回溯算法等，竞赛的目的是使得大学生能够通过计算机来充分展示其分析问题和解决问题的能力以及创新能力的培养。由此可见，《算法设计与分析》课程与ACM-ICPC 的目标是不谋而合的，将ACM-ICPC 竞赛模式结合到课程教学中，能有效地加深学生对知识的理解程度，增强学生分析问题和解决问题的能力，有利于激发学生学习和竞赛的热情。同时，基于ACM-ICPC 的课程改革对于高质量人才的培养具有重要的现实意义。

1 教学中存在的主要问题

《算法设计与分析》是面向设计的一门课程，旨在培养学生具体问题具体分析、抽象建模和算法设计的能力。要学好这门课，学生需要以高级语言程序作为工具，具有较好的高等数学、离散数学和数据结构基础。在教学过程中，我们发现，学生在学习该课程的过程中主要存在以下的问题：

（1）对于算法的基本理论知识，部分学生感觉枯燥、乏味，导致学习的兴趣不大；有些学生甚至出现“畏学”“厌学”的情绪，觉得自己“学不会”、“学不好”，造成被动学习、消极学习的局面；

（2）理论与实践脱节的问题在课程学习中是比较突出的问题，很多学生学而不能用。对于某个具体问题，能够设计求解的算法，但如何考虑问题操作对象的存储，编写代码存在不小的困难；

（3）对于算法知识的灵活应用是全体学生都亟待提高的能力。对于课本上给定的问题和算法，大部分学生能够理解和掌握求解算法的思路且编程实现，一旦问题模型发生变化，就很难独立设计求解算法。

综上所述，如何上好《算法设计与分析》这门课，给任课教师带来了巨大的挑战和考验，基于ACM-ICPC模式的教学改革将为《算法设计与分析》注入一针强心剂，有效地促进教学效果和实践水平的提高。

2 教学方法改革

针对教学过程中的诸多问题，课题组老师通过看视频、研讨会等手段对教学方法进行了系列调整，大体总结如下：

（1）对于《算法设计与分析》课程的几类算法，采用贴近生活的实例进行讲解，引导学生深入理解各类算法的基本思想、适用条件和求解步骤，从而消除学生对该课程的距离感和畏惧心，激发学生的积极性和热情。例如在讲解贪心算法时，选择日常生活中“售货员找零钱”作为引入，该问题寻找“找出的零钱张数最少”的找零钱方式。日常生活中，学生对该问题耳熟能详，非常轻松就掌握了贪心算法的基本思想和基本步骤，无形中增强了学生学习该课程的兴趣，消除了学生的“畏学之心”。

（2）在课堂教学过程中，以高级语言作为工具，采用离散数学进行模型抽象，根据算法的思想，选择有效的数据存储方式，从而实现高级语言、离散数学、数据结构和算法设计与分析的无缝衔接，从而将理论与实践有机结合。算法问题需要严谨的程序评判系统，将ACM-ICPC 的在线判别系统OJ 引入到《算法设计与分析》的课堂教学中来，布置OJ 系统在线作业，编程实现各类算法的经典ACM-ICPC 题目。这样做，将《算法设计与分析》的理论与实践有机统一。同时，对每次作业设置排行榜功能，学生通过排行榜可以及时查看其他学生的做题情况，进一步激励了学生学习的积极性和热情。

（3）对各类算法的基本思想、基本步骤讲解清楚外，需要加强算法之间的比较，帮助学生把所学的知识融会贯通，加深理解的程度。为此，可以采用讨论课的形式，让学生们以小组为单位，讨论回溯法和分支限界法，说明它们之间的相同点和不同点，对于同一个问题如何应用，分析它们的时间复杂性等，将学生的被动学生改为主动学习，让学生真正参与到课堂中来，成为课堂教学的主体。这也符合ACM 比赛中强调的最优、最快的宗旨。

（4）在教学方式上，主要采用启发式教学，引入ACM-ICPC 中“一题多解”的问题，鼓励学生“分析问题-抽象建模-数据存储-算法设计-复杂性分析”，进而提出改进的算法，达到灵活运用各类算法，“一题多解”的教学目的。通过这些训练，可以提高学生灵活应用算法的能力，培养学生的创新思维，也有助于培养学生之间的协作意识，增强学生触类旁通、举一反三的能力。

通过三年的教学改革，《算法设计与分析》课程的教学质量有显著的提高，学生学习该课程的信心和主动性都被明显带动加强，编程能力也有明显的提升，教学改革初见成效。

3 实践环节改革

在《算法设计与分析》课程新大纲中，添加了算法设计与分析实验课程，共计16 学时。

所有实验题目通过OJ 系统发布，学 生需要在规定的时间内把作业提交到OJ 系统中，由系统自动评判。在实践方面的改革主要体现在如下四个方面。

（1）从理论课中，选取各类算法中具有代表性的问题进行验证性实验，并进行初步的拓展，这部分实验内容由每个学生独立完成，OJ 系统会列出每个学生运行程序的相关信息。这样做，将理论教学与实践相结合，既可以加深学生对基本理论知识的理解，也可以有效地提高学生编程的能力，也有利于教学效率和教学质量的提高。

（2）参考ACM-ICPC 的三人小组制，将学生分为若干小组，将竞赛的算法题目引入课程，对课程内容进行基本的引申，与实践应用联系起来。通过小组讨论、分析、解决问题的形式，充分调动学生的积极性和参与性，锻炼学生独立思考的能力。此外，通过一题多解和对复杂性的分析，起到举一反三、触类旁通的作用，充分展现了学生的思维活力，突出团队合作精神，也有助于学生结合实际进行具体的应用

（3）实验课中设置提高题目，采用ACM-ICPC 中部分具有挑战性的算法题目作为加分题，鼓励学生设计更优、更快的算法进行求解。ACM-ICPC 中的题目都是原创性题目，需要学生综合运用所学的知识，不断通过编写程序来进行相应的建模和算法设计。既具有趣味性，又可以极大地激发学生自主学习的能力以及不断进行探索的精神。同时，提高题目的设置也有利于高质量人才的培养和选拔，为ACM-ICPC 队员的挑选提供了可靠的依据。

（4）将OJ 系统作业作为实验教学、检验学生成绩的主要手段。OJ 系统对学生完成的题目的数量、时间等均有统计，教师根据系统信息给出的实验平时成绩和测试成绩，最终给出《算法设计与分析》的实验成绩。值得一提的是，OJ 系统考虑到算法的运行效率分析、做题数量和完成时间，是比较公平的考核方式。

通过教学改革，将课堂讲授与实验讨论有机结合、竞赛与测试相结合，切实给学生提供了一个理论与实践的学习与锻炼平台，既加深了学生对理论课程的理解，也有效锻炼了学生的动手能力。从OJ 系统期末测试的成绩也可以看出，学生能运用所学的理论知识，对问题进行分析和算法设计，且对算法的复杂性分析能力也有显著的提高。通过实践教学改革，学生能够得到充分的实践锻炼，对算法设计方法的应用掌握的更牢固，也进一步培养了学生求真务实的科学态度。

4 结语

2018 年6 月和10 月，我院已成功举办了2018 年ACM 国际大学生程序设计竞赛全国邀请赛（江苏）和第43 届ACM/ICPC 国际大学生程序设计竞赛亚洲区域赛（徐州），获得了邀请赛以及亚洲赛金奖和银奖的好成绩。基于ACM-ICPC 模式的《算法设计与分析》课程的教学改革，将课程教学与竞赛有机地结合在一起，既激发了学生学习课程知识的兴趣，也大幅提高了学生的分析能力、动手能力、团队协作能力和创造能力，教学改革取得了良好的效果。