算法设计与分析课程教学方法

摘要：“算法设计与分析（双语）”是北京林业大学计算机科学与技术专业的专业核心课程。根据课程的教学目标，提出“以赛启教”的教学实践思路，从教学内容、教学方法和考核方式３个方面加以实施。在教学内容方面，对国内外知名院校相关课程进行了调研分析，并参考了竞赛常用算法，精选了教学内容；在教学方法方面，利用竞赛平台在线评判系统，在教学的每个环节都贯彻了“实践最重要”的教学理念；在考核方式方面，结合竞赛形式提出了一套有效的考核评价体系。“以赛启教”的教学实践促进“算法设计与分析（双语）”课程完成从知识型向能力型教学的转变，并反哺了竞赛。

关键词：算法设计与分析；程序设计竞赛；能力型课程；工程实践；过程化考核

在计算机科学与技术领域，算法至关重要［１］。正如经典巨著《ＴｈｅＡｒｔｏｆＣｏｍｐｕｔｅｒＰｒｏｇｒａｍ－ｍｉｎｇ》的作者、１９７４年图灵奖获得者ＤｏｎａｌｄＥＫｎｕｔｈ［２－３］所说“Ｍｙｆａｖｏｒｉｔｅｗａｙｔｏｄｅｓｃｒｉｂｅｃｏｍ－ｐｕｔｅｒｓｃｉｅｎｃｅｉｓｔｏｓａｙｔｈａｔｉｔｉｓｔｈｅｓｔｕｄｙｏｆａｌｇｏ－ｒｉｔｈｍｓ”（计算机科学就是算法的研究），而算法研究的核心就是算法设计与分析。北京林业大学计算机科学与技术专业在２０１９级本科人才培养方案中设置了“算法设计与分析（双语）”专业核心课程，该课程强调夯实编程基础，提升学生的专业能力和素养［２］，为各行各业输送工程应用创新型人才［３］。

一、“以赛启教”的“算法设计与分析

（双语）”课程教学的思路近１０年来，北京林业大学每年都组织学生参加国际大学生程序设计竞赛，这是一项已经举办５０余年的全球大学生顶级程序设计竞赛，该赛事的核心是考察学生的算法水平。受竞赛的启发，“算法设计与分析（双语）”课程组提出了在该课程教学中开展“以赛启教”的教学构想。首先，充分考虑“算法设计与分析（双语）”课程与先修课程“数据结构”的衔接，调研分析国内外知名院校相关课程教学内容的安排，精选教学内容，并增加竞赛中出现频率最高的算法内容。其次，鉴于竞赛的形式是使用计算机编程解题，“算法设计与分析（双语）”课程组在教学方法上注重实践教学，在每个教学环节都始终贯彻“实践最重要”的理念。最后，在实验、期中考试和期末考试的评分标准上参考竞赛中的排名方案，增设大作业考核。

二、“以赛启教”的“算法设计与分析（双语）”课程教学的实践

（一）优化教学内容

北京林业大学“算法设计与分析（双语）”课程组调研了国内外知名高等院校计算机专业该门课程的教学内容设置情况，这些高等院校包括２０２１年度ＱＳ全球大学计算机专业排名前三［４］的Ｍａｓｓａｃｈｕ－ｓｅｔｔｓＩｎｓｔｉｔｕｔｅｏｆＴｅｃｈｎｏｌｏｇｙ［５］、ＳｔａｎｆｏｒｄＵｎｉｖｅｒｓｉ－ｔｙ［６］、ＣａｒｎｅｇｉｅＭｅｌｌｏｎＵｎｉｖｅｒｓｉｔｙ［７］和国内的北京大学、北京航空航天大学和中山大学，见表１。同时，参考了竞赛中出现最频繁的算法，确定了适合北京林业大学计算机科学与技术专业本科生的“算法设计与分析（双语）”课程教学内容，见表２。教学内容优化主要考虑了以下５点。①纳入所有高等院校都会涉及的内容，这些也是“算法设计与分析（双语）”课程最基本的内容，包括算法分析、分治、动态规划、贪心和ＮＰ完备性等［８］；②增加其他在竞赛中出现频率很高的算法内容，包括并查集、线段树和字符串算法（字典树、ＡＣ自动机）［９－１０］；③对照“数据结构”课程，对教学内容进行排重，“数据结构”课程涉及的最小生成树、排序和查找、二叉（平衡）查找树和图基础算法内容，在“算法设计与分析（双语）”课程教学中不再重复讲授［１１］；④增加智能算法模拟退火内容，目的是让学生对随机算法有一个初步的认识；⑤删除难度较高或者其他课程涉及的内容，比如网络流、密码学相关算法、博弈论、近似算法、计算几何、快速傅里叶变换和遗传算法等。

（二）采用注重理论联系实践的教学方法

“算法设计与分析（双语）”课程的教学主要包括理论教学和实验教学。为了对学生进行综合性实践训练并提高学生的工程素养，“算法设计与分析（双语）”课程组在每个教学环节都始终贯彻“实践最重要”的教学理念。１．以问题为驱动的理论教学方法“算法设计与分析（双语）”课程教学的一个普遍现象是重知识、轻能力，理论与实践脱节，导致许多学生虽然掌握了算法的理论知识，但代码量严重不足、写程序非常生涩、编程求解问题时依然无从下手。为了打破这样的现状，“算法设计与分析（双语）”课程组设计了以问题驱动的理论教学方法，见图１。下面以动态规划专题为例详细介绍以问题驱动的理论教学方法的实施流程：首先，用比较简单的寻宝问题（又名数塔问题，见图２）作为引例展开思维挖掘，从最优子结构到重叠子问题到状态迁移方程再到递归和递推，逐步介绍动态规划的核心思想。其次，在学生理解了这些思想之后，在课堂上提出若干道经典的动态规划问题，包括嵌套盒子问题、硬币问题、地铁里的间谍、单向旅行商、０－１背包、最长上升子序列和最长公共子序列等。之后，带领学生阅读这些题目，分析问题并设计满足题目要求的算法。最后，编程求解这些问题，使得学生能够掌握这些经典动态规划问题的解法。２．基于竞赛的实验教学方法在国际大学生程序设计竞赛和中国大学生程序设计竞赛中，参赛队伍需要使用给定的电脑，在５个小时内编程求解１１～１３道题目，比赛过程中选手提交解题代码到在线评判（ＯｎｌｉｎｅＪｕｄｇｅ，简称ＯＪ）系统，在线评判系统实时返回评判结果（包括ａｃｃｅｐｔ－ｅｄ，ｗｒｏｎｇａｎｓｗｅｒ，ｒｕｎｔｉｍｅｅｒｒｏｒ，ｔｉｍｅｌｉｍｉｔｅｘｃｅｅ－ｄｅｄ，ｍｅｍｏｒｙｌｉｍｉｔｅｘｃｅｅｄｅｄ等）。选手可以实时看见所有队伍的排名，解题越多的队伍排名越靠前，解题数相同时，解题用时越少排名越靠前。为了支撑北京林业大学程序设计竞赛集训队的训练，集训队在２０１０年建设了北京林业大学在线评判系统（ｗｗｗ．ｂｊｆｕａｃｍ．ｃｏｍ），该系统已经历３次迭代更新。“算法设计与分析（双语）”课程的实验教学在该系统上开展。每次讲完课程的理论知识之后，教师在系统上创建对应的专题实验，专题实验包括５～８道难度不等的题目。实验开始后，学生在系统上提交代码求解这些题目，实验过程中学生能实时看见自己的解题排名（和竞赛规则一样，解出题目越多排名越靠前；当解题数相同时，用时越少排名越靠前）。实时排名能起到很好的激励作用，激发学生探究进取的精神。此外，在线评判系统还集成了代码查重功能，再结合人工查重，很大程度上避免了实验抄袭现象。使用计算机编程解决问题要求代码百分百精确，不精确的代码不能通过在线评判系统的评判，这有助于培养学生缜密的逻辑思维和细致的观察能力，让学生感悟到程序设计的优美，促进学生养成良好的编程习惯。另外，教师还会在每次实验结束后给出各大知名在线评判系统上和本次实验专题知识点相近的题目编号，这些题目可以作为课后训练和拓展使用，有助于学生对所学知识融会贯通举一反三。３．综合性工程实践训练方法“算法设计与分析（双语）”课程教学的另一个问题是不能将知识串联起来。为了进一步培养复合型、工程型和创新型人才，该课程增设了大作业，以训练学生的综合性工程实践能力。为了增加趣味性，大作业一般为游戏类工程项目，比如“贪吃蛇”等。在大作业环节，教师首先给出用英语描述的大作业任务书和大作业报告模板；然后，学生按照任务书的要求，查阅中英文资料，分析、设计一系列算法解决工程问题，再编写界面封装算法，实现和用户的交互，并把整个过程用文档描述出来；最后，学生提交工程的源文件、用英语写的说明文档及大作业报告。

（三）完善课程考核评价体系

目前，国内算法课程的考核成绩主要包括平时成绩和期末考试成绩。其中，平时成绩占４０％，期末考试成绩占６０％。期末考试一般为笔试，导致的结果往往是背得越好得分越高而不是编程越好得分越高。另外，期末考试成绩占比过大，过程考核不足。为了使北京林业大学“算法设计与分析（双语）”课程的考核结果能真正反映学生的编程水平，“算法设计与分析（双语）”课程组完善了该课程考核评价体系，见表３。其中，期中考试和期末考试均为开卷考试，学生不需要死记硬背，而是要能够运用学到的知识编程解决问题，这样才能真正考核学生分析问题、设计算法以及编程实现算法的能力。表３中的实验、期中考试和期末考试均在北京林业大学在线评判系统上进行，每位学生都能实时看到所有同学的解题情况和排名，真正做到了考核过程公平公正公开。在线评判系统考察的是学生的编程能力，因此考核结果能真实反映学生的编程水平。此外，除了分析和设计算法编程求解问题的考核，课程组还设置了大作业，这样能更全面地考察学生利用算法知识开发工程项目的能力。

三、“以赛启教”的“算法设计与分析

（双语）”课程教学实践的效果经过一年多的探索，“以赛启教”的“算法设计与分析（双语）”课程教学实践初见成效。

（一）由知识型课程教学转向能力型课程教学

通过贯彻“实践最重要”的教学理念，在“算法设计与分析（双语）”课程教学中，教师让学生参与到每个教学环节，使学生掌握了所学算法的精髓并把算法应用到问题的求解中，提高了学生程序设计、算法设计与分析、逻辑推理、数学建模和工程实践的能力。通过实施一套更注重编程实践的过程化考核机制，使“背得越好得分越高”变成了“编程越好得分越高”，打破了课程重知识、轻能力的问题，促进了课程由知识型课程向能力型课程的转变。图３为北京林业大学２０２０—２０２１学年“算法设计与分析（双语）”课程学生成绩分布和做题数目的对应关系。可以看出，学生的成绩和做题数目呈正比关系，做题数目直接反映了编程能力，这就印证了该课程的考核机制，即“编程越好得分越高”。经统计，平均每位学生在在线考评系统上做出的算法编程题（包括实验题和课外练习题）数目为１１９道，较传统教学模式有了很大提升，这说明考核机制能有效激励学生的编程积极性。

（二）课程教学反哺竞赛

通过“以赛启教”的教学实践，学生接受了基于竞赛的实验教学方法，学生在实验中编写程序，培养了对竞赛的兴趣，最终也反哺了竞赛。近年来，北京林业大学参加国际大学生程序设计竞赛、中国大学生程序设计竞赛和团体程序设计天梯赛的学生人数明显增加，也获得了较好的成绩。以２０２０—２０２１年为例，１７８名学生参加了上述３个程序设计竞赛的校内初选，经过多轮选拔，５２名学生参加了正式比赛，共获得部级一等奖１次、部级二等奖６次、部级三等奖１９次和省部级二等奖３次。总之，“以赛启教”的教学实践有效提升了学生的算法设计与分析能力和编程能力，促进了课程教学由知识型课程向能力型课程的转变。但和知识型课程的传统教学模式相比，这种教学模式由于更加强调实践，学生需要通过编程解决问题，这就要求学生具有一定的编程基础。具体地说，学生需要在上课前预习教师提前发的课件，上课时认真听讲、参与讨论，理解理论知识，掌握每道题目的解题思路，并在课后完成课上每道题目的代码实现，这样才能在实验课上编程解出题目，学生也才能顺利地通过考核。如果学生的编程训练不够，某个环节没能跟上进度，那么学习该课程将会非常困难。针对这些问题，需要进一步强化课程的激励导向，减少编程压力带给学生的懈怠情绪。为了打破“算法设计与分析（双语）”课程重知识、轻能力的教学现状，“算法设计与分析（双语）”课程组提出了“以赛启教”的教学实践思路，激发了学生学习计算机领域专业知识与技能的兴趣，培养了复合型、工程型和创新型专业人才。

作者：徐艳艳 李冬梅 陈志泊 单位：北京林业大学信息学院