Объединение 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)

Алгоритм U ₁  

Алгоритм U ₂  

А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?

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

 

А0: Ввод массива, i=1 А12: prn=0 А22: prn=i А3: i++ Ак: print(prn)

p12: M[i]=4? p2: i>10?

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

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₁₁¯² r­⁶p₁₁­⁷A₂₁¯⁷A₃ p₂­²r­⁵A₄ ω­⁵¯⁴A₁₂¯⁶p₁₂­⁷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.

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

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

Дата добавления: 2015-05-26