ОПЕРАЦИОННЫЕ СХЕМЫ АЛГОРИТМОВ

НЕКОТОРЫЕ СВЕДЕНИЯ ИЗ ТЕОРИИ АЛГОРИТМОВ

В данном разделе приведены основные положения теории алгоритмов, виды представления алгоритмов (операционные схемы алгоритмов – ОСА: графические схемы алгоритмов – ГСА, логические схемы алгоритмов – ЛСА, матричные схемы алгоритмов – МСА, другие виды представления и способы перехода от одного представления алгоритма к другому, а также методы оптимизации алгоритмов).

ОПЕРАЦИОННЫЕ СХЕМЫ АЛГОРИТМОВ

1. Граф-схема алгоритма (ГСА) – ориентированный связный граф, содержащий вершины четырех типов: начальную, конечную, операторную и условную (Рис. 1).

Рис. 1. Вершины содержательной ГСА.

Начальная вершина имеет один выход и не имеет входов, конечная вершина имеет один вход и не имеет выходов, операторная вершина имеет один вход и один выход, условная вершина имеет один вход и два помеченных символами “0” (“нет”) и “1” (“да”) выхода.

ГСА удовлетворяет следующим условиям:

1.1. Содержит конечное число вершин, каждая из которых относится к одному из перечисленных (Рис. 1) типов.

1.2. Имеет одну начальную и одну конечную вершины.

1.3. Входы и выходы вершин соединены между собой с помощью дуг (стрелок или графов), направленных всегда от выхода к входу.

1.4. Каждый выход соединен только с одним входом.

1.5. Любой вход соединяется, по крайней мере, с одним выходом (на него могут поступать стрелки с нескольких выходов).

1.6. Для любой вершины графа существует, по крайней мере, один путь из этой вершины к конечной вершине (через другие вершины или непосредственно).

1.7. Один из выходов условной вершины может соединяться с ее входом (такая вершина называется “ждущая” условная вершина), что недопустимо для операторной вершины.

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

1.9. В каждой операторной вершине записывается оператор (микрокоманда) Y_t – подмножество множества , называемого множеством микроопераций:

(1)

При Æ, что допустимо.

Если в вершинах Рис. 1 записано содержание (формула, осуществляемая операция или проверяемое условие), то такая ГСА называется содержательной граф-схемой алгоритма.

Если записать в отдельную таблицу перечень содержания всех T операторных вершин, поставив им в соответствие символы , и всех N условных вершин, поставив им в соответствие символы , то такую таблицу можно назвать Таблицей соответствия.

Используя Таблицу соответствия, можно из содержательной граф-схемы алгоритма получить абстрактную ГСА или собственно ГСА.

Представление алгоритмов в виде такого рода графических схем очень информативно, поскольку наглядно даёт представление о его сложности и возможности осуществлять различные способы реализации отображаемой данным алгоритмом задачи управления. Существенным недостатком такого вида алгоритмов является громоздкая форма записи. Особенно при большом числе операций и проверяемых решений описываемого процесса управления. Реальные ГСА могут не вместиться на один лист рабочего формата. В таких случаях ГСА может занимать несколько листов, а переход с одного листа на другой должен осуществляться введением системы адресов. В соответствии с действовавшим до последнего времени в России ГОСТом было рекомендовано следующее. Во-первых, присвоить всем вершинам ГСА номера (в произвольном порядке, но без повторений), во-вторых, если путь к следующей вершине проходит на следующую (другую) страницу, то соответствующей стрелке присваивается метка в виде номера той вершины ГСА, в которую приходит данный путь развития на другой странице (листе).

А соответствующей стрелке на новом листе алгоритма присваивается метка в виде номера вершины ГСА на предыдущей странице, из которой приходит данная стрелка. Данный способ поясняется следующим примером.

Однако по опыту работы с такими алгоритмами выработался более удобный способ – способ “склейки”, показанный на следующем примере:

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

Пример ГСА представлен на следующей странице.

ПРИМЕР ГСА

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

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

Между этими символами записываются в соответствии с изображаемым алгоритмом операторы по числу операторов данного алгоритма (использовать символы операторов с одинаковым номером, даже если они описывают одно и то же содержание, не допускается) и логические условия .

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

Прочтение алгоритма осуществляется слева направо от к непрерывно, пока не встречается символ логического условия из множества с соответствующим символом . После этого прочтение алгоритма переходит на символ и т.д.

Ниже приводится пример такой ЛСА.

Пример ЛСА:

Очевидно, что все свойства алгоритмов, оговоренные для ГСА, остаются справедливыми и для ЛСА.

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

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

Эти функции перехода могут принимать следующие значения:

- тождественной единицы, если сразу после выполнения алгоритмом действия, предписанного оператором метки-строки, по алгоритму следует выполнение оператора метки-столбца этого алгоритма;

- тождественного нуля, если после выполнения алгоритмом действия, предписанного оператором метки-строки, по алгоритму не следует выполнение соответствующего оператора метки-столбца;

- функция перехода может составляться в виде дизъюнкции конъюнкций (логических сумм логических произведений) условий, выполнение которых необходимо, чтобы от оператора метки-строки перейти к соответствующему оператору метки-столбца.

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: