ОЦЕНКА СЛОЖНОСТИ АЛГОРИТМОВ, РЕАЛИЗУЮЩИХ ОПЕРАЦИИ НАД МЕТАГРАФАМИ

Горячкин Борис Сергеевич, Гапанюк Юрий Евгеньевич, Винников Степан Сергеевич

Постановка проблемы. На сегодняшний день не описаны и не реализованы алгоритмы для проведения операций над метаграфами, что ограничивает возможности для обработки таких структур. Цель. Дать возможность работать с метаграфами на математическом и алгоритмическом уровне. Результаты. Рассмотрено альтернативное описание метаграфовой модели, указаны её существенные отличия от классической. Описаны математические операции над метаграфами. Приведены алгоритмы, реализующие данные операции. Дана теоретическая оценка сложности таких алгоритмов. Написана программа, реализующая данные алгоритмы, проверена её работоспособность. Проведены эксперименты с расчётами над метаграфами разных размеров. Проведено сравнение теоретических и экспериментальных данных, подтверждена теоретическая оценка. Практическая значимость. Переход от классического описания метаграфов к новому позволил удобно и лаконично описывать операции над метаграфами, а также упростил работу с данной структурой. Описание операций над метаграфами и реализация алгоритмов, позволяющих проводить такие операции, расширило возможности для использования метаграфовой модели данных.

Ключевые слова:Метаграфы, метаграфовая модель данных, алгоритмы, асимптотическая оценка сложности, дискретная математика.