Формы записи алгоритмов

Любой алгоритм записывается в виде определенной последовательности выполнения определенных действий над входной информацией. Эти действия называются операторами. Операторы могут кодироваться определенными символами, изображающими арифметические, логические и неарифметические операции. В зависимости от используемых символов возможны различные способы записи алгоритмов.

Графический способ записи алгоритмов (ГСА). Графическое изображение алгоритмического процесса, в котором каждый оператор переработки данных изображается в виде геометрических фигур (символов), называется схемой алгоритма. Фигуры при таком способе записи соединяются между собой линиями, указывающими последовательность выполнения каждого оператора. Внутри фигур дается формульное или словесное описание содержания соответствующего действия. Перечень используемых операторов и способы их изображения определяются в ГОСТ 19002-80 и ГОСТ 19003-80, которые устанавливают для изображения схем алгоритмов и программ всего 42 символа: 30 – обязательных и 12 – рекомендуемых. Рассмотрим некоторые, наиболее часто встречающиеся операторы (рис. 8.2)

На рис. 8.2 представлены наиболее часто встречающиеся операторы.

Рис. 8.2. Условные графические обозначения в схемах алгоритмов и программ: а – Пуск, Останов.; б – Процесс; в – Решение; г – Узел; д – Слияние линий потока; е – Типовой процесс; ж - Параллельные действия; з – Данные; к – Дисплей.

Операторы s_н и s_к могут отсутствовать при описании функционирования систем управления, работающих в ждущем режиме. Все остальные операторы делятся на исполнительные (A _i) условные (P _i).

Исполнительные операторы иначе называют преобразователями. К типовым преобразователям задач логического управления относят операторы решения логического уравнения, выдачи управляющего воздействия, опроса датчиков контролируемых параметров, сигнализации, запоминания промежуточных действий системы управления или эксплуатационных состояний объекта, счета числа воздействий, восстановления алгоритма и паузы между воздействиями. Из исполнительного оператора выходят одна дуга, если он детерминированный, и несколько дуг, если он вероятностный. Независимо от результата действия оператора вслед за ним выполняется тот оператор, в который в общем случае с наибольшей вероятностью заходит дуга из исполнительного оператора.

Условные операторы P _i изменяют порядок выполнения исполнительных операторов в зависимости от выполнения некоторых условий. Часто условные операторы называют распознавателями и выделяют шесть типов операторов проверки результатов: решения логического уравнения (=, ¹); анализа правильного выполнения команд управления объектом (=, ¹); контроля числа попыток (>, £); учета реального масштаба времени (<, ³); контроля параметров объекта (Да, Нет); контроля действий системы управления (=, ¹). На схемах они обозначаются символом “Решение” (рис. 8.2, в). Каждый оператор P _i имеет две выходящие дуги, отмеченные символами 0 и 1. Если условие выполнено, то следующим реализуется оператор, в который ведет дуга с символом 1, а если условие не выполнено, то переход происходит по дуге с символом 0.

Обычно в ГСА стрелки ставят только на дугах, направленных вверх и налево; вертикальные дуги операторов P _i соответствуют символу 1, а горизонтальные – символу 0; если последнее не выполняется, то на дугах операторов P_i ставят символы, соответствующие действительному ходу процесса.

На рис. 8.3 приведены примеры графического описания алгоритмов.

Рис. 8.3. Граф-схемы алгоритмов

Операторный способ записи алгоритмов. Такой способ также называют логические схемы алгоритмов. В нем в качестве операторов используются буквы русского алфавита. Обозначения операторов определяются разработчиком. Перечень принятых обозначений и их «объем» устанавливаются заранее и даются в качестве пояснения к алгоритму.

Эта форма является более компактной. В ЛСА операторы записываются в строку слева направо в порядке их естественного выполнения. При этом начальный оператор не пишется. Порядок выполнения операторов в строке принимается следующим. Если выполняется оператор A _i, то следом за ним выполняется оператор, стоящий в строке справа от A _i. Если же выполняется оператор P _i, то дальнейшее выполнение алгоритма зависит от того, выполнено или не выполнено условие, которое проверяется этим оператором. Если условие выполнено, то следующим выполняется оператор, записанный справа от P _i, Если же условие не соблюдено, то справа от P _i, ставится стрелка вверх над которой пишется номер этого оператора, а перед оператором, к которому должна идти стрелка, ставится стрелка концом вниз, отмеченная тем же номером. Для алгоритма, записанного в форме ГСА и представленного на рис. 8.3, а соответствует следующая запись в форме ЛСА:

Р₁­¹А₂¯¹А₃ s _к.

Возможно и несколько иное представление аналогичной записи:

Р₁­³А₂¯¹А₃ s _к, или в общем случае - А₁¯^кА₂……А_к-1Р_к­²А_к+1, т.е. у стрелки, направленной вверх, ставится номер оператора, к которому осуществляется переход, а у стрелки, направленной вниз, - номер логического условия, от которого сделан переход.

Оператор безусловного перехода обозначается - ω_i. После его выполнения всегда происходит переход по стрелке, стоящей справа от него. Так для алгоритма, ГСА которого приведена на рис. 8.3, б, форма ЛСА имеет вид:

¯¹Р₁­¹¯⁹Р₂­²А₄ Р ₅­⁵¯¹⁰А₇ ω₈­⁸¯²А₃ω₉­⁹¯⁵А₆ω₁₀­¹⁰¯⁸ s _к.

При описании в форме ЛСА процесса функционирования системы управления часто бывает необходимо отразить параллельность выполнения некоторых операторов, Для этого при составлении ЛСА используют следующие приемы. Предварительно перед каждой ветвью ЛСА, заключенной в фигурные скобки, помещают в квадратных скобкам символ (например, букву греческого алфавита), который является отметкой этой ветви. Так, в ЛСА

[a]{ А ₃}[b]{ А ₄}[g]{ А ₅, А ₆},

имеются три ветви с отметками a, b, g. После этого вводят оператор П (a, b, g), указывающий на необходимость параллельного выполнения ветвей с отметками a, b, g,

П (a, b, g)[a]{ А ₃}[b]{ А ₄}[g]{ А ₅, А ₆}.

В ЛСА также используется оператор вида W(a₁, a₂,..., a_к). Он указывает на то, что переход к оператору, стоящему справа от него, осуществляется лишь после завершения выполнения операторов в ветвях с отметками a₁, a₂,..., a_к.

Так, запись

¯¹ Р ₁­¹ А ₂ П (a, b, g)[a]{ А ₃}[b]{ А ₄}[g]{ А ₅, А ₆} W (a, b)[ d ]{ А ₇} W (g, d)¯¹² Р ₈­⁸ А ₁₀ω₁₁­¹¹¯⁸ А ₉

ω₁₂­¹²¯¹¹ s _к

означает следующее. Вначале выполняются операторы Р ₁ и А ₂, затем начинается одновременное выполнение трех ветвей с отметками a, b, g. Только после того, как будет закончено выполнение ветвей с отметками a и b, начнет выполняться ветвь с отметкой d. Когда же будут закончены ветви с отметками g и d, будут выполняться операторы Р ₈, А ₉, А ₁₀ и s _к.

Если в ЛСА необходимо отразить некоторые временные зависимости, например, выдержку во времени между подачей сигналов на исполнительные органы, то вводят дополнительный оператор D (А _j, t). Смысл этого оператора состоит в том, что при записи А _i D (А _j, t) после выполнения оператора А _i проходит t тактов условного времени, а затем начинается выполнение оператора А _j.

Если каждому оператору в ЛСА сопоставить время его выполнения в некоторых условных единицах, то ЛСА становится временной. В этом случае в операторе W вместо отметок ветвей может быть указано время, по прошествии которого будет выполняться ветвь, начинающаяся с оператора, расположенного справа от оператора W. ЛСА могут включать частные ЛСА, для разделения которых используется знак разделения *.

При записи сложных алгоритмов с большим числом связей применение стрелок для обозначения переходов не удобно. В этом случае для изображения переходов используются различные дополнительные знаки.

Логические схемы алгоритмов позволяют формально проводить некоторые преобразования по минимизации числа условных операторов. Методы минимизации ЛСА базируются на теории логических функций.

Словесная форма записи алгоритмов предусматривает запись алгоритма по шагам. При этом алгоритм разделяется на ряд элементарных операций - шагов. Содержание шага записывается в словесной форме с указанием номера очередного шага, к которому следует перейти после выполнения данного. В случае разветвления процесса описание шага состоит из двух частей, разделенных наречием «иначе». В каждой из частей указывается номер очередного шага, к которому следует перейти после выполнения сформулированного условия. Наиболее существенный недостаток словесного описания - малая наглядность и, как следствие, плохая обозримость алгоритма.

Алгоритмы управления имеют конкретное содержание, которое не зависит от формы записи: наглядной ГСА или компактной ЛСА.

Дата добавления: 2014-01-20