Имитационная модель алгоритма поиска подграфа в семантической сети

Фокусом работы является разработка и программная реализация имитационной модели алгоритма поиска изоморфного подграфа в семантической сети с целью исследования алгоритма, его преимуществ и недостатков перед существующими подходами. В модели семантическая сеть аппроксимируется помеченным неориентированным графом. Работа включает в себя две части. В первой рассматриваются теоретические вопросы данной области: производится обзор, классификация и сравнение уже существующих алгоритмов, нотаций и программных продуктов, предназначенных для поиска изоморфного подграфа. Вторая часть посвящена описанию практической реализации имитационной модели и исследовании с ее помощью характеристик алгоритма поиска изоморфного подграфа. Алгоритм, для которого реализуется имитационная модель, предназначен для ускорения поиска подграфа за счет использования промежуточной информационная конструкции. Конструкция эта представляет граф, называемый топологической слойкой. Слойка однозначно отображает структуру графа и метки его вершин. В работе приводится описание алгоритма поиска изоморфного подграфа с использованием механизма слойки и его программной реализации. Кроме того, описываются результаты исследования временной и емкостной сложности алгоритма по результатам запуска имитационной модели. Данная работа содержит 171 страницу. В работе используется 3 таблицы и 21 рисунок. В ходе исследования было использовано 33 источника.