Page 294 - Microsoft Word - Милогиё 2019-чом 1

М.И.Беляев, Милогия, том 1, ©, 2019г.

произвольных структур все известные алгоритмы «срав-
нимости», гарантирующие однозначную оценку, явля-
ются экспоненциальными. Фактически для структур, име-
ющих небольшое число уровней иерархии, эту задачу ре-
шить нелегко. Перед лицом этого комбинаторного взрыва
исследователи часто отказываются от поиска эффектив-
ного алгоритма сравнения и взамен этого строят простые
процедуры, от которых ожидается хорошая работа в боль-
шинстве случаев.
Инвариантом структуры называют параметр, имеющий
одно и тоже значение для сравниваемых структур. Среди
самых очевидных можно назвать: число элементов, число
связей, число модулей соответствующего ранга, число
уровней иерархии, уровень декомпозиции и т. д. При срав-
нении двух структур, как только обнаруживается, что два
значения одного и того же параметра отличаются друг
друга, то приходят к заключению, что данные структуры
не эквивалентны. Упорядочивая подобные параметры по
их сложности и значимости, мы тем самым определяем
код, по которому и сравниваем две структуры. В нашем
случае таким кодом может служить спектр соответствую-
щего ранга, который фактически является числом, даю-
щего относительную оценку сложности структуры и вы-
раженным в некоторой позиционной иерархической си-
стеме счисления. В этом случае при оценке эквивалентно-
сти структур мы можем говорить, что две структуры экви-
валентны друг с другом с точностью до n - го уровня
иерархии (до n - го уровня декомпозиции). Подобный под-
ход к оценке сложности структур по их спектру соответ-
ствующего ранга позволяет определять сложность рас-

сматриваемых структур по существу, т. е. с требуемой

293