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

Для эффективного использования компьютеров каждый пользователь должен уметь формулировать задачи, разрабатывать алгоритмы их решения и составлять программы, понятные компьютеру. Процесс составление алгоритмов для последующей реализации в виде программ для ЭВМ называется алгоритмизацией.

Понятие алгоритма, его свойства и виды

Л 5.2. Основы алгоритмизации

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

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

Алгоритмы являются объектом систематического исследования пограничной между математикой и информатикой научной дисциплины, примыкающей к математической логике -теории алгоритмов.

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

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

Слово алгоритм происходит от algoritmi, являющегося латинской транслитерацией арабского имени хорезмийского математика IX века
аль-Хорезми. Благодаря латинскому переводу трактата аль-Хорезми европейцы в XII веке познакомились с позиционной системой счисления, и в средневековой Европе алгоритмом называлась десятичная позиционная система счисления и правила счета в ней.

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

Применительно к ЭВМ алгоритм определяет вычислительный процесс, начинающийся с обработки некоторой совокупности возможных исходных данных и направленный на получение определенных этими исходными данными результатов. Термин вычислительный процесс распространяется и на обработку других видов информации, например, символьной, графической или звуковой. Если вычислительный процесс заканчивается получением результатов, то говорят, что соответствующий алгоритм применим к рассматриваемой совокупности исходных данных. В противном случае говорят, что алгоритм неприменим к совокупности исходных данных.

Исполнителя (компьютер) характеризуют: среда, элементарные действия, система команд, отказы.

Среда (или обстановка) - это «место обитания» исполнителя, определяемое пространственные, временные и другие условия существования объекта и ограничения.

Система команд - исполнитель выполняет команды только из некоторого строго заданного списка (системы команд исполнителя). Для каждой команды должны быть заданы условия применимости (в каких состояниях среды может быть выполнена команда) и описаны результаты выполнения команды.

Отказы исполнителя возникают, если команда вызывается при недопустимом для нее состоянии среды.

Для алгоритма характерны следующие основные свойства:

1. Дискретность (прерывность, раздельность) - алгоритм должен быть представлен как последовательное выполнение простых шагов. Шагом называется каждое действие алгоритма. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, т.е. преобразование исходных данных в результат осуществляется во времени дискретно.

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

3. Результативность (или конечность) - алгоритм должен приводить к решению задачи за определенное число шагов.

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

5. Понятность - исполнитель алгоритма должен знать, как его выполнять.

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

Алгоритм линейной структуры – алгоритм, в котором шаги (команды) следуют один за другим, не повторяясь, действия происходят только в одной заранее намеченной последовательности.

Алгоритм разветвленной структуры - алгоритм, содержащий хотя бы одно условие, в результате которого обеспечивается переход на один из нескольких возможных шагов (ветвей). В основе организации разветвления лежит проверка логического условия, которое может быть истинно или ложно. Частный вид логического условия – это операции типа =, , , >, , <.

Алгоритм циклической структуры - алгоритм, в котором предусмотрено неоднократное выполнение одной и той же последовательности действий для различных значений данных. Эту последовательность называют циклом. Различают циклы, в которых условие прекращения проверяется в начале (циклы с предусловием) или в конце (циклы с послеусловием).

Для задания алгоритма необходимо описать следующие его элементы:

· набор объектов, составляющих совокупность возможных исходных данных, промежуточных и конечных результатов;

· правило начала;

· правило непосредственной переработки информации (описание последовательности действий);

· правило окончания;

· правило извлечения результатов.

Для записи алгоритмов, а именно для описания последовательности действий, используют самые разнообразные средства. Выбор средства определяется типом исполняемого алгоритма. Выделяют следующие основные способы записи алгоритмов:

· вербальный (словесный), когда алгоритм описывается на естественном (человеческом) языке;

· графический, когда алгоритм описывается с помощью набора графических изображений;

· символьный, когда алгоритм описывается с помощью набора символов (например, с помощью математической символики или с помощью алгоритмического языка (структурированной записи, псевдокода).

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

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

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

Таблица 1

Название	Символ (рисунок)	Выполняемая функция (пояснение)
1. Процесс		Символ отображает функцию обработки данных любого вида (выполнение определенной операции или группы операций, приводящее к изменению значения, формы или размещения информации или к определению, по которому из нескольких направлений потока следует двигаться).
2. Решение		Символ отображает решение или функцию переключательного типа, имеющую один вход и ряд альтернативных выходов, один и только один из которых может быть активизирован после вычисления условий, определенных внутри этого символа.
3. Данные		Символ отображает данные, носитель данных не определен.
4. Документ		Символ отображает данные, представленные на носителе в удобочитаемой форме (машинограмма, документ для оптического или магнитного считывания, микрофильм, рулон ленты с итоговыми данными, бланки ввода данных).
5. Граница цикла	Условие завершения, Имя цикла Процесс Имя цикла	Символ, состоящий из двух частей, отображает начало и конец цикла. Обе части символа имеют один и тот же идентификатор. Условия для инициализации, приращения, завершения и т.д. помещаются внутри символа в начале или в конце в зависимости от расположения операции, проверяющей условие.
6. Предопределенный процесс		Символ отображает предопределенный процесс, состоящий из одной или нескольких операций или шагов программы, которые определены в другом месте (в подпрограмме, модуле).
7. Соединитель		Символ отображает выход в часть схемы и вход из другой части этой схемы и используется для обрыва линии и продолжения ее в другом месте.
8. Терминатор		Символ отображает выход во внешнюю среду и вход из внешней среды (начало или конец схемы программы, внешнее использование и источник или пункт назначения данных).
9. Ручной ввод		Символ отображает данные, вводимые вручную во время обработки с устройств любого типа (клавиатура, переключатели, кнопки, световое перо, полоски со штриховым кодом).
10. Дисплей		Символ отображает данные, пред-ставленные в человекочитаемой форме на носителе в виде отображающего устройства (экран для визуального наблюдения, индикаторы ввода информации).
11. Подготовка		Символ отображает модификацию команды или группы команд с целью воздействия на некоторую последую-щую функцию (установка переключа-теля, модификация индексного регистра или инициализация программы).
12. Линия		Символ отображает поток данных или управления. При необходимости или для повышения удобочитаемости могут быть добавлены стрелки-указатели.
13. Канал связи		Символ отображает передачу данных по каналу связи.
14. Пунктирная линия		Символ отображает альтернативную связь между двумя или более сим-волами. Кроме того, символ исполь-зуют для обведения аннотированного участка.
15. Комментарий		Символ используют для добавления описательных комментариев поясни-тельных записей в целях объяснения или примечаний. Пунктирные линии в символе комментария связаны с соответствующим символом или могут обводить группу символов. Текст комментариев или примечаний должен быть помещен около ограничивающей фигуры.