Элементы блок-схем алгоритмов

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

Существует множество определений понятия “алгоритм”:

1. «процедура, которая принимает любой из возможных входных экземпляров задачи и преобразует его в соответствии с требованиями, указанными в условии задачи» [1];
2. «точное предписание, однозначно определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату» [2];
3. «конечный набор правил, однозначно раскрывающих содержание и последовательность выполнения операций для систематического решения определенного класса задач за конечное число шагов» [3];
4. «a detailed sequence of actions to perform to accomplish some task» [4].

Из определений вытекают свойства алгоритма [5]:

1. дискретность. В определениях 3 и 4 говорится, что алгоритм состоит из отдельных действий или правил. Алгоритм обладает дискретностью, если его можно разделить на отдельные этапы (части, команды);
2. детерминированность (определенность). Алгоритм обладает свойством детерминированности, если для одних и тех же наборов исходных данных он будет выдавать один и тот же результат, т.е. результат однозначно определяется исходными данными (на это свойство указывается в определении 3);
3. результативность. Свойство результативности означает, что алгоритм должен выдавать результат за конечное число шагов. О том, что число шагов должно быть конечным говорится в определениях 3 и 4;
4. массовость. В определениях 1, 2, 3 говорится о некоторых классах задач (входных экземплярах задачи, варьируемых начальных данных) на которых алгоритм должен работать алгоритм. Это означает, что набор исходных данных, на которых алгоритм должен выдавать верное решение, заранее ограничен;
5. правильность. Под правильностью понимается соответствие результатов работы алгоритма условию задачи (определение 1). Казалось бы, очень сомнительное свойство, ведь выше было описано свойство результативности, однако, программа должна не просто выдавать результат, а результат правильный.

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

Элементы блок-схем алгоритмов

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

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

Терминатор начала и конца работы функции	Терминатором начинается и заканчивается любая функция. Тип возвращаемого значения и аргументов функции обычно указывается в комментариях к блоку терминатора.
Операции ввода и вывода данных	Определено множество символов ввода/вывода, например вывод на магнитные ленты, дисплеи и т.п. Если источник данных не принципиален, обычно используется символ параллелограмма. Подробности ввода/вывода могут быть указаны в комментариях.
Выполнение операций над данными	В блоке операций обычно размещают одно или несколько операций присваивания, не требующих вызова внешних функций.
Блок, иллюстрирующий ветвление алгоритма	Блок в виде ромба имеет один вход и несколько подписанных выходов. В случае, если блок имеет 2 выхода (соответствует оператору ветвления), на них подписывается результат сравнения – “да/нет”. Если из блока выходит большее число линий (оператор выбора), внутри него записывается имя переменной, а на выходящих дугах – значения этой переменной.
Вызов внешней процедуры	Вызов внешних процедур и функций помещается в прямоугольник с дополнительными вертикальными линиями.
Начало и конец цикла	Символы начала и конца цикла содержат имя и условие. Условие может отсутствовать в одном из символов пары. Расположение условия, определяет тип оператора, соответствующего символам на языке высокого уровня – оператор с предусловием (while) или постусловием (do … while).
Подготовка данных	Символ “подготовка данных” в произвольной форме (в ГОСТ нет ни пояснений, ни примеров), задает входные значения. Используется обычно для задания циклов со счетчиком.
Соединитель	В случае, если блок-схема не умещается на лист, используется символ соединителя, отражающий переход потока управления между листами. Символ может использоваться и на одном листе, если по каким-либо причинам тянуть линию не удобно.
Комментарий	Комментарий может быть соединен как с одним блоком, так и группой. Группа блоков выделяется на схеме пунктирной линией.