Алгоритм

Алгори́тм (от лат. написания арабского имени аль-Хорезми – Algorithmi), инструкция, точное описание способа действия с использованием простых, общепонятных элементов (например, операций). В математике понятие алгоритма сужается и уточняется следующим образом. Действие состоит в последовательности переходов от одного состояния вычисления (процесса работы алгоритма) к другому; состояния – это конструктивные объекты (например, слова в данном алфавите; в частности, целые числа в десятичной или двоичной записи). Алгоритм также является конструктивным объектом (см. Конструктивная математика). Первое состояние называется исходным данным, последнее – результатом работы алгоритма. Фиксированный алгоритм можно применять к различным исходным данным; для некоторых он может не заканчивать работу. Тем самым алгоритм задаёт (возможно, не всюду определённую) функцию, вычисляемую этим алгоритмом. Такие функции называются вычислимыми. Понятия алгоритма и вычислимой функции относятся к исходным понятиям математики и через другие понятия не выражаются. Рассматриваются расширения понятия алгоритма, например вероятностные алгоритмы, т. н. алгоритмы с оракулом, алгоритмы взаимодействия с окружающей средой, параллельные алгоритмы. Часто алгоритм определяется с помощью абстрактной вычислительной машины, получающей на вход программу действия и исходное данное.

До конца 19 в. алгоритм – общее понятие, относящееся к известным алгоритмам, таким как алгоритм выполнения арифметических операций в десятичной системе счисления, алгоритм дифференцирования функций, алгоритм Евклида нахождения общей меры отрезков или наибольшего общего делителя многочленов. В 1900–1910-х гг. были осознаны трудности в построении общего алгоритма решения некоторых массовых проблем. В 1930-е гг. предложены математические определения понятия вычислимой функции, исходящие из представлений о том, что может делать человек-вычислитель; среди них – понятие рекурсивной функции и понятие функции, вычислимой машиной Тьюринга. Тогда же была доказана эквивалентность различных понятий вычислимой функции и классов вычислимых функций, порождаемых этими понятиями; сформулирован т. н. тезис Чёрча, принятый в качестве естественно-научного факта: класс вычислимых функций совпадает с любым из упомянутых выше классов. Развитие компьютерных технологий не изменило представлений о классе функций, вычисляемых алгоритмами.

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

См. также статьи Алгоритмическая проблема, Сложность алгоритма, Теория алгоритмов.