СодержаниеОГЛАВЛЕНИЕ
ОГЛАВЛЕНИЕ 2
1. ВВЕДЕНИЕ 3
1.1. Глоссарий 3
1.2. Описание предметной области 3
1.3. Неформальная постановка задачи 4
1.4. Обзор существующих методов решения 4
1.4.1. MOSS 5
1.4.2. YAP3 5
1.4.3. JPlag 5
2. ТРЕБОВАНИЯ К ОКРУЖЕНИЮ 5
2.1. Требования к аппаратному обеспечению 5
2.2.Требования к программному обеспечению 6
2.3. Требования к пользователям 6
3. АРХИТЕКТУРА СИСТЕМЫ 6
4. СПЕЦИФИКАЦИЯ ДАННЫХ 7
4.1. Входные данные подсистемы обработки текста 7
4.2. Выходные данные подсистемы обработки текста 7
4.2.1. Описание простого нормализованного текста 7
4.2.2. Описание сложного нормализованного текста 7
4.3. Входные данные подсистемы сравнения текстов 7
4.4. Выходные данные подсистемы сравнения текстов 7
5. Функциональные требования 8
5.1. Подсистема обработки текста 8
5.2. Подсистема сравнения текстов 8
5.2. Подсистема управления и взаимодействия с пользователем 8
6. Требования к интерфейсу 8
6.1. cmp_frame 9
6.2. cmp_show_params 9
6.3. cmp_output_problem 9
6.4. cmp_output_team 10
6.5. cmp_show_sources 10
6.6. diff_runs_frame 10
6.7. cmp_show_part 10
6.8. cmp_show_part_team 10
7. ПРОЕКТ 11
7.1. Средства реализации 11
7.2. Классы 12
8. АЛГОРИТМЫ 12
8.1. Основные алгоритмы обработки текстов 12
8.2. Алгоритмы сравнения текстов 15
8.2.1. Сравнение с помощью утилиты DIFF 15
8.2.2. Специальный алгоритм 15
9. РЕАЛИЗАЦИЯ И ТЕСТИРОВАНИЕ 16
10. ЗАКЛЮЧЕНИЕ 16
Список использованной литературы 18Введение1. ВВЕДЕНИЕ
1.1. Глоссарий
Команда – группа из 1-3 человек, зарегистрированная в тестирующей системе.
Алгоритм – последовательность действий, решающая некоторую задачу.
Команда-участник – команда, зарегистрированная в некотором турнире как основной участник.
ooc-команда - команда, зарегистрированная в некотором турнире как участник вне конкурса (out of contest).
Аккаунт – регистрационная запись о команде в базе данных.
Текст – синтаксически правильный программный код, реализующий алгоритм решения некоторой задачи, разработанный некоторой командой и отправленный на проверку тестирующей системе.
Эквивалентные тексты – тексты, реализующие один и тот же алгоритм.
Коэффициент сходства – число, отражающее процент похожести двух алгоритмов, полученное из сравнения реализующих их текстов.
Таблица сравнения (сравнительная таблица) – таблица, в которой отражаются коэффициенты сходства текстов.
Полная таблица сравнения – формат таблицы сравнения, имеющий вид:
ID_1 ID_2 … ID_N
ID_1 A11 A12 A1N
ID_2 A21 A22 ... A2N
… ... ... ... ...
ID_N AN1 AN2 ... ANN
где Aij – число сравнения для текстов i и j.
ID_k – идентификатор, уникальный для каждого текста.
Таким образом, при построении полной сравнительной таблицы для N текстов, каждый текст сравнивается с каждым.
Частичная таблица сравнения – формат таблицы сравнения, имеющий вид:
ID 1-1 ID 1-2 A1
ID 2-1 ID 2-2 A2
… … ...
ID N-1 ID N-2 AN
При построении частичной сравнительной таблицы для N текстов необязательно сравнивать каждый текст с каждым, можно выбрать только определенные пары.
Порог похожести – такое число Ax, что два текста, у которых коэффициент сходства больше Ax, считаются очень похожими.
BEGIN-блок - последовательность операторов в операторных скобках BEGIN-END.
1.2. Описание предметной области
Каждый год на базе ИМиКН ДВГУ проводятся четвертьфиналы студенческого чемпионата мира АСМ по программированию. Два года назад выпускником ИМиКН Рожковым М. была написана тестирующая система CATS, позволяющая автоматизировать проверку задач, ведение базы данных чемпионатов и построение итоговой таблицы, а также предоставляющая возможность администрирования турниров. Со временем возможности CATS расширялись. Сейчас она активно используется и в образовательном процессе – при подготовке к чемпионатам АСМ, при занятиях школьного мастер-класса по программированию, при проведении городских и краевых школьных олимпиад по информатике.
1.2.1. Модуль сравнения программного кода
Еще одно направление, работа над которым давно была в планах команды разработчиковЛитератураСПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
[1] Рожков М. Система автоматического тестирования программ и организации соревнований по программированию, дипломная работа, Владивосток: 2004
[2] Храпченков И.Ф. Измерение степени сходства версий программного кода, дипломная работа, Владивосток: 2003
[3] George Columbow, Алгоритм преобразует алгоритм! www.citforum.ru
[4] Матросов А.В., Чаунин В.М. Perl, С.-Пб.: Питер, 2001 г., 587 с.
[5] Perl Release Notes
[6] http://html.manual.ru
[7] Firebird 1.5 Quick Start Guide, document version 2.1.1, IBPhoenix Editors, (1 March 2005)
[8] Грубер М., Введение в SQL
[9] Котеров Д., Apache + Perl + PHP3 + MySQL для Windows 95/98: руководство по установке, www.dklab.ru
[10] www.xpoint.ru
[11] www.sql.ru
|
