Понятие алгоритм. Понятие исполнителя алгоритма. Свойства алгоритма. Основные подхо­ды к формализации понятия алгоритма

Слово "алгоритм" произошло от имени среднеазиатского математика Мухамеда из Хорезма (по-арабски - Аль Хорезми (IX в)) и использовалось в математике для обозначения правил выполнения четырех арифметических действий: сложения, умножения, вычитания и деления.

Мухаммед Аль Хорезми подробно объясняет правила действия с числами, записанными в десятично-позиционной системе счисления, и исследует квадратные уравнения. Слова "алгебра" и "алгоритм" впервые появились в переводе его трактатов. Первое из них означало операцию переноса членов из одной части уравнения в другую, а второе – искаженное имя автора – Аль Хорезми – Algorithmi. Оно применялось первоначально для обозначения правил вычисления в десятичной позиционной системе счисления.

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

Интуитивное понятие алгоритма, которым люди пользуются уже много лет, можно выразить следующим образом:

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

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

Исполнитель алгоритма – это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнять действия, предписываемые алгоритмом.

Исполнителя характеризуют:

Среда;

Система команд;

Отказы.

Среда (обстановка) – это "место обитания" исполнителя. Например, среда ТР.

Система команд. Отдельные указания исполнителю, содержащиеся в каждом шаге алгоритма, называют командами. Исполнители отличаются друг от друга возможностями - наборами команд, которые они "понимают" и умеют выполнять. Совокупность команд, которые могут быть выполнены конкретным исполнителем, называется Системой Команд Исполнителя (СКИ).

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

Свойства алгоритма

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

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

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

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

Конечность. Выполнение алгоритма заканчивается после выполнения конечного числа шагов. При выполнении алгоритма некоторые его шаги могут выполняться многократно.

В математике существуют вычислительные процедуры, имеющие алгоритмический характер, но не обладающие свойством конечности. Например, процедура вычисления числа π. Такая процедура описывает бесконечный процесс и никогда не завершится. Если же прервать ее искусственно, например, ввести условие завершения процесса вычислений вида: "Закончить вычисления после получения п десятичных знаков числа", то получится алгоритм вычисления п десятичных знаков числа π. На этом принципе основано получение многих вычислительных алгоритмов: строится бесконечный, сходящийся к искомому решению процесс. Он обрывается на некотором шаге, и полученное значение принимается за приближенное решение рассматриваемой задачи. При этом точность приближения зависит от числа шагов.

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

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

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

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

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

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

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

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

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