Проектирование информационной системы для проведения олимпиад по спортивному программированию

Размещено на http://www.allbest.ru/

ПРОЕКТИРОВАНИЕ ИНФОРМАЦИОННОЙ СИСТЕМЫ ДЛЯ ПРОВЕДЕНИЯ ОЛИМПИАД ПО СПОРТИВНОМУ ПРОГРАММИРОВАНИЮ

С.Н. Блинов, С.П. Якимов

Сибирский университет науки и технологий, г. Красноярск, Россия

Рассматривается проектирование информационной системы для проведения личных олимпиад по спортивному программированию. Проектируемая система позволяет автоматизировать сбор и обработку данных об участниках и задачах олимпиады, реализует механизм проведения таких соревнований, а также позволяет получать сведения об общей статистике выполнения задач и итоговых результатах олимпиады. Обозначены особенности представленной информационной системы, в том числе правила проведения олимпиады и алгоритм начисления баллов.

Ключевые слова: олимпиада, соревнование, спортивное программирование, проектирование информационной системы, алгоритм расчета баллов.

Design of the information system for sports programming olympiads

Blinov S.N., Yakimov S.P.

Reshetnev Siberian State University of Science and Technology, Krasnoyarsk, Russia

This article discusses the design of an information system for conducting personal Olympiads in sports programming. The designed system makes it possible to automate the collection and processing of data on participants and tasks of the Olympiad, implements a mechanism for conducting such competitions, and also enables to obtain information about the general statistics of the tasks and the final results of the Olympiad. The features of the presented information system are indicated, including the rules of the Olympiad and the algorithm for scoring. As a result of analysis of the subject area we have developed a functional model of the main problem facing the projected software product -- “Holding an Olympiad in sports programming”, which includes three main processes: “Holding organization activities”, “Competition”, “The results of the competition”.

As a result of analysis of the functional model we have decided to divide the system into four software modules: the administrator module, the Olympiad participant module, the jury module, and the “Information board” module.

The administrator module is responsible for resetting results of the Olympiad and filling the system with data by maintaining internal directories.

The Olympiad participant module is designed for performing the following functions: selecting problems to perform, entering problem solutions, sending solutions for verification, viewing your submitted solutions and compiler messages, viewing personal results and statistics.

The jury module is in charge of the organization aspects of the Olympiad: viewing, confirmation or rejection of results of problems performed by participants of the Olympiad.

The “Information board” module is used to receive information about general statistics of problems performance and results of the Olympiad. This module can be displayed on an interactive whiteboard in audiences of the Olympiad or put on a shared network resource available to all users of the system.

The presented information system has a unique scoring algorithm. A distinctive feature of this algorithm is that the accrued number of points for successful completion of problems as well as the number of penalty points for their erroneous performance is unstable and dynamically changing during the competition. The final calculation of points depends on results of completing problems by all participants of the Olympiad.

The designed information system can be recommended for using competitions in sports programming on basis of secondary schools, secondary special and higher educational institutions. The system allows you to gain additional experience and knowledge in the field of information technology, is of paramount importance in training of highly qualified IT specialists and can be used to test knowledge in field of programming not only for schoolchildren and students, but also for professional programmers.

Keywords: olympiad, competition, sports programming, design of information system, scoring algorithm.

Введение

Среди учащихся средних, средних специальных и высших учебных заведений ежегодно проводится большое количество всевозможных конкурсов и олимпиад, и с каждым годом количество проводимых олимпиад только увеличивается. Возрастает интерес к программированию в качестве спортивной дисциплины. Большую популярность приобрели олимпиады по спортивному программированию, которые проводятся на самых различных уровнях -- от всероссийского (школьного, муниципального, областного значения) до международного -- чемпионата мира International Collegiate Programming Contest (ICPC) среди студентов вузов [1]. Полученные участниками олимпиады знания и опыт имеют первостепенное значение при подготовке высококвалифицированных специалистов, способных решать нестандартные задачи.

Олимпиада по спортивному программированию -- интеллектуальное соревнование по решению задач на ЭВМ, для решения которых участникам олимпиады необходимо разработать программу на одном из языков программирования [2]. В спортивном программировании задачи формулируются математически точно, у них есть строгие рамки. Время проведения олимпиады ограничено.

Для проверки правильности программ обычно используется встроенная система автоматической проверки решений, определяющая эквивалентность представленного участником фактического и базового результатов. Также может быть выполнена дополнительная проверка членами компетентного жюри.

Для решения участникам предоставляется определенный перечень задач. Задача считается успешно решенной, если подготовленная участником программа работает верно на всем наборе заранее подготовленных тестов. Тесты представляют собой набор входных и соответствующих им выходных данных, не доступных для просмотра участникам олимпиады.

Организационно соревнования подразделяются на личные и командные. Личные соревнования подразумевают индивидуальное участие, при этом для каждой задачи устанавливается ее значимость, характеризуемая максимальным числом баллов, которые может набрать участник [3]. В командных соревнованиях обычно принимают участие команды, состоящие из трех человек. Как правило, на время олимпиады им предоставляется один компьютер. Место команды-участника определяется в зависимости от количества решенных задач и набранных баллов всеми участниками команды.

Для автоматизации проведения соревнований по спортивному программированию существует большое количество программных продуктов, каждый из которых имеет свои достоинства и недостатки. Рассмотрим наиболее популярные системы, такие как «ACMP -- Школа программиста» и «Timus Online Judge» [4, 5]. Данные системы содержат большой архив задач с автоматизированной проверкой решений, на базе которых проводятся соревнования и олимпиады по программированию. Основным недостатком подобных систем, на наш взгляд, является линейный порядок начисления баллов за выполнение задачи, не учитывающий количество использованных попыток и результаты выполнения задачи другими участниками олимпиады. Зачастую исход олимпиады можно предсказать еще до ее завершения из-за недостатка «драматичности», которая является неотъемлемой частью реальных спортивных соревнований. Такие системы недостаточно динамичны, так как в них отсутствуют «переломные» и непредсказуемые моменты, которые могут изменить ход всего соревнования.

В данной статье рассматривается проектирование информационной системы для проведения личных олимпиад по спортивному программированию, призванной решить данную проблему.

Проектирование информационной системы

В ходе анализа предметной области были исследованы правила проведения различных олимпиад по спортивному программированию, проведены консультации с преподавателями и участниками олимпиад с целью более точного определения функций и задач системы.

По результатам проведенного исследования составлен свод собственных правил, который должен быть реализован в данной информационной системе:

1. До тех пор, пока председателем жюри не будет дан старт к началу олимпиады, ее участникам нельзя начинать выполнение задач.

2. После того, как будет дан старт к началу олимпиады, участники могут приступать к знакомству с задачами и непосредственному их решению.

3. При выборе задачи участнику доступна для просмотра следующая информация:

- номер задачи;

- название задачи;

- текущее количество баллов за задачу, рассчитываемое по формулам (1) и (3);

- текущее количество штрафных баллов за попытку, рассчитываемое по формуле (2);

- количество участников, выполняющих задачу в данный момент;

- количество участников, верно выполнивших задачу.

4. Каждый участник может одновременно выполнять не более одной задачи.

5. Участник выбирает из списка доступных языков программирования язык, на котором будет решать выбранную задачу.

6. Участник вносит решение задачи в систему и отправляет его на проверку.

7. Отправленное участником решение компилируется и автоматически проверяется на сервере обработки решений с помощью заранее подготовленных тестов.

8. В случае возникновения спорных ситуаций результат может быть пересмотрен решением компетентного жюри. Также если для выбранного участником языка программирования на сервере не установлен компилятор или не поддерживается информационной системой, то решение отправляется на ручную проверку жюри.

9. Для решения каждой задачи участникам предоставляется определенное количество попыток.

10. Если задача решена верно с первой попытки, то участнику начисляется определенное количество баллов по формуле (1):

где СБЗ_уч - сумма баллов за задачу, начисляемая участнику;

КБ_тах - максимальное количество баллов за успешное выполнение задачи;

УВ_общ - количество успешных выполнений задачи всеми участниками олимпиады.

11. Если задача решена неверно с n-й попытки, то участнику начисляются штрафные баллы по формуле (2):

где ШБ_тах - максимальное количество штрафных баллов за задачу;

КП_тах - максимальное количество попыток, предоставляемых для выполнения задачи;

n - номер текущей попытки участника.

12. Если задача решена верно со второй и более попыток, то участнику начисляются баллы по формуле (3):

взамен ранее начисленных штрафных баллов.

13. Отмена выбранной задачи также приводит к начислению штрафных баллов по формуле (2) и засчитывается как неудачная попытка.

14. Начисленное участникам количество баллов за успешно выполненную задачу по формулам (1) либо (3) непостоянно и может меняться в ходе проведения олимпиады. После очередного успешного выполнения задачи одним из участников олимпиады происходит перерасчет начисленных баллов у всех остальных участников.

15. Участники могут видеть личные результаты, статистику выполнения задач, а также просматривать все свои отправленные решения и сообщения компиляторов непосредственно в интерфейсе программы.

16. Определение мест участников олимпиады осуществляется путем ранжирования суммарного количества баллов, начисленных каждому участнику по формуле (4):

где N - количество задач, выбранных данным участником.

17. Все пользователи системы могут просматривать на информационном табло общую статистику выполнения задач и результаты олимпиады.

18. Признак завершения олимпиады устанавливается председателем жюри.

19. После завершения олимпиады участники не могут выбирать новые задачи, а также отправлять решения на проверку.

20. Участникам, не отправившим решение выбранной задачи до завершения олимпиады, начисляются штрафные баллы по формуле (2).

В результате анализа предметной области была разработана функциональная модель основной задачи, стоящей перед проектируемым программным продуктом - «Провести олимпиаду по спортивному программированию».

На рис. 1 представлена контекстная диаграмма системы в методологии IDEF0 [6], отображающая, какие данные являются необходимыми для реализации поставленной задачи.

В качестве управления системой предусмотрены «Условия проведения олимпиады», включающие в себя все документы, которые регламентируют правила проведения олимпиады.

В качестве входных данных выступают:

- «Состав участников» - информация об участниках, принимающих участие в олимпиаде;

- «Состав жюри» - информация о членах жюри, участвующих в проведении олимпиады;

Рис. 1. Контекстная диаграмма системы

- «Состав администраторов» - информация об администраторах системы;

- «Языки программирования» - список языков программирования, на которых участники олимпиады могут выполнять и отправлять решения на проверку;

- «Задания олимпиады» - информация о задачах, которые могут быть использованы при проведении олимпиады;

- «Решения участников» - текст решения задания олимпиады участником, который представляет собой исходный код программы, написанный на одном из допустимых языков программирования;

- «Решения жюри» - подтверждение / отклонение результатов выполнения заданий участниками олимпиады.

В качестве ресурсов в системе используются:

- «Администраторы» - пользователи, исполняющие роль администраторов (организаторов) олимпиады;

«Участники» - пользователи, исполняющие роль участников олимпиады;

- «Члены жюри» - пользователи, исполняющие роль членов жюри олимпиады.

Результатом работы системы являются «Результаты олимпиады» - информация о количестве набранных баллов участниками по окончании олимпиады.

На рис. 2 показана декомпозиция процесса «Провести олимпиаду по спортивному программированию», представленного на контекстной диаграмме.

В результате декомпозиции выделяются три основных процесса:

«Провести организационные мероприятия» - процесс, предназначенный для организации всех действий, выполняемых администратором олимпиады, включающих в себя добавление заданий олимпиады, определение состава жюри, участников, администраторов и сброс результатов олимпиады.

«Соревноваться» - процесс, предназначенный для выбора и решения участниками заданий олимпиады, отправки их на проверку и непосредственной оценки компилятором или членами жюри.

«Подвести итоги соревнований» - процесс, предназначенный для завершения олимпиады, окончательной оценки членами жюри решений участников, а также подсчета суммарной оценки набранных участниками баллов, определения мест участников олимпиады путем ранжирования суммарного количества баллов, начисленных каждому участнику по формуле (4).

В результате анализа функциональной модели было принято решение разделить систему на четыре программных модуля:

- модуль администратора системы;

- модуль участника олимпиады;

- модуль жюри олимпиады;

- модуль «Информационное табло».

Модуль администратора системы должен выполнять следующие функции:

- сброс результатов олимпиады;

- ведение справочника пользователей системы;

- ведение справочника задач олимпиады;

- ведение справочника языков программирования.

Для автоматической проверки решений данная информационная система должна поддерживать наиболее популярные языки программирования, используемые в олимпиадном программировании, например, такие как С, С++, Object Pascal (Delphi) и др. Для компиляции текста программ, написанных на перечисленных языках, можно воспользоваться следующими компиляторами: GCC (для языка программирования С), G++ (для языка С++) и DCC (для языка Object Pascal). Программы, написанные на других языках программирования, направляются на ручную проверку. Для этого необходимо, чтобы выбранный участником язык был включен в справочник языков программирования.

Модуль участника олимпиады должен выполнять следующие функции:

- выбор задач для выполнения;

- ввод решений задач;

- отправка решений на проверку;

- просмотр своих отправленных решений и сообщений компиляторов;

- просмотр личных результатов и статистики.

Модуль жюри олимпиады должен выполнять следующие функции:

- просмотр текста решений участников олимпиады;

- просмотр тестов и сообщений компиляторов;

- проверка / перепроверка заданий участников путем подтверждения, либо отклонения их решений;

- старт / стоп олимпиады (выполняется председателем жюри).

Модуль «Информационное табло» должен выполнять:

- вывод общей статистики выполнения задач и результатов олимпиады.

Варианты использования проектируемой системы приведены на рис. 3.

Представленная UML-диаграмма вариантов использования описывает функциональность информационной системы в целом, показывает, какие действия предоставляются каждому пользователю.

Проектирование базы данных информационной системы

Фундаментальной основой всех современных информационных систем является база данных. Все информационные системы так или иначе используют базы данных, так как предполагают использование большого количества данных, которые нужно хранить и обрабатывать.

Рис. 3. UML-диаграмма вариантов использования системы

Разрабатываемая информационная система не является исключением из данного правила.

Рис. 4. Логическая модель базы данных

В результате анализа предметной области были выделены следующие сущности и их атрибуты:

— пользователь (ФИО, логин, хэш пароля);

— роль (наименование);

— задачи (номер, краткое название, полная формулировка, максимальное количество баллов за успешное выполнение, максимальное количество штрафных баллов, максимальное количество попыток, тесты для автоматической проверки);

— задания участников (участник, задача, проверяющий, текст решения, номер попытки, количество баллов, сообщение);

— статус задачи (наименование);

— языки программирования (наименование).

Между выявленными сущностями были определены следующие связи (ER-модель):

— пользователь имеет роль;

— пользователь (участник) имеет задачи;

— пользователь (жюри) имеет задания участников;

— задание участника имеет статус задачи;

— задание участника имеет язык программирования;

— олимпиада имеет признак активности (определяется председателем жюри для объявления старта и завершения олимпиады).

В результате преобразования ER-модели в реляционную была разработана логическая модель базы данных проектируемой информационной системы, которая изображена на рис. 4.

Разработанная логическая модель представляет собой наиболее эффективную структуру данных для проектируемой информационной системы, обеспечивающую быстрый доступ к данным, исключение дублирования и целостность данных.



Рис. 5. Участник олимпиады - основное окно

Проектирование пользовательского интерфейса

Заключительным этапом проектирования информационной системы для проведения олимпиад по спортивному программированию является проектирование пользовательского интерфейса.

В данной информационной системе для модулей участника олимпиады и «Информационное табло» предлагается реализация в виде Web- приложения, так как они должны быть доступны большому числу пользователей.

На рис. 5 представлен пользовательский интерфейс модуля участника олимпиады, который разделен на две экранные области: «Задачи» и «Информация об участнике».

В области «Задачи» представлен перечень задач, входящих в состав текущей олимпиады. В данной области отображаются следующие сведения:

Рис. 6. Участник олимпиады - окна работы с заданием

— номер задачи;

— краткое название - краткое наименование задачи;

— количество баллов - текущее количество баллов за верное решение;

— штраф за попытку - текущее количество штрафных баллов за неверную попытку;

— доступно попыток - значение текущего доступного количества попыток для решения задачи;

— в работе - количество участников, которые выполняют данную задачу в настоящий момент;

— количество выполнений - количество успешных выполнений всеми участниками олимпиады.

Участник выбирает задачу, после чего последовательно открываются следующие модальные окна: окно подтверждения выбора задачи и предварительного просмотра задания, окно выбора языка программирования и ввода решения. Интерфейс указанных окон приведен на рис. 6.

Введенное участником олимпиады решение отправляется на проверку на сервер обработки решений по нажатии кнопки «Сдать». Каждое отправленное решение проходит автоматическую проверку на всех имеющихся тестах, введенных администратором системы. В случае неверного выполнения задания последнее отправленное на проверку решение может быть пересмотрено решением компетентного жюри.

В области «Информация об участнике» отражается количество выполненных участником задач, текущая сумма баллов и текущее занимаемое им место в олимпиаде. По нажатии на кнопку «Подробно» открывается окно статистики выполнения задач данным участником, в котором он может просматривать свои отправленные решения, а также сообщения компиляторов.

Для получения информации об общей статистике выполнения задач и результатах олимпиады служит дополнительное Web-приложение «Информационное табло», которое может быть выведено на интерактивную доску в аудиториях проведения олимпиады либо выставлено на общий сетевой ресурс, доступный всем пользователям системы.

Также для данной информационной системы необходимо реализовать еще два важных модуля: модуль администратора и модуль жюри. Данные модули не имеют специфических требований к интерфейсу и могут быть реализованы в виде Desktop или Web-приложений.

информационный олимпиада автоматизация интерфейс

Вывод

Представленная в данной статье информационная система отвечает всем необходимым требованиям для проведения олимпиад по спортивному программированию и обладает уникальным алгоритмом расчета баллов. Отличительная особенность данного алгоритма заключается в том, что начисленное количество баллов за успешное выполнение задач, а также количество штрафных баллов за их ошибочное выполнение непостоянно и динамически меняется в ходе проведения соревнования. Итоговый расчет баллов зависит от результатов выполнения задач всеми участниками олимпиады.

Спроектированная информационная система может быть рекомендована к использованию для проведения олимпиад по спортивному программированию на базе общеобразовательных школ, средних специальных и высших учебных заведений. Данная система позволяет получить дополнительный опыт и знания в сфере информационных технологий, имеет первостепенное значение при подготовке высококвалифицированных IT-специалистов и может быть использована для проверки знаний в области программирования не только школьников и студентов, но и профессиональных программистов.

Литература

1. «За время, которое обычный программист тратит на понимание задачи, спортивный ее уже решает». Как устроены международные олимпиады по информатике / / Индикатор. URL: https://indicator.ru/mathematics/ mezhdunarodnaya-olimpiada-po-informatike.htm (дата обращения: 20.01.2020).

2. Самощенко Ю.Ю. Исследование эффективности автоматизированной проверки решений при проведении олимпиад по программированию // Молодой ученый. 2016. № 11. С. 223--226.

3. Положение о проведении соревнований // Олимпиады по спортивному программированию. URL: https:// acmp.ru/asp/champ/index.asp?main=polog (дата обращения: 20.01.2020).

4. Беляев С.Н., Лалетин Н.В. Школа программиста (http://acmp.ru): образовательный интернет-ресурс олим- пиадного программирования для школьников // Вестник Адыгейского государственного университета. Сер. 3: Педагогика и психология. 2010. № 1. С. 130--135.

5. Timus Online Judge. URL: http://acm.timus.ru (дата обращения: 20.01.2020).

6. Кулябов Д.С., Королькова А.В. Введение в формальные методы описания бизнес-процессов : учеб. пособие. М. : РУДН, 2008. 173 с.

References

1. «Za vremya, kotoroe oby'chny'j programmist tratit na ponimanie zadachi, sportivny'j ee uzhe reshaet». Kak ustroeny' mezhdunarodny'e olimpiady' po informatike // Indikator. URL: https://indicator.ru/mathematics/mezhdunarodnaya- olimpiada-po-informatike.htm (data obrashheniya: 20.01.2020).

2. Samoshhenko Yu.Yu. Issledovanie e'ffektivnosti avtomatizirovannoj proverki reshenij pri provedenii olimpiad po programmirovaniyu // Molodoj ucheny'j. 2016. № 11. S. 223-226.

3. Polozhenie o provedenii sorevnovanij // Olimpiady' po sportivnomu programmirovaniyu. URL: https://acmp.ru/asp/ champ/index.asp?main=polog (data obrashheniya: 20.01.2020).

4. Belyaev S.N., Laletin N.V. Shkola programmista (http:// acmp.ru): obrazovatel'ny'j internet-resurs olimpiadnogo programmirovaniya dlya shkol'nikov // Vestnik Ady'gejskogo gosudarstvennogo universiteta. Ser. 3: Pedagogika i psixologiya. 2010. № 1. S. 130-135.

5. Timus Online Judge. URL: http://acm.timus.ru (data obrashheniya: 20.01.2020).

6. Kulyabov D.S., Korol'kova A.V. Vvedenie v formal'ny'e metody' opisaniya biznes-processov : ucheb. posobie. M. : RUDN, 2008. 173 s.

Размещено на Allbest.ru