Алгоритм
АЛГОРИТМ (от algorithmi - латинское написания арабского имени аль-Хорезми), инструкция, точное описание способа действия с использованием простых, общепонятных элементов (например, операций). В математике понятие алгоритма сужается и уточняется следующим образом. Действие состоит в последовательности переходов от одного состояния вычисления (процесса работы алгоритма) к другому; состояния - это конструктивные объекты (например, слова в данном алфавите; в частности, целые числа в десятичной или двоичной записи). Алгоритм также является конструктивным объектом. Первое состояние называется исходным данным, последнее - результатом работы алгоритма. Фиксированный алгоритм можно применять к различным исходным данным; для некоторых он может не заканчивать работу. Тем самым алгоритм задаёт (возможно, не всюду определённую) функцию, вычисляемую этим алгоритмом. Такие функции называются вычислимыми. Понятия алгоритма и вычислимой функции относятся к исходным понятиям математики и через другие понятия не выражаются. Рассматриваются расширения понятия алгоритма, например, вероятностные алгоритмы, так называемый алгоритм с оракулом, алгоритм взаимодействия с окружающей средой, параллельные алгоритмы. Часто алгоритм определяется с помощью абстрактной вычислительной машины, получающей на вход программу действия и исходное данное.
Реклама
До конца 19 века алгоритм - общее понятие, относящееся к известным алгоритмам таким, как алгоритм выполнения арифметических операций в десятичной системе счисления, алгоритм дифференцирования функций, алгоритм Евклида нахождения общей меры отрезков или наибольшего общего делителя многочленов. В 1900-10-х годах были осознаны трудности в построении общего алгоритма решения некоторых массовых проблем. В 1930-е годы предложены математические определения понятия вычислимой функции, исходящие из представлений о том, что может делать человек-вычислитель; среди них - понятие рекурсивной функции и понятие функции, вычислимой машиной Тьюринга. Тогда же была доказана эквивалентность различных понятий вычислимой функции и классов вычислимых функций, порождаемых этими понятиями; сформулирован так называемый тезис Чёрча, принятый в качестве естественного научного факта: класс вычислимых функций совпадает с любым из упомянутых выше классов. Развитие компьютерных технологий не изменило представлений о классе функций, вычисляемых алгоритмов.
Построение и анализ конкретных алгоритмов, предназначенных для выполнения компьютером, относится к программированию. Выделяются также классы алгоритмов вычислительных и алгоритмов обучающихся.
Смотри также статьи Алгоритмическая проблема, Алгоритма сложность, Алгоритмов теория.
А. Л. Семёнов.