基于深度学习策略的算法设计分析类课程线上线下混合教学设计

董文永，邵艳玲，刘树波，郭 松

（1.武汉大学 计算机学院，湖北 武汉 430072；（2.南阳理工学院 计算机与信息工程学院，河南 南阳 473000）

0 引言

算法设计类课程的主要教学目的是学生掌握基本的算法设计技术，掌握算法的时间和空间复杂度分析，并通过常用的算法设计策略用某种特定的计算机语言解决实际问题。为实现该目标，需要学生进行大量的编程题目练习。实际上，仅靠传统物理课堂的讲解没有办法完成该任务，即使有上机实践类课程，学生往往停留在对程序设计语言语法的掌握或编译器的掌握上。另一方面，目前很多在线的MOOC 资源，题目设置比较传统，如选择题、判断题和一些简单的编程题。这些题目往往以考试为目的，不能以解决问题为出发点，题目设计比较粗糙，不能体现算法的精髓所在，更不能针对实际问题锻炼学生设计算法的能力。同时，很多学校都有自己的在线程序测评网站，比如武汉大学、北京大学、南阳理工学院等的OJ（Online Judge）系统。这些网站能够进行学生程序设计的训练、参赛队员的训练和选拔,但这些专用的在线评测系统局限于参加程序设计大赛的队员，普及面窄，造成资源的浪费。因此如何利用在线评测系统辅助算法设计类教学，在减轻教师工作量的同时，进一步规范课程的教学，使学生能够深度掌握算法的精髓，是算法设计分析类课程教学要解决的关键问题。

1 基于深度学习策略的线上线下混合教学模式

深度学习是一种主动探究性的学习方式，要求学生进行深度的信息加工、主动的知识建构、批判性的高阶思维、有效的知识转化与迁移应用及实际问题的解决。本研究正是把深度学习策略应用到算法设计分析类课程以开展线上线下混合式教学：在线上，除了可以预习或复习相关教学视频和PPT、进行题目练习测试以外，还可以展开讨论，协作学习；在线下，物理课堂以问题驱动为导向，教师进行问题的引导和深度分析探讨，面对面答疑解惑。让学生利用在线测试平台，以弥补物理课堂学时和空间的限制，把物理课堂延伸到线上来，并给师生提供个性化的学习交流平台。基于在线评测平台的设计主要包括算法设计分析课程内容、平台测试和讨论区。在线下课堂，教师通过案例进行问题提出，启发引导学生通过所了解的算法知识解决实际问题，引起学生的学习兴趣；在教师的引导下对案例进行分析研讨，提出解决方案并进行应用；对解决方案进行分析评价，逐渐增大知识理解的范围，可以激发学生的内驱力，促进学生反思，有利于加深新旧知识的联系与新知识的进一步理解与建构，达到深度学习的目的。

2 试题库的设计

在进行试题库的设计过程中，出题人要充分考虑各类学生的接受水平，因此试题库应包含若干难易程度不同的试题。图1 是武汉大学“千练万花”在线评测主系统问题Problem 界面。从图中可以看出题目的难易是不同的，其中“A+B”问题比较简单，能够通过的人数很多（300 人）。图2 描述了整个试题的具体细节展示，试题设计和目前国际竞赛试题接轨，包括试题描述、输入数据格式描述、输出数据格式描述，以及输入数据和输出数据样例。因此，整个试题库的设计需要符合算法描述规范，还要能够清楚地描述实际要解决的问题，可以看出题库的设计在整个在线平台中非常关键。

3 在线评测教学平台的设计

图1 武汉大学“千练万花”在线评测主系统问题Problem 界面

图2 问题样例

为了方便用户的使用，本研究的目标是设计并实现一个功能完备、高可用的算法设计分析类课程辅助教学系统。对于代码评测部分，目标是设计一个通用可扩展的代码评测核心，支持市面上的常见开发语言，并可以扩展支持部分对于教学有用的硬件描述语言或者汇编语言。对于作业方面，目标是设计一个便于使用的作业提交平台，并支持在线预览、打分、打包下载等功能，同时提供一种便于使用的交流或者通知手段。对于出题过程中存在的困难，目标是设计一个易于使用的试题编写平台。

该课程辅助教学系统采用浏览器/服务器（B/S）模式，学生与教师通过浏览器即可轻松使用本系统。系统模块之间通过JSON-RPC 来实现通信。服务器基于Docker 部署，网页前端使用Vue.js 框架来实现。系统包括前端网页展示和教学核心平台，教学核心平台包括Problem CI 试题维护、试题评测、比赛、作业、小组以及试题存储等子系统，教学核心平台中的试题维护系统、试题编辑系统、试题评测系统独立编写，试题存储使用Git 完成版本管理。

3.1 前端网页

前端网页采用单页应用模式。相比于传统网页，其牺牲首次加载时间以换取后续使用的流畅性，当用户在不同的页面切换时，仅需加载与页面直接相关的内容，无需下载已经在初次载入处理完毕的网页框架内容，从而降低用户消耗的流量。Problem CI 与“千练万花”平台均基于ElementUI 的用户界面，试题编辑系统考虑到未来可能发布客户端版本，使用更适合客户端的基于Vuetify 的Material 风格界面。当用户使用不同尺寸的屏幕时，均会自动调整布局以尽最大可能满足用户在不同设备上使用系统的需求。

3.2 “千练万花”教学核心平台

“千练万花”教学核心平台是整个教学系统的核心，承载了整个系统面向终端用户的全部功能，如试题阅读、代码提交，作业提交、批改，参加比赛、参加小组等，在高峰时期，需要承载极高的并发请求数量。

武汉大学现在对外有两个在线评测系统：面向所有人，供研究、训练、交流的WOJ 系统和用于大四“编程实践课”评测任务的WOJWeblearn 系统。由于维护、管理起来十分不便，同时大量重复的试题存在导致存储空间的浪费，为解决这些问题，“千练万花”教学核心平台对外使用“小组”作为基本单位，各个小组之间拥有较为独立的用户系统，包括完全独立的题库、评测、比赛、作业功能。用户使用现有账号即可登录使用，亦可以根据小组管理员设置加入小组。

3.2.1 Problem CI试题维护系统

Problem CI 即CI for Algorithm Contest Problems，即面向算法竞赛试题的持续集成系统，通过与Git 版本仓库深度集成以实现当试题产生改动，即可以主动触发相应的变化。

Problem CI 试题维护系统提供用户添加、编辑试题和更新等维护功能。当试题出错时，可以查看出错的原因，也可以便捷地返回到上一个正确的版本。版本管理概念的出现，极大程度提升了出题的鲁棒性。同时，试题维护系统无需关心试题的实现等数据，可以一键从Problem CI 中导入已经由Problem CI 编排好的HTML 格式的题面文档。在试题发生更新时，只需要重新导入试题，不用再次检查排版、时限、样例等是否与评测数据一致。另外，Problem CI 引入了名为“ACL Key”的子模块，用于控制试题的访问权限，以在不透露密码的情况下，方便地调用外部程序进行试题的操作，同时还可以撤销之前分发的ACL Key，在大赛场景下，可以充分保证试题的安全以避免未授权人员访问试题内容。

3.2.2 Final Judger试题评测子系统

Final Judger 的试题评测核心子系统包含试题编译功能、代码评测功能、试题测试功能3 个功能。当用户提交试题之后便触发提交子系统。提交子系统主要负责将用户的代码封装为Problem CI 的评测任务对象，并处理由Problem CI 回调得到的评测结果，并推送到用户前端。根据历史数据，用户提交数量远小于试题访问的数量，不会成为试题的瓶颈，但一个快速、稳定的提交结果推送仍然是有利于提升用户的使用体验。另一方面，用户代码在比赛过程中的安全极为重要，因此提交子系统还负责了极其复杂的用户访问权限控制，比如在比赛过程中，用户的提交不能被任何用户（包括自己）查看，也不能得到除了提交编译信息之外的信息，而在比赛结束后，比赛过程中的所有代码、结果都会公开，以方便用户之间的分享交流。

代码评测功能是在线测试平台的基本功能。在编写试题的过程中，往往会添加、删除评测数据，或是修改标程以实现更好的复杂度。在以往的试题编写过程当中，这一系列操作一般由人力完成，在涉及一定规模的比赛当中，单个试题的评测数据可能会多达百余组甚至数百组，这样大量的测试过程费时费力，同时由于多人协作，各人手上可能拥有的数据并不总是一致，这样就会带来漏测、误测的问题，轻则影响出题效率，重则导致试题数据出错。为了避免这一问题，在整合试题编译器和代码评测器的功能的基础上，开发除了试题测试功能，其向上对接Problem CI 试题仓库，向下对接Git 代码仓库，当有新的版本被同步到Git 时，试题测试模块即会收到Git 仓库的推送，并自动拉取试题，完成编译、测试的过程。在试题中，可以指定特殊的代码必须通过或者不通过，或者评测机必须返回代码出现了怎样的错误。在测试完成之后，该模块会将测试的结论以及测试过程中出现的问题上传到Problem CI 的数据库当中，以禁止或者推荐某一个试题版本成为最终使用的试题版本。

3.2.3 比赛子系统

无论是比赛或是平时涉及编程的作业，都需要比赛子系统的支持。比赛子系统的榜单采用了可扩展性的操作，计算在客户端完成。用户可编写一个适合特定的分数计算脚本以用于计算排名，除了用户名、排名之外，其他各列都能更改，如可以设计特定比赛专用的栏目，如“得分”“罚时”“奖励分”或者选手子集中的排名等，相比于市面上的类似系统大多使用服务器计算的方式，在客户端计算分数可以降低服务器的负载，同时给用户更方便的定制操作。

3.2.4 小组（域）子系统

小组（域）子系统是本辅助教学系统中极其重要的一个组成部分。不同于传统的在线评测系统，基于域的辅助教学系统可以充分实现评测基础设施的复用，使其在用户端体验近似于账号共享的分离系统。同时，相比于部分同类产品对比赛采用独立账号的做法，本系统允许用户绑定不同小组（域）中的同一账号。

对于前文中提到的部分聊天工具提供“公告”或“置顶”的功能，由于篇幅有限，难以提供长篇幅的消息的情况，本系统中允许教师在小组首页填写长篇重要文字，同时小组内尚未截止提交的作业、即将开始的比赛（考试）等，都将在相应的列表置顶以保证相应的曝光度，避免学生遗忘重要事项。

3.2.5 作业子系统

作业子系统是供教师在课程上布置作业使用，目的是为了方便教师评阅部分无法由机器评测的试题，在作业子系统中，教师可以创建、修改作业，也可以一键导出学生的作业提交，并自动打包为压缩文件，省去了传统作业提交工作流中学生—学习委员—教师/教辅这一路径，将学生提交的作业直接送达教师。

对于教师而言，一个常见的问题在于，纵然反复强调平时作业的按时提交，仍有学生忘记作业的完成日期，或者提交错误的文件名。为此，在本系统中通过设定严格的作业截止日期，与自动重命名来解决这些问题。当学生提交作业之后，他的作业将自动被重命名存储；当打包下载后，不同学生的作业也分文件夹存放；当同时收集多项作业时，也可以在作业后台看到每一个学生的提交状态。对于常见的作业类型，如PDF、图片、代码或者文本等，还可以直接在线上浏览批改作业，并导出成绩，既方便了师生使用，而常见的登分错误的问题也可以因此避免。

4 系统测试及结果分析

4.1 系统部署

本系统通过发布Docker 镜像和Docker Compose 部署配置文件，可以轻松地在数分钟之内搭建并部署一个完整地在线评测系统。通过进一步扩展，可以为整个系统实现高可用方案、高可用状态下的集群结构，如图3 所示。另一方面，通过引入持续集成（即CI）系统，对于系统源代码的任何修改都将实时地反馈到镜像当中，而当版本完成测试，功能较为稳定而错误较少的时候，即可直接发布新版本，真正实现了自动化部署，方便了系统的使用者测试或者更新。

图3 高可用实现方案

4.2 压力测试结果

本评测系统的压力测试为3 000 人同时在线的数据。系统部署在同一个服务器上。如图4 所示当使用单机部署时，本系统可以支撑超过3 000 人同时在线，并在2 分钟之内完成了25 万请求数，由于人数递增，可以得知在最后阶段系统承载了较测试前期更多的用户请求数。

相比于传统使用的在线评测系统，本系统将试题维护、评测工作从整个系统中独立出来，成为近乎完全独立的新系统。独立的试题维护工作带来了更高的安全性。众所周知，实现一个完全安全的计算机系统，成本最低的方案是使含有机密信息的计算机脱网运行。本系统通过将试题维护、评测工作独立，允许了用户在出题时使用独立的Problem CI 实例，当真正比赛时，再接入公开的“千练万花”系统运行，前后的切换不会让平台终端用户体验有所下降。

图4 “千练万花2.0”系统性能测试

另一方面，现有的许多开源在线评测系统缺乏一个易用的出题辅助工具，为了出题，教师往往需要复杂的命令行操作，而复杂的命令行操作对于非专业运维人员而言不甚友好，还带来了误操作的问题。此外，其他系统常常要求用户了解系统的评测规范细节。Problem CI 的试题编辑器虽然提供了复杂操作的能力，但对于大多数试题，用户不需要对评测原理有任何了解，只需要上传数据、选择比较器、设置时间限制、编写试题等必需的操作，即可构造一道合法的试题，简便的试题管理操作方便了教师的使用，还允许了学生用于日常自我训练、测试使用。真正实现了辅助教学系统中的“教”“学”两大功能。

5 教学效果

目前，该教学模式已经在武汉大学算法设计课程以及南阳理工学院C 语言程序设计等课程推广，其中在线评测系统可以用于平时的作业测试、竞赛以及考试，题库模块中包含编程题数据800 余条。自从2018 年度采用基于深度学习模式策略的算法设计分析类课程混合教学模式以来，普通学生学习算法和程序设计的热情高涨，课程的目标达成度明显提升且极大减轻了教师的工作量。

6 结语

为了实现算法设计分析类课程中学生通过常用的算法设计策略用某种特定的计算机语言解决实际问题能力，通过研究基于在线评测系统的算法设计分析类课程混合教学设计和实践，笔者提出基于深度学习策略的线上线下混合教学模式、试题库的设计方案以及开发了一个在线评测教学平台。通过教学实践证明，该课程设计方案适合算法设计分析类特征，能激发出学生的学习热情，提升广大学生的编程素养和课程目标达成度，也减轻了任课教师的工作量。