Автономное решение систем неотрицательных линейных диофантовыхуравнений на базе системы Web-SynDic

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

Заказчик

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

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

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

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

Система Web-SynDic должна поддерживать дополнительную группу "продвинутых пользователей", с собственными ограничениями.
Пользователь из группы "продвинутых пользователей" должен иметь возможность управлять собственными сеансами.
Пользователь из группы "продвинутых пользователей" должен иметь возможность задавать для сеанса отдельную очередь генерации/решения.
Администратор системы Web-SynDic должен иметь возможность управлять группами пользователей, сеансами, настройками пользователя.

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

Системой одНЛДУ называется система линейных уравнений, коэффициенты которой - целые числа, а решения ищутся только в неотрицательных целых. В матричном виде: Ax=0. Если перенести неизвестные с отрицательными коэффициентами в правую часть, то получим систему с неотрицательными целыми коэффициентами: A'x=A"x. Система одАНЛДУ является системой одНЛДУ со специальной левой частью A'.
Алгоритмы решения систем одНЛДУ и одАНЛДУ предназначены либо для нахождения некоторого частного ненулевого решения x*, либо для нахождения базисных решений.
Пользователи системы Web-SynDic разбиваются на две категории ? зарегистрированные и анонимные (гости). Зарегистрированные пользователи обладают дополнительными преимуществами по сравнению с гостями, такими как сохранение различных настроек, возможностью идентификации и обратной связи и т.п. Среди зарегистрированных пользователей выделяют группу администраторов, которые имеют права на управление учетными записями пользователей, настройками системы и т.п.
Работа пользователей с системой Web-SynDic измеряется в сеансах. Каждый сеанс пользователя начинается с момента первого обращения к системе Web-SynDic и заканчивается завершением работы или по истечении определенного времени бездействия пользователя. Во время сеанса пользователю присваивается уникальный идентификатор. Система Web-SynDic позволяет использовать одинаковые учетные записи пользователей для нескольких сеансов одновременно в случае, если клиентские части различны. Под завершением работы понимается смена учетной записи, явный выход из системы Web-SynDic и т.п. Контроль над истечением времени бездействия возлагается на сервер Apache Tomcat.
Система Web-SynDic использует технологию сеансов для определения пользователей системы, предоставления пользователю персональных данных (настройки генерации и решения, текущая система одАНЛДУ, текущее решение и т.п.), для сбора статистики и т.п.
Под автономной работой понимается работа "сквозь" сеансы, т.е. возможность сохранять и восстанавливать текущие данные сеанса по истечении продолжительного времени. При этом пользователь может завести новый сеанс с сохранением старого.
Система Web-SynDic использует технологию очередей для обработки задач - по одной очереди для задач генерации и решения. Новые задачи помещаются в очередь и ожидают окончания обработки предыдущих задач. Преимуществом такой технологии является максимальное использование системных ресурсов на каждую задачу. Недостатком такого метода является длительное ожидание в случае вычислительно сложных задач (больших размерностей, большого множества элементов и т.п.). Вычислительно сложные задачи появляются при работе системы Web-SynDic "продвинутыми пользователями" (большое множество систем) и администраторами (отсутствие ограничений). Поэтому для такого класса задач необходима возможность использования отдельных очередей.

Ссылки

Сервер системы 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.