Пояснительная записка (1231610)
Текст из файла
Министерство транспорта Российской федерации
Федеральное агентство железнодорожного транспорта
Федеральное государственное бюджетное
образовательное учреждение высшего образования
«Дальневосточный государственный университет путей сообщения»
Кафедра «Вычислительная техника и компьютерная графика»
К защите допустить
Заведующий кафедрой
_____ Ю.В. Пономарчук
«___» ___________ 2016
Система для проведения соревнований по программированию с модулем подведения итогов
Выпускная квалификационная работа
ВКР 09.03.01.ИВТ.17.00.943 – ПЗ
Студент 943 гр. ________________________________________ А.В. Усманов
Руководитель
к.т.н., доцент __________________________________________ Ю.А. Сухобок
Нормоконтролёр
к.т.н., доцент __________________________________________ Е.В. Буняева
Хабаровск 2016
Содержание
Введение 4
1 Обзор предметной области 6
1.1 Соревнования по программированию 6
1.1.1 Командный чемпионат по программированию ACM ICPC 6
1.1.2 Правила командных чемпионатов 7
1.1.3 Подведение итогов соревнований по программированию 8
1.2 Обзор существующих систем для проведения соревнований по программированию 9
1.2.1 Системы Codeforces и Polygon 9
1.2.2 Системы PC2 и PCMS2 10
1.2.3 Система Timus Online Judge 10
1.2.4 Система Ejudge 11
1.2.5 Система Contester 12
2 Проектирование системы для проведения соревнований по программированию с модулем подведения итогов 14
2.1 Общая архитектура системы Ejudge 14
2.1.1 Управляющие компоненты 14
2.1.2 Обработчики запросов 16
2.1.3 Вспомогательные программы 17
2.2 Описание технологий для создания web-сайтов 19
2.2.1 Hyper Text Markup Language 19
2.2.2 Cascading Style Sheets 20
2.2.3 JavaScript 21
2.2.4 PHP: Hypertext Preprocessor 24
2.2.5 Система управления базами данных MySQL 25
2.3 Требования, предъявляемые к модулю подведения итогов 27
3 Реализация системы для проведения соревнований по программированию с модулем подведения итогов 28
3.1 Установка и настройка системы для проведения соревнований по программированию Ejudge 28
3.1.1 Подготовка рабочей среды для установки Ejudge 28
3.1.2 Настройка web-сервера Apache2 29
3.1.3 Установка системы Ejudge 29
3.1.4 Настройка и запуск системы Ejudge 30
3.1.5 Экспорт истории посылок из системы Ejudge 32
3.2 Разработка модуля подведения итогов 33
3.2.1 Реализация меню настроек 33
3.2.2 Хранение историй посылок на сервере 34
3.2.3 Реализация загрузки истории посылок 35
3.2.4 Формат историй посылок 38
3.2.5 Обработка историй посылок 41
3.2.6 Хранение информации о командах, задачах и посылках 43
3.2.7 Структура таблицы с результатами 45
3.2.8 Цветовая схема таблицы с результатами 47
3.2.9 Обновление таблицы с результатами 49
3.2.10 Реализация «разморозки» таблицы с результатами 50
3.3 Технико-экономическое обоснование 53
Заключение 55
Список использованных источников 56
Приложение А – Программная реализация модуля подведения итогов 59
Введение
Олимпиады по программированию в век наступления «промышленного программирования» остаются одним из немногих интеллектуальных конкурсов, на которых участники могут продемонстрировать свои способности в искусстве программирования в его классическом понимании и которые поддерживают традиции этой области теоретической информатики.
На первый взгляд кажется, что эти состязания относятся к области «высокого чистого искусства», имеющего мало точек соприкосновения с «реальной жизнью» современного программиста. Действительно, круг из нескольких десятков одаренных молодых людей, реально претендующих на победу в мировом первенстве, и их тренеров весьма узок, математико-программистское содержание состязаний понятно достаточно ограниченному числу специалистов и педагогов высшей квалификации.
Однако, результаты этих интеллектуальных игр мировой программисткой элиты представляет интерес уже для гораздо более широких кругов, поскольку процесс формирования и подготовки команд опирается на всю образовательную, научную, промышленную и культурную инфраструктуру данной страны. Эти результаты достаточно точно отражают распределение мирового компьютерного интеллектуального потенциала по различным странам и позволяют оценить способность нации не только использовать разработанные в других странах компьютерные технологии, но и вносить свой вклад в их создание.
Проведение соревнований по программированию играет немалую роль при подготовке специалистов сферы информационных технологий. Подведение итогов подобных соревнований происходит по определенным правилам, и, зачастую, на награждении используется стороннее от системы проведения соревнований программное обеспечение.
Целью выпускной квалификационной работы является проектирование и разработка системы для проведения соревнований по программированию с модулем подведения итогов.
В соответствии с указанной целью поставлены следующие задачи:
– изучить предметную область: правила проведения и подведения итогов соревнований по программированию;
– произвести анализ существующих систем для проведения соревнований по программированию;
– произвести анализ существующих модулей подведения итогов, анализ способов и средств их реализации;
– выполнить проектирование системы для проведения соревнований по программированию с модулем подведения итогов;
– разработать спроектированную систему.
Разработанная система будет внедрена и начнёт использоваться в подготовке студентов, проходящих обучение на кафедре «Вычислительная техника и компьютерная графика» «Дальневосточного государственного университета путей сообщения».
1 Обзор предметной области
Системы для проведения соревнований по программированию могут автоматизировать процесс подготовки студентов к самим соревнованиям по программированию, а так же развить их навыки программирования в целом.
1.1 Соревнования по программированию
Можно выделить следующие регулярные мировые соревнования по программированию [1]:
– командный чемпионат ACM ICPC, проводимый компанией IBM [2];
– командный чемпионат VK Cup [3];
– чемпионат Facebook Hacker Cup [4];
– чемпионат Google Code Jam [5];
– чемпионат Russian Code Cup, проводимый компанией Mail.ru Group [6];
– чемпионат Алгоритм, проводимый компанией Яндекс [7].
Самым престижным и развитым является командный чемпионат ACM ICPC, в то время как остальные мировые соревнования проводятся по большей части в онлайн режиме.
1.1.1 Командный чемпионат по программированию ACM ICPC
Командные чемпионаты мира по программированию (International Collegiate Programming Contest) среди сборных команд высших учебных заведений проводятся с 1977 г. под эгидой международной организацией Association for Computing Machinery (ACM), которая была основана в 1947 г. сотрудниками Пенсильванского университета, создавшим первый в мире компьютер ENIAC [2].
Схема организации чемпионата включает два этапа: региональный и финальный. Команды-победительницы региональных групп выходят в финал и разыгрывают звания чемпионов мира, Европы, Азии и других континентов.
Впервые о чемпионате мира российские вузы узнали осенью 1996 г., когда был образован новый Восточно-Европейский регион. За более чем двадцатилетнюю историю полуфинала чемпионата мира в России, российские команды достойно выступали в финалах. Например, российские команды Санкт-Петербургского государственного университета информационных технологий, механики и оптики занимали первое место в финалах в 2004, 2008, 2009, 2012, 2013, 2015 годах.
1.1.2 Правила командных чемпионатов
За почти сорокалетнюю историю состязаний сформировались международные правила [8] этих соревнований, в соответствии с которыми команде, состоящей из трех участников, предоставляется один компьютер и предлагается в течение 5 часов решить максимальное число из предложенных задач. Количество задач обычно варьируется от 8 до 15. Побеждает команда, решившая наибольшее число задач, а в случае равенства числа решенных задач – команда, затратившая меньше времени.
Время, затраченное на решение задач – это время в минутах, прошедшее с начала соревнований до посылки первой принятой попытки для этой задачи плюс заданное количество штрафных минут за каждую неудачную попытку для этой задачи. Время, затраченное на нерешенную задачу, равно нулю. Общее время равно сумме времен, затраченных на решение всех задач.
Решением является программа на одном из предложенных языков программирования. Тестирование производится автоматически по ходу соревнований в специальной тестирующей системе на заранее подготовленном наборе тестов для каждой задачи. Решения задач, посланные жюри, называются попытками. Каждая попытка может быть принята или отвергнута. Попытка считается принятой, если программа выдает верные результаты и укладывается в ограничения на всех тестах.
В различных соревнованиях правила могут немного отличаться от описанных. Например, в соревнованиях Google Code Jam и Facebook Hacker Cup тестирование программ происходит на компьютере участника, после чего он отсылает результаты и свою программу жюри.
1.1.3 Подведение итогов соревнований по программированию
Системы для проведения соревнований по программированию позволяют получать результаты тестирования решений участников в течение нескольких минут после их отправления. Все участники и зрители в реальном времени могут наблюдать за тем, какое количество задач решила каждая команда посредством таблицы результатов. Такой формат проведения соревнований исключает какую-либо интригу относительно победителя, так как он известен сразу по окончании соревнования.
Для сохранения интриги, в соответствии с правилами, таблица результатов замораживается за час до конца соревнования [9]. Так называемая «разморозка» таблицы происходит лишь на церемонии награждения по определённому алгоритму. Вместо того чтобы просто показать участникам финальную таблицу, её «размораживают» последовательно снизу вверх. В случае, если команда в последний час имела успешные посылки, она поднимается вверх по таблице, что увеличивает её шансы на победу. Иначе, если удачных посылок у команды не осталось – она приглашается на сцену для награждения.
В настоящее время существует множество модулей, позволяющих «разморозить» таблицу результатов, но все они функционируют отдельно от систем для проведения соревнований. Такие модули не имеют открытого распространения, поэтому сложно рассматривать способы их реализации. Часто можно встретить два способа реализации модуля подведения итогов: в виде web-страницы и в виде исполняемого файла. Первый вид реализации является более универсальным, так как может быть запущен с различных платформ, в отличие от исполняемого файла, который, скорее всего, будет привязан к конкретной операционной системе. Более того, web-страница не потребует установки, а будет иметь открытый доступ через интернет.
Исходя из этого, следует рассмотреть средства и технологии для разработки web-сайтов и определиться с требованиями, предъявляемыми к модулю подведения итогов.
1.2 Обзор существующих систем для проведения соревнований по программированию
На данный момент существует множество систем для проведения соревнований по программированию:
– системы Codeforces и Polygon;
– системы PC2 и PCMS2;
– система Timus Online Judge;
– система Ejudge;
– система Contester.
Так же своими системами с автоматизированной проверкой решений обладают компании Facebook, Google и Яндекс, но об этих системах почти ничего неизвестно.
1.2.1 Системы Codeforces и Polygon
Codeforces – сайт для проведения соревнований по программированию разработанный Михаилом Мирзаяновым в 2010 г. при поддержке Саратовского государственного университета [10].
Polygon – система для автоматизированной подготовки задач олимпиадного программировании, также разработанная Михаилом Мирзаяновым [11]. Данная система напрямую связана с системой Codeforces: после того, как задача прошла полную подготовку в Polygon – её можно добавить в Codeforces.
За пятилетнюю историю на базе Codeforces было проведено множество соревнований:
– более 300-х регулярных раундов;
– чемпионат Яндекс Алгоритм;
– чемпионат Russian Code Cup;
– чемпионат ABBYY Cup;
– чемпионат КРОК;
– чемпионат VK Cup;
– множество тренировок, созданных на основе задач различных соревнований, который проводились не в рамках Codeforces.
Системы Codeforces и Poligon не имеют свободного распространения.
1.2.2 Системы PC2 и PCMS2
Системы PC2 и PCMS2 используются для проведения самых популярных соревнований по программированию – ACM ICPC [12]. Первая система используется на полуфинале и некоторых четвертьфиналах NEERC, в то время, как вторая система используется на финале.
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.
Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.
Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
