Объединение 3-х и более алгоритмов

 

Задача. Автомат должен выполнять три алгоритма U₁, U₂ и U₃ в зависимости от значений набора логических условий r₁, r₂.

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

Алгоритм решения.

1. Составить граф-схему и логическую схему каждого алгоритма.

2. Оценить эффективность минимизации объединенного алгоритма по количеству общих (одинаковых) операторов и логических переменных исходных алгоритмов. Если это количество меньше 2, то минимизация неэффективна, U_об = r₁­¹r₂­²U₁w­³ ¯¹U₂w­³¯²U₃¯³, иначе перейти к п. 3.

3. Составить матричную схему каждого алгоритма.

4. Построить объединенную МСА, каждый элемент которой

где

Определяющие функции вычисляются по формуле:

Здесь R_i - определяющие конъюнкции для всех объединяемых МСА.

Оператор А_i входит только в ЛСА U_i , поэтому есть выбор R/0, который позволяет минимизировать систему формул перехода и объединенную ЛСА.

Практика объединения алгоритмов показывает, что МСА с наибольшим числом совпадающих элементов желательно приписывать определяющие конъюнкции с соседним кодированием.

Совпадающие элементы:

- элементы, состоящие из одинаковых логических функций;

- элементы строки оператора А_i, если он отсутствует в другой МСА.

 

4.1. Построить неориентированный граф, вершины которого помечены обозначениями алгоритмов, а ребра - числом совпадающих элементов.

4.2. Закодировать определяющие конъюнкции алгоритмов набором логических переменных r₁r₂, используя соседнее кодирование для пар МСА с наибольшим числом совпадающих элементов.

4.3. Построить набор определяющих функций для каждого оператора каждого алгоритма.

4.4. Построить объединенную МСА.

 

5. Составить систему формул перехода, провести ее минимизацию и упрощение.

6. По системе схемных формул перехода составить объединенную ЛСА.

7. Проверить выполнение каждого алгоритма в объединенной ЛСА, подставляя соответствующие значения r₁, r₂. Если алгоритм имеет большое количество элементарных выражений и безусловных переходов, то проверку рекомендуется проводить по объединенной ГСА.

 

Пример. U₁ – вывести максимум массива из 10 элементов.

U₂ – вывести минимум массива из 10 элементов.

U₃ – вывести номер первого элемента массива, равного 4.

 

1)

U₁ =A₀A₁₁¯²p₁₁­¹¹A₂₁¯¹¹A₃p₂­²A₄₁A_к

U₂ =A₀A₁₂¯²p₁₂­¹²A₂₂¯¹²A₃p₂­²A₄₂A_к

U₃ =A₀A₁₃¯²p₁₃­¹³A₂₃ω­³¯¹³A₃p₂­²¯³A_к

 

2) Общие операторы и логические переменные – A₀ , A₃ , p₂ , A_к . Минимизация должна быть эффективна.

 

3)

U1   A11 A21 A3 A41 Aк A0         A11   p11 !p11     A21         A3   !p2p11 !p2!p11 p2   A41         1

U2   A12 A22 A3 A42 Aк A0         A12   p12 !p12     A22         A3   !p2p12 !p2!p12 p2   A42         1

U3   A13 A23 A3 Aк A0       A13   p13 !p13   A23       A3   !p2p13 !p2!p13 p2

 

4) Определяющие конъюнкции и функции

 

4.1) Граф с числами совпадающих элементов

U₁-U₂: строки А₁₁+А₂₁+А₁₂+А₂₂+А₄₁+А₄₂ = 2+1+2+1+1+1 = 8 .

U₁-U₃: строки А₁₁+А₂₁+А₄₁+А₁₃+А₂₃ = 2+1+1+2+1 = 7 .

U₂-U₃: строки А₁₂+А₂₂+А₄₂+А₁₃+А₂₃ = 2+1+1+2+1 = 7 .

Для большей минимизации введена пустая МСА U_ø , число совпадающих с ней элементов равно числу элементов всей матрицы.

 

4.2) Определяющие конъюнкции

 

Наибольшее число совпадающих элементов у пар матриц U₁-U₂ , U₁-U_ø , U₂-U_ø .

Закодируем определяющие конъюнкции для U₁ , U₂ , U_ø соседними кодами:

R₁ = r₁r₂ , R₂ = r₁!r₂ , R_ø = !r₁r₂ , R₃ = !r₁!r₂ .

 

4.3) Определяющие функции

 

Определяющие функции операторов А₀ и А₃ первого алгоритма (присутствуют во всех алгоритмах кроме пустого):

.

Определяющие функции остальных операторов первого алгоритма (присутствуют только в нем):

.

Аналогично для остальных алгоритмов:

;

;

.

 

4.4) Объединенная недоопределенная МСА

 

	A11	A12	A13	A21	A22	A23	A3	A41	A42	Aк
A0	(r1/1)r2	r1!r2	!r1(!r2/1)
A11				p11			!p11
A12					p12		!p12
A13						p13	!p13
A21
A22
A23
A3				!p2p11 (r1/1)r2	!p2p12r1!r2	!p2p13 !r1(!r2/1)	!p2!p11(r1/1)r2v !p2!p12r1!r2 v !p2!p13!r1(!r2/1)	p2(r1/1)r2	p2r1!r2	p2!r1 (!r2/1)
A41
A42

 

Доопределяем МСА, сокращая число и сохраняя полноту логических условий.

 

	A11	A12	A13	A21	A22	A23	A3	A41	A42	Aк
A0	r1r2	r1!r2	!r1
A11				p11			!p11
A12					p12		!p12
A13						p13	!p13
A21
A22
A23
A3				!p2p11 r1r2	!p2p12r1!r2	!p2p13 !r1!r2	!p2!p11r1r2v !p2!p12r1!r2 v !p2!p13!r1	p2r1r2	p2r1!r2	p2!r1
A41
A42

 

return false">ссылка скрыта

 

5) Скобочная система формул перехода S₂

 

A₀ → r₁r₂A₁₁ V r₁!r₂A₁₂ V !r₁A₁₃ → r₁(r₂A₁₁ V !r₂A₁₂) V !r₁A₁₃

A₁₁ → p₁₁A₂₁ V !p₁₁A₃

A₁₂ → p₁₂A₂₂ V !p₁₂A₃

A₁₃ → p₁₃A₂₃ V !p₁₃A₃

A₂₁ → A₃

A₂₂ → A₃

A₂₃ → A_к

A₃ → !p₂r₁r₂(p₁₁A₂₁ V !p₁₁A₃) V !p₂r₁!r₂(p₁₂A₂₂ V !p₁₂A₃) V !p₂!r₁(p₁₃A₂₃ V !p₁₃A₃) V p₂(r₁(r₂A₄₁ V !r₂A₄₂) V !r₁A_к) → p₂(r₁(r₂A₄₁ V !r₂A₄₂) V !r₁A_к) V !p₂(r₁(r₂(p₁₁A₂₁ V !p₁₁A₃) V !r₂(p₁₂A₂₂ V !p₁₂A₃)) V !r₁(p₁₃A₂₃ V !p₁₃A₃))

A₄₁ → A_к

A₄₂ → A_к

 

Схемная система формул перехода S₃

 

A₀ → r₁­¹r₂­²A₁₁ * ¯²A₁₂ * ¯¹A₁₃

A₁₁ → p₁₁­¹¹A₂₁ * ¯¹¹A₃

A₁₂ → p₁₂­¹²A₂₂ * ¯¹²A₃

A₁₃ → p₁₃­¹³A₂₃ * ¯¹³A₃

A₂₁ → A₃

A₂₂ → A₃

A₂₃ → A_к

A₃ → p₂­³ r₁­⁴ r₂­⁵A₄₁ * ¯⁵A₄₂ * ¯⁴A_к * ¯³ r₁­⁶ r₂­⁷ p₁₁­¹¹A₂₁ * ¯¹¹A₃ * ¯⁷ p₁₂­¹²A₂₂ * ¯¹²A₃ * ¯⁶ p₁₃­¹³A₂₃ * ¯¹³A₃

A₄₁ → A_к

A₄₂ → A_к

 

Преобразованная схемная система формул перехода S₃'

 

A₀ → r₁­¹ r₂­² A₁₁ * ¯²A₁₂ * ¯¹A₁₃

A₁₁ → ¯³ r₁­⁶ r₂­⁷ p₁₁­⁸A₂₁

A₁₂ → ¯⁷ p₁₂­⁸A₂₂

A₁₃ → ¯⁶ p₁₃­⁸A₂₃

A₂₁ → ω­⁸

A₂₂ → ¯⁸A₃

A₂₃ → ω­⁹

A₃ → p₂­³ r₁­⁹ r₂­⁵A₄₁ * ¯⁵A₄₂

A₄₁ → ω­⁹

A₄₂ → ¯⁹A_к

 

6) Объединенная ЛСА

U_об = A₀ r₁­¹ r₂­²A₁₁¯³ r₁­⁶ r₂­⁷ p₁₁­⁸A₂₁ω­⁸¯²A₁₂¯⁷ p₁₂­⁸A₂₂¯⁸A₃ω­¹⁰¯¹A₁₃¯⁶ p₁₃ ­⁸A₂₃ω­⁹ ¯¹⁰ p₂­³ r₁­⁹ r₂­⁵A₄₁ω­⁹¯⁵A₄₂¯⁹A_к

 

7) Проверка:

 

r₁=1, r₂=1 U₁ = A₀A₁₁¯³p₁₁­⁸A₂₁¯⁸A₃p₂­³A₄₁A_к

r₁=1, r₂=0 U₂ = A₀A₁₂¯³p₁₂­⁸A₂₂¯⁸A