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




Скачать 37.89 Kb.
НазваниеПроект web-syndic: web-сервер для тестирования и экспериментального анализа алгоритмов решения линейных диофантовых уравнений в неотрицательных целых числах
Дата06.10.2012
Размер37.89 Kb.
ТипДокументы
ПРОЕКТ 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.

Похожие:

Проект web-syndic: web-сервер для тестирования и экспериментального анализа алгоритмов решения линейных диофантовых уравнений в неотрицательных целых числах iconПроект Web-SynDic: разработка web -системы для демонстрации и тестирования синтаксических алгоритмов решения неотрицательных линейных диофантовых уравнений
Проект Web-SynDic: разработка web-системы для демонстрации и тестирования синтаксических алгоритмов решения неотрицательных линейных...
Проект web-syndic: web-сервер для тестирования и экспериментального анализа алгоритмов решения линейных диофантовых уравнений в неотрицательных целых числах iconСистема web-syndic для демонстрации и исследования синтаксических алгоритмов решения линейных диофантовых уравнений в неотрицательных целых числах
Д. Ж. Корзун, Ю. А. Богоявленский, К. А. Кулаков, А. Ю. Сало, М. А. Крышень, А. В. Ананьин
Проект web-syndic: web-сервер для тестирования и экспериментального анализа алгоритмов решения линейных диофантовых уравнений в неотрицательных целых числах iconПрограмма элективного курса по алгебре «Методы решения рациональных уравнений и систем уравнений» для учащихся 9 класса
В лучшем случае, они могут только угадывать корни в целых числах. Данный элективный курс позволит ликвидировать этот пробел. Учащиеся...
Проект web-syndic: web-сервер для тестирования и экспериментального анализа алгоритмов решения линейных диофантовых уравнений в неотрицательных целых числах iconЗащита изображений на основе решения систем диофантовых уравнений и неравенств
Следовательно, встает важный вопрос о ее защите. В работе предлагается метод преобразования, защиты и передачи изображений, основанный...
Проект web-syndic: web-сервер для тестирования и экспериментального анализа алгоритмов решения линейных диофантовых уравнений в неотрицательных целых числах icon«Решение задач в целых числах»
«багаж» знаний теоремами и задачами, которые мы не изучали на уроках математики, но они необходимые для решения подобных задач. Также...
Проект web-syndic: web-сервер для тестирования и экспериментального анализа алгоритмов решения линейных диофантовых уравнений в неотрицательных целых числах iconИстория развития Интернет
Службы Интернета: World Wide Web. Web-браузеры. Навигация. Работа с документом. Прокси-сервер 34
Проект web-syndic: web-сервер для тестирования и экспериментального анализа алгоритмов решения линейных диофантовых уравнений в неотрицательных целых числах iconОбратный прокси-сервер в рамках системы управления информационным обменом сети web-порталов
В данной статье рассмотрены решения по построению подсистемы разграничения доступа к Web-порталам. Произведено моделирование взаимодействия...
Проект web-syndic: web-сервер для тестирования и экспериментального анализа алгоритмов решения линейных диофантовых уравнений в неотрицательных целых числах iconПрограмма вступительных испытаний в магистратуру по направлению 010100. 68 Математика Программа обсуждена на заседании кафедры ит
Системы линейных уравнений. Метод Гаусса решения систем линейных уравнений. Определитель матрицы. Свойства определителя. Метод Крамера...
Проект web-syndic: web-сервер для тестирования и экспериментального анализа алгоритмов решения линейных диофантовых уравнений в неотрицательных целых числах iconПредложение методики нагрузочного тестирования web-приложений
Предлагается подход к проведению тестирования для оценки качества работы web-приложений при различных уровнях нагрузки. Данная разработка...
Проект web-syndic: web-сервер для тестирования и экспериментального анализа алгоритмов решения линейных диофантовых уравнений в неотрицательных целых числах iconWeb dizains web design
Основные компоненты web-страницы и способы их визуального представления на страницах сайта
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница