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

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

Происхождение термина «алгоритм». Слово произошло от имени среднеазиатского ученого Аль-Хорезми (8–9 вв., Хорезм – историческая область на территории современного Узбекистана). В 1857 в библиотеке Кембриджского университета был найден перевод на латинский язык математической работы Аль-Хорезми, в котором имя Аль-Хорезми упо- минается как Алгоритми, откуда и появилось слово «алгоритм». Оно стало особенно употребительным с появлением компьютеров для обо- значения совокупности действий, составляющих какой-либо вычисли- тельный процесс.

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

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

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

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

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

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

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

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

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

Скачано с www.znanio.ru