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

ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ

Абстрактный алфавит; алфавитный оператор; массовость: результативность:

алгоритмы случайный, самоизменяющийся, детерминированный, недетерминированный, расплывчатый, полиномиальный, экспоненциальный, операторный, Ван-Хао, нормальные Маркова; рекурсия; машина Тьюринга; временная сложность алгоритма: NP-, NPC-проблемы: схемы логические, структурные; граф-схемы; словесный способ представления; расплывчатое множество

Понятие алгоритма является одним из основополагающих понятий современной науки и техники. Термин «алгоритм» происходит от имени узбекского математика Аль-Хорезми, который в IX веке дал набор правил выполнения четырех арифметических действий в десятичной системе счисления.

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

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

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

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

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

А = {схема, БИС, 0, 1, 2, а. В, шкаф, кабель}, В ={-,/, х}, С= {+, -, 0, ЭВА, ЭВМ} и т.д.

Соответственно под словом в алфавите понимают любую конечную упорядоченную последовательность символов. Например, выражение «+, БИС, ЭВА» является словом в АА. Число символов в слове называется длиной этого слова. Пустое слово обозначается так же, как и пустое множество 0.

Алфавитным оператором (АО) называется функция, которая задает соответствие между словами входного и выходного алфавитов.

Например, пусть в АА заданы слова Χ и Υ и соответствия между этими словами (рис. 1.1):

Х={а, Ь, БИС, СБИС, РЭА}, У={с, стойка, кристалл, ТЭЗ, панель, шкаф, /}.

Если χ—слово в АА X, а у—- слово в АА У, то алфавитный оператор Δχ=_>' перерабатывает входное слово χ в выходное слово у. Например, слово (а, РЭА) АА Χ перерабатывается в выходные слова АА У, т. е. (с, /) (шкаф), (стойка, панель).

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