В.3. Базовые фрагменты схем алгоритмов

В теоретическом плане [3] СА – это ориентированный граф (совокуп-ность вершин и связей между ними), вершины которого могут быть одного из трёх типов (рис. В.1):

 функциональная (используется для представления функции f: X→Y, т. е. арифметического выражения);

 предикатная (используется для представления предиката p: X→{FALSE (ложь), TRUE (истина)}, т. е. логического выражения, опреде-ляющего управление по одной из возможных ветвей);

 объединяющая (реализует передачу управления от одной из двух входных ветвей к одной выходной ветви).

Отметим, что в практике объединяющие вершины не выделяются (они ясны по умолчанию).

Из данных вершин графа составлены (рис. В.2) простейшие струк-туры управления вычислительным процессом (базовые фрагменты СА). Здесь В интерпретируется как булево выражение, а S₁ и S₂ – как прог-раммные операторы (процедуры). Схема на рис. В.2,а называется компо-зицией (следованием) и записывается в виде S₁; S₂. Схема на рис. В.2,б называется альтернативой (выбором) и записывается в виде if B then S₁ else S₂; в частном случае S₂= получается часто используемый сокращён-ный оператор if B then S₁. Схема на рис. В.2,в¹ называется итерацией (циклом или повторением); получили распространение 3 частных случая:

1. S₂ = . Этому случаю соответствует оператор while B do S₁.

2. S₁ = . Этому случаю соответствует оператор do S₂ while B или, в эквивалентной форме, оператор repeat S₂ until .

3. S ₁ = S₂ = . Схема вырождается в ждущую вершину (ждущие вершины используются в СА процессов, управляющих событиями).

Теоретически было показано [3], что любая СА может быть сос-тавлена путём суперпозиции базовых фрагментов СА, изображённых на рис. В.2 (теорема Дейкстра). Поскольку каждый из базовых фрагментов имеет один вход и один выход, то у любой СА, составленной из этих фрагментов, также будет один вход и один выход. СА, в которой используются только базовые фрагменты, называется структурированной. Этот же принцип (один вход и один выход) лежит в основе структурного программирования.

И так, совокупность трёх структур управления процессом вычислений достаточна для построения любой СА. Но СА, полученная путём суперпо-зиции этих структур, не обязательно будет простейшей или наиболее естественной. Поэтому в практике допускается некоторое расширение базового набора структур управления. Например, в некоторых случаях удобнее использовать оператор множественного выбора (типа case…of).

Допускается также преждевременный выход из цикла – операторы while…do и repeat…until, аккуратное применение оператора goto и др. Во всех этих случаях выдерживается основной принцип управления про-цессом вычислений – структура СА должна иметь один вход и один выход.

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

В зависимости от характера связи между вершинами СА алгоритмы делятся на линейные, ветвящиеся, циклические.

В гл. 1 рассматриваются соответствующие примеры.