Понятие алгоритма

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

1. Дискретность – свойство, отражающее выполнение вычислительного процесса, задаваемого алгоритмом по шагам.

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

3. Элементарность – свойство, согласно которому действие, которое выполняется на каждом шаге должно быть простым.

4. Направленность – свойство, обуславливающее необходимость указания, что является результатом того шага, на котором нельзя выполнить определенную в нем операцию.

5. Массовость – свойство, согласно которому алгоритм может быть применен к любой совокупности из допустимого множества исходных данных.

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

1. Временная сложность – показатель, отражающий время выполнения алгоритма или количество шагов его выполнения.

2. Емкостная сложность – показатель, по которому производят оценку количества данных, необходимых для выполнения алгоритма.

3. Сложность описания – показатель, отражающий длину описания алгоритма, количество инструкций операторов.

Для представления алгоритма используют различные средства, в том числе граф-схемы алгоритмов, каждая из которых представляет собой граф. Понятие элементарного графа дополнено введением надстройки, которая задает вычисления, каждому из которых соответствует путь в этом графе и последовательность меток узлов, лежащих на этом пути. Узлы графа, с помощью введения типизации, интерпретируются как действия, а дуги задают порядок передачи управления. Для каждого алгоритма существует одна начальная дуга и одна или множество конечных. В табл.1 представлены типы узлов граф-схемы алгоритма в соответствии с ГОСТ 19.701-90 «Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения».

Таблица 1

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

 

Приведем основные свойства граф-схем.

1. Графическое представление.

2. Поддержка описания управляющей части алгоритма.

3. Возможность реализации синтаксического контроля.

4. Возможность проверки управляющей части алгоритма.

5. Отсутствие возможности верификации информационной части.

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