Эквивалентное преобразование схем алгоритмов

Преобразования ГСА → ЛСА, ЛСА → ГСА, ЛСА → МСА и ГСА → МСА интуитивно понятны и не требуют комментариев. Преобразование МСА → ГСА осуществляется через ЛСА. Рассмотрим преобразование МСА → ЛСА, которое широко применяется при объединении алгоритмов.

1) По строкам МСА записываем систему формул перехода S₁:

Логическая функция α_ij является «приведенной» по переменной, если она представлена в виде

2) Приводим систему формул перехода по всем переменным p_s, т. е. выносим за скобки p_s и их отрицание, получая скобочную систему формул перехода S₂.

3) Переходим к схемной системе формул перехода S₃ за 3 операции:

Схемные формулы перехода состоят из «блоков», разделенных «*», с помощью которых будет построена ЛСА.

4) Проводим эквивалентные преобразования системы схемных формул перехода с целью устранения повторяющихся операторов А_j и минимизации количества логических переменных p_s, получая системы схемных формул перехода S₃’, S₃’’ и т. д.

При этом используем следующие правила тождественных преобразований схемных формул перехода:

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

Вначале в строке выбирается оператор А₀. К нему справа приписывается начальное выражение из его схемной формулы.

Пример. Составить граф-схему алгоритма, выводящего номер третьего элемента массива, большего 5, или 0, если его нет. Провести эквивалентное преобразование ГСА в ЛСА, затем ЛСА в МСА и МСА в ЛСА. Массив состоит из 10 целых чисел. Начальный оператор А₀ – ввод массива и инициализация переменных, конечный оператор А_к – вывод результата на экран.

ГСА

ЛСА U = A0¯3p1­1p2­2ω­4¯2А1¯1A2 p3­3A3¯4Aк МСА   А1 A2 A3 Aк A0 p1!p2 !p1 - p1p2 А1 -   - - A2 !p3p1!p2 !p3!p1 p3 !p3p1p2 A3 - - -

А0: Ввод массива, i=1, c=0 А1: c++ А2: i++ А3: i=0 Ак: Вывод i p1: M[i]>5? p2: с>2? p3: i>10?

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

A₀ → p₁!p₂A₁ V!p₁A₂ V p₁p₂A_к

A₁ → A₂

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

A₃ → A_к

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

A₀ → p₁(p₂A_к V!p₂A₁) V!p₁A₂

A₁ → A₂

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

A₃ → A_к

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

A₀ → p₁­¹p₂­²A_к * ¯²A₁ * ¯¹A₂

A₁ → A₂

A₂ → p₃­³A₃ * ¯³p₁­¹p₂­²A_к * ¯²A₁ * ¯¹A₂

A₃ → A_к

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

A₀ → ¯³p₁­¹p₂­²A_к * ¯²A₁

A₁ → ¯¹A₂

A₂ → p₃­³A₃

A₃ → A_к

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

A₀ → ¯³p₁­¹p₂­² ω­⁴ * ¯²A₁

A₁ → ¯¹A₂

A₂ → p₃­³A₃

A₃ → ¯⁴A_к

ЛСА, построенная по минимизированной схемной системе формул перехода

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

Построенная ЛСА совпадает с исходной. Преобразование выполнено верно.

Задача. Составить граф-схему алгоритма, выводящего номер предпоследнего элемента массива, большего 5, или 0, если его нет. Провести эквивалентное преобразование ГСА в ЛСА, затем ЛСА в МСА и МСА в ЛСА. Массив состоит из 10 целых чисел. Начальный оператор А₀ – ввод массива и инициализация переменных, конечный оператор А_к – вывод результата на экран.