3. Элементы теории алгоритмов

Понятие «алгоритм» принадлежит к числу основных понятий математики.

Еще в IX веке узбекский ученый Мухаммед бен–муса аль–Хорезми разработал систему правил четырех арифметических действий над числами в десятичной позиционной системе счисления. Эти правила предписывали строгую последовательность действий над исходными данными – числами для получения искомого результата – числа. Эти правила получили название «алгоритм» в честь арабского имени аль-Хорезми.

В ХХ веке в связи с развитием вычислительных машин и техники управления понятие алгоритма расширило свои границы. Так, исходными данными и результатами работы алгоритма стали различные конструктивные объекты математики: числа и многочлены, кортежи и матрицы, графы и автоматы, слова и тексты. Эти конструктивные объекты формируются по правилам соответствующих грамматик из элементарных объектов.

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

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

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

В процессе развития теории были сформулированы основные свойства алгоритма:

1) свойство дискретности: алгоритм состоит из отдельных элементарных действий, выполняемых по шагам; множество элементарных шагов, из которых состоит алгоритмический процесс, конечно и счетно.

2) свойство детерминированности: после каждого шага дается точное указание, как и в какой последовательности выполнять следующие шаги алгоритмического процесса.

3) свойство массовости: алгоритм должен быть пригоден для решения всех задач из заданного класса.

4) свойство сходимости или результативности: обязательна остановка алгоритмического процесса после конечного числа шагов с указанием достигнутого конструктивного объекта в виде искомого результата.

Для доказательства свойств алгоритмов формируется конечный набор элементарных объектов и элементарных шагов для построения новых объектов и организации всего алгоритмического процесса. Эти наборы составляют основу алгоритмической модели. Для различных наборов элементарных действий могут быть сформированы различные алгоритмические модели. Однако выделяют два основных типа универсальных алгоритмических моделей.

С развитием науки и практики появились задачи, для которых не были найдены методы их решения. Возник вопрос: отсутствие алгоритма решения для данного класса задач есть результат недостаточного знания о задачах этого класса либо решающий алгоритма для данного класса не существует вообще?

Для решения этой проблемы было введено понятие вычислимой функции.

Пусть имеется некоторый алгоритм α. Областью применимости алгоритма α называют совокупность тех объектов, к которым он применим.

Говорят, что алгоритм α вычисляет функцию ƒ, если его область применимости совпадает с областью определения функции ƒ, и алгоритм α перерабатывает всякий элемент х из своей области применимости в ƒ(х).

Функция ƒ(х) называется вычислимой, если существует вычисляющий ее алгоритм.

Данное определение функции также не является строгим. Американскими математиками Клини, а впоследствии Чёрчем были строго определены математические функции, названные примитивно-рекурсивными. Чёрч высказал гипотезу о том, что множество всех рекурсивных функций совпадает с множеством всех вычислимых функций. Это предположение получило название тезиса Чёрча. Гипотеза Чёрча не может быть доказана, поскольку использует нестрогое понятие вычислимой функции.

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

Доказано, что для всякой рекурсивной функции может быть построена машина Тьюринга и, обратно, всякая машина Тьюринга вычисляет рекурсивную функцию.

Известны также другие способы уточнения понятия алгоритма, например нормальный алгоритм Маркова.

Практический опыт показывает, что тезисы Чёрча и Тьюринга являются верными, не имеется ни одного опровержения этих утверждений.