Автоматизированная система проведения олимпиад по информатике

1) одно решение на задачу - файл с исходным текстом программы на одном из допустимых языков программирования;

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

Рис. 2. Интерфейс участника олимпиады

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

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

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

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

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

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

1) превышение лимита памяти;

2) превышение лимита времени;

3) ошибки в программе, приводящие к сбоям операционной системы Windows;

4) внутренние ошибки времени выполнения (runtime error);

5) ошибки в алгоритме, приводящие к выдаче неверного ответа.

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

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

Преимущества системы. Укажем основные преимущества разработанной СПО.

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

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

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

4. Система имеет простой и удобный пользовательский интерфейс, разработанный профессиональными дизайнерами.

а)б)

Рис. 3. Временные диаграммы загрузки процессора: а - корректно работающая программа; б - зависшая программа

Начиная с 2006 г. рассмотренная система используется при проведении ежегодной Всероссийской олимпиады школьников по информатике в рамках интернет-тура, число участников которого, как правило, превышает 700 человек [1].