英语原文共 35 页，剩余内容已隐藏，支付完成后下载完整资料
A Survey on Online Judge Systems and Their Applications
摘要：
在线评判系统是对用户提交的算法源代码进行可靠评估而设计的系统，然后在代码同类环境中进行编译和测试。在线评判在各种应用中越来越受欢迎。因此，我们想回顾一下这些系统的现状。我们根据它们的主要目标将它们分类为支持组织竞争性编程竞赛的系统;增强教育和招聘流程、帮助解决数据挖掘挑战的系统;在线编译器和集成为其他定制系统组件的开发平台。此外，我们还介绍了在线评判系统的正式定义，并总结了该系统所支持的常用评价方法。最后，我们简要讨论Optil.io平台，该平台已经提出了一种用于解决复杂优化问题的在线评判系统，并对利用该平台进行的比赛结果进行了分析。该竞赛证明，通过众包概念增强的在线评判系统可以成功地应用于准确有效地解决复杂的工业和科学驱动的挑战。
关键字：在线评判，众包，评估即服务，调整，竞赛
1、介绍
1970年,当德克萨斯农工大学举办首届ACM国际大学生程序设计竞赛(ICPC)时，没有人会想到，几十年后，它将成为世界上规模最大、最负盛名的程序设计竞赛。2015年，来自近3000所大学和102个国家的4万多名学生参加了这一竞赛的区域阶段。在持续5个小时的比赛中，参赛者要解决8到13个算法问题。获胜者是最先解决最多问题的团队。该竞赛环境的关键组件是一个自动验证参赛者提交的解决方案是否正确的系统。它根据在预定义的测试集上执行所获得的结果来评估所提交解决方案的正确性。它还验证解决方案是否超出了资源利用限制(例如时间和内存)。在进行评估的基础上，所有参与者的在线排名将在正在进行的比赛中实时计算和呈现。
自从ICPC的第一次决赛以来，许多其他需要类似自动评判系统的算法竞赛已经开始了。其中最重要的可能是1989年首次举办的国际信息学奥林匹克竞赛(IOI)。它与ICPC类似，但专门面向中学生。上述比赛的最大区别是:参赛者单独解决问题，而不是团队合作;IOI考虑的问题数量低于ICPC;在IOI中，参与者收到每个提交的解决方案的部分分数，而不是在ICPC中应用的二进制分数(每个解决方案只被视为正确或不正确)。最受欢迎的编程比赛使用的基本规则和评分函数的详细信息由Cormack等人发布(Cormack等人，2006)。
IOI的重要补充作用是建立一个由致力于组织编程竞赛的人组成的国际社区。它的一项重要活动是建立《Olympiads in Informatics》期刊，该期刊每年出版提交给与IOI同时举办的会议的论文(Dagiene等人，2007年)。它提供了一个讨论在国家和国际信息学奥林匹克竞赛期间获得的经验的国际论坛，包括准备有趣的问题和支持其组织的软件。如前所述，这些软件中最重要的条目是自动评估参与者提交的解决方案的系统;这种系统被称为在线评判系统。在线评判一词是由Kurnia、Lim和Cheang在2001年首次提出的，它是一个在线平台，支持对源代码、二进制文件甚至文本输出的全自动、实时评估(Kurnia等，2001年)。然而，在线评判系统的发展历史要长得多，可以追溯到1961年，当时它出现在斯坦福大学(Forsythe and Wirth 1965;Leal和Moreira 1998)。
在设计和实现在线评判系统时，需要考虑许多重要因素。关键问题是系统的安全性。在线评判的概念假设用户提交解决方案为源代码，有时甚至是可执行文件，这些文件通常会在基于云的基础架构中进行下一步评估。在线评判的设计者应该确保系统能够抵抗大范围的攻击，如遭遇长的编译时间、修改测试环境或访问受限资源。有关在2006年斯洛伐克编程比赛中可能的攻击类型和针对这些攻击的保护方法的详细说明，请参见(Forisek 2006b)。不幸的是，尽管上述威胁的原因仍未改变，但上述论文中提出的安全威胁解决方案大多已过时。目前，避免这些问题的最流行的方法依赖于在线评判系统(Yi等，2014年)管理的专用沙箱中提交的解决方案的执行，如虚拟化、LXC容器(Felter等，2015年)和Docker框架(Merkel 2014)。这些方法可以显著提高系统的安全性和可靠性。
在开发此类系统时应该考虑的另一个重要方面是执行时间的测量精度。单个测试用例的执行期限通常是用毫秒, 因此评估期间使用的性能分析方法应足够灵敏并具有确定性，以精确地区分这么小的时间，确保针对特定测试用例的相同代码的连续执行的可重复测量。可以使用多种方法来度量处理时间，比如使用简单的命令行工具、分析硬件性能计数器、代码检测甚至代码采样。每种方法的应用都有不同的优点和缺点，应该意识到这些优点和缺点与测量精度、时间开销和可用的集成方法有关(Ilsche et al. 2015)。
在所有在线评判系统中，要求之一是应在一致且可靠的服务器基础结构中评估用户提交的解决方案代码。因此，这些系统被开发为平台即服务(PaaS)云计算服务，因为这样一个高度交互的系统的可伸缩性是至关重要的，特别是在竞争截止日期临近和提交的数量迅速增加的情况下。因此，利用并发和并行处理的体系结构通常可以保证此类系统的效率。Drung等人(Drung et al. 2011)详细分析了在线评判对对称多处理(SMP)环境的利用情况。
最后，不仅软件本身很重要，系统中存储的问题描述和准备好的测试用例的质量也很重要。Forisek指出作者的问题,在比赛时自动计算如ACM ICPC IOI应特别注意问题的类型和测试用例的准备。他证明了使用启发式算法可以轻松解决某些类型的问题，例如子字符串搜索。此外，他还提出了一些ICPC和IOI竞赛中的问题，可以使用一般不正确的算法解决这些问题，并且仍然获得很好的评估分数。此外，Mani等人(Mani et al. 2014)注意到，在线评判输出的呈现方式也非常重要。特别是教育机构在课程中使用的在线判断系统中提供的评估摘要应易于阅读和理解。
在线评判系统中经常出现的问题一般被归类为组合问题。组合问题依赖于发现满足特定约束条件的离散变量的值。它们分为决策问题(必须验证所提供的解决方案是否存在)和搜索问题(必须找到解决方案)。搜索问题的一个特殊情况是最优化问题，我们必须找到满足某个目标函数的最优解。组合问题非常有趣，因为它们直观上是可以理解的，但是解决它们通常具有挑战性。上述观测结果被证实为各种组合问题，并成为计算复杂性理论兴起的一个原因。该研究领域关注的是这类问题的分类，考虑到寻找解决方案的过程是多么复杂。在线评判系统中发布的问题通常可以在多项式时间内解决，并且对找到解决方案所需的处理时间的最大限制进行了调整，以确保每个被考虑的测试用例都能找到最优解决方案。虽然这些系统也可以用来评估在处理时间限制内只能找到局部最优的更复杂的问题，但是目前可用的在线评判都不能简单地处理这些问题。最著名的比赛是法国运筹学协会组织的ROADEF挑战赛，这项挑战每两年进行一次，它的主要目标是解决与业务伙伴协作提出的一些工业驱动的问题，并辅以现实的测试用例。还有其他一些专门竞赛，通常以更具体的主题为重点,例如, 在国际自动规划和计划会议（ICAPS）期间组织的国际规划竞赛着重于解决方案实例的规划者的实施以规划域定义语言（PDDL）格式定义的规划问题。另一个例子是关于计算机体系结构竞赛的JILP研讨会，参与者可以解决与优化计算机硬件或基础结构所使用的算法参数有关的问题。
上述竞赛采用了一种称为众包的非常有效的技术来解决实际的优化问题。众包外包以公开电话的形式向大型人员网络工作。在优化挑战的情况下，调用的主题与优化问题相关，潜在的参与者网络包括通过Internet分组在一起的感兴趣的程序员和科学家。虽然众包的概念至少在18世纪就已经被直观地应用，但直到2006年Jeff Howe才正式定义它。21世纪的前15年是众包快速发展的时期，这得益于互联网的普及。利用众包成功解决行业挑战的最好例子是Kaggle平台。它是一个门户网站，数据挖掘问题在此发布，然后由参与竞争的外部专家解决。2016年，Kaggle完成了34项比赛，总奖金额达1116万美元。参赛队伍的数目在50至3500支之间。假设参加单个竞赛的团队平均数量为500，团队的平均规模为3，每个人解决问题的平均时间最多为3天，从而产生135,000天或370人年解决行业问题的时间。
Kaggle平台主要关注与数据科学概念相关的数据挖掘问题，这一概念最近很流行。然而，各种优化问题的解决方案也可以实际应用，例如来自运筹学领域的问题。因此，迫切需要开发高效的算法，以通过弹性社区在安全可靠的环境中求解它们。在本文中，我们将回顾在线判断系统领域的最新技术，并简要讨论以Optil.io平台为例的此类系统，该平台的设计着眼于应用众包解决复杂的优化问题。这实现了在线评判概念，该概念利用目标函数而不是二进制评估来对提交的解决方案进行排名。
本文的范围如下：由于文献中没有在线评判系统的正式定义，因此，我们决定填补这一空白以阐明进一步的分析。接下来，我们对现有的在线评判系统进行调查，重点放在潜在的应用程序上，并简要介绍每个系统。这些类型的系统的多样性是如此之大，以致于基于应用程序的分类对于感兴趣的从业者而言非常重要。我们主要关注支持评估用于解决组合问题的算法的系统。首先，这是因为，从理论的角度来看，它们是基本的问题类型；第二，它们包含了许多数据挖掘问题；第三，此类系统最常解决这些问题。此外，我们总结了这些系统支持的通用评估方法。最后，基于对使用Optil.io平台进行的比赛的讨论，我们简要演示了在线评判系统的潜在应用。对该系统的应用结果进行简短讨论，不仅可以使您对本文中描述的概念有更广泛的了解，而且还可以使他们更深入地了解在线评判系统的设计和开发的实际意义。我们相信这样的评论，再加上在线评判系统的示例应用，对于许多希望在自己的研究中使用在线评判系统的科学家，或者想将其用于教育目的的老师来说可能会很有趣。
2、在线评判系统
总的来说，在线评判系统的目标是对分布在世界各地的用户提交的算法进行安全、可靠、持续的、基于云的评估。为了更好地理解本文的范围，我们将首先定义一个评估程序，这是至关重要的，应该由任何在线评判执行，至少是部分执行。
定义2.1(评估程序)。评估程序包括三个步骤:(1)提交，(2)评估，(3)评分
在提交阶段，如果需要，将编译提交的代码，并验证它是否可以在同类评估环境中成功执行。在成功的验证之后，每个提交都基于特定于问题的测试用例集，在一致的基础架构上进行可靠的评估。对于特定提交的每个测试用例的执行，验证是否：
(1)执行过程没有出现错误
(2)没有超出任何特定于问题的资源限制
(3)得到的输出符合问题定义中描述的规则
最后，根据所有考虑的测试用例的结果计算提交的汇总分数。常用的评判程序的详细定义见第3节。我们将各种在线平台视为广义上的在线评判，包括通常在基于云的环境中支持任何评估过程阶段子集的所有系统。定义3.6第3节提供了在线评判的正式定义。
2.1 方法
在文献中，我们可以找到各种使用在线评判系统对比赛进行分类的尝试，以及在这种环境下解决的问题。2006年，Pohl提出了第一个简单的分类，考虑了与竞赛风格、持续时间、评分、提交程序和参赛标准相关的标准。在2014年，Combrsquo;efis和Wautelet提出了另一种分类方法，主要针对编程比赛的情况以及比赛中解决的问题。2015年，Nrsquo;emeth等人用几个新的标准改进了这个分类，更深入地描述了比赛，描述了对教育视角至关重要的编程练习类型和在线评判系统的特征。然而，所有这些审查的范围仅限于单一的应用程序，无论是在教育领域，还是在组织编程竞赛。到目前为止，还没有人根据潜在用户的兴趣对在线评判系统进行分类。这样的分类应该是该系统的主要目标，并且对于寻找满足其需求的在线评判系统的用户非常有用。这就是为什么我们决定把这个标准作为区分在线评判系统的关键。根据这一标准，我们区分了六类集成在线裁判系统的系统。最大级别代表在线平台，致力于分享在编程竞赛(类似ACM icpc)和信息学奥林匹克竞赛中解决的挑战。其他类型的系统有助于教育目的、员工招聘、解决数据挖掘问题的专门算法的评估，以及作为在线编译器的关键组件的集成(允许用户在线编译任意代码)。最后，我们介绍了一类开发平台，它们提供了一个在线评判组件，可以简单地在定制应用程序中使用。在某些情况下，很难应用这样的分类，因为有几个系统可以被认为是多个组的成员。在这种情况下，我们确定了服务的主要目标，并对其进行分类。这篇文章的目的是提供一个教程，展示广泛的在线评判系统，这些系统是基于使用科学网、谷歌学者和Scopus索引进行的广泛文献综述而编写的。此外，我们详细地审查了《Olympiads in Informatics》上发表的绝大多数奥林匹克竞赛文章，并在互联网上查询了这些系统的信息，即使它们尚未发表。对于所有的查询，我们使用了以下关键字集:在线评判、在线评判系统、自动程序评分和自动评分编程。学生作业评估的领域已经在许多著名的评论文章中被广泛探索，这些论文根据潜在的应用来描述这些系统，例如，教学用例。为了确保在线评判可能的应用程序的完整性，我们从面向应用程序的角度选择了最全面的系统作为这一类别的代表。
遵循准备系统文献综述的指南，我们定义了以下验收标准，所有这些标准都应该被评判中考虑的系统所满足;即系统:
1)支持的任何子集评价过程阶段
(2)能够评估算法,用于解决组合问题
(3)有英语,或者是用英语发表的一篇文章中描述的一些杂志或会议论文集
(4)是公开的(免费或商业的基础上)
(5)正常运作,即它应该提供一种可能性，为2017年6月通过它提供的至少一个问题注册和提交解决方案。
本文对在线裁判系统进行了分类，重点从用户的角度总结了其可能的应用。对于我们在文献中找到的每个在线评判系统，我们选择了两到五个最直观的使用场景。然后，对于前面确定的每个使用场景，我们计算一个简单的覆盖率系
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[235306]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
