Свойства алгоритмов
Алгоритмы обладают свойствами определенности, массовости и результативности. Свойство определенности выражает тот факт, что совокупность операций, выполняемых в соответствии с не-которым алгоритмом, не допускает никакого произвола относительно их последовательности и толкования, т. е. является детерминированным процессом. Массовость алгоритма означает возмож-ность решения с его помощью целого класса задач с изменяющимися исходными данными. Результа-тивность алгоритма состоит в том, что искомый результат может быть получен с помощью алгоритма путем выполнения конечного числа операций при всех допустимых значениях исходных данных. Рассмотренные свойства алгоритма являются эмпирическими и их нельзя считать определением понятия алгоритм.
Областью применимости алгоритма называется наибольшая область исходных данных, на которой алгоритм обладает свойством результативности. Если исходные данные не входят в область применимости алгоритма, то он не обеспечивает получения результата за конечное число опера-ций.
3.3. Алгоритмические системы: операторные описания и граф-схемы
Общий стандартный способ задания алгоритмов называется алгоритмической системой. В теории и проектировании технических средств ВТ для этих целей используются две алгоритмические системы: операторные описания (ОО) и граф-схемы алгоритмов (ГСА). В ОО буквами обозначаются отдельные действия алгоритмов по переработке информации — операции и проверяемые логические условия. Последовательное выполнение нескольких операций обозначается как их произведение, причем левая операция выполняется раньше правой. В такой линейной записи алгоритма операция отличается от логического условия тем, что после последнего ставится стрелка, направленная вверх и снабженная числовым индексом. Если логическое условие А выполнено (т. е. А = 1), то осуществляется переход к операции или логическому условию, указываемому стрелкой. Если же условие А не выполнено (А = 0), то осуществляется переход к операции или логическому условию, записанному непосредственно за условием А. Например, операторное описание
означает, что после выполнения операций В1, В2и В3необходимо проверить логическое условие А1. Если А1= 0, то далее необходимо переходить к операциям В4, В5и логическому условию А2. Если же А1 = 1, то следует сразу перейти к проверке А2. В зависимости от значения А2возможны два варианта продолжения алгоритма: выполнить операцию В6(при А2 = 0) либо В3и далее проверить А1 (при А2 = 1).
Рис. 1
При записи алгоритмов в виде ГСА используются три основных символа, имеющих опре-деленное геометрическое начертание (рис.1) и называемых вершинами ГСА. Начало и конец алго-ритма обозначается вершиной на рис. 1, а. Любой алгоритм, представленный ГСА, начинается и заканчивается этой вершиной. Операторной вершиной (рис. 1, б) ГСА называется условное или содержательное обозначение выполняемой операции.
Содержательное обозначение операции удобно записывать с помощью оператора присваи-вания, обозначаемого как : = . Например, запись X := Х + 1 означает, что к переменной величине X необходимо прибавить 1 (т. е. переменной X «присвоить» новое значение, равное X + 1). Совокупность операторов присваивания, записанных в одной и той же операторной вершине, выполняется одновременно. Условная вершина (рис. 1, в) соответствует проверяемому логическому условию, два возможных исхода которого обозначены 0 (условие не выполнено) и 1 (условие вы-полнено). Внутри условной вершины записывается либо логическое выражение, отражающее смысл проверяемого условия, либо двоичная переменная (например, А), обозначающая результат проверки. Линии на ГСА означают переходы от одной вершины к другой. На рис. 1, г в качестве примера построена граф-схема алгоритма по приведенному выше операторному описанию.