Труды КНЦ вып.29 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ вып. 3/2015(29))

Диагональная С-система - С- система размерности п хп , у которой все недиагональные элементы равны полной компоненте (компоненте, содер­ жащей все элементы своего домена; записывается как *). D -кортеж - отношение, равное диагональной С-системе, записанное в виде кортежа диагональных компонент С-системы, ограниченного пере­ вернутыми скобками: ]Аи ...,АпІ (6) D -система - структура, эквивалентная пересечению нескольких одно­ типных D -кортежей. Записывается следующим образом: Также были определены базовые операции между вышеописанными структурами данных. К ним можно отнести обобщенное пересечение, объединение однотипных систем, преобразование систем в альтернативные классы, а также операции с атрибутами. На основе данных структур и их свойств были разработаны схемы решения некоторых известных задач логического анализа, таких как: задача проверки правильности следствия, задача генерации возможных следствий с ограничениями на состав переменных и т. д. Несмотря на возможность решать различные задачи с использованием матричных структур, в работах Б.А. Кулика не было предложено конкретных эффективных методов решения задач большой размерности. Был рассмотрен лишь алгоритм выполнимости КНФ, удовлетворительно работающий для формул логики высказываний. Для формул над одноместными предикатами он характеризуется большой вычислительной сложностью. Данный алгоритм реализовывал слепой поиск, то есть в нем не использовались эвристики, также сомнительным представляется и используемый принцип организации процесса ветвления, когда уровням дерева поиска сопоставляются строки (кортежи) D -системы, а узел дерева поиска соответствует некоторой компоненте выбранной строки. Интеграция методов вычислительной логики и методов удовлетворения ограничений Позднее А.А. Зуенко [17-19] было предложено использовать матрич­ ное представление конечных предикатов для решения более широкого класса задач, чем задача выполнимости КНФ, а именно для задач удовлетворения ограничений. Для разработки эффективных методов решения ЗУО было предложено использовать специфические свойства матриц ограничений. Анализ этих свойств позволил существенно ускорить традиционные алгоритмы распространения ограничений. Предложенные в работах [17-19] методы и алгоритмы реализуют эвристический (интеллектуальный) поиск на основе оригинальных эвристик, обеспечивая существенное увеличение скорости и экономию памяти по сравнению с прототипами. Данные методы 72