РАЗДЕЛ 2
РАЗРАБОТКА АЛГЕБРАИЧЕСКОГО МЕТОДА ПРЕОБРАЗОВАНИЯ АЛГОРИТМИЧЕСКИХ СТРУКТУР
2.1. Классификация бесповторных структур
Многообразие алгоритмов обработки информации, управления, контроля и диагностики, приводит к необходимости унификации программного обеспечения, при этом возникает необходимость определения свойств, характерных для данных алгоритмических структур.
Проведенный в работах [183, 184] анализ алгоритмов показал, что основными классами формул, используемых для описания систем, являются: бесповторные формулы; функции, обладающие групповой инвариантностью; функции, допускающие разделительную декомпозицию; однородные функции. Таким образом, для устройств управления техническими средствами, систем контроля и диагностики, а также устройств переработки информации бесповторность формул является характерным свойством, тем более, что и однородные, и разделимые функции имеют малую повторность переменных в соответствующих формулах.
Бесповторные алгоритмические структуры являются классом структур, которые наиболее широко используются на практике. Однако отсутствие единого подхода к исследованию этого класса алгоритмических структур затрудняет их анализ и синтез. Таким образом, возникает необходимость различать виды бесповторности в зависимости от формы представления алгоритмов [185, 186].
Переменную, которая входит в формулу один раз, будем называть бесповторной переменной. Формулу, в которую каждая переменная входит только один раз, будем называть бесповторной формулой.
Булева формула называется бесповторной, если число букв в ней равно числу переменных (коэффициент повторности ?=1). Повторные алгоритмические структуры (АС) могут быть преобразованы в бесповторные путем введения дополнительных переменных.
Вид каталогов типовых представителей зависит от вида объекта классификации. Ниже приведены примеры каталогов.
В таблице 2.1 приведен каталог бесповторных формул, а в таблице 2.2 каталог бесповторных булевых функций.
Таблица 2.1
Бесповторные формулы n=7
№ п/пВид формулы№ п/пВид функции16+183+2+225+293+2+1+135+1+1103+1+1+1+144+3112+2+2+154+2+1122+2+1+1+164+1+1+1132+1+1+1+1+173+3+1141+1+1+1+1+1+1
Наряду с комбинационными схемами произвольной конфигурации рассматривают следующие более узкие классы комбинационных схем: схемы без разветвлений (схемы, в которых выход каждого элемента может быть соединен только с одним элементом схемы) и бесповторные схемы (схемы без разветвлений, в которых каждая входная переменная поступает на вход только одного элемента схемы) [187].
Использование более узких классов комбинационных схем позволяет существенно упростить выполнение функциональных задач системы. Так, например, в бесповторных схемах эквивалентная нормальная форма (ЭНФ), сокращенная ЭНФ, и единичная ЭНФ совпадают и существует минимальный одиночный контролирующий тест, являющийся полным контролирующим тестом [187]. Пример бесповторной схемы приведен на рис. 2.1.
Таблица 2.2
Бесповторные булевы функции n=5
№ п/пВид функции№ п/пВид функции1(ab?c)d?e13((a?b)c?d)e2(a?b?c)d?e14(abc?d)e3(a?b)(c?d) ?e15(ab?cd)e4(a?b)cd?e16(ab?c?d)e5abcd?e17(a?b?c?d)e6(a?b)c?de18(ab?c)(d?e)7abc?de19(a?b?c)(d?e)8(a?b)c?d?e20(ab?c)de9abc?d?e21(a?b?c)de10ab?cd?e22(a?b)(c?d)e11аb?c?d?e23(a?b)cde12а?b?c?d?e24аbcde
Рис. 2.1. Бесповторная схема
Контактная схема называется бесповторной, если разным ребрам приписаны разные переменные, пример приведен на рис. 2.2.
В табл. 2.3 приведены примеры бесповторных регулярных выражений, а в табл. 2.4 бесповторные графы.
Рис. 2.2. Бесповторная контактная схема
Таблица 2.3
Бесповторные регулярные выражения
№ п/пВыражение№ п/пВыражение1(Х(Х(Х?Х)?Х)?
?Х(Х?Х))7(((ХХХ?ХХ)?(ХХХ?ХХ))?
?(ХХ?Х(Х?Х)))2(Х(Х(Х?Х)?Х)?
?Х((Х?Х)?(Х?Х)))8(((ХХХ?ХХ)?(ХХХ?ХХ))?
?((ХХ?ХХ)?(ХХ?ХХ)))3(Х(Х(Х?Х)?
?(ХХ?Х))?Х(Х?Х))9((Х(ХХ?Х)?ХХ)?
? (Х(ХХ?Х)?ХХ))4(Х(Х(Х?Х)?(ХХ?Х))? ?Х((Х?Х)?(Х?Х)))10((Х(ХХ?Х)?ХХ)?
?((ХХХ?ХХ)?(ХХ?ХХ)))5((Х(Х?Х)?ХХ(Х?Х))?
?(ХХ?Х(Х?Х)))11(((ХХХ?ХХ)?(ХХ?ХХ))?
? (Х(ХХ?Х)?ХХ))6((Х(Х?Х)?ХХ(Х?Х))?
?((ХХ?ХХ)?(ХХ?ХХ)))12(((ХХХ?ХХ)?(ХХ?ХХ))?
?((ХХХ?ХХ)?(ХХ?ХХ)))
Бесповторность на уровне алгоритмических структур представляется следующим образом [6]. Пусть алгоритмическая структура содержит условные и линейные операторы.
Таблица 2.4
Бесповторные графы n=5
№ п/пВид графа№ п/пВид графа№ п/пВид графа1
10192
11203
12214
13225
14236
15247
16258
179
18
Алгоритмическая структура называется условно бесповторной, если в регулярное выражение условные переменные входят только один раз. Алгоритмическая структура называется операторно-бесповторной, если в регулярное выражение линейные операторы входят только один раз. Алгоритмическая структура называется операторно-условно бесповторной, если алгоритмическая структура является условно и операторно-бесповторной [6].
Например, АС вида A 1= P4( (P3 (P1 v P2) ?v (P2 v P1)? )? v P5(P1 v P6)? ) ?, является условно-бесповторной АС, A2= ((P1 (P6 v P4) ? v (P5 v P3)? )? v (P2 v v P7P8)? ) ?, является операторно-бесповторной АС.
2.2. Преобразование алгоритмических структур
Другим важным свойством исследуемых алгоритмов является коммутативность. Коммутативность на уровне условий позволяет логические условия менять местами без усложнения структуры регулярных схем [111].
При разработке сложных систем обработки информации и управления необходимо иметь удобный математический аппарат, с помощью которого техника формальных преобразований для указанного класса формул была бы более простой и удобной. Среди известных алгебр регулярных схем алгоритмов следует отметить расширенную алгебру с коммутативными условиями для регулярных схем алгоритмов [