Свойства алгоритмов и способы их задания

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

Само слово «алгоритм» происходит от латинской формы написания имени великого математика IX века Аль Хорезми (Muhammed ibn Musa al Horesmi), который сформулировал правила выполнения арифметических действий. Первоначально под алгоритмом и понимали только правила выполнения четырех арифметических действий над многозначными числами, а в дальнейшем это понятие стало использоваться для обозначения последовательности действий, приводящих к решению поставленной задачи. Сейчас с помощью алгоритмов решаются не только вычислительные, но и многие другие задачи.

Качество алгоритма определяется его свойствами (характеристиками). К основным свойствам алгоритма относятся следующие.

1. Массовость. Предполагается, что алгоритм может быть пригоден для решения всех задач данного типа. Например, алгоритм для решения системы линейных алгебраических уравнений должен быть применим к системе, состоящей из произвольного числа уравнений.

2. Результативность. Это свойство означает, что алгоритм должен приводить к получению результата за конечное число шагов. Если же способ получения последующей системы величин из какой-либо заданной не даёт результата, то должно быть указано, что надо считать результатом алгоритма.

3. Определенность. Предписания, входящие в алгоритм, должны быть точными и понятными. Эта характеристика обеспечивает однозначность результата вычислительного процесса при заданных исходных данных.

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

5. Элементарность шагов.Описываемый алгоритмом процесс и сам алгоритм могут быть разбиты на отдельные элементарные этапы, возможность выполнения которых на ЭВМ у пользователя не вызывает сомнений. Можно сказать, что алгоритм — это задание, которое нужно исполнить. Утверждения и вопросы могут быть использованы в алгоритмах только как подчиненные предложения в составе предписания.

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

1) каждое предписание записывается с новой строки;

2) после предписания ставится точка с запятой;

3) если предписание не поместилось в одной строке, то его можно продолжить на следующей строке без каких-либо знаков переноса.

Такую словесную запись алгоритма называют псевдокодом (ПCK), подчеркивая этим ее промежуточное положение между нашей естественной речью и понятным для компьютера языком программ. Достоинством псевдокодов является их универсальность, а к недостаткам можно отнести малую наглядность записи. Наглядностью обладает другая форма записи — графическая схема алгоритмов (ГСА), или блок-схема. Такая схема представляет собой графический документ, который дает представление о порядке работы алгоритма. Здесь предписания имеют вид различных геометрических фигур, а последовательность выполнения операций отображается с помощью линий, соединяющих эти фигуры. Условные обозначения, применяемые при составлении граф-схем алгоритмов, и правила выполнения определены в ГОСТ 19.701-90 (ИСО 5807-85) «Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения».

В табл. 1 приведены наименования, обозначения и определения отображаемых функций для символов, используемых при описании программ и алгоритмов.

Таблица 1