ПРОЕКТИРОВАНИЕ  АВТОМАТИЗИРОВАННОЙ  СИСТЕМЫ  ПРОВЕРКИ  ОЛИМПИАДНЫХ  ЗАДАНИЙ  ПО  ПРОГРАММИРОВАНИЮ

Фролов  Дмитрий  Александрович

ассистент  кафедры  «Информационные  системы  и  технологии»

БИТТиУ  (филиал)  СГТУ  имени  Гагарина  Ю.А.,  РФ,  г.  Балаково

Email :  kafist@bittu.org.ru

Балашов  Андрей  Дмитриевич

студент  кафедры  «Информационные  системы  и  технологии»

БИТТиУ  (филиал)  СГТУ  имени  Гагарина  Ю.А.,  РФ,  г.  Балаково

Email: 

DEVELOPMENT  OF  AUTOMATED  VERIFICATION  SYSTEM  FOR  PROGRAMMING  OLYMPIAD  TASKS

Dmitry  Frolov

assistant  of  the  department  “Information  Systems  and  Technology”  BITTiU  (branch)  Yuri  Gagarin  State  Technical  University  of  Saratov,  Russia,  Balakovo

Andrey  Balashov

student  of  the  department  “Information  Systems  and  Technology”  BITTiU  (branch)  Yuri  Gagarin  State  Technical  University  of  Saratov,  Russia,  Balakovo

АННОТАЦИЯ

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

ABSTARCT

The  aim  of  this  work  is  to  design  an  automated  verification  system  for  programming  Olympiad  tasks.  During  the  designing  was  performed  an  overview  of  the  existing  automated  systems.

Ключевые  слова:  программирование;  задачи;  олимпиада.

Keywords :  programming;  tasks;  Olympiad.

В  последнее  время  появился  такой  термин,  как  «спортивное  программирование».  Спортивное  программирование  необязательно  связано  с  образовательной  и  научной  работой  студентов  напрямую,  в  нем  могут  принимать  участие  и  профессиональные  программисты  [1].  Крупные  IT-компании  регулярно  проводят  свои  личные  соревнования  по  программированию:

·     Google  —  Google  Code  Jam;

·     Yandex  —  Yandex.Алгоритм;

·     1C  —  открытая  студенческая  олимпиада.

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

Решение  любой  задачи  в  такой  ситуации  представляет  собой  прохождение  следующих  этапов:

·     начальная  формализация  задачи;

·     построение  алгоритма  решения  задачи;

·     воплощение  алгоритма  на  языке  программирования;

·     отладка  и  тестирование  работы  алгоритма  на  ЭВМ.

Эти  этапы  приходится  рассматривать  совместно,  так  как  выбор  языка  предопределяет  способ  представления  данных  и  методов  и  влияет  на  выбор  будущего  алгоритма.

Крупнейшей  международной  турнирной  системой  по  программированию  является  ACM  International  Collegiate  Programming  Contest.  Генеральными  спонсорами  организации  выступают  гиганты  IT-мира  —  Microsoft  и  IBM.  Команды  из  России  неоднократно  становились  победителями  этого  престижного  соревнования  и  по  итогам  удостаивались  встречи  с  Президентом  РФ.  Так,  последние  три  года  победителями  становились  команды  Санкт-Петербургских  высших  учебных  заведений.

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

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

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

Рассмотрим  моделирование  системы  на  функциональных  языках  и  языках  объектного  моделирования.  Разработка  моделей  системы  на  языках  объектного  моделирования  требует  предварительного  функционального  моделирования  [2].

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

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

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

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

Цель:  моделирование  процесса  автоматизированной  проверки  решений  олимпиадных  задач

Точка  зрения:  Администратор

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

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

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

Рисунок  2.  Диаграмма  декомпозиции  DFD

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

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

Часть  дублирующейся  информации  в  диаграмме  вариантов  использования  устраняется  с  внедрением  взаимосвязей  между  прецедентами:  включение  прецедента  “include”  и  расширение  прецедента  “extend”.

Рисунок  3.  Диаграмма  вариантов  использования  UML

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

Рисунок  4.  Диаграмма  компонентов  UML

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

Сущность  —  некоторый  обособленный  объект  или  событие  моделируемой  системы,  имеющий  конкретный  набор  параметров  –  атрибутов. 

Рисунок  5.  Диаграмма  IDEF 1X  автоматизированной  системы

Концептуальная  модель,  построенная  согласно  со  стандартом  IDEF1X,  является  логической  схемой  базы  данных  для  проектируемой  автоматизированной  системы.  На  этой  диаграмме  находятся  сущности:  Задача,  Участник,  Решение,  Турнир,  Учебное  заведение,  которые  объединены  между  собой  с  помощью  внешних  ключей  и  образуют  связи  «один  ко  многим».

Ниже  приведен  список  популярных  автоматизированных  систем,  которые  распространяются  бесплатно  или  условно-бесплатно  (данные  на  май  2015  года).

Таблица  1.

Автоматизированные  системы,  рассмотренные  при  проектировании

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

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

Список  литературы:

1.Виштак  Н.М.  Информационное  обеспечение  научно-исследовательской  работы  студентов  /  Н.М.  Виштак  //  Научные  труды  SWorld.  —  2013.  —  Т.  5.  —  №  2.

2.Виштак  Н.М.  Функционально-структурная  модель  интеллектуальной  обучающей  системы  /  Н.М.  Виштак,  Д.А.  Фролов,  Е.В.  Варгина  //  Научный  журнал  «Фундаментальные  исследования».  М.:  ИД  «Академия  естествознания»,  2013.  —  С.  871—874.

3.Виштак  О.В.  Направления  программной  реализации  электронных  образовательных  ресурсов  /  О.В.  Виштак  //  Научные  труды  SWorld.  —  2013.  —  Т.  5.  —  №  2.  —  С.  36—39.