Министерство образования и науки Российской Федерации
Министерство образования Саратовской области
Национальный исследовательский Саратовский государственный университет имени Н.Г. Чернышевского
Саратовский областной институт развития образования
Комитет по информатизации Саратовской области
Комитет по образованию администрации муниципального образования «Город Саратов»
Автономная некоммерческая организация «Информационные технологии в образовании»
Автономная некоммерческая организация «Научно-исследовательский центр «Образование. Качество. Отрасль»»
IX Всероссийская (с международным участием) научно-практическая конференция
«Информационные технологии в образовании»
«ИТО-Саратов-2017»
2-3 ноября 2017 года, г. Саратов

СИСТЕМА ПОДГОТОВКИ ТЕСТОВЫХ НАБОРОВ ДЛЯ АВТОМАТИЧЕСКОЙ ПРОВЕРКИ РЕШЕНИЙ

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

Введение

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

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

 

Верное решение

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

На олимпиадах решение считается верным только в том случае, если оно правильно обработало все тесты из тестового набора [1]. В учебном процессе зачастую отступают от чистой дихотомии «верно/не верно» и вводят сравнение решений по количеству правильно обрабатываемых частных случаев. «Более правильной» считается та программа, которая выдает верный ответ для большего количества тестов.

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

Задача построения разбиения области входных данных на классы эквивалентности является непростой даже для специалистов [2]. Теория, позволяющая правильно выбирать представителей из каждого класса, также пока недостаточно проработана [3].

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

 

Задачные комплекты

Для проведения автоматической проверки при помощи системы АПР, необходимо предварительно создать задачный комплект. В него входят:

1)    условие задачи (текст);

2)    спецификация форматов ввода-вывода данных;

3)    тестовый набор;

4)    эталонное решение.

Ошибки разработчиков могут встретиться при создании любой из этих четырех частей [5], но наиболее сложной является задача создания полного тестового набора, а особенно проверки и доказательства его полноты [2].

Чем выше уровень олимпиады, тем большее количество человек принимают участие в создании задачного комплекта. Разумеется, один человек может быть одновременно автором и условия, и тестов, и эталонного решения. Однако для повышения надежности работу над задачным комплектом целесообразно поручать нескольким специалистам.

При индивидуальной разработке задачного комплекта его автор несет ответственность за все возможные ошибки. Чтобы облегчить самопроверку, большую часть работы необходимо передать системе подготовки тестовых наборов (СПТН), которая поможет автору задачи в поиске ошибок, неточностей, неполноты и т.п.

 

Создание задачного комплекта

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

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

2. Опираясь на спецификации Sи разбиение D, проектируется первоначальный тестовый набор, который используется при отладке эталонного решения.

3. Создается и отлаживается эталонное решение (ЭР) задачи.

 

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

 

Применение СПТН

На первом этапе разработки задачного комплекта СПТН может:

1.    Извлечь из текста условия предварительный набор спецификаций S0и предложить его на проверку автору задачи. Результатом должен стать набор авторских спецификаций S.

2.    Проверить заданные спецификации на непротиворечивость.

3.    Извлечь из спецификации Sграничные условия, особые точки, т.п.

4. Предложить предварительное разбиение D0пространства данных на очевидные классы эквивалентности (например, базовым может стать соображение «длины переменной»).

5.    Уточнить разбиение, основываясь на дополнительных сведениях, введенных автором задачи.

 

На втором этапе разработки [6] СПТН может:

1.    Основываясь на заданном разбиении D, создать набор входных «половинок» тестов.

2.    Если имеется авторский тестовый набор Т0, проверить его на полноту охвата заданного разбиения.

3.    Проверить соответствие авторских тестов заданным спецификациям.

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

 

Окончательный вариант тестового набора генерируется с использованием эталонного решения. На этом третьем этапе СПТН может:

1.    Проверить соответствие полученных выходных данных спецификациям S.

 

При коллективной разработке задачного комплекта СПТН должна предоставлять дополнительные возможности.

Предположим, что два автора АР1 и АР2 пишут два разных эталонных решения ЭР1 и ЭР2, используя для отладки два тестовых набора Т1 и Т2. Для каждого из них СПТН производит описанные выше действия, после чего возникает ещё один этап сравнения и объединения этих тестовых наборов.

Оба решения ЭР1 и ЭР2 необходимо протестировать на объединенном тестовом наборе Т = Т1 U Т2. При отсутствии явных ошибок этот тестовый набор также должен пройти проверку на полноту охвата заданного разбиения и на соответствие спецификациям.

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

Заметим, что при индивидуальной разработке задачного комплекта в качестве наборов Т1 и Т2 могут выступать авторский тестовый набор и автоматически сгенерированный тестовый набор.

 

Заключение

СПТН должна уметь оперировать разбиениями области входных данных и тестовыми наборами как их отображениями.

В части разбиений:

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

2.    Хранить разбиения в специально разработанном формате.

3.    Предоставлять возможность задать или исправить разбиение вручную: добавлять, удалять, объединять или дробить классы эквивалентности.

4.    Проверять разбиение на соответствие заданным спецификациям и ограничениям.

5.    Сравнивать два разбиения.

6.    Создавать объединения и пересечения разбиений.

 

В части тестовых наборов:

1.    Генерировать входные данные на основе имеющегося разбиения.

2.    Проверять, все ли классы эквивалентности из опорного разбиения представлены в некотором тестовом наборе.

3.    Проверять набор на избыточность относительно опорного разбиения.

4.    Объединять тестовые наборы (безусловное и условное объединения).

5.    Пополнять и сокращать тестовые наборы.

6.    Проверять соответствие тестов спецификациям.

7.    Сохранять тестовые наборы.

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

Список использованных источников
  1. ACM International Collegiate Programming Contest (Rules) https://icpc.baylor.edu/worldfinals/rules
  2. Кулямин В. В., Петухов А. А. Обзор методов построения покрывающих наборов. / ж. Программирование, 37(3). – 2011. – С. 3-41.
  3. Manpreet Kaur, Rupinder Singh. A Review of Software Testing Techniques /International Journal of Electronic and Electrical Engineering. ISSN 0974-2174, Volume 7, Number 5 (2014), pp. 463-474.
  4. Андреева Т. А. Возможность автоматизации процесса генерирования тестовых наборов. / ж. Universum: Технические науки. – N 8(41). – Москва, 2017 г. – с.5-7.
  5. Андреева Т. А. Структура и классификация текстов олимпиадных задач. / ж. Компьютерные инструменты в образовании. – N 3-4. – 2002. – C. 50-59.
  6. Андреева Т.А. Генерирование тестовых наборов для автоматического тестирования. / Материалы XXVII международной конференции «Современные информационные технологии в образовании». 28 июня 2016 г. ТРОИЦК – МОСКВА, 2016 г. – С.296-297.
Вид представления доклада  Публикация
Ключевые слова  автоматическая проверка решений, генерация тестовых наборов на основе спецификаций

В статусе «Черновик» Вы можете производить с тезисами любые действия.

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

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

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

Статус «Отклонен» означает, что по ряду причин, которые указаны в комментариях к тезису, Оргкомитет не может принять тезисы к публикации. Из отклоненных тезис в «Черновики» может вернуть только Председатель программного или председатель оргкомитета.