Основные понятия теории алгоритмов

Во всех сферах своей деятельности, и частности в сфере обработки информации, человек сталкивается с различными способами, или методиками, решения задач. Они определяют порядок выполнения действий для получения желаемого результата – это можно трактовать как первоначальное или интуитивное определение алгоритма. Некоторые дополнительные требования приводят к неформальному определению алгоритма:

1. Алгоритм - это заданное на некотором языке конечное предписание, задающее конечную последовательность выполнимых элементарных операций для решения задачи, общее для класса возможных исходных данных.

2. Алгоритм – это всякая система вычислений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.

3. Алгоритм – это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.

Отметим, что различные определения алгоритма, в явной или неявной форме, постулируют следующий ряд требований:

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

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

· алгоритм должен быть единым для всех допустимых исходных данных, т.е. удовлетворять требованию универсальности;

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

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

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

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

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

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

1) рекурсивные функции — связывает понятие алгоритма с элементарными вычислительными операциями на множестве целых положительных чисел;

2) машина Тьюринга — связывает понятие алгоритма с механическим устройством, способным выполнять строго фиксированное множество элементарных действий над простейшими символами;

3) нормальный алгоритм Маркова — связывает понятие алгоритма с элементарными преобразованиями слов произвольного алфавита, замещая части или всего слова другим словом.

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

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