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

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

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

Усовершенствование вычислительных машин даёт возможность реализовать на них всё более сложные алгоритмы. Однако встретившийся в описывающей понятие алгоритм формулировке термин «вычислительный процесс» не следует понимать в узком смысле только цифровых вычислений. Можно пойти дальше и рассматривать вычисления с произвольными символами и их комбинациями; именно таким широким пониманием пользуются при описании понятия алгоритма. Так, можно говорить об алгоритме перевода с одного языка на другой, об алгоритме работы поездного диспетчера (перерабатывающего информацию о движении поездов в приказы) и других примерах алгоритмического описания процессов управления; именно поэтому понятие алгоритма является одним из центральных понятий кибернетики.

Термин “алгоритм” обязан своим происхождением великому ученому средневекового Востока - Муххамад ибн Муса ал-Хорезми (Магомет, сын Моисея, из Хорезма). Он жил приблизительно с 783 по 850 гг., и в 1983 году отмечалось 1200-летие со дня его рождения в городе Ургенче – областном центре современной Хорезмской области Узбекистана. В латинских переводах с арабского арифметического трактата ал-Хорезми его имя транскрибировалось как algorismi. Откуда и пошло слово “алгоритм” – сначала для обозначения алгоритмов цифровых вычислений десятичной позиционной арифметики, а затем для обозначения произвольных процессов, в которых искомые величины решаемых задач находятся последовательно из исходных данных по определенным правилам и инструкциям.

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

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

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

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

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

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

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

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

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

- детерминированность (точность указаний, исключающая их произвольное толкование),

- дискретность (возможность расчленения вычислительного процесса на отдельные элементарные операции, возможность выполнения которых не вызывает сомнений),

- массовость (пригодность алгоритма для решения всех задач заданного класса),

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

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

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

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

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