Библиотека визуализации данных о трудоемкости алгоритмов решения линейных диофантовых уравнений

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

Заказчик

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

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

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

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

Библиотека представляет собой набор функций/классов. Интерфейсная часть реализуется на языке Java, а вычислительная - на языке Java или C/C++.
По известным данным измерений, представленных в формате системы Web-SynDic, строятся следующие зависимости:
- Временная трудоемкость \tau(p), т. е. затраченное время на решение системы одАНЛДУ в зависимости от параметра p.
- Емкостная трудоемкость \mu(p), т. е. затраченная память на решение системы одАНЛДУ в зависимости от параметра p.
- Параметром p может выступать: число неизвестных m, число уравнений n, число базисных решений q, норма матрицы коэффициентов ||A||, а также некоторые комбинации базовых параметров (n+m, n*m, n*m*q и др.).
- Динамика трудоемкости при последовательном решении множества систем, т. е. зависимость временной и емкостной трудоемкости от порядкового номера k решаемой системы одАНЛДУ. Эти зависимости могут представляться в текстово-табличном виде, в виде 2D-графиков (ось X - параметр p или k, ось Y - трудоемкость) или в виде диаграмм распределения (ось X - интервалы для трудоемкости или параметра p, ось Y - частоты).
При построении зависимостей из п. 2 в визуальном представлении могут использоваться следующие статистические характеристики: среднее, среднеквадратичное отклонение, медиана, процентили, минимум и максимум.
Результаты визуализации должны быть интегрированы в отчет о решении, который представляет собой документ HTML.

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

Системой одНЛДУ называется система линейных уравнений, коэффициенты которой - целые числа, а решения ищутся только в неотрицательных целых. В матричном виде: Ax=0. Если перенести неизвестные с отрицательными коэффициентами в правую часть, то получим систему с неотрицательными целыми коэффициентами: A'x=A"x. Система одАНЛДУ является системой одНЛДУ со специальной левой частью A'.
Алгоритмы решения систем одНЛДУ и одАНЛДУ предназначены либо для нахождения некоторого частного ненулевого решения x*, либо для нахождения базисных решений. Любой алгоритм при решении заданной системы одНЛДУ затрачивает определенное время и память - так называемые временная и емкостная сложность. Это основные показатели сложности любого алгоритма.
Для поддерживаемых 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.
M.Filgueiras, A.-P.Tomas. Package Slopes. http://www.ncc.up.pt/~apt/dioph/
M. Berkelaar. LP_SOLVE. http://www.cs.sunysb.edu/~algorith/implement/lpsolve/implement.shtml

Ноябрь, 25