vestnik Экологический вестник научных центров Черноморского экономического сотрудничества Ecological Bulletin of Research Centers of the Black Sea Economic Cooperation 1729-5459 Кубанский государственный университет RU 324 Научная статья Original article Статьи Article Вычислительная сложность распознавания трассируемости конфигураций Computational complexity of traceability recognition configurations Костенко К.И. Костенко Константин Иванович Kostenko Konstantin I. kostenko@kubsu.ru

канд. физ.-мат. наук, доцент кафедры информационных технологий, начальник отдела разработки информационных систем Центра интернет Кубанского государственного университета

 Кубанский государственный университет, КраснодарKuban State University, Krasnodar 22 03 2010 1 42 48 10 03 2010 13 03 2010 22 03 2010 Copyright (c) 2010 Костенко К.И. 2010 Костенко К.И. Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.

This paper presents algorithms testing possibility of c- and p-tracing between configurations of abstract knowledge spaces at n2 time, measured by quantity of vertex marking comparisons and structural representations.

Приведёны алгоритмы, проверяющие возможность c и p-трассирования между конфигурациями абстрактных пространств знаний за время n2, измеряемое количеством сравнений разметок вершин их структурных представлений.

 семантическая структура трассирование структур сложность алгоритма semantic structure tracing of structures algorithm complexity Костенко К.И. Сжатия конфигураций в пространствах знаний // Экологический вестник научных центров Черноморского экономического сотрудничества. 2008, №4. С. 26-33. Baader F. Logic-Based Knowledge Representation // Artificial intelligence today. 1999, LNAI 1600. P. 13-41. Gupta A., Nashimura N. Finding largest subtrees and smallest supertrees // Algorithmica. 1998. Vol. 21. P. 183-210. Ахо А., Хопрокрофт Д., Ульман Д. Структуры данных и алгоритмы. М.: Вильямс, 2003. 382 с.