АЛГЕБРА АЛГОРИТМОВ
— система, состоящая из двух алгебр

и

называемых соответственно алгеброй операторов и алгеброй условий. Элементы алгебры

— это частичные преобразования (операторы) некоторого абстрактного мн-ва В, а элементы алгебры

частичные предикаты (условия), определенные на мн-ве В. А. а. используют для описания преобразований, выполняемых дискретными преобразователями (см. Дискретных преобразователей теория). В этом случае мн-во В наз. информационным мн-вом.
Осн. операция алгебры
— это обычная операция умножения (суперпозиции) операторов.
Кроме этой операции, для каждого условия Р из S в алгебре
определяются еще две операции, называемые Р-дизъюнкцией и Р-итерацией операторов. Результатом
-дизъюнкции (Р V Q) двух операторов Р и Q является оператор R такой, что для любого состояния
если условие
истинно на состоянии
если
ложно и, наконец, оператор R считается неопределенным на состоянии b, если
не определено. Результатом Р-итерации
оператора
является оператор Q такой, что для любого
имеет место
где n — наименьшее из чисел
таких, что
истинно
для любого оператора
.
На мн-ве
условий определены обычные булевые операции
которые распространяются и на случай, когда значения условий на некоторых элементах мн-ва В не определены. Напр., дизъюнкция
двух условий есть новое условие у. Это условие принимает значение «1» на тех элементах мн-ва В, на которых одно из условий а или
принимает значение «1». Значение
оно принимает на тех элементах, на которых
равны
и не определено, если одно из условий а и
не определено, а другое равно
Кроме этих операций, определяется операция
умножения оператора на условие. Результатом выполнения этой операции является условие Р, значение которого равно значению условия а после выполнения оператора
.
Если в А. а.
зафиксировать систему образующих (элементарные операторы и элементарные условия), то элементы алгебры операторов и алгебры условий можно задавать в виде выражений, составленных из этих образующих и операций системы алгебр. Такие выражения наз. регулярными операторными и условными выражениями, а операторы и условия, действующие на мн-ве В, которые можно задать таким образом, наз. регулярными операторами и условиями. В приложениях теории дискретных преобразователей к проектированию вычисл. машин А. а. наз. также микропрограммными алгебрами, а регулярные операторные выражения — регулярными микропрограммами.
С каждой интерпретацией входных и выходных сигналов дискретного преобразователя на информационном мн-ве В связывают А. а.
, выбирая в качестве элементарных операторов операторы
соответствующие символам выходного алфавита, а в качестве элементарных условий — условия вида
, где
функция выходов автомата операционного
символ входного алфавита.
Осн. соотношение между дискретными преобразователями и А. а. устанавливает следующая теорема о регуляризации: всякий оператор, представленный дискретным преобразователем, может быть задан в виде операторного регулярного выражения в А. а., соответствующей интерпретации входных и выходных сигналов этого дискретного преобразователя. На этой теореме основаны применения А. а. к решению практических задач проектирования дискретных устройств и задач программирования. Изучение структуры и соотношений конкретных А. а. дает возможность выполнять глубокие эквивалентные преобразования алгоритмов, представленных в виде регулярных выражений, отыскивая такие представления, которые позволяют получить оптимальную с точки зрения того или иного критерия реализацию алгоритма в виде дискретного преобразователя.
Лит. Глушков В. М. Теория автоматов и формальные преобразования микропрограмм. «Кибернетика», 1965, № 5. А, А. Летичевспий.