Кафедра информатики и математического обеспечения, ПетрГУ



Скачать 32.42 Kb.
Дата01.01.2013
Размер32.42 Kb.
ТипДокументы
УДК 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. Кулаков К.А., Корзун Д.Ж. Технология автоматизации тестирования алгоритмов решения неотрицательных линейных диофантовых уравнений. Данный сборник.

Похожие:

Кафедра информатики и математического обеспечения, ПетрГУ iconАвтоматизированная система обработки и анализа литературных текстов «смалт»
Республика Карелия, г. Петрозаводск, пр. Ленина, 33, ПетрГУ, математический факультет, кафедра математического моделирования систем...
Кафедра информатики и математического обеспечения, ПетрГУ iconРазвитие учебной дисциплины «технология разработки программного обеспечения» в Петрозаводском государственном университете
Ледние три года в области «технология разработки программного обеспечения» произошло существенное развитие элементов учебного плана...
Кафедра информатики и математического обеспечения, ПетрГУ iconПетргу положение об Открытом университете Петргу общие положения
...
Кафедра информатики и математического обеспечения, ПетрГУ iconКафедра информатики и икт
Кафедра информатики и икт осуществляет обучение по предмету в 3-5 и 8-11 классах
Кафедра информатики и математического обеспечения, ПетрГУ iconКафедра «Прикладная математика и фундаментальная информатика»
Кафедра физико-математического направления высшего образования по прикладной математике и информатике. Кафедра ведет бюджетный набор...
Кафедра информатики и математического обеспечения, ПетрГУ iconРазработка экономико-математических методов управления образовательными информационными ресурсами
Диссертация выполнена на кафедре Математического обеспечения и администрирования информационных систем Московского государственного...
Кафедра информатики и математического обеспечения, ПетрГУ iconКафедра, как и человек, как и государство, имеет свою историю. Для кафедры прикладной математики и кибернетики она молода, но интересна и поучительна. И, безусловно, связана с историей одного человека
Ленинградских вузов, безусловно, насторожил тихий омут физико-математического факультета ПетрГУ. Я вспоминаю первую открытую лекцию...
Кафедра информатики и математического обеспечения, ПетрГУ iconУчебно-методический комплекс по дисциплине «B230100-11-2 r k plM» «Дисциплина по выбору-9 (Кафедра информатики и ито)»
«B230100-11-2 r k plM» «Дисциплина по выбору-9 (Кафедра информатики и ито)» (Практикум по программированию на JavaScript)
Кафедра информатики и математического обеспечения, ПетрГУ iconПоложение о проведении олимпиады по базовому курсу информатики среди общеобразовательных учреждений г. Новосибирска
Научно-образовательный центр информатики и информационных технологий Института физико-математического информационно экономического...
Кафедра информатики и математического обеспечения, ПетрГУ iconКак добраться до учебных корпусов петргу
Троллейбус №2, №5 (Петргу (Студенческий бульвар) – ул. Лыжная, а дальше пешком до Банковской школы)
Разместите кнопку на своём сайте:
ru.convdocs.org


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