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

Схемы алгоритмов

Формальный язык для описания алгоритмов был первоначально ориентирован на задачи оптимизации программ для ЭВМ, а в последствии оказался удобным и для оптимизации микропрограмм. Задачи этих классов широко распространены как в области проектирования средств вычислительной техники, так и при построении систем автоматического управления, связи и многих других.

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

Функцию задания алгоритма А. А. Ляпунов предложил записывать определенным способом, а именно в виде конечной строки, состоящей из символов элементарных действий А_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₁.

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