Понятие алгоритма. Лекция 10. 21. Алгоритм, его свойства

Лекция 10. 21. Алгоритм, его свойства. Способы записи алгоритма.

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

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

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

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

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

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

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

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

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

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