Проект Web-SynDic: разработка web-системы для демонстрации и тестирования синтаксических алгоритмов решения неотрицательных линейных диофантовых уравнений
Авторы: Кулаков Кирилл Александрович, 5 курс, математический факультет ПетрГУ;
Сало Алексей Юрьевич, 4 курс, математический факультет ПетрГУ;
Крышень Михаил Александрович, 3 курс, математический факультет ПетрГУ;
Ананьин Андрей Валерьевич, 3 курс, математический факультет ПетрГУ.
Научные руководители: Корзун Дмитрий Жоржевич, ст.преподаватель, к.ф.-м.н.;
Богоявленский Юрий Анатольевич, зав.кафедрой, доцент, к.т.н.
Кафедра информатики и математического обеспечения, Петрозаводский государственный университет, 185640, г.Петрозаводск, пр.Ленина, 33.
Неотрицательными линейными диофантовыми уравнениями (НЛДУ) называются линейные уравнения с целыми коэффициентами и с решениями в неотрицательных целых числах. В общем случае решение НЛДУ есть NP-полная или даже overNP- задача. Это включает задачи определения совместности, поиска частного решения, нахождения базиса Гильберта. В практических приложениях ограничения на время и память являются критичными. Полиномиальные алгоритмы решения частных классов НЛДУ, в том числе нахождения базиса Гильберта, могут быть построены на основе нового синтаксического метода решения НЛДУ [1,2], сводящего решение к построению синтаксических выводов в некоторой формальной грамматике. Такие системы называются ассоциированными с грамматикой (системы АНЛДУ).
В рамках представляемого нами проекта Web-SynDic — командного проекта по технологии производства программного обеспечения — реализуется уникальный Интернет-ресурс удаленной демонстрации и тестирования разработанных на кафедре оригинальных синтаксических алгоритмов решения систем АНЛДУ. Полученная программная система Web-SynDic позволяет исследователям задавать вручную или генерировать автоматически системы АНЛДУ, находить их базис Гильберта, проверять правильность результата, оценивать потребление ресурсов (системное и общее время, объем оперативной памяти) и сравнивать результаты решения и эффективность синтаксического алгоритма с известными аналогами.
Система Web-SynDic поддерживает два алгоритма нахождения базиса Гильберта: синтаксический (основной) [2] и slopes (альтернативный) [3]. Другим альтернативным решателем выступает алгоритм lp_solve [4], реализующий симплекс-метод в сочетании с методом ветвей и границ. Этот алгоритм позволяет находить частное ненулевое решение системы АНЛДУ на основе решения задачи целочисленного линейного программирования.
Система Web-SynDic предоставляет полноценную вычислительную услугу для научных исследований — удаленное решение задаваемых пользователем: а) одиночных систем АНЛДУ, б) набора систем АНЛДУ. Это включает и системы большой размерности (до нескольких тысяч уравнений и неизвестных), решение которых известными альтернативными алгоритмами затруднительно.
Наряду с этим система Web-SynDic является и средством распределенного beta-тестирования алгоритмов решения систем АНЛДУ: 1) найденные решения проверяются на корректность, 2) для альтернативного решателя выполняется сравнение решений, полученных разными алгоритмами, 3) возможно непосредственное вмешательство пользователя, если он считает найденное решение неверным или хочет прокомментировать результаты. Для генерации тестовых систем, оценки потребления ресурсов и обработки результатов решения реализована оригинальная технология автоматического тестирования, включающая специально разработанные генераторы тестовых систем.
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

Подпись руководителя

«_____»___________________