Исследование некоторых задач в алгебрах и пространствах программ
Информация - Компьютеры, программирование
Другие материалы по предмету Компьютеры, программирование
Исследование некоторых задач в алгебрах и пространствах программ
Казиев В.М.
Рассмотрим пару алгебр (A,B): алгебру X= событий - алгоритмических процедур (программ) заданную над алфавитом X={x1,x2,...,xn} и В-трехзначную алгебру логики (0,1,2 - неопределенность). В алгебре А определим двухместные операции конъюнкции и условной дизъюнкции и одноместную операцию итерации следующим образом: конъюнкция s1s2 событий s1, s2 состоит из всех слов вида pq, p s1, q s2; - дизъюнкция (s1+s2) совпадает с s1(s2), если условие истинно (ложно); итерация с постусловием {s} состоит из пустого события s0=e и всевозможных слов вида p1p2...pk т.е. , {s}=sm, где sm - последний из степеней s, для которого условие выполнено; итерация с предусловием {s} определяется аналогично. В алгебре А задается событие называемое неопределенным и обозначаемое символом . Элементарные события в А - события е, x1, x2,..., xn. Аксиомы алгебры А ниже рассмотрены. Все аксиомы алгебры B и правила вывода в ней сохраняются. Правила вывода, используемые в алгебре А включают правила вывода, принятые в программировании - см., например, [1]. Событие, получаемое применением конечного числа операций алгебры А над элементарными, называется регулярным.
Имеет место важная теорема Клини [2]: регулярные события и только они представимы в конечных автоматах.
Рассмотрим задачу построения алгоритма регуляризации во введенной паре алгебр (А,B). Алгоритм в укрупненных шагах состоит в следующем.
Шаг 1. Задается произвольное событие s=s0 s1 s2...sn+1, где si - событие номер i, начальное событие - s0, конечное - sn+1, остальные события - преобразователи и/или события - распознаватели.
Шаг 2. Составляется система уравнений алгебры событий А: записывается функция F события, его дерево D и дерево состояний определяющее все к путей выполнения : , где Fi - функция ветви дерева состояний. Функция ветви дерева - композиция всех функций (событий) данной ветви; программная функция F - объединение всех функций ветвей дерева.
Шаг 3. Система уравнений с помощью подстановок и операций дизъюнкции и конъюнкции представляется в виде : X=XA+B, где X - событие, представленное заключительным состоянием sn+1, .
Шаг 4. Находим решение системы. Используется теорема [3]: если характеристический граф матрицы А (орграф соединяющий ребрами вершины i и j только тогда, когда eaij) не содержит ни одного цикла, то система X=XA+B имеет единственное решение X=B{A}, которое регулярно при регулярных A, B. При решении системы эффективно преобразовывать уравнения, - как и при решении линейных алгебраических уравнений, например, брать дизъюнкцию событий, изменять порядок исключения событий и др.
Шаг 5. По условиям выполнимости событий находим регулярную форму этого решения. Используются аксиомы алгебры логики В и соотношения алгебры событий А, например, следующие (AB=AB, (A) - условие выполнимости события А, A - проверка условия после события А и для этого условия верны все аксиомы алгебры В, - отрицание условия ):
Ae=eA=A,
e=(e)=,
A=A=,
2(A+B)=,
((A))=,
A(BC)=(AB)C,
(A+B)=((A)+ (B)),
((A+B))=((A))+( (B)),
(A+B)C=(AC+BC),
A(B+C)=(AB+AC),
(AB)=(A)B(B),
(AB)=A(B),
A{B}={BA}A,
({A})={A},
{A}=(e+A{A}),
{(A)}(B)={A}B,
{A}{A}={A},
{ {A}}={A},
{A}{A}={A},
{{A}}={A} ,
{(A)}={A} ,
{A}+e={A},
A{A}={A}A={A} .
Пример 1. Регуляризуем микропрограмму А деления с фиксированной запятой. Для простоты считаем, что числа неотрицательны, а операция не приводит к переполнению разрядной сетки компьютера фон - Неймановского типа, операционный автомат которого состоит из регистров R1, R2 сумматора R3 и счетчика сдвигов R4. Делимое храниться на R1, делитель - на R2, частное накапливается на R3. Введем обозначения: li - микрооперация сдвига регистра Ri влево (i=1,2,3); s-1ij - микрокоманда вычитания из содержимого регистра Rj содержимого регистра Ri; i - условие заполненности регистра Ri; i - условие отрицательности содержимого регистра Ri; pi - микрооперация занесения единицы в младший разряд Ri; si,j- микрокоманда добавления содержимого регистра Ri к содержимому Rj.
Выпишем систему уравнений, обозначив через xi - событие соответствующее каждому из 11 пунктов алгоритма деления (см., например, [3]):
Решим эту систему. После очевидных подстановок, вводя обозначения:
x=x3+x7+x10 ,
B=el3s-113,
A=3p2l2p4l3s-113+3l2p4l3s-113
получим уравнение X=XA+B, решение которого будет X=B{A} и после упрощений с помощью приведенных аксиом, заключительное событие S равно
s=x11l3s-113{3(l2p4l3s13+p2 l2p4l3s13-1)}4
2. Рассмотрим задачу нахождения оптимальных (например, в смысле операции, длины и т.д.) структурированных программ из заданного набора базовых процедур (некоторые из них - см. в [5]), а также построения грамматик для анализа структур из программных единиц. При решении этой задачи используются аксиомы алгебры А.
Пример 2. Дана программа Р, где А,В,С - процедуры, - предикаты:
P=(BA+CA)(A{A}+e)=(B+С)A(A{A}+e)=(B+С)A({A}+e)=(B+С)A{A}=(B+C){A}=T.
Программа Т - более оптимальна и ее правильность доказываема формально.
Доказана теорема (доказательство не приводим из-за объема).
Теорема 1. Если R,A,S A, ,,B, A и S - коммутативны, то:
а)AX=A(R+SX)AX=A{S}R, б)A=A(+S)A=A{S},
в)A=A(+S )A=A{S2}(+S ),=+S,
г)A=A{S2}A=A(e+S2), =(+S), =+S.
Рассмотрим задачу исследования разрешимости в пространствах программ.
Пусть x= - программа, определенная на входном алфавите Х, выходном алфавите Y и состоящая из подпрограмм (процедур) М с логической схемой (структурой) S. Структуре S поставим в соответствие орграф: Вершины - подпрограммы, ребра - в соответствии со структурой их взаимодействий. Метрика (x,y) в этом пространстве - сумма всех весов ребер орграфов программ не совпадающих при заданной