Глава 5. Основы теории алгоритмов

Понятие "алгоритм" принадлежит к числу основных понятий математики и занимает одно из центральных мест в вычислительной математике и проектировании разнообразных дискретных устройств.

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

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

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

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

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

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

• Свойство массовости: использование алгоритма допустимо для множества алгоритмических объектов заданного типа и заданного класса задач.

• Свойство результативности: обязательна остановка алгоритмического процесса после конечного числа шагов с указанием искомого результата.

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

Выделяют три основных типа алгоритмических моделей.

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

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

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

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

Рассмотрим подробнее реализацию алгоритмических процессов для вычисления значений числовых функций на трех типах моделей алгоритмов.