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

 

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

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

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

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

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

3. Составить объединенную МСА, в которой операторы не повторяются. Если исходный оператор присутствует в обоих МСА, то проставляем r при переходе к оператору из 1-го алгоритма и !r при переходе к оператору из 2-го алгоритма.

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

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

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

 

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

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

 

1)

Алгоритм U1	Алгоритм U2
А0 : Ввод массива, i=1 А11 : max=M[1] А21 : max=M[i] А3 : i++ A4 : prn=max Ак : print(prn) p11 : M[i]>max ? p2 : i>10 ?     U1 =A0A11¯2p11­11A21¯11A3p2­2A4Aк	А0 : Ввод массива, i=1 А12 : prn=0 А22 : prn=i А3 : i++ Ак : print(prn) p12: M[i]=4 ? p2 : i>10 ?     U2 =A0A12¯2p12­12A22ω­3¯12A3p2­2¯3Aк

 

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

3) На базе ГС или ЛС исходных алгоритмов строим объединенную МСА, в заголовках строк и столбцов которой операторы обоих алгоритмов. Переходы между операторами одного алгоритма соответствуют ЛСА или ГСА этого алгоритма. При переходе от общего оператора к оператору определенного алгоритма вставляется соответствующее логическое условие r или !r.

 

Объединенная МСА

 

	A11	A12	A21	A22	A3	A4	Aк
A0	r	!r
A11			p11		!p11
A12				p12	!p12
A21
A22
A3			r !p2p11	!r !p2p12	r !p2 !p11 V !r !p2 !p12	r p2	!r p2
A4

 

4) По объединенной МСА строим системы скобочных и схемных формул перехода и затем строим объединенную ЛСА.

 

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

A₀ → rA₁₁ V !rA₁₂

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

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

A₂₁ → A₃

A₂₂ → A_к

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

A₄ → A_к

 

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

A₀ → r­⁴A₁₁ * ¯⁴A₁₂

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

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

A₂₁ → A₃

A₂₂ → A_к

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

A₄ → A_к

 

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

A₀ → r­⁴A₁₁ * ¯⁴A₁₂

A₁₁ → ¯² r­⁶p₁₁­⁷A₂₁

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

A₂₁ → ¯⁷A₃

A₂₂ → ω­⁵

A₃ → p₂­²r­⁵A₄

A₄ → ¯⁵A_к

 

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

U_об =A₀ r­⁴A₁₁ ω­²¯⁴A₁₂¯² r­⁶p₁₁­⁷A₂₁ω­⁷¯⁶p₁₂­⁷A₂₂ω­⁵¯⁷A₃p₂­²r­⁵A₄¯⁵A_к

 

6) Проверка:

r=1 U₁ = A₀A₁₁¯²p₁₁­⁷A₂₁¯⁷A₃p₂­²A₄A_к

r=0 U₂ = A₀A₁₂¯²p₁₂­⁷A₂₂ω­⁵¯⁷A₃p₂­²¯⁵A_к

 

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

В объединенной ЛСА 14 элементарных выражений, а в необъединенной – 16. Минимизация эффективна.

 

Объединить 2 алгоритма работы с массивом из 10 элементов:

U₁ – вывести сумму элементов массива;

U₂ – вывести номер первого элемента массива, большего 5.

Первый оператор А₀ – инициализация массива и переменных.

Последний оператор А_к – вывод искомого значения на экран.