Транслятор однородной системы неотрицательных линейных диофантовых уравнений, ассоциированных с формальной грамматикой

Вернуться к списку проектов На главную страницу курса

Заказчик

Корзун Дмитрий Жоржевич, доцент, к.ф.-м.н., кафедра Информатики и математического обеспечения. Эл.почта: dkorzun@cs.karelia.ru. Раб.тел.: 711084. 217 каб.
Кулаков Кирилл Александрович, преподаватель, кафедра Информатики и математического обеспечения. Эл.почта: kulakov@cs.karelia.ru. Раб.тел.: 711015. 215 каб.

Аннотация проекта

Данный проект выполняется в рамках разработки системы Web-SynDic [1] - web-системы демонстрации, тестирования и экспериментального анализа синтаксических алгоритмов решения неотрицательных линейных диофантовых уравнений (НЛДУ). Данная система позволяет удаленно решать системы НЛДУ специального вида (ассоциированные с формальной грамматикой однородные системы НЛДУ - системы одАНЛДУ). В качестве основного алгоритма решения используется решатель syntactic [2].
В настоящее время к системе Web-SynDic подключен транслятор, преобразующий исходную систему одАНЛДУ, представленную в текстово-математическом виде во внутренний формат системы Web-SynDic. В то же время, известно преобразование любой системы одАНЛДУ к более простому виду [3].
Требуется разработать транслятор (Java, jflex, jyacc), который бы выполнял упомянутое преобразование исходной системы одАНЛДУ. Исходная система и преобразованная система представляются в текстово-математическом виде. За основу берется уже имеющийся транслятор системы Web-SynDic.

Первичные требования

Входным текстом для транслятора является система одАНЛДУ, записанная в стандартном текстово-математическом виде.
Транслятор преобразует систему к одному из простых видов, как это показано в [3]. Результирующая система также записывается в текстово-математическом виде.
Транслятор должен отслеживать корректность исходной системы, проверяя правильность синтаксиса записи системы и ее соответствие классу систем одАНЛДУ.

Предметная область

Системой одНЛДУ называется система линейных уравнений, коэффициенты которой - целые числа, а решения ищутся только в неотрицатель-ных целых. В матричном виде: Ax=0. Если перенести неизвестные с отрица-тельными коэффициентами в правую часть, то получим систему с неотрица-тельными целыми коэффициентами: A'x=A"x. Система одАНЛДУ является системой одНЛДУ со специальной левой частью A'.
Например, следующая система одНЛДУ является системой одАНЛДУ.
x1 + x3 = 3*x4 + x5
x2 = 5*x1 + 7*x3 + 2*x4 + 3*x5
x4 + x5 = 3*x5.
Система записана в стандартном текстово-математическом виде. Результатом ее преобразования является уравнение:
x4 = 2*x5.
Для следующей системы одАНЛДУ
x1 + x3 = x2 + 3*x3
x2 = x1 + 5*x3
x4 = 2*x1 + 3*x2 + 7*x3
результатом преобразования является система одАНЛДУ
x1 = x2
x2 = x1.

Ссылки

Сервер системы Web-SynDic. http://websyndic.cs.karelia.ru, http://www.cs.karelia.ru/software/index.php.ru.
Корзун Д. Ж. "Grammar-Based Algorithms for Solving Certain Classes of Nonnegative Linear Diophantine Systems // Труды международного семинара Finnish Data Processing Week at the University of Petrozavodsk (FDPW'2000): Advances in Methods of Modern Information Technology. Vol. 3. - Петрозаводск: Изд-во ПетрГУ, 2001. - С. 52-67.
Кулаков К. А. "Генерация систем неотрицательных линейных диофантовых уравнений и ее приложения" Магист. Дисс. Петрозаводск, ПетрГУ, 2005. 82с.

Ноябрь, 25