Глава 9. ОСНОВЫ АЛГОРИТМИЗАЦИИ

Понятие алгоритма

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

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

Термин «алгоритм» произошел от имени арабского математика аль-Хорезми (IX в.), которым были описаны общие правила (названные позднее алгоритмами) выполнения основных арифметических действий в десятичной системе счисления. Эти алгоритмы изучаются в начальных разделах школьной математики. К числу алгоритмов школьного курса математики относятся также правила решения определенных видов уравнений или неравенств, правила построения различных геометрических фигур и т. п. Понятие алгоритма используется не только в математике, но и во многих областях человеческой деятельности, например, говорят об алгоритме управления производственным процессом, алгоритме управления полетом ракеты, алгоритме пользования бытовым прибором. Причем интуитивно под алгоритмом понимают некоторую систему правил, обладающих определенными свойствами.

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

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

2. Исполнитель может выполнить алгоритм, если он ему понятен, то есть записан на понятном ему языке и содержит предписания, которые исполнитель может выполнить. Набор действий, которые могут быть выполнены исполнителем, называется системой команд исполнителя. Алгоритм не должен содержать описания действий, не входящих в систему команд исполнителя, т. е. своей структурой команд и формой записи алгоритм должен быть ориентирован на конкретного исполнителя.

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

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

5. Цель выполнения алгоритма – получение конечного результата посредством выполнения указанных преобразований над исходными данными. В алгоритмах аль-Хорезми исходными данными являются два десятичных числа, результатом – также некоторое десятичное число. Причем при точном исполнении всех предписаний алгоритмический процесс должен заканчиваться за конечное число шагов. Это обязательное требование к алгоритмам – требование их результативности или конечности.

В математике известны вычислительные процедуры алгоритмического характера, не обладающие свойством конечности. Например, процедура вычисления числа p. Однако, если мы введем условие завершения вида «закончить после получения n десятичных знаков числа p», то получим алгоритм вычисления n десятичных знаков числа p. На этом принципе построены многие вычислительные алгоритмы.

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