СодержаниеСодержание
СОДЕРЖАНИЕ 2
1. ВВЕДЕНИЕ 3
1.1. ГЛОССАРИЙ 3
1.2. ОПИСАНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ 3
1.2.1. CATS 3
1.2.2. Тесты и проблема их объема 3
1.2.3. Генерация тестов 3
1.3. НЕДОСТАТКИ СУЩЕСТВУЮЩЕГО ПОДХОДА 4
1.4. ФОРМАЛЬНОЕ ОПИСАНИЕ ВХОДНЫХ ДАННЫХ 4
1.5. ВСПОМОГАТЕЛЬНАЯ БИБЛИОТЕКА 4
1.6. НЕФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ 4
1.7. МАТЕМАТИЧЕСКИЕ МЕТОДЫ ГЕНЕРИРОВАНИЯ СЛУЧАЙНЫХ ДАННЫХ 5
1.7.1. Генерирование случайного целого числа 5
1.7.2. Генерирование случайного действительного числа 5
1.7.3. Генерирование случайной строки 5
2. ТРЕБОВАНИЯ К ОКРУЖЕНИЮ 5
3. ЯЗЫК ФОРМАЛЬНОГО ОПИСАНИЯ 6
3.1. ОБЩАЯ СТРУКТУРА ЯЗЫКА 6
3.2. ТИПЫ ОБЪЕКТОВ 6
3.2.1. newline 6
3.2.2. softline 6
3.2.3. integer 6
3.2.4. float 7
3.2.5. string 7
3.2.6. seq 7
3.3. ТИПЫ АТРИБУТОВ 7
3.3.1. ident 7
3.3.2. int 7
3.3.3. intrange 7
3.3.4. chars 8
3.4. СИНТАКСИС 8
3.5. ПРИМЕРЫ 8
3.5.1. Пример 1 9
3.5.2. Пример 2 9
4. ФУНКЦИОНАЛЬНЫЕ ТРЕБОВАНИЯ 9
5. ПРОЕКТ 9
5.1. СТРУКТУРА СИСТЕМЫ 9
5.2. СРЕДСТВА РАЗРАБОТКИ 10
5.3. ВСПОМОГАТЕЛЬНАЯ БИБЛИОТЕКА 10
5.3.1. Генерирование случайных чисел 10
5.3.2. Обработка ошибок 11
5.3.3. Лексический анализ 11
5.3.4. Синтаксический анализ 11
5.3.5. Генерирование данных 12
5.3.6. Прочие функции 13
5.4. ОСНОВНАЯ БИБЛИОТЕКА 13
5.4.1. Обработка ошибок 14
5.4.2. Интерфейс библиотеки 14
5.4.3. Параметры командной строки 14
5.4.4. Универсальный генератор тестов 15
5.5. ИЗМЕНЕНИЯ В CATS 15
6. РЕАЛИЗАЦИЯ И ТЕСТИРОВАНИЕ 15
6.1. ОБЪЕМ КОДА 15
6.2. ТЕСТИРОВАНИЕ 15
ЗАКЛЮЧЕНИЕ 15
ПРИЛОЖЕНИЕ 1. АНАЛИЗ ЗАДАЧ ПРОШЛЫХ ЛЕТ 16
СПИСОК INTERNET-РЕСУРСОВ 19
СПИСОК ЛИТЕРАТУРЫ 19Введение1. Введение
Данная курсовая работа направлена на разработку и внедрение в систему CATS меха-низма, позволяющего упростить создание тестовых данных. Вместе с этим рассматривается вопрос о формальном описании тестов к задачам.
1.1. Глоссарий
Randseed — первый элемент в последовательности псевдослучайных чисел.
Блок — набор последовательных символов в файле.
Генератор тестов (генератор) — программа, выходными данными которой является тест для задачи. Генератор, как правило, разрабатывается автором задачи или тестов к ней.
Задача — формальное описание некоторой алгоритмической задачи в виде текстового документа, набора тестов, необходимых для проверки правильности решений, и программы проверки.
Пакет задачи — задача в специальном документированном формате.
1.2. Описание предметной области
1.2.1. CATS
В последние годы бурно развивается спортивное программирование — особый вид со-ревнований, в которых участникам предлагается решать алгоритмические задачи.
Для автоматизации проведения соревнований существует специальное программное обеспечение — проверяющие системы. Одна из таких систем, CATS [1], разработана на ка-федре информатики ДВГУ. Система успешно используется для проведения четвертьфиналь-ных соревнований чемпионата мира по программированию (ACM ICPC), городских и крае-вых олимпиад школьников, личных и командных тренировок.
1.2.2. Тесты и проблема их объема
Существуют различные схемы проведения соревнований в области спортивного про-граммирования (правила ACM ICPC [6][1], правила школьных олимпиад по информатике [10], схемы проведения соревнований программ искусственного интеллекта [8], правила со-ревнований организации TopCoder [7] и т. д.), но общим для большинства из них остается принцип проверки — решения проверяются на наборе тестов одинаковом для всех участни-ков.
При подготовке тестов жюри сталкивается с проблемой большого (порядка мегабайта на тест) объема тестовых данных. Создание таких тестов вручную невозможно в приемлемые сроки, а хранение их в явном виде нерационально. Однако, присутствие тестов такого объе-ма необходимо для всесторонней проверки решений участников.
1.2.3. Генерация тестов
В настоящий момент общепринятой практикой в решении проблемы создания и хране-ния «больших» тестов является написание генераторов. Кроме того, генераторы с различ-ными целями применяются и для создания тестов малого объема (сравнимого с кодом самого генератора). Например, с помощью такой программы можно подчеркнуть структуру и смысл теста.
Существует множество тестирующих систем. Но обычно проблема генерации тестов не рассматривается в рамках системы — организацию генераторов осуществляет жюри. Такой подход используется в системах E-judge [12] и SPOJ Ошибка! Источник ссылки не най-ден..
Подобным образом организовано и тестирование решений участников на Всероссий-ских олимпиадах школьников по информатике (материалы олимпиад доступны по адресу [9]).
Сами генераторы могут содержать ошибки, связанные, как правило, с несоответствием генерируемых данных ограничениям на входные данные. Организаторы школьных олимпиад по информатике в США (USACO) используют на соревнованиях высокого уровня для отладЛитератураСписок internet-ресурсов
[1] CATS, http://imcs.dvgu.ru/cats/docs
http://imcs.dvgu.ru/event/jpa/2007/ai_colors.html
http://neerc.ifmo.ru /information/ contest-rules.html
[2] Mersenne Twister Home Page, http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
[3] North-Eastern European Regional Contest Rules,
[4] Perl Manual, http://perldoc.perl.org/
[5] Sphere Online Judge, http://www.spoj.pl/
[6] The Rules of ACM-ICPC World Finals, http://icpc.baylor.edu/icpc/finals/About.htm
[7] TopCoder, Inc., http://www.topcoder.com/tc
[8] Задача для соревнований ИИ: Builders and painters,
[9] Олимпиады по информатике, http://neerc.ifmo.ru/school/information/index.html
[10] Сайт IOI'2007, http://www.hsin.hr/ioi2007
Список литературы
[11] «Compiler Construction», Wirth N., 2005, http://www.oberon.ethz.ch/WirthPubl/CBEAll.pdf
[12] Документация системы E-judge, http://www.ejudge.ru/documentation.shtml
[13] «Система автоматического тестирования программ и организации соревнований по программированию», Рожков М., 2004,
http://imcs.dvgu.ru/works/data/2004/259_Rozhkov_d.rar'
|
