Что такое алгоритм?

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

$\mathcal{A}$

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

$y= \mathcal{A(x)$

из некоторого множества Y. В этом случае говорят, что алгоритм

$\mathcal{A}$

вычисляет функцию

$F(x)= \mathcal{A}(x)$

типа X

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

Начиная с тридцатых годов ХХ века, был предпринят ряд исследований для формализации понятия алгоритма. Перечислим некоторые из предложенных разными авторами в разное время формальных моделей: машины Тьюринга-Поста, частично-рекурсивные функции (Гедель, Клини), ?-исчисление (Черч, Клини), итеративные автоматы Неймана, нормальные алгорифмы Маркова, счетчиковые автоматы Минского, автоматы на графах Колмогорова-Барздиня и др. Заложенные в них идеи в значительной степени повлияли затем на архитектуру и языки программирования реальных компьютеров (например, на базе ?-исчисления построен широко применяемый в задачах искусственного интеллекта язык ЛИСП, а из нормальных алгорифмов Маркова произошел хорошо подходящий для текстовой обработки язык РЕФАЛ). Каждый из многочисленных языков программирования также задает некоторую формальную модель алгоритмов. Мы вначале рассмотрим один из простейших таких языков - простые структурированные программы.

Содержание Вперед