СИСТЕМА WEB-SYNDIC ДЛЯ ДЕМОНСТРАЦИИ И ИССЛЕДОВАНИЯ
СИНТАКСИЧЕСКИХ АЛГОРИТМОВ РЕШЕНИЯ ЛИНЕЙНЫХ ДИОФАНТОВЫХ
УРАВНЕНИЙ В НЕОТРИЦАТЕЛЬНЫХ ЦЕЛЫХ ЧИСЛАХ
Д.Ж. Корзун, Ю.А. Богоявленский, К.А. Кулаков, А.Ю. Сало, М.А. Крышень, А.В. Ананьин
Неотрицательными линейными диофантовыми уравнениями (НЛДУ) называются линейные уравнения с целыми коэффициентами и с решениями в неотрицательных целых числах. Они являются актуальным объектом научных исследований в теории чисел, теории полугрупп и теории алгоритмов, а также находят важные приложения в задачах целочисленного программирования, исследования операций и кибернетики.
В общем случае решение НЛДУ есть NР-полная или даже overNP- задача. Это включает задачи определения совместности, поиска частного решения, нахождения базиса Гильберта. В практических приложениях ограничения на время и память являются критичными. Полиномиальные алгоритмы решения частных классов НЛДУ, в том числе нахождения базиса Гильберта, могут быть построены на основе нового синтаксического метода решения НЛДУ [1,2], сводящего решение к построению синтаксических выводов в некоторой формальной грамматике. Такие системы называются ассоциированными с грамматикой (системы АНЛДУ).
В рамках представляемого нами программного проекта Web-SynDic реализуется уникальный Интернет-ресурс для удаленной демонстрации и тестирования разработанных синтаксических алгоритмов. Система Web-SynDic позволяет исследователям задавать вручную или генерировать автоматически системы АНЛДУ, находить их базис Гильберта, проверять правильность результата, оценивать потребление ресурсов и сравнивать эффективность синтаксического алгоритма с альтернативными.
В качестве примера рассмотрим следующую однородную систему АНЛДУ
x1+x2 = 2*x1 + 3*xЗ,
xЗ + x4 = х1 + 2*x2 + xЗ, 
базис Гильберта которой состоит из двух решений
h1= (1,1,0,3) и h2 = (0,3,1,6).
Общее решение представляется в виде неотрицательной целочисленной линейной комбинации базисных:
x = а*h1+ b*h2, где a и b - произвольные неотрицательные целые числа.
Система Web-SynDic поддерживает два алгоритма нахождения базиса Гильберта: синтаксический (основной) [2] и slopes (альтернативный) [3]. Для решения приведенной выше системы АНЛДУ оба алгоритма затрачивают примерно одинаковый объем ресурсов - около 10мс системного времени процессора и 2Мб оперативной памяти (CPU: Intel(R) Се1егоп(ТМ) 1200МГц, RAM: 512Мб, Linux 2.4.21). В то же время, при решении систем большей размерности (более 10-15 неизвестных и уравнений или с коэффициентами, превышающими значения 50-100) использование алгоритма slopes уже невозможно, в отличие от синтаксического алгоритма.
Другим альтернативным решателем выступает алгоритм lp_solve [4], реализующий симплекс-метод в сочетании с методом ветвей и границ. Этот алгоритм позволяет находить частное ненулевое решение системы АНЛДУ на основе решения задачи целочисленного линейного программирования (ЦЛП) с целевой функцией
x1 + x2 + ... + x[m] -> min 
и дополнительным ограничением (отсечение нулевого решения)
x1 + x2 + ... + x[m] >= 1, 
где m - число неизвестных.
Так, для приведенного ранее примера, соответствующая задача формулируется следующим образом:
x1 + x2 + xЗ + x4 -> min
x1 + x2 = 2*x1 + 3*xЗ
x3 + x4 = x1 + 2*x2 + xЗ
x1 + x2 + xЗ + x4 >= 1
x1, x2, xЗ, x4 - неотрицательные целые.
Оптимум достигается на одном из базисных решений
x = (1,1,0,3)
Его нахождение с помощью решателя lp_solve требует примерно такого же объема вычислительных ресурсов, что и первые два решателя. Отметим, что при этом решается более узкая задача по сравнению с задачей нахождения всего базиса Гильберта. Несмотря на это, методы ЦЛП становятся неэффективными для задач большой размерности. Так, в случае однородных систем АНЛДУ, при увеличении числа уравнений и неизвестных до нескольких десятков решатель lp_solve "погружается в вычисления" и решение за выделяемый период времени становится невозможным (в системе Web-SynDic: ограничение по умолчанию - 120с и может варьироваться).
Таким образом, система Web-SynDic удаленно демонстрирует эффективность работы синтаксического алгоритма решения систем АНДЦУ в сравнении с известными аналогами. Выполняется измерение затрачиваемых на решение каждым из алгоритмов вычислительных ресурсов (системное и общее время, объем оперативной памяти). В дальнейшем предполагается подключение и других альтернативных решателей.
В рамках такой демонстрации система Web-SynDic также предоставляет полноценную вычислительную услугу для научных исследований - удаленное решение задаваемых пользователем:
а) одиночных систем АНДЦУ, б) набора систем АНЛДУ.
Это включает и системы большой размерности (до нескольких тысяч уравнений и неизвестных), решение которых за приемлемое время возможно только лишь с помощью предлагаемого нами синтаксического алгоритма.
Наряду с этим система Web-SynDic является и средством распределенного beta-тестирования алгоритмов решения систем АНЛДУ. Любой запрос пользователя к услуге решения является тестом: найденные решения проверяются на корректность, в случае использования альтернативного решателя выполняется сравнение решений, полученных разными алгоритмами (синтаксическим и альтернативным). Кроме автоматических средств контроля возможно непосредственное вмешательство пользователя, если он считает найденное решение неверным или хочет прокомментировать результаты решения. Измеряемые показатели использования ресурсов позволяют экспериментально оценить эффективность решателей - как для конкретной системы АНЛДУ, так и для некоторого их множества.
Для задачи распределенного тестирования алгоритмов важной услугой является генерация тестовых систем, оценка потребления ресурсов и обработка результатов решения. Для этого в рамках системы Web-SynDic реализована оригинальная технология автоматического тестирования, реализованная на языке С (соответствие ANSI и POSIX)[6,7].
В настоящее время система Web-SynDic  поддерживает два генератора систем АНЛДУ: на основе преобразований Жордано и Гаусса. Эти генераторы позволяют строить системы АНДЦУ специальных классов. Основная проблема заключается не просто в построении системы АНДЦУ, а в одновременном построении соответствующего системе базиса Гильберта - для последующего сравнения с решением, полученным тестируемым алгоритмом. В такой постановке задача генерации представляет самостоятельный интерес, текущие результаты представлены в [6].
Алгоритмы - решатели и генераторы систем АНЛДУ - являются внешними по отношению к web-системе. Это означает, что сами реализации алгоритмов недоступны непосредственно пользователям, демонстрируются лишь результаты работы этих алгоритмов. Таким образом нами решается задача обеспечения защиты реализаций алгоритмов от несанкционированного доступа.
Официальные языки разработки проекта Web-SynDic — русский и английский. Поддерживается полноценный набор проектной документации на основе Adaptable Process Model (R.S.Pressman & Associates, Inc.), см. ресурс разработки http://zeta.cs.karelia.ru/Web-SynDic/doc/eng/. Документация пользователя включает руководство и обзор теории систем АНЛДУ. Встроена система подсказок и примеров для пользователя. Поддерживаются регистрация пользователя (по желанию) и механизм обратной связи. Для запуска клиента Web-SynDic достаточно стандартного Интернет обозревателя - используется технология тонкого web-клиента. Сервер реализован на Java, использует пакет Tomcat, поддерживаются операционные системы Windows NT и Linux. Трансляторы входных систем АНЛДУ во внутреннее представление реализованы с помощью программных средств jflex и byaccj. Исходный код системы содержит около 10 тыс. строк кода Java и 70 Кб страниц JSP.
Проект по разработке Web-SynDic был начат 7.07.2003, первая рабочая версия получена 20.12.2003. В настоящее время выполняется альфа-тестирование. Публикация системы в Интернет планируется осенью 2004 г.

ЛИТЕРАТУРА:
1.   Богоявленский Ю.А., Корзун Д.Ж. Общий вид решения системы линейных диофантовых уравнений, ассоциированной с контекстно-свободной грамматикой. Труды Петрозаводского государственного университета. Сер. "Прикладная математика и информатика". Вып. 6. Петрозаводск: Изд-во ПетрГУ, 1998. С.79-94.
2.   Корзун Д.Ж. Синтаксические алгоритмы решения неотрицательных линейных диофантовых уравнений и их приложение к моделированию структуры нагрузки канала Интернет. Дисс. на соиск. канд. физ.-мат. наук. Петрозаводск, ПетрГУ, 2002. 185 с.
3.   M. Filgueras, 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.html
5.   Кулаков К.А., Сало А.Ю., Ананьин А.В., Крышень, М.А., Корзун Д.Ж., Богоявленский Ю.А. Web-SynDic - система демонстрации и тестирования синтаксических алгоритмов решения неотрицательных линейных диофантовых уравнений. Материалы межвузовского конкурса-конференции студентов и молодых ученых Северо-Запада "Технологии Microsoft в теории и практике программирования". СПб.: Изд-во СПбГПУ, 2004. с.43-44.
6.   Кулаков К.А. Тестирование и экспериментальный анализ алгоритмов решения неотрицательных линейных диофантовых уравнений. Выпускная квалификационная работа бакалавра, Петрозаводск, ПетрГУ, 2003. 42 с.
7.   Кулаков К.А., Корзун Д.Ж. Технология автоматизации тестирования алгоритмов решения неотрицательных линейных диофантовых уравнений. Материалы межвузовского конкурса-конференции студентов и молодых ученых Северо-Запада "Технологии Microsoft в теории и практике программирования". СПб.: Изд-во СПбГПУ, 2004. с. 142-143.