Исследование эффективности автоматизированной проверки решений при проведении олимпиад по программированию

В настоящее время информационные технологии проникают во все сферы жизни человека, оказывая огромное влияние на развитие общества. Растет число людей, у которых вызывает интерес программирование в качестве спортивной дисциплины. В России соревнования студентов по программированию проводятся с 1996 г., когда впервые был проведен полуфинал чемпионата мира по программированию, который также стал чемпионатом России по программированию [1]. С 2000 г. число различных соревнований по информатике и программированию для школьников и студентов постоянно растет.

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

Сервер — это программа, запускаемая на отдельном ПК, и выполняющая определенные задачи. Для работы сервера обычно выделяется порт, к которому будет обращаться клиент для пользования его ресурсами.

Клиент — программа, позволяющая запрашивать у сервера выполнить какую-либо задачу (внести, изменить, удалить, найти информацию) и вернуть полученные данные клиенту.

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

Набор тестов — набор данных, которые используются для проверки решения на правильность. Считается, что решение проходит тестирование, если полученная программа успешно завершается, не превысив ограничений на ресурсы, и выдает верный ответ. Корректность решения проверяет специальная программа — чекер (от англ. checker), определяющая эквивалентны ли фактический (ответ участника) и ожидаемый (правильный ответ) результат работы программы.

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

Однако внедрение системы может повлечь за собой нежелательные последствия. Например, в системе может возникнуть ошибка, из-за которой вердикт будет неверным или баллы будут вычислены некорректно. Иногда проблемой является её уязвимость, участники могут воспользоваться этим и обмануть систему, что позволит им изменить ход соревнования. В настоящее время тестирующие системы проектируют таким образом, чтобы избежать утечек по части безопасности. Следующее последствие связано с тем, что пользоваться тестирующей системой не всегда легко. Соответственно, необходимо ознакомление, разнообразная помощь.

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

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

Рис. 1. Преимущества использования тестирующей системы

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

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

Таким образом, для эффективной работы пользователя от системы определены следующие потребительские свойства:

‒ доступность информации в реальном времени;

‒ наглядность информации, простота интерфейса;

‒ надежность сетевого взаимодействия;

‒ безопасность персональных данных;

‒ удобство использования;

‒ отсутствие возможности использования уязвимостей ПО;

Сформированные описания (выполняемые функции) к требованиям, которым должна удовлетворять система автоматической проверки, ориентированная на использование в учебном процессе приведены в таблице 1.

Таблица 1

Требования ктестирующей системе для проведения олимпиад по программированию

В настоящее время наиболее известными являются такие тестирующие системы, как Contester, Executor, PCMS2 и Ejudge.

Contester — это система для проведения турниров и индивидуального решения задач по олимпиадному программированию (спортивному программированию). Автор проекта «Contester»: Клопов Игорь Николаевич (Ковровская Государственная Технологическая Академия). Contester работает на Windows и на Linux. Поскольку система разработана до выхода Windows 7, то в полной мере она функционирует только на Windows XP и Linux. Также существует множество проблем с подключением к Contester современных сред разработки. Неполный функционал: любую задачу из архива можно использовать только в одном соревновании; поддерживает только ACM правила.

Executor — удобная тестирующая система под Windows. Из преимуществ: легконастраиваемость, интутивно-понятный интерфейс. Недостатками являются следующие ограничения: 16 задач, малофункциональность (нельзя вручную регистрировать участников). Чтобы устраивать командные и личные соревнования, нужно использовать две разные версии.

PCMS2 — кроссплатформенная тестирующая система, была написана на языке программирования java больше 10 лет назад для полуфинала чемпионата мира по программированию. Помимо Russian Code Cup эту систему также используют для проведения таких соревнований как NEERC (полуфинал чемпионата мира по программированию), Всероссийская олимпиада по информатике и Всероссийская командная олимпиада по программированию. Недостатками данной системы является отсутствие документации, отсутствие возможности проведения двух соревнований разного вида, отсутствует возможность дорешивания после окончания соревнования.

Ejudge — это полнофункциональная тестирующая система под Linux. Из плюсов: функциональная, очень защищенная система, поддерживает командные, личные олимпиады, а также виртуальное участие. Из недостатков: на Windows-машинах не работает.

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

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

1. https://ru.wikipedia.org/wiki/Олимпиады_по_программированию [Электронный ресурс]
2. Кирюхин В. М. Методика проведения и подготовки к участию в олимпиадах по информатике. Всероссийская олимпиада школьников. — М.: БИНОМ. Лаборатория знаний, 2011. –271 с.
3. Скиена С. С., Ревилла М. А. Олимпиадные задачи по программированию. Руководство по подготовке к соревнованиям. — М.: Кудиц — образ, 2005. — 416 с.
4. Гагарина Л. Г., Колдаев В. Д. Алгоритмы и структуры данных. -М.: Финансы и статистика; ИНФРА-М, 2009. — 304 с.