2. 6. Алгоритмы. Граф-схемы алгоритмов

Термин "алгоритм" происходит от латинского написания имени выдающегося средневекового математика аль-Хорезми, - сформулировавшего правила выполнения четырех арифметических действий, которые всегда и всеми выполняются одинаково, а значит, если нужно, могут быть авто­матизированы. Понятие "алгоритм" выражает стремление к расчленению сложных процессов на простые, доступные для выполнения без каких-либо дополнительных пояснений.

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

порядок их исполнения; строгое выполнение этих операций всегда при­водит к решению любой задачи данного типа.

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

Алгоритмы в форме инструкции встречаются часто, но не всякую инструкцию можно назвать алгоритмом. Инструкция, претендующая на название "алгоритм", должна обладать следующими свойствами:

1. должна быть записана в виде последовательности четко различаемых отдельных пунктов (свойство дискретности);

2. каждое указание инструкции должно быть понятно, недвусмысленно и доступно для исполнения (свойство доступности);

3. инструкцию можно применить к решению не одной, а всех задач одного класса (свойство массовости);

4. инструкция, если она применяется к доступным исходным дан­ным, через конечное число шагов всегда должна привести к результату (свойство результативности).

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

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

Формульные алгоритмы записываются на языке математических фор­мул и, как правило, в более сжатом виде по сравнению с алгоритмами-инструкциями. Кроме того, формула может быть подвергнута исследова­нию, упрощению и стать объектом дальнейших исследований. Казалось бы, их преимущество над алгоритмами-инструкциями бесспорно. Однако это не так. Дело в том, что большинство технических и практических задач невозможно строго описать математическими формулами, а алгоритмы-ин­струкции настолько нестандартны, особенно при решении технических задач, что их не удается исследовать чисто формально. В этих случаях удобнее использовать язык граф-схем алгоритмов.

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

Операторные вершины (рис. 2.13,б) обозначаются прямоугольника­ми, в которых записываются операторы, т.е. действия, которые следует выполнять на данном шаге процесса решения задачи.

Условные вершины ГСА (рис. 2.13,в) изображаются ромбами с ука­занием вопросов, на которые следует получить ответы, и на основании этих ответов продолжать решение - переходить к тому оператору, кото­рый указан одной из стрелок, ведущих из ромба.

Любая вершина ГСА, кроме вершины "Начало", имеет по одному входу. Вершина "Начало" входов не имеет. Вершина "Начало" и любая опера­торная вершина имеет по одному выходу. Вершина "Конец" выходов не имеет. Любая условная верши­на имеет два выхода, помечаемых символами "Да" и "Нет" или циф­рами "1" и "0" соответственно.

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

а

Рис. 2.13. Типы вершин ГСА

ГСА должна удовлетворять следующим условиям [13]:

1. Входы и выходы вершин соединяются друг с другом с помощью дуг, направленных всегда от выхода ко входу.

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

3. Любой вход соединяется по крайней мере с одним выходом.

4. Любая вершина ГСА лежит по крайней мере на одном пути из вершины "Начало" в вершину "Конец",

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

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

7. В каждой операторной вершине записывается оператор, пред­ставляющий собой выходной сигнал или совокупность таких сигналов. Допускается в различных операторных вершинах записывать одинаковые операторы.

Алгоритмы, в соответствии с которыми решение поставленных задач сводится к арифметическим действиям, называются численными алгорит­мами.

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

Вместе с тем существуют алгоритмы, где предписание о способе действия относится не к цифровым объектам, а решение задачи требует произвольного поиска. Такой класс задач требует построения так назы­ваемого логического алгоритма, а их решение сводится к поиску путей на графе (в лабиринте) [13; 18].

Различают два формы представления алгоритмов: содержательные ГСА и логические схемы алгоритмов. При решении технических задач, как правило, предварительно составляется содержательная ГСА.

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

Логические схемы алгоритмов представляют собой алгоритм в виде конечной строки, содержащей символы операторов, логических условий, а также верхние и нижние стрелки, которым приписаны натуральные числе [13, 18]. Логические схемы алгоритмов читаются слева направо и ис­пользуются в тех случаях, когда нужна компактная запись алгоритма, например при машинной обработке. От логической схемы алгоритма можно перейти к соответствующей ГСА. Возможен и обратный переход, однако он сложнее и используется редко.

Создание понятия "алгоритм" и его описание - большое достижение в решении задач многих классов, а потому растет стремление к алгоритмизации, ширится круг задач, которые удается алгоритмизировать.