Задача. Автомат должен выполнять два алгоритма U 1 и U 2. Если логическое условие r истинно, то выполняется U 1, иначе - U 2.
Получить минимизированный объединенный алгоритм U об, в котором отсутствуют повторяющиеся операторы.
Алгоритм решения.
1. Составить граф-схему и логическую схему каждого алгоритма.
2. Оценить эффективность минимизации объединенного алгоритма по количеству общих (одинаковых) операторов и логических переменных исходных алгоритмов. Если это количество меньше 2, то минимизация неэффективна, U об = r1 U 1w2 ¯1 U 2¯2, иначе перейти к п. 3.
3. Составить объединенную МСА, в которой операторы не повторяются. Если исходный оператор присутствует в обоих МСА, то проставляем r при переходе к оператору из 1-го алгоритма и !r при переходе к оператору из 2-го алгоритма.
4. Составить систему формул перехода, провести ее минимизацию и упрощение.
5. По минимизированной системе схемных формул перехода составить объединенную ЛСА.
6. Проверить выполнение каждого алгоритма в объединенной ЛСА, подставляя соответствующее значение r.
Пример. U 1 – вывести максимум массива из 10 элементов.
U 2 – вывести номер первого элемента массива, равного 4.
1)
Алгоритм U 1 | Алгоритм U 2 | ||||
U 1 =A0A11¯2p1111A21¯11A3p22A4Aк |
U 2 =A0A12¯2p1212A22ω3¯12A3p22¯3Aк |
2) Общие операторы и логические переменные – A0 , A3 , p2 , 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) По объединенной МСА строим системы скобочных и схемных формул перехода и затем строим объединенную ЛСА.
Скобочная система формул перехода S2
A0 → rA11 V!rA12
A11 → p11 A21 V!p11A3
A12 → p12 A22 V!p12A3
A21 → A3
A22 → Aк
A3 → p2 (rA4 V!rAк) V!p2 (r (p11A21V!p11A3) V!r (p12A22 V!p12A3))
A4 → Aк
Схемная система формул перехода S3
A0 → r4A11 * ¯4A12
A11 → p1111A21 * ¯11A3
A12 → p1212A22 * ¯12A3
A21 → A3
A22 → Aк
A3 → p22r5A4 * ¯5Aк * ¯2 r6p1111A21 * ¯11A3 * ¯6p1212A22 * ¯12A3
A4 → Aк
Преобразованная схемная система формул перехода S3'
A0 → r4A11 * ¯4A12
A11 → ¯2 r6p117A21
A12 → ¯6p127A22
A21 → ¯7A3
A22 → ω5
A3 → p22r5A4
A4 → ¯5Aк
5) Объединенная ЛСА
U об =A0 r4A11 ω2¯4A12¯2 r6p117A21ω7¯6p127A22ω5¯7A3p22r5A4¯5Aк
6) Проверка:
r=1 U1 = A0A11¯2p117A21¯7A3p22A4Aк
r=0 U2 = A0A12¯2p127A22ω5¯7A3p22¯5Aк
При подстановке соответствующих значений r оба алгоритма выполняются, следовательно объединенная ЛСА составлена правильно.
В объединенной ЛСА 14 элементарных выражений, а в необъединенной – 16. Минимизация эффективна.
Объединить 2 алгоритма работы с массивом из 10 элементов:
U 1 – вывести сумму элементов массива;
U 2 – вывести номер первого элемента массива, большего 5.
Первый оператор А0 – инициализация массива и переменных.
Последний оператор Ак – вывод искомого значения на экран.