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

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

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

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

Формальное определение алгоритма

Концепции алгоритмов в математических терминах были впервые описаны в 1930 - 1940 гг, когда велись поиски условий, с помощью которых возможно доказательство проблемы разрешимости задач или, в общем случае, автоматическое доказательство математических теорем. Существуют три основных типа алгоритмических моделей. В первом понятие алгоритм связывается с вычислимыми числовыми функциями.

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

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

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

Свойства алгоритма

Всякий алгоритм любому входному слову ставит в соответствие только одно выходное слово. Это одно из основных свойств алгоритма – формальность. Иначе это свойство называют детерминированностью или однозначностью.

К числу других свойств алгоритма относятся массовость и результативность.

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

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

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