Общие сведения об алгоритмах

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 1

Описание условных графических обозначений (УГО),

Используемых в СА

Наименование	Обозначение	Функции
Данные		Символ отображает данные, носитель данных не определен. Используется для обозначения операций ввода и вывода данных
Процесс		Символ отображает функцию обработки данных любого вида (выполнение определенной операции или группы операций, приводящее к изменению значения, формы или размещения информации). Используется для обозначения операций присваивания

Продолжение табл. 1

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

Продолжение табл. 1

Наименование	Обозначение	Функции
Терминатор		Символ отображает выход во внешнюю среду и вход из внешней среды. Используется для обозначения начала или окончания алгоритма
Линия		Символ отображает поток данных или управления. Направления справа налево и снизу вверх обозначаются стрелками. Используется для соединения символов в алгоритме
Параллельные действия		Символ отображает синхронизацию двух или более параллельных операций
Пунктирная линия		Символ отображает альтернативную связь между двумя или более символами. Кроме того, символ используется для обведения аннотированного участка при записи комментариев
Комментарий		Символ используется для добавления описательных комментариев или пояснительных записей с целью объяснений или примечаний. Пунктирные линии в символе комментария связаны с соответствующим символом или могут обводить группу символов. Текст комментариев или примечаний должен быть помещен около ограничивающей фигуры

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

Внутри соединителей ставятся номера (координаты) блоков к которым или от которых идут линии связи. Вместо номера (координат) может быть поставлен некоторый (один и тот же в обоих соединениях) идентификатор (рис. 5).

Рис. 5. Применение соединений

Недостатком графических схем алгоритмов является громоздкость. Для решения специальных задач, например проектирования вычислительных устройств, применяются другие способы задания алгоритмов, такие, как логические (операторные) и матричные схемы. Их достоинствами являются компактность и простота дальнейшей формализации, а недостатком — малая наглядность.

Предыдущая 123 4 5 6 7 8 Следующая