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

С алгоритмами или эффективными процедурами, однозначно приводящими к результату, уже приходилось сталкиваться в других математических дисциплинах. Методы умножения чисел и многочленов, метод исключения неизвестных при решении систем линейных уравнений, метод проверки функциональной полноты систем булевых функций - все это алгоритмы. До последнего времени термин “алгоритм” встречался в математике лишь в связи с построением конкретных алгоритмов, когда утверждение о существовании алгоритма для задач определенного типа сопровождалось его описанием. При таких обстоятельствах достаточно интуитивного представления об алгоритме и вопрос о точном его определении не возникает. Однако в ходе развития математики накапливались факты, которые коренным образом изменили ситуацию. Приведем один пример. Пусть p(x₁,…,x_n) - многочлен от переменных x₁,…,x_n с целыми коэффициентами. Тогда уравнение p(x₁,…,x_n)=0, для которого ищутся только целые решения, называется диофантовым. Знаменитая десятая проблема Гильберта, сформулированная им в 1900 году, состоит в том, чтобы установить, существует ли эффективная процедура, с помощью которой можно определить, имеет ли решение любое наперед заданное диофантово уравнение.

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

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