Составление алгоритмов и их программная реализация

Виды алгоритмов и их реализация

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

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

Формальные определения алгоритма появились в 30—40-х гг. XX в. Можно выделить три основных типа универсальных алгоритмических моделей, различающихся исходными соображениями относительно того, что такое алгоритм.

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

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

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

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

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

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

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

В программировании алгоритмы подразделяются на три типа:

1. линейный — набор команд (указаний), выполняемых последовательно один за другим;
2. разветвляющийся — алгоритм, содержащий хотя бы одну проверку условия, в результате которой обеспечивается переход на один из возможных вариантов решения;
3. циклический — алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций) над новыми исходными данными. К циклическим алгоритмам сводится большинство методов вычислений и перебора вариантов.

Вспомогательный (подчиненный) алгоритм — это такой, который разработан ранее и целиком используется при алгоритмизации конкретной задачи.

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

На практике наиболее распространены следующие способы: словесный; формульно-словесный; блок-схемный; псевдокод; структурные диаграммы; языки программирования.

Словесный способ — содержание этапов вычислений задается на естественном языке в произвольной форме с требуемой детализацией.

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

Шаг 1. Выбираем первый элемент массива — к шагу 2.
Шаг 2. Сравниваем: принадлежит ли выбранный элемент массива интервалу — если «да», то к шагу 3, если «нет» — к шагу 6.
Шаг 3. Все ли элементы массива просмотрены? Если «да», то к шагу 5, если «нет» — то к шагу 4.
Шаг 4. Выбираем следующий элемент — к шагу 2.
Шаг 5. Печать сообщения: «все элементы принадлежат интервалу» — на шаг 7.
Шаг 6. Печать сообщения: «не все элементы принадлежат интервалу» — на шаг 7.
Шаг 7. Конец.

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

Формульно-словесный способ — задание инструкций с использованием математических символов и выражений в сочетании со словесными пояснениями.

Например, вычислить площадь треугольника по трем сторонам (а,b,с).

Соответствующий алгоритм может быть представлен следующим образом:
Шаг 1. Вычислить полупериметр треугольника:

Шаг 2. Вычислить

Шаг 3. Напечатать результат S и прекратить вычисления.

При использовании этого способа может быть достигнута любая степень детализации более наглядно, но не строго формализованно.

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

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

Псевдокод — представляет собой совокупность операторов языка программирования и естественного языка. Запись алгоритма в виде псевдокода имеет следующий вид.

Выбираем первый элемент (i = 1).
IF Л > или х. > В THEN печать сообщения и выход на конец
ELSE переход к следующему элементу.
IF массив не кончился THEN переход на проверку интервала
ELSE печать сообщения, что все элементы входят в интервал.
Конец.

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

Пример. Вычислить при заданном х.

Рассмотрим пример блок-схемы задачи, которая ранее представлена словесным алгоритмом (рисунок ниже).

Решение. Запись алгоритма на псевдокоде:
* Ввод (х)
* * Если х < 0, то
* * * у: = х ^. х
* * иначе
* * * у: = х + 1
* * конец проверки условия
* вывод (у)
* конец алгоритма

Структурные диаграммы могут использоваться в качестве структурных блок-схем, для показа межмодульных связей, для отображения структур данных и систем обработки данных. Существуют следующие структурные диаграммы: диаграммы Насси — Шнейдермана, Варнье, Джексона, МЭСИД и др.

Пример. Задан одномерный массив из положительных и отрицательных чисел. Требуется определить частное от деления суммы положительных элементов на сумму отрицательных элементов этого массива. Справа от диаграммы (рис. ниже) приводятся соответствующие операторы языка Turbo Pascal.