Алгоритмика программ - часть 3
Операция фильтрации Ф (u ) = ((u ) Е, N} в АД представлена суперпозицией тождественного Е и неопределенного N операторов и альтернативы алгебры алгоритмики, где N – фильтр разрешения выполнения операций вычислений. Оператор цикла while do также представлен суперпозицией операций композиции и цикла в алгебре алгоритмики.
Алгебра схем Янова АЯ включает в себя операции построения неструктурных логических схем программ. Схема Янова состоит из предикатных символов множества P{p1, p2,…), операторных символов множества A{a1, a2,…} и графа переходов. Оператором в данной алгебре есть пара A{p}, состоящая из символов множества А и множества предикатных символов. Граф перехода представляет собой ориентированный граф, в вершинах которого располагаются преобразователи, распознаватели и один оператор останова. Дуги графа задаются стрелками и помечаются они знаками + и –.
Преобразователь имеет один преемник, а распознаватель – два. Каждый распознаватель включает в себя условие выполнения схемы, а преобразователь представляет операторы, включающие логические переменные, принадлежащие множеству {p1, p2,…).
Каждая созданная схема АЯ отличается большой сложностью, требует серьезного преобразования при переходе к представлению программы в виде соответствующей последовательности действий, условий перехода и безусловного перехода. В работе [86] разработана теория интерпретации схем Янова и доказательство эквивалентности двух операторных схем исходя из особенностей алгебры алгоритмики.
Для представления схемы Янова аппаратом алгебры алгоритмики сигнатура операций АЯ вводятся композиции А* В и операции условного перехода, который в зависимости от условия u выполняет переход к следующим операторам или к оператору помеченному меткой (типа goto). Условный переход трактуется как бинарная операция P (u, F), которая зависит от условия u и разметок схемы F. Кроме того, производится замена альтернативы и цикла типа while do.