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. Модуль сравнения программного кода
Еще одно направление, работа над которым давно была в планах команды разработчиков
|