Логические схемы алгоритмов

 

Реализация алгоритма есть последовательное выполнение команд ЭВМ, каждая из которых в свою очередь является последовательностью элементарных действий-микрокоманд, выполняемых за один машинный такт.

Функцию задания алгоритма А. А. Ляпунов предложил записывать определенным способом, а именно в виде конечной строки, состоящей из символов элементарных действий А_i , где i изменяется от 1 до n (n – целое положительное число), логических функций α_p (p =1,m) и специальных символов начала и конца стрелок с индексом, где индекс также целое положительное число.

Символы A₁,A₂,…,A_n он предложил называть операторами, а символы α₁,α₂,...-логическими условиями. Логическое условие (ЛУ) - это такая функция, которая может принимать лишь два значения – 0 или 1. Оказалось, что с помощью введенных понятий возможно формально описать любой алгоритм, используя терминологию логики. Действительно, допустим символ α₁ (х₁=х₂) означает, что α₁=1, если равенство истинно и α₁=0 в противном случае.

Рассмотрим некоторый алгоритм как определенную последовательность операторов.

 

U = A₁ α₁­¹ A₂ α₂ ­² A₃ α₃ ­³… ¯²A₁₀ α₁₀­³… A_k

 

Будем считать, что ЛУ, за исключением α₂, равны единице. Тогда выражение можно переписать в виде

 

U =A₁ A₂ α₂­² A₃ … ¯²A₁₀ … A_k ,

 

так как действия стрелок трактуются следующим образом: после выполнения оператора A₁ проверяется его ЛУ α₁; если α₁=1, то выполняется следующий оператор, т.е. А₂, а если α₁=0 , то необходимо в строке отыскать конец стрелки ¯¹ и выполнить стоящее справа от неё элементарное выражение. Так как все ЛУ, кроме α₂, равны 1, то это и позволяет нам перейти от первого выражения ко второму.

 

Определение. Логической схемой алгоритма (ЛСА) будем называть конечную строку, состоящую из символов операторов А₁, А₂, …, А_n, логических условий со стрелками α₁­¹, α₂­², … α_m­^m и концов стрелок ¯¹, ¯², … ¯^m такую, что для каждого начала стрелки c индексом i найдётся один и только один конец стрелки с тем же индексом.

 

Из этого определения следует, что несколько начал стрелок могут иметь одинаковые индексы, но все они привязаны к единственному концу стрелки с этим индексом.

 

Каждый отдельный оператор или логическое условие назовём “элементарным выражением”, а фрагмент строки из элементарных выражений со стрелками, где для каждого индекса i имеется не более одного начала стрелки и одного конца с индексом i – “выражением”.

Из ранее приведённых рассуждений вполне понятно, что в любой ЛСА порядок выполнения операторов определяется состоянием всех ЛУ. Будем для определённости считать, что ЛУ могут изменять своё состояние, но только во время выполнения некоторого оператора.

Таким образом, описание алгоритма в общем виде в терминах ЛСА может быть представлено:

 

U = U (A₁,…,A_n; p₁,…,p_m)

 

здесь A_i (i = 0, n) - множество операторов,

p_j ( j = (1, к)) - множество логических переменных, входящих в функции α_t(p₁,p₂,…,p_m).

 

Всевозможные наборы состояний логических переменных p₁, …, p_m обозначим

 

Δ₁ , Δ₂ ,…, Δ_m , Δ_m+1 , …

 

Тогда процесс реализации ЛСА для этой произвольной последовательности наборов определяется следующим образом:

1. Выбираем начальный набор независимых логических переменных Δ₁.

2. Анализируем самое левое элементарное выражение ЛСА: если это ЛУ, то может быть два продолжения: при р_i =1 переходим к анализу следующего элементарного выражения, а при р_i = 0 переходим к анализу элементарного выражения, стоящего справа от конца стрелки с индексом i. При выполнении оператора совершается переход от набора Δ₁ к Δ_s , где s – индекс выполняемого оператора.

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

 

Пример. Дана ЛСА U =A₀p₂­¹p₃­²¯¹A₂A₃¯²A₄A₅A_K

Рассмотрим процесс реализации ЛСА при всевозможных наборах ЛУ.

 

Δ₁ = p₂p₃ U₁ = A₀A₂A₃A₄A₅A_K;

Δ₂ = p₂!p₃ U₂ = A₀A₄A₅A_K;

Δ₃ = !p₂p₃ U₃ = A₀A₂A₃A₄A₅A_K= U₁;

Δ₄ = !p₂!p₃ U₄ = A₀A₂A₃A₄A₅A_K= U₁.