Элементы теории алгоритмов. Абстрактный алфавит, алфавитный оператор, массовость, результативность, страница 2

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

Говорят, что АО, задаваемые с помощью конечной системы правил, называются алгоритмами.

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

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

Основными свойствами алгоритмов являются массовость и результативность. Массовость алгоритма—это его свойство быть применимым для множества исходных данных. Для каждого алгоритма существует класс объектов, и все они допустимы в качестве исходных данных. Тогда под массовостью понимают допустимость всех объектов этого класса, а не некоторого их числа. Результативность алгоритма—это свойство, обеспечивающее получение результата через конечное число шагов. Считают, что алгоритм применим к допустимым исходным данным, если с его помощью на основе этих исходных данных можно получить искомый результат за конечное число шагов. Если результат получить нельзя, хотя исходные данные и допустимы, алгоритм к ним не применим. Отметим, что требование завершения алгоритмического процесса за конечное число шагов в конструкторских и технологических задачах не учитывает реальных возможностей по затрате времени, памяти, технических ресурсов и т. п. В этой связи считается, что алгоритм потенциально, а не реально выполним. Неприменимость алгоритма к допустимым исходным данным заключается в том, что алгоритмический процесс или не оканчивается, или его выполнение наталкивается на непреодолимое препятствие. Выделяют также такие свойства алгоритма, как определенность, понятность, корректность. Формулировка алгоритма должна быть точной и полностью определять все действия исполнителя. Это свойство называют определенностью алгоритма. Свойство понятности— это наличие алгоритма, определяющего процесс выполнения заданного в виде текста алгоритма.

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

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

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

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