§1.2. Основные сведения об алгоритмах Понятие алгоритма
Алгоритм – это формальное предписание, однозначно определяющее содержание и последовательность операций, переводящих совокупность исходных данных в искомый результат – решение задачи.
Иначе говоря, алгоритм – это набор понятных исполнителю инструкций (команд), точное выполнение которых приводит к достижению требуемого результата.
Алгоритм позволяет формализовать выполнение информационного процесса. Если исполнителем является человек, то он может выполнять алгоритм формально, не вникая в содержание поставленной задачи, а только строго выполняя последовательность действий, предусмотренную алгоритмом. Представление информационного процесса в форме алгоритма позволяет поручить его автоматическое исполнение различным техническим устройствам, среди которых особое место занимает компьютер. При этом говорят, что компьютер исполняет программу (последовательность команд), реализующую алгоритм.
С алгоритмами связаны следующие области исследований [2].
Анализ алгоритмов. Предмет этой области состоит в том, чтобы для заданного алгоритма определить рабочие характеристики. Например, часто требуется, чтобы алгоритм был быстрым.
Теория алгоритмов. К этой области относятся вопросы существования или отсутствия эффективных алгоритмов вычисления определенных величин.
Построение алгоритмов. В этой области рассматриваются стандартные приемы и методы, используемые при создании алгоритмов.
Свойства алгоритма
Все алгоритмы обладают рядом свойств. Основными свойствами алгоритмов являются [4]:
Конечность (результативность, финитность). Свойство так определять процесс преобразования исходных данных, чтобы он через конечное число шагов для любых допустимых исходных данных приводил к искомому результату. Процедуру, обладающую всеми характеристиками алгоритма, за исключением конечности, можно назвать вычислительным методом.
Определенность (детерминированность). Предполагает такое составление алгоритма, которое не допускает различных толкований или искажения результата. При словесном описании алгоритмов оно дается на обычном разговорном языке, поэтому не исключена возможность неточного понимания предписания, например, человеком. Чтобы преодолеть эту трудность, для описания алгоритмов разработаны формально определенные языки программирования, в которых каждое утверждение имеет абсолютно точный смысл.
Ввод (массовость, наличие входных данных). Определяет возможность использования любых исходных данных из некоторого определенного множества для однотипных задач. Так, правило умножения столбиком является алгоритмом, т.к. оно используется для любых чисел (как целых, так и вещественных или дробных), но таблица умножения — не алгоритм. Это свойство подразумевает в программе наличие блока ввода, но в некоторых случаях число входных данных может быть равно нулю [4].
Вывод (наличие выходных данных). Алгоритм имеет одно или несколько выходных данных, имеющих определенную связь с входными данными. Здесь подразумевается наличие в программе блока вывода, иначе выполнение программы становится бессмысленным.
Эффективность. Алгоритм считается эффективным, если его операторы достаточно просты для того, чтобы их можно было точно выполнить в течение конечного промежутка времени.
Иногда приводят и дополнительные свойства алгоритмов, например:
Направленность. Означает наличие способа однозначного перехода от одного действия к другому.
Дискретность. Свойство, означающее, что алгоритм разбивается на последовательные команды, возможность выполнения которых человеком или машиной (исполнителем) не вызывает сомнений.
Понятность. Означает, что все команды алгоритма должны быть понятны для конкретных исполнителей.
Формы записи алгоритмов
Существуют три основных способа записи или представления алгоритма [5]:
словесная (текстуальная) запись алгоритма;
описание на алгоритмическом языке;
структурная схема (графическая схема).
Словесное описание алгоритма представляет собой текст, в котором на каком-либо разговорном языке (например, на русском) по пунктам записана последовательность действий. Строгие требования к форме такой записи не предъявляются, но существуют определенные правила, выполнение которых облегчает понимание алгоритма. Все действия расписываются по шагам или нумеруются, чтобы было удобно ссылаться при необходимости по номеру шага или пункта. Начало алгоритма и его окончание иногда отмечают словами «начало» и «конец». Можно указывать в одном пункте не одно действие, а группу простых действий.
Пример. Вычисление  . Вычисление производится по итерационной формуле
 .
При последовательных приближениях необходимо задавать точность, с которой подсчитывается выходная величина. Обозначим ее как ε. За начальное приближение примем само значение а.
Шаг 1. Определим начальные значения а и ε.
Шаг 2. Выберем начальное приближение хп равным а.
Шаг 3. Вычислим следующее приближение хп+1 по формуле
.
Шаг 4. Если  , то хп+1 – искомый результат, и алгоритм окончен.
Шаг 5. Положим хп = хп+1 и перейдем к шагу 3.
Количество шагов для этой задачи может быть и другим, например, если в шаге 4 записать «…, то перейти к шагу 6». И далее
Шаг 6. Вывести значение хп+1.
Шаг 7. Конец алгоритма.
В словесной форме удобно задавать алгоритмы для людей. Например, инструкции по эксплуатации различных бытовых приборов можно рассматривать как алгоритм. Но для ЭВМ при сложных задачах, с множеством ветвлений и циклов такая форма записи не наглядна.
Любая программа является представлением алгоритма. Но наиболее наглядными с точки зрения человека являются программы на алгоритмических языках высокого уровня. Но программа есть представление алгоритма с максимальной степенью детализации, и укрупненные алгоритмы в такой форме представления записывать нельзя. По способу записи эта форма близка к словесной, но со строгими формальными правилами.
Графическое представление алгоритма изображается в виде блок-схем или граф-схем. Рисунки, или графические изображения считаются наиболее наглядным представлением информации, поэтому и сложные алгоритмы наиболее удобны и понятны при их графическом представлении. Здесь отдельные шаги представляются в виде геометрических фигур, соединенных линиями, указывающими последовательность перехода от блока к блоку. Конструкторскую документацию по алгоритмам при разработке программных продуктов оформляют в виде блок-схем, поэтому существуют определенные стандарты в ЕСПД, регламентирующие запись алгоритмов [6]. Более подробно они будут рассмотрены далее.
Существуют и другие формы записи алгоритмов [3]:
операторный способ;
с использованием диаграммы Нэсси-Шнейдермана;
с использованием Р-схемы;
с помощью псевдокода.
Последний способ получил достаточно широкое распространение и является промежуточным перед записью алгоритма в терминах выбранного языка программирования. По сути своей является симбиозом естественного языка и языка программирования. В некоторых случаях псевдокод практически является алгоритмическим языком высокого уровня.
Блок-схемы алгоритмов
В настоящее время в вычислительной технике для записи алгоритмов используется «ГОСТ 19.701-90. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения». Он входит в группу стандартов единой системы программной документации (ЕСПД) [6]. Этот стандарт введен взамен «ГОСТ 19.002-80. Схемы алгоритмов и программ. Правила выполнения. ГОСТ 19.003-80. Схемы алгоритмов и программ. Обозначения условные графические» [7,8]. Но стандарт от 1990 года не совсем полный, в частности, там отсутствуют размеры и отношения сторон блоков, изменены название и трактовка некоторых из них. Поэтому совместно с ГОСТ 19.701-90 рекомендуется использовать и ГОСТ 19.002-80, ГОСТ 19.003-80.
Далее приводятся выдержки из этих стандартов. В них графические блоки называются символами.
2.2. Схема программы.
2.2.1. Схемы программ отображают последовательность операций в программе.
2.2.2. Схема программы состоит из:
1) символов (т.е. блоков) процесса, указывающих фактические операции обработки данных (включая символы, определяющие путь, которого следует придерживаться с учетом логических условий);
2) линейных символов, указывающих поток управления;
3) специальных символов, используемых для облегчения написания и чтения схемы.
Из-за разночтений в табл. 1.1 приводится описание основных символов (в стандарте их существенно больше) как по ГОСТ 19.701-90, так и по ГОСТ 19.003-80.
Таблица 1.1. Наименование и обозначение символов и отображаемые ими функции
Обозначение и размеры
|
Наименование и функция по ГОСТ 19.701-90
|
Наименование и функция по ГОСТ 19.003-80
|
|
Процесс. Символ отображает функцию обработки данных любого вида (выполнение операции или группы операций, приводящие к изменению значения, формы или размещения информации или к определению, по которому из нескольких направлений потока следует двигаться).
|
Процесс. Выполнение операций или группы операций, в результате которых изменяется значение, форма представления или расположение данных.
|
|
Линия. Символ отображает поток данных или управления. При необходимости или для повышения удобочитаемости могут быть добавлены стрелки-указатели.
|
Линия потока. Указание последовательности перехода между символами. Направления линии потока сверху вниз и слева направо принимают за основные и, если линии потока не имеют изломов, стрелками можно не обозначать. В остальных случаях направление линии потока обозначать стрелкой обязательно.
|
Продолжение табл. 1.1.
1
|
2
|
3
|
|
Решение. Символ отображает решение или функцию переключательного типа, имеющую один вход и ряд альтернативных выходов, один и только один из которых может быть активизирован после вычисления условий, определенных внутри этого символа. Соответствующие результаты вычисления могут быть записаны по соседству с линиями, отображающими эти пути.
|
Решение. Выбор направления выполнения алгоритма или программы в зависимости от некоторых переменных условий.
|
|
Подготовка. Символ отображает модификацию команды или группы команд с целью воздействия на некоторую последующую функцию (установка переключателя, модификация индексного регистра или инициализация программы).
|
Модификация. Выполнение операций, меняющих команды или группу команд, изменяющих программу.
|
|
Граница цикла. Символ, состоящий из двух частей, отображает начало и конец цикла. Обе части символа имеют один и тот же идентификатор. Условия для инициализации, приращения, завершения и т.д. помещаются внутри символа вначале или в конце в зависимости от расположения операции, проверяющей условие.
|
(отсутствует)
|
Продолжение табл. 1.1.
1
|
2
|
3
|
|
Данные. Символ отображает данные, носитель данных не определен.
|
Ввод-вывод. Преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов обработки (вывод)
|
|
Ручной ввод. Символ отображает данные, вводимые вручную во время обработки с устройств любого типа (клавиатура, переключатели, кнопки, световое перо, полоски со штриховым кодом).
|
Ручной ввод. Ввод данных вручную при помощи неавтономных устройств с клавиатурой, набором переключателей, кнопок.
|
|
Документ. Символ отображает данные, представленные на носителе в удобочитаемой форме (машинограмма, документ для оптического или магнитного считывания, микрофильм, рулон ленты с итоговыми данными, бланки ввода данных).
|
Документ. Ввод-вывод данных, носителем которых служит бумага
|
|
Предопределенный процесс. Символ отображает предопределенный процесс, состоящий из одной или нескольких операций или шагов программы, которые определены в другом месте (в программе, модуле).
|
Предопределенный процесс. Использование ранее созданных и отдельно описанных алгоритмов или программ.
|
Окончание табл. 1.1.
1
|
2
|
3
|
|
Терминатор. Символ отображает выход во внешнюю среду и вход из внешней среды (начало или конец схемы программы, внешнее использование и источник или пункт назначения данных).
|
Пуск – останов. Начало, конец, прерывание процесса обработки данных или выполнения программы.
|
|
Соединитель. Символ отображает выход в часть схемы и вход из другой части этой схемы и используется для обрыва линии и продолжения ее в другом месте. Соответствующие символы-соединители должны содержать одно и то же уникальное обозначение.
|
Соединитель. Указание связи между прерванными линиями потока, связывающими символами.
|
|
Комментарий. Символ используют для добавления описательных комментариев или пояснительных надписей в целях объяснения или примечаний.
|
Комментарий. Связь между элементом схемы и пояснением.
|
Расстояния между параллельными линиями потока должно быть не менее 3 мм, между остальными символами схемы - не менее 5 мм.
Размер a должен выбираться из ряда 10, 15, 20 мм. Допускается увеличивать размер a на число, кратное 5. Размер b равен 1,5a.
Записи внутри символа или рядом с ним должны быть краткими. Сокращение слов и аббревиатуры, за исключением установленных государственными стандартами, должны быть расшифрованы в нижней части поля схемы или в документе, к которому эта схема относится.
Координаты зоны символа или порядковый номер проставляют в верхней части символа в разрыве его контура по аналогии с примером, изображенным на рис. 1.2.
Рис. 1.2. Пример фрагмента схемы с обозначением порядковых номеров символов на схеме
При числе исходов не более трех признак условия решения (Да, Нет, =, <, >) проставляют над каждой выходящей линией потока или справа от линии потока. При числе исходов более трех условие исхода проставляется в разрыве линии потока. Адрес исхода проставляется в продолжении условия исхода и отделяется от него пробелом (см. рис. 1.3).
 
Рис. 1.3. Возможные варианты отображения блока решения
Здесь Yi - условие i-го исхода, 011E1, 016A3, 005B5, 015E4 – адреса исходов.
Рис. 1.4. Пример использования символов границы цикла.
На рис. 1.4 приводится фрагмент алгоритма с введенным в ГОСТ 19.701-90 символом «Граница цикла».
Рис. 1.5. Пример блок-схемы алгоритма вычисления кубического корня с блоком «решение»
Рис. 1.6. Пример блок-схемы алгоритма вычисления кубического корня с блоками границы цикла
На рис. 1.5 и 1.6 изображены примеры блок-схем одного и того же алгоритма, но с использованием разных символов.
|
