【PHP开源代码栏目提醒】:网学会员为需要PHP开源代码的朋友们搜集整理了本科生毕业设计(论文)文献综述 - 讲义教程相关资料,希望对各位网友有所帮助!
本科生
毕业设计
论文文献综述 2012 届
论文题目 多类在线程序评判系统分析与实时测试 学生姓名 石兆斌 学号 0804011010 专业 计算机 班级 计081 指导教师 陈根方 职称 副教授 杭州国际服务工程学院信息科学与工程学院教学部制 文献综述基本要求 一、文献综述 含本选题国内外研究现状、研究主要成果、发展趋势、存在问题等内容字数不少于3000字力求内容切题具综合归纳性 二、查阅中外文献资料目录 所查阅的中外文献资料不得少于10篇含作者、书名或
论文题目、出版社或刊名、出版年月或期号及页码等未经本人查阅的文献资料目录不得列上 指导教师意见 该同学认真学习了广泛使用的ACM/ICPC程序设计竞赛及其的发展与在线评测系统测应用分析和总结了
常用的在线评测系统的功能和特点分析了它们的设计思路和方法为以后的工作打下了良好的基础。
指导教师签名 年 月 日 一、文献综述 1. 引言 在线评测系统Online Judge System一般简称OJ是一个为程序设计竞赛爱好者和ACM/ICPC国际大学生程序设计竞赛训练队伍提供训练及交流的平台同时也可以为程序设计语言、数据结构、算法等
课程提供
作业练习、实现及检测的平台对每个由评测系统展示的题目接收用户提交的源
代码在编译执行后将用户程序的输出与系统的标准输出进行比较并给出用户程序运行和比较的结果从而判断用户提交的源
代码是否正确。
目前国内外已有类似网上评测系统其中国外著名的网上评测系统有西班牙的UVA Online Judge、俄罗斯的Timus Online Judge国内著名的网上评测系统有PKU Online Judge北京大学和ZJU Online Judge浙江大学。
国内计算机专业培养的学生理论功底一般会很好但实践能力总是略显不足从而无法在科研学术领域及工业界有较强的竞争能力。
Online Judge正式设计用来改变这一现象巩固学生的数据结构知识和算法设计能力。
提高学生对计算机的认识。
2. ACM/ICPC国际大学生程序设计竞赛简介 ACM国际大学生程序设计竞赛ACM International Collegiate Programming Contest or ACM-ICPC是由美国计算机协会ACM主办的一项旨在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的年度竞赛。
经过近30多年的发展ACM国际大学生程序
设计竞赛已经发展成为最具影响力的大学生计算机竞赛。
赛事目前由IBM公司赞助。
ACM-ICPC以团队的形式代表各学校参赛每队由3名队员组成。
每位队员必须是在校学生有一定的年龄限制并且最多可以参加2次全球总决赛和5次区域选拔赛。
比赛期间每队使用1台电脑需要在5个小时内使用C、C或
Java中的一种编写程序解决7到10个问题。
程序完成之后提交裁判运行运行的结果会判定为正确或错误两种并及时通知参赛队。
而且有趣的是每队在正确完成一题后组织者将在其位置上升起一只代表该题颜色的气球。
最后的获胜者为正确解答题目最多且总用时最少的队伍。
每道试题用时将从竞赛开始到试题解答被判定为正确为止其间每一次提交运行结果被判错误的话将被加罚20分钟时间未正确解答的试题不记时。
例如A、B两队都正确完成两道题目其中A队提交这两题的时间分别是比赛开始后1:00和2:45B队为1:20和2:00但B队有一题提交了2次。
这样A队的总用时为1:002:453:45而B队为1:202:000:203:40所以B队以总用时少而获胜。
与其它
计算机程序竞赛例如国际信息学奥林匹克IOI相比ACM-ICPC的特点在于其题量大每队需要5小时内完成8道题目甚至更多。
另外一支队伍3名队员却只有1台电脑使得时间显得更为紧张。
因此除了扎实的编程能力良好的团队协作和心理素质同样是获胜的关键。
赛事由各大洲区域预赛和全球总决赛两个阶段组成。
各预赛区第一名自动获得参加全球总决赛的资格。
决赛安排在每年的3-4月举行而区域预赛一般安排在上一年的9-12月举行。
一个大学可以有多 支队伍参加区域预赛但只能有一支队伍参加全球总决赛。
全球总决赛第一名将获得奖杯一座。
另外成绩靠前的参赛队伍也将获得金、银和铜牌。
而解题数在中等以下的队伍会得到确认但不会进行排名。
网址 http://icpc.baylor.edu/icpc/ 除ACM-ICPC程序设计竞赛外还有Google?? Code Jam、TopCoder、百度之星程序设计大赛、英特尔杯全国计算机多核程序设计大赛、Imagine Cup 微软全球大赛、ICFP程序设计竞赛等
程序设计竞赛这些竞赛都采取类似的评判机制各有各的特点。
3. 源
代码评测简介 程序设计竞赛平台采用源
代码评测技术.源
代码评测一般分为手工评测、和自动评测后者又可分为在线评测和离线评测两种。
当手工评测只能离线完成时自动评测能够离线或者在线评测。
在最后期限之前一个离线自动评分机将获取提交否则什么都不做。
当最后期限到达它将开始检查所有收到的提交并且产生这些提交的判断报告。
相反在最后期限前在线自动评测会获取提交并且立即产生判断
报告允许学生决定他们是否希望对这个
问题有其它的尝试以获得更好的分数。
4. 源
代码评测机制 通常情况下的实现方式是服务器后台运行守候程序每一个时间间隔查询一次数据库如发现有提交纪录则启动评判进程进行相关题目的评判。
每道题目均对应的数据输入输出文件开始时评判进程启动一个子进程编译运行用户提交上来的程序当程序启动时计时在时间允许范围之内如果其得到了正确答案则修改数据库令其status为Accepted如果答案错令其status为Wrong Answer如果运行异常等则向该进程发出SIGKILL信号强行中止该进程把数据库记录进行相应的修改。
流程图如下 守护进程等待一定间隔时间是否有提交 启动评判进程编译用户程序是否通过编译重定向输入输出设置运行权限设置资源限制运行用户程序接收输出数据与标准输出数据比较把记录写入数据库 是是否否 在另外一些系统上如POJZOJ采用了事件驱动的方式当有用户提交源
代码到服务器上后 就启动一个进程/线程去按照如上流程图所示的方式进行测评。
5. 评测系统的实现 早期的一些测评系统几乎都是在Linux平台下实现的如浙江大学的ZOJ哈尔滨工业大学的HIT OJ武汉大学的WOJ等均是在Linux下使用C语言编程开发读取系统表获取进程资源占用信息这类系统中大多数还需要使用Perl和SHELL编写一些系统命令配合使用。
大多数采用这样的架构Linux MySQL GCC Apache
PHP 然而特别的是国内著名的在线判题系统POJ北京大学ACM在线判题系统是在Windows下实现的它的实现方式后端采用C利用Win32API获取进程资源占用信息。
在前端用户界面部分使用JSP实现。
类似的近年开始红火的HDOJ杭州电子科技大学ACM在线判题系统也是在Windows下利用Win32API实现技术路线为Windows 2003MySQL GCC Apache
PHP 一般情况下采用JAVA来实现也可以完成整个系统的开发更便于平台的移植但是JAVA的读取效率不佳是影响该系统运行的主要因素。
类似的今年来频繁出现的在.NET框架下的实现也遇到了类似的问题但总的来说不管是JAVA还是.
NET都简化了类似系统的实现方法。
除了以上实现方式外笔者还看到过使用Python实现的系统以及使用Qt实现的系统总的来说无论在何种语言框架开发下实现类似系统的思路都是一样的但语言的选择在能够帮助程序员减轻编写
代码的负担方面占据着很大的比重。
相对于一些经常更换平台的系统来说在线测评系统并不需要频繁的更换平台相反的它一般是长期驻留在同一个平台上相对于平台的选择来说后期系统维护成本才是考虑的重点。
6. 常见源
代码评测系统简介 a PKU Online Judge PKU JudgeOnline free version 是由北京大学开发的ACM判题系统公开版它是北大系统的精简版主要是去除了对JAVA语言的支持和取消了一些WEB界面的功能。
该版本是国内最早公开发行的在线判题系统。
目前一些高校和中学均选用北大系统作为程序设计训练及考试解决
方案平台。
北大的这套平台采用Win32API开发测评部分
JSP开发用户界面MySQL作为数据库Tomcat作为Web服务器。
相对于其它的一些B/S架构判题系统北大的系统安装部署是较简洁的没有太多的复杂设置更好的是它运行在Windows平台下很容易普及缺点是不开放源
代码定制性较弱。
b Celiz Judge System Celiz 是一个
开源评价系统。
这个软件用于奥林匹克信息学竞赛OI也可以用于ACM-ICPC 国际大学编程竞赛。
该平台采用C C开发运行于Linux之上。
目前该系统已经停止开发最后一版发布日期为2004年7月30日。
c DOMjudge DOMjudge是一款专门用于竞赛的自动判题
系统。
它同样运行于Linux之上采用
PHP作为用户界面开发语言使用MySQL数据库支持用户添加自己需要的支持语言。
同时支持命令行提交方式是一套较成熟的竞赛系统。
该系统目前仍在开发最近版本为3.3.2发布日期2012年1月25日。
d PC2 PC2是由美国加利福尼亚大学为国际大学生编程竞赛开发研制的竞赛控制系统。
目前主要用于ACM/ICPC等国际编程竞赛。
PC2最新的版本是9.2系统采用JAVA语言编写可以运行在任何支持JAVA的平台windows系列以及Solaris/Linux/ Free
BSD等网络模式为C/S竞赛语言可以选用绝大多数的编程语言。
PC2系统提供编程竞赛控制阅卷记分等功能。
在使用PC2系统过程中我们发现它可以极大的提高在诸如竞赛或者学校考试过程中教师的工作效率。
由于PC2系统不依赖于硬件和
软件系统使得PC2系统几乎可以适用于任何的机器环境。
C语言竞赛作为可以实际发挥学生编程能力、扩展学生视野、提高学生上机动手能力的竞赛正日益受到越来越多的人的重视。
e Cena评测系统 Cena 是一款国产开放源程序的信息学竞赛评测系统能满足大多数的评测需求。
它也采用C/S模式
工作通过局域网自动收取选手程序。
它能够自动选用对应的编译器来编译选手程序也能使用解释器或直接评测可执行文件。
能准确测出选手程序的运行时间和内存使用量并可加入对运行时间和内存使用的限制。
自动比较选手程序的输出和标准输出的差异并能将两者出现差异的具体位置告诉评测者。
支持使用自定义校验器可评测有多解的试题。
可对评测结果进行统计分析。
可将评测结果以各种样式打印或导出。
7. 评测系统发展趋势 随着参加ACM/ICPC 的同学越来越多随着提交量的增加原始的单服务器模式越来越不能承受多用户同时访问时的压力表现在Web 的响应速度无法跟上用户的大面积访问以及判题服务的响应时间慢于用户提交新程序的时间从而进入无法提供服务给新登录用户且已登录用户的服务也会变得无法响应的恶性循环。
近两年国内ACM/ICPC 举行的亚洲区各赛点的网络预选赛充分暴露了这一问题。
特别是竞赛的时候涌入的庞大数据量单一的服务器测评已经不能满足要求。
在线测评系统迫切需要提升自身处理能力除了升级服务器硬件配置外分布式处理云计算都是未来的发展方向。
可分布式部署的在线评测系统是一个运用B/S与C/S模式的综合性可分布式部署应用系统。
本系统不仅支持传统在线评测系统的动态WebB/S模式的访问同时支持使用客户端C/S模式访问。
可分布式部署的在线评测系统分为Web 服务模块、用户终端模块、中心服务模块、评测模块、数据接口模块等五个大的功能模块。
其中Web 服务模块和用户终端模块提供和用户的交互接口中心服务模块负责整个系统的处理逻辑和数据导向评测模块对用户提交的源
代码进行评测数据接口模块负责所有数据的存储与
查询。
下图是该系统的分布式架构模型 测评服务器用户WEB服务器数据库服务器打印服务器内部路由网络连接
网络连接网络连接网络连接防火墙互联网客户机用户机平台管理员便携终端系统维护员综合评测客户端C语言评测客户端C评测客户端JAVA评测客户端 在应用分布式系统方面目前国内的武汉大学的WOJ和浙江大学的ZOJ均处于国内前列武汉大学的相关开发者完成了分布式在线评测系统的开发与测试工作并取得了好的成绩。
更值得庆祝的是浙江大学的新在线评测系统已经采用分布式部署给国内该系统研究者提供了不少可以借鉴的资料。
采用可分布式部署将原始的单服务器模式转换为由一个中心服务模块作为系统核心组件一个底层数据库服务模块提供数据支持多个Web 服务模块和多个评测判题服务模块组成的服务集群本集群中的任何一个部件均可部署在不同的服务器上且负载高峰期可以用普通PC 临时替代由局域网或高速Internet 负责连接从而大大减轻单个服务器的压力并提升整个集群的服务性能。
二、查阅中外文献资料目录 1 01 KurniaAndyLimAndrewCheangBrenda.Online JudgeJ. Computers and Education 200136299–315 2 肖颖刘禹. 针对ACM/ICPC的在线评测系统J. 哈尔滨哈尔滨工业大学2003. 3 邓子睿唐巧. 北京师范大学ACM在线题库J. 北京师范大学校2007年9月5日第3版 4 王卓威尹宝林.一个基于网络的程序自动评测系统J. 北京航空航天大学学报2004306502-505 5 LIU Yu. Inside HIT Online Judge SystemJ. 哈尔滨哈尔滨工业大学2005. 6 Brenda CheangAndy KurniaAndrew Lim Wee-Chong Oon. On automated grading of programming assignments in an academic institutionJ. Computers Education200341121–131 7 Songwen XuYam San Chee. Automatic Diagnosis of Student Programs in Programming Learning EnvironmentsJ. Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence19991102 – 1107 8 Adrian Kosowski Micha?? Ma??afiejski and Tomasz Noiński. Application of an Online Judge Contester System in A
cademic TuitionJ. Advances in Web Based Learning – ICWL 20072008Volume 4823343-354 9 Don Colton Leslie Fife Randy Winters. Building a Computer Program GraderJ. The Proceedings of ISECON2004 Volume 3§2233 10康海燕樊孝忠汤世平. 基于J2EE的在线评测系统的研究与设计J. 计算机工程2004年7月第30卷第13期169-171 11苑文会彭四伟. 源
代码在线评测系统J. 计算机与数字工程2006年第34卷第9期130-132 12王腾姚丹霖. Online Judge系统的设计开发J. 计算机应用与软件200612 13李文新郭炜. 北京大学程序在线评测系统及其应用J. 吉林大学学报信息科学版2005S2 14韩志科王贵韩俊杰. 基于API自动测试的程序设计在线判题系统的研究与实现J. 计算机系统应用. 2008年第7期9-13 15徐本柱王浩胡学钢. ACM/ ICPC 的教学与实践J. 合肥工业大学学报社会科学版2008年第22 卷第6 期133-137 16董浩亮张坤杨文剑. 程序
代码抄袭检测系统J. 2008 年7月13日 17陈江勇. 基于B/S结构的ACM 竞赛在线评测系统J. 广东广东技术师范学院2005. 18Scoring of a Regional ContestEB/OL. http://icpc.baylor.edu/icpc/Regionals/About.htm. 2012-3-3 19Peking University Judge Online For ACM/ICPCEB/OL. http://http://poj.org/. 2012-3-3 20Zhejiang University Online JudgeEB/OL. http://acm.zju.edu.cn/. 2008-9-23 21Hangzhou Dianzi University Online JudgeEB/OL. http://acm.hdu.edu.cn/. 2012-3-3