Свойства алгоритмов

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

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

3.3. Алгоритмические системы: операторные описания и граф-схемы

Общий стандарт­ный способ задания алгоритмов называется алгоритмической системой. В теории и проектировании техни­ческих средств ВТ для этих целей используются две алгоритмические системы: операторные описания (ОО) и граф-схемы алгоритмов (ГСА). В ОО буквами обозначаются отдельные действия алгоритмов по переработке информации — операции и проверяемые логические условия. Последовательное выполнение нескольких операций обозначается как их произведение, причем левая операция выполняется раньше правой. В такой линейной записи алгоритма операция отличается от логического условия тем, что после послед­него ставится стрелка, направленная вверх и снабженная числовым индексом. Если логическое условие А выполнено (т. е. А = 1), то осуществляется переход к операции или логическому условию, указываемому стрелкой. Если же условие А не выполнено (А = 0), то осуществляется переход к операции или логическому условию, записанному непосредственно за условием А. Например, оператор­ное описание

означает, что после выполнения операций В ₁, В ₂и В ₃необходимо проверить логическое условие А ₁. Если А ₁= 0, то далее необходи­мо переходить к операциям В ₄, В ₅и логическому условию А ₂. Если же А ₁ = 1, то следует сразу перейти к проверке А ₂. В зависи­мости от значения А ₂возможны два варианта продолжения алго­ритма: выполнить операцию В ₆(при А ₂ = 0) либо В ₃и далее прове­рить А ₁ (при А ₂ = 1).

Рис. 1

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

Содержательное обозначение операции удобно записывать с по­мощью оператора присваи-вания, обозначаемого как: =. Например, запись X:= Х + 1 означает, что к переменной величине X необхо­димо прибавить 1 (т. е. переменной X «присвоить» новое значение, равное X + 1). Совокупность операторов присваивания, записан­ных в одной и той же операторной вершине, выполняется одновре­менно. Условная вершина (рис. 1, в) соответствует проверяемому логическому условию, два возможных исхода которого обозначены 0 (условие не выполнено) и 1 (условие вы-полнено). Внутри услов­ной вершины записывается либо логическое выражение, отражающее смысл проверяемого условия, либо двоичная переменная (напри­мер, А), обозначающая результат проверки. Линии на ГСА озна­чают переходы от одной вершины к другой. На рис. 1, г в качестве примера построена граф-схема алгоритма по приведенному выше операторному описанию.