14. Алгоритм синтеза согласованной системы ВС

14.1. Алгоритм синтеза согласованной системы ВС

Алгоритм синтеза согласованной системы ВС по информации о составляющих основы системы ВС:

• T - дерево разбиения
• COM и SEL – коммутаторы и селекторы
• VS⧋ - базовые ВС
• VS₸ - частичные ВС

делает заключение о существовании согласованной с ней системы ВС (и корректности собственно основы). █

Вначале необходимо на основе теоремы 10.1 проверить, корректность каркаса.

При положительном результате проверки следующий алгоритм, который должен рекурсивного применяться к корневому узлу всего дерева разбиения, претендует на соответствие указанному определению алгоритма синтеза.

Как видно, работа алгоритма сводится к одной из трёх следующих альтернатив в зависимости от типа узла:

1. для листа - алгоритм возвращает состояния сопряжённой с ним базовой ВС
2. для И-узла - алгоритм:
   1. рекурсивным вызовом определяет состояния ВС всех вершин, непосредственно подчинённых данному
   2. при заданном коммутаторе проверяет, что каждое состояние каждого из полученных множеств имеет произведение ровно с одним ключом из его состава
   3. получает произведение ВС, сопряжённых с вершинами, непосредственно подчинённых данному
   4. проверяет, что все частичные ВС, сопряжённые с данным узлом, являются проекциями полученной ВС
3. для ЛИБО-узла - алгоритм:
   1. рекурсивным вызовом определяет состояния ВС всех вершин, непосредственно подчинённых данному
   2. получает сумму ВС, сопряжённых с вершинами, непосредственно подчинённых данному
   3. проверяет, что все частичные ВС, сопряжённые с данным узлом, являются проекциями полученной ВС

Ошибка говорит о том, что не может быть построено либо множество состояний ВС одного из подчинённых узлов, либо, при их существовании, - их произведение или их сумма. █

Назад Вперёд