Title: ПРОЕКТ WEB-SYNDIC: WEB-СЕРВЕР ДЛЯ ТЕСТИРОВАНИЯ И ЭКСПЕРИМЕНТАЛЬНОГО АНАЛИЗА АЛГОРИТМОВ РЕШЕНИЯ ЛИНЕЙНЫХ ДИОФАНТОВЫХ УРАВНЕНИЙ
Author: kulakov
Last saved by: Bo0oG
Company: Petrozavodsk State University

ПРОЕКТ WEB-SYNDIC: WEB-СЕРВЕР ДЛЯ ТЕСТИРОВАНИЯ И ЭКСПЕРИМЕНТАЛЬНОГО АНАЛИЗА АЛГОРИТМОВ РЕШЕНИЯ ЛИНЕЙНЫХ ДИОФАНТОВЫХ УРАВНЕНИЙ В НЕОТРИЦАТЕЛЬНЫХ ЦЕЛЫХ ЧИСЛАХ

К.А.Кулаков, М.А.Крышень
Петрозаводский государственный университет
(185910, респ.Карелия, г.Петрозаводск, пр.Ленина, д.33)
Руководители проекта: к.т.н., доцент Богоявленский Ю. А. и к.ф.-м.н., доцент Корзун Д. Ж.
Система неотрицательных линейных диофантовых уравнений (система НЛДУ) — это система линейных уравнений с целочисленными коэффициентами и решениями в неотрицательных целых числах. Базисом Гильберта однородной системы НЛДУ (системы одНЛДУ) называется конечное множество неразложимых решений. Любое решение системы одНЛДУ может быть представлено в виде линейной комбинации базисных решений. Нами рассматривается частный класс систем одНЛДУ, ассоциированных с формальными грамматиками — системы одАНЛДУ. Для них известен псевдополиномиальный алгоритм нахождения базиса Гильберта, основанный на методах синтаксического анализа [1].
Анализ синтаксического алгоритма решения систем одАНЛДУ, включая тестирование его реализации, экспериментальное исследование сложности и сравнение с аналогами требует автоматической генерации тестовых систем одАНЛДУ с эталонными решениями. Системы одАНЛДУ должны генерироваться в широком диапазоне изменения таких параметров, как число уравнений и неизвестных в генерируемой системе, размер коэффициентов, число базисных решений и т.п. 
Целью проекта является разработка алгоритмов генерации тестовых систем одАНЛДУ различных классов, разработка web-сервера Web-SynDic для: 1) решения систем одАНЛДУ синтаксическим методом и другими алгоритмами, 2) автоматической генерации тестовых систем одАНЛДУ с эталонными решениями, 3) распределенного тестирования реализаций алгоритмов решения, 4) экспериментального анализа и сравнения синтаксического алгоритма с аналогами.
В ходе разработки нами получена теорема о преобразовании произвольной системы одАНЛДУ к одному из двух частных случаев. На основе теоремы предложено пять алгоритмов генерации тестовых систем одАНЛДУ: четыре алгоритма строят некоторые подклассы систем одАНЛДУ, а последний — более общий вариант. Реализована оригинальная технология автоматического тестирования, реализованная на языке C (соответствие ANSI и POSIX). В систему Web-SynDic включены два генератора систем одАНЛДУ специальных классов на основе преобразований Жордано и Гаусса.
Текущая версия системы Web-SynDic поддерживает два алгоритма нахождения базиса Гильберта: синтаксический (основной) [1] и алгоритм португальских математиков slopes (альтернативный). Другим альтернативным решателем выступает алгоритм lp_solve (симплекс-метод в сочетании с методом ветвей и границ для решения задачи целочисленного линейного программирования), который находит частное решение системы одАНЛДУ. 
Реализации алгоритмов — решатели и генераторы систем одАНЛДУ — являются внешними по отношению к web-системе. Это означает, что сами реализации алгоритмов недоступны непосредственно пользователям, демонстрируются лишь результаты работы этих алгоритмов. 
Система Web-SynDic предоставляет полноценную вычислительную услугу для научных исследований — решение задаваемых пользователем одиночных систем одАНЛДУ и их наборов. Также система Web-SynDic является средством распределенного тестирования алгоритмов решения. Любой запрос пользователя к услуге решения является тестом: найденные решения проверяются на корректность, в случае использования альтернативного решателя выполняется сравнение решений, полученных синтаксическим и альтернативным алгоритмами. Измеряемые показатели использования ресурсов позволяют экспериментально оценить эффективность решателей.
Сервером поддерживается полноценный набор документации проекта (общий объем — 363 с.). Документация пользователя включает руководство и обзор теории систем НЛДУ. Встроена система подсказок и примеров для пользователя. Поддерживаются регистрация пользователя (по желанию) и механизм обратной связи. Для работы с системой Web-SynDic достаточно стандартного Интернет обозревателя, используется технология тонкого web-клиента. Сервер реализован на Java, использует пакет Tomcat, поддерживаются операционные системы Windows NT и Linux. Трансляторы входных систем АНЛДУ во внутреннее представление реализованы с помощью программных средств jflex и byaccj. Исходный код системы содержит около 12 тыс. LOC. 
Проект по разработке Web-SynDic был начат 7.07.2003, первая рабочая версия получена 20.12.2003. В настоящее время выполнены вторая итерация разработки и публикация системы Web-SynDic в сети Интернет. На разработку было затрачено более 2300 человеко-часов. Основными разработчиками проекта являлись студенты К.А. Кулаков, М.А. Крышень, А.Ю. Сало, А.В. Ананьин. Первые два из них в настоящее время продолжают развитие этого проекта.
Система Web-SynDic внедрена в учебный и научно-исследовательский процессы на кафедре Информатики и математического обеспечения Петрозаводского государственного университета. Система представляет удобный инструмент для проведения анализа алгоритмов решения одАНЛДУ, а также может использоваться при решении задач математического моделирования, сводящихся к системам одАНЛДУ.
1.	Проект Web-SynDic. http://websyndic.cs.karelia.ru. 
2.	Web-ресурс разработчиков. http://websyndic.cs.karelia.ru/site.