Проект Web-SynDic: разработка web-системы для демонстрации и тестирования синтаксических алгоритмов решения неотрицательных линейных диофантовых уравнений



Скачать 29.55 Kb.
Дата12.10.2012
Размер29.55 Kb.
ТипДокументы
Проект 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
Подпись руководителя

«_____»___________________

Похожие:

Проект Web-SynDic: разработка web-системы для демонстрации и тестирования синтаксических алгоритмов решения неотрицательных линейных диофантовых уравнений iconКафедра информатики и математического обеспечения, ПетрГУ
Целью проекта Web-SynDic является разработка web-системы для демонстрации и тестирования этих алгоритмов. Она позволяет исследователям...
Проект Web-SynDic: разработка web-системы для демонстрации и тестирования синтаксических алгоритмов решения неотрицательных линейных диофантовых уравнений iconК. А. Кулаков, М. А. Крышень
Целью проекта является разработка алгоритмов генерации тестовых систем оданлду различных классов, разработка web-сервера Web-SynDic...
Проект Web-SynDic: разработка web-системы для демонстрации и тестирования синтаксических алгоритмов решения неотрицательных линейных диофантовых уравнений iconМеждународный Фестиваль «Звезды Нового Века» 2012 Точные науки (от 14 до 17 лет) «Исследование методов решения линейных диофантовых уравнений»
Практическая часть исследования. Методы решения линейных диофантовых уравнений с двумя переменными
Проект Web-SynDic: разработка web-системы для демонстрации и тестирования синтаксических алгоритмов решения неотрицательных линейных диофантовых уравнений icon«Web- проектирование и Web-дизайн. Пакет FrontPage2003. Управление Web-сайтом»
Цель работы: Ознакомление с основами Web-проектирования и Web-дизайна. Формирование навыков использования пакета FrontPage 2002/2000...
Проект Web-SynDic: разработка web-системы для демонстрации и тестирования синтаксических алгоритмов решения неотрицательных линейных диофантовых уравнений iconСистема web-syndic: разработка программного обеспечения на основе прецедентов
Интернет задавать вручную или генерировать автоматически системы анлду, находить их базис Гильберта, проверять правильность результата,...
Проект Web-SynDic: разработка web-системы для демонстрации и тестирования синтаксических алгоритмов решения неотрицательных линейных диофантовых уравнений iconПрограмма по курсу «Линейная алгебра», 2 семестр 2011/2012 учебного года повышенный уровень
Системы линейных уравнений. Алгоритм Гаусса упрощения системы линейных уравнений и матрицы. Главные и свободные неизвестные. Разложение...
Проект Web-SynDic: разработка web-системы для демонстрации и тестирования синтаксических алгоритмов решения неотрицательных линейных диофантовых уравнений iconСистемы линейных уравнений
Решить систему линейных уравнений – значит указать все решения системы, то есть такие наборы значений переменных, которые обращают...
Проект Web-SynDic: разработка web-системы для демонстрации и тестирования синтаксических алгоритмов решения неотрицательных линейных диофантовых уравнений iconЛекция № Методы решения систем линейных уравнений
Мы будем рассматривать частный случай системы линейных уравнений, а именно случай, когда т е число уравнений равно числу неизвестных....
Проект Web-SynDic: разработка web-системы для демонстрации и тестирования синтаксических алгоритмов решения неотрицательных линейных диофантовых уравнений iconСоздание Web страниц с помощью html
Обучающая: дать представление основных понятий Web – сервер, Web – сайт, Web – страница, гиперссылка, тег, структура html – документа,...
Проект Web-SynDic: разработка web-системы для демонстрации и тестирования синтаксических алгоритмов решения неотрицательных линейных диофантовых уравнений iconРешение систем линейных алгебраических уравнений с ленточными матрицами. Пример решения линейной системы с трехдиагональной матрицей
Метод Гаусса для решения системы линейных алгебраических уравнений. Устойчивость метода Гаусса. Использование метода Гаусса для вычисление...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org