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

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

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

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

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

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

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

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

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

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

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

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

ГСА

ЛСА

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

МСА

	А1	A2	A3	Aк
A0	p1!p2	!p1	-	p1p2
А1	-		-	-
A2	!p3p1!p2	!p3!p1	p3	!p3p1p2
A3	-	-	-

  А₀: Ввод массива, i=1, c=0 А₁: c++ А₂: i++ А₃: i=0 А_к: Вывод i   p₁: M[i]>5? p₂: с>2? p₃: 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 целых чисел. Начальный оператор А₀ – ввод массива и инициализация переменных, конечный оператор А_к – вывод результата на экран.

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