АЛГЕБРА АЛГОРИТМОВ

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

Осн. операция алгебры — это обычная операция умножения (суперпозиции) операторов.

Кроме этой операции, для каждого условия Р из S в алгебре определяются еще две операции, называемые Р-дизъюнкцией и Р-итерацией операторов. Результатом -дизъюнкции (Р V Q) двух операторов Р и Q является оператор R такой, что для любого состояния если условие истинно на состоянии если ложно и, наконец, оператор R считается неопределенным на состоянии b, если не определено. Результатом Р-итерации оператора является оператор Q такой, что для любого имеет место где n — наименьшее из чисел таких, что истинно для любого оператора .

На мн-ве условий определены обычные булевые операции которые распространяются и на случай, когда значения условий на некоторых элементах мн-ва В не определены. Напр., дизъюнкция двух условий есть новое условие у. Это условие принимает значение «1» на тех элементах мн-ва В, на которых одно из условий а или принимает значение «1». Значение оно принимает на тех элементах, на которых равны и не определено, если одно из условий а и не определено, а другое равно Кроме этих операций, определяется операция умножения оператора на условие. Результатом выполнения этой операции является условие Р, значение которого равно значению условия а после выполнения оператора .

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

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

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

Лит. Глушков В. М. Теория автоматов и формальные преобразования микропрограмм. «Кибернетика», 1965, № 5. А, А. Летичевспий.