УДК 519.1+681.3
К.А. Кулаков (5 курс), А.Ю. Сало (4 курс), А.В. Ананьин (3 курс), М.Ю. Крышень (3 курс), Д.Ж. Корзун (менеджер проекта, к.ф.-м.н.), Ю.А. Богоявленский, рук. проекта, к.т.н., зав.каф.
Кафедра информатики и математического обеспечения, ПетрГУ

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

Неотрицательными линейными диофантовыми уравнениями (НЛДУ) называются линейные уравнения с целыми коэффициентами и с решениями в неотрицательных целых. Они являются актуальным объектом исследований в теории чисел, теории полугрупп и теории алгоритмов, а также находят многочисленные практические приложения в задачах целочисленного программирования, исследования операций и кибернетики.
В общем случае решение НЛДУ есть NP-полная или даже overNP- задача. Однако в приложениях ограничения на время и память являются критичными. Полиномиальные алгоритмы решения частных классов НЛДУ, в том числе нахождения базиса Гильберта, могут быть построены на основе нового синтаксического метода решения НЛДУ [1,2], сводящего решение к построению синтаксических выводов в некоторой формальной грамматике. Такие системы называются ассоциированными с грамматикой (системы АНЛДУ). Алгоритмы реализованы на языке C и автоматически протестированы [2,5].
Целью проекта Web-SynDic является разработка web-системы для демонстрации и тестирования этих алгоритмов. Она позволяет исследователям через Интернет задавать вручную или генерировать автоматически системы АНЛДУ, находить их базис Гильберта, проверять правильность результата, оценивать потребление ресурсов и сравнивать эффективность нашего алгоритма с альтернативными (slopes [3], lp_solve [4]).
Официальные языки проекта — русский и английский. Поддерживается полноценный набор проектной документации на основе Adaptable Process Model (R.S.Pressman & Associates, Inc.). Документация пользователя включает руководство и обзор теории систем АНЛДУ. Встроена система подсказок и примеров для пользователя. Поддерживаются регистрация пользователя (по желанию) и механизм обратной связи.
Для запуска клиента Web-SynDic достаточно стандартного Интернет обозревателя. Сервер реализован на Java, использует пакет Tomcat, работает в ОС Windows NT и Linux. Трансляторы входных систем АНЛДУ реализованы с помощью jflex и byaccj. Исходный код системы содержит около 110 тыс. строк кода Java и 166 Кб страниц JSP. Для генерации, решения и обработки результатов применяется технология автоматического тестирования [5], реализованная на языке C (соответствие ANSI и POSIX).
Проект начат 7.07.2003, рабочая версия получена в 20.12.2003. В настоящее время выполняется α-тестирование. Публикация системы в Интернет планируется в 2004 г.
Система Web-SynDic обеспечит демонстрацию синтаксического метода широкому кругу исследователей, выполнение распределенного β-тестирования алгоритмов.
1.	Богоявленский Ю.А., Корзун Д.Ж. Общий вид решения системы линейных диофантовых уравнений, ассоциированной с контекстно-свободной грамматикой. Труды Петрозаводского государственного университета. Сер. «Прикладная математика и информатика». Вып. 6. Петрозаводск: Изд-во ПетрГУ, 1998. С.79-94.
2.	Корзун Д.Ж. Синтаксические алгоритмы решения неотрицательных линейных диофантовых уравнений и их приложение к моделированию структуры нагрузки канала Интернет. Дисс. на соиск. канд. физ.-мат. наук. Петрозаводск, ПетрГУ, 2002. 185 с.
3.	M. Filgueiras, A.-P. Tomas. Package Slopes. http://www.ncc.up.pt/~apt/dioph/
4.	M. Berkelaar. LP_SOLVE. http://www.cs.sunysb.edu/~algorith/implement/lpsolve/implement.shtml
5.	Кулаков К.А., Корзун Д.Ж. Технология автоматизации тестирования алгоритмов решения неотрицательных линейных диофантовых уравнений. Данный сборник.