Исследование некоторых задач в алгебрах и пространствах программ

КазиевВ.М.

Рассмотрим пару алгебр (A,B): алгебру X=<X,&,_a
(+),_a
{},{}_a
> событий - алгоритмических процедур (программ) заданную над алфавитом X={x₁
,x₂
,...,x_n
} и В-трехзначную алгебру логики (0,1,2 - неопределенность). В алгебре А определим двухместные операции конъюнкции и условной дизъюнкции и одноместную операцию итерации следующим образом: конъюнкция s₁
&s₂
событий s₁
, s₂
состоит из всех слов вида pq, pÎ s₁
, qÎ s₂
; a - дизъюнкция _a
(s₁
+s₂
) совпадает с s₁
(s₂
), если условие a истинно (ложно); итерация с постусловием {s}_a
состоит из пустого события s₀
=e и всевозможных слов вида p₁
p₂
...p_k
т.е. , {s}_a
=s^m
, где s^m
- последний из степеней s, для которого условие a выполнено; итерация с предусловием _a
{s} определяется аналогично. В алгебре А задается событие называемое неопределенным и обозначаемое символом Æ. Элементарные события в А - события е, x₁
, x₂
,..., x_n
. Аксиомы алгебры А ниже рассмотрены. Все аксиомы алгебры B и правила вывода в ней сохраняются. Правила вывода, используемые в алгебре А включают правила вывода, принятые в программировании - см., например, [1]. Событие, получаемое применением конечного числа операций алгебры А над элементарными, называется регулярным.

Имеет место важная теорема Клини [2]: регулярные события и только они представимы в конечных автоматах.

Рассмотрим задачу построения алгоритма регуляризации во введенной паре алгебр (А,B). Алгоритм в укрупненных шагах состоит в следующем.

Шаг 1. Задается произвольное событие s=s₀
s₁
s₂
...s_n+1
, где s_i
- событие номер i, начальное событие - s₀
, конечное - s_n+1
, остальные события - преобразователи и/или события - распознаватели.

Шаг 2. Составляется система уравнений алгебры событий А: записывается функция F события, его дерево D и дерево состояний определяющее все к путей выполнения : , где F_i
- функция ветви дерева состояний. Функция ветви дерева - композиция всех функций (событий) данной ветви; программная функция F - объединение всех функций ветвей дерева.

Шаг 3. Система уравнений с помощью подстановок и операций дизъюнкции и конъюнкции представляется в виде : X=XA+B, где X - событие, представленное заключительным состоянием s_n+1
, .

Шаг 4. Находим решение системы. Используется теорема [3]: если характеристический граф матрицы А (орграф соединяющий ребрами вершины i и j только тогда, когда eÎa_ij
) не содержит ни одного цикла, то система X=XA+B имеет единственное решение X=B{A}, которое регулярно при регулярных A, B. При решении системы эффективно преобразовывать уравнения, - как и при решении линейных алгебраических уравнений, например, брать дизъюнкцию событий, изменять порядок исключения событий и др.

Шаг 5. По условиям выполнимости событий находим регулярную форму этого решения. Используются аксиомы алгебры логики В и соотношения алгебры событий А, например, следующие (AB=A&B, ab=a&b,a(A) - условие выполнимости события А, Aa - проверка условия a после события А и для этого условия верны все аксиомы алгебры В, - отрицание условия a):

Ae=eA=A,

ea=a(e)=a,

AÆ=ÆA=Æ,

₂
(A+B)=Æ,

a(b(A))=b,

A(BC)=(AB)C,

_b
(A+B)=(a(A)+ (B)),

a(_b
(A+B))=(ba(A))+( (B)),

_a
(A+B)C=_a
(AC+BC),

A_a
(B+C)=_a
(AB+AC),

a(AB)=a(A)Ba(B),

(AB)a=A(Ba),

A{B}_a
={B_A
a
}A,

a({A}_b
)={A_b
}b,

{A}_a
=_a
(e+A{A}_a
),

{a(A)}(B)={A}
B,

_a
{A}_a
{A}=_a
{A},

{_a
a
{A}}=_a
{A},

{A}_a
{A}_a
={A}_a
,

{{A}_aa
}={A}_a
,

{a(A)}={A} ,

{A}_a
+e=_a
{A},

A_a
{A}=_a
{A}A={A}_a
.

Пример 1. Регуляризуем микропрограмму А деления с фиксированной запятой. Для простоты считаем, что числа неотрицательны, а операция не приводит к переполнению разрядной сетки компьютера фон - Неймановского типа, операционный автомат которого состоит из регистров R₁
, R₂
сумматора R₃
и счетчика сдвигов R₄
. Делимое храниться на R₁
, делитель - на R₂
, частное накапливается на R₃
. Введем обозначения: l_i
- микрооперация сдвига регистра R_i
влево (i=1,2,3); s^-1
_ij
- микрокоманда вычитания из содержимого регистра R_j
содержимого регистра R_i
; a_i
- условие заполненности регистра R_i
; g_i
- условие отрицательности содержимого регистра R_i
; p_i
- микрооперация занесения единицы в младший разряд R_i
; s_i,j
- микрокоманда добавления содержимого регистра R_i
к содержимому R_j
.

Выпишем систему уравнений, обозначив через x_i
- событие соответствующее каждому из 11 пунктов алгоритма деления (см., например, [3]):

Решим эту систему. После очевидных подстановок, вводя обозначения:

x=x₃
+x₇
+x₁₀
,

B=el₃
s^-1
₁₃
,

A=g₃
p₂
l₂
p₄
l₃
s^-1
₁₃
+g₃
l₂
p₄
l₃
s^-1
₁₃

получим уравнение X=XA+B, решение которого будет X=B{A} и после упрощений с помощью приведенных аксиом, заключительное событие S равно

s=x₁₁
l₃
s^-1
₁₃
{_g
3
(l₂
p₄
l₃
s₁₃
+p₂
l₂
p₄
l₃
s₁₃
^-1
)}_a
4

2. Рассмотрим задачу нахождения оптимальных (например, в смысле операции, длины и т.д.) структурированных программ из заданного набора базовых процедур (некоторые из них - см. в [5]), а также построения грамматик для анализа структур из программных единиц. При решении этой задачи используются аксиомы алгебры А.

Пример 2. Дана программа Р, где А,В,С - процедуры, a,b - предикаты:

P=_a
(BA+CA)_b
(A_b
{A}+e)=_a
(B+С)A_b
(A_b
{A}+e)=_a
(B+С)A_b
({A}_b
+e)=_a
(B+С)A_b
{A}=_a
(B+C){A}_b
=T.

Программа Т - более оптимальна и ее правильность доказываема формально.

Доказана теорема (доказательство не приводим из-за объема).

Теорема 1. Если R,A,S Î A, a,b,gÎB, A и S - коммутативны, то:

а)AX=A_a
(R+SX)ÛAX=A{S}_a
R, б)Ag=A_a
(b+Sg)ÛAg=A{S}_a
b,

в)Ag=A_a
(b+S )ÞAg=A{S²
}_t
a
(b+S ),t=a+Sa,

г)Ag=A{S²
}_t
gÞAg=A_t
(e+S²
)g, g=_a
(b+S), t=a+Sa.

Рассмотрим задачу исследования разрешимости в пространствах программ.

Пусть x=<X, Y, M, S> - программа, определенная на входном алфавите Х, выходном алфавите Y и состоящая из подпрограмм (процедур) М с логической схемой (структурой) S. Структуре S поставим в соответствие орграф: Вершины - подпрограммы, ребра - в соответствии со структурой их взаимодействий. Метрика r(x,y) в этом пространстве - сумма всех весов ребер орграфов программ не совпадающих при заданной структуре S или отклоняющихся от оптимальной структуры, т.е. Аксиомы метрики проверяемы.

Отметим метризуемость пространства и по некоторым характеристикам качества программ Холстеда [6], а также с помощью понятия интеллектуальной работы программы, оцениваемой как разность энтропии до работы (статической формы программы) и после работы (динамической формы). У идеальной программы энтропия равна нулю. Отметим, что если ds/dt - общее изменение энтропии программного комплекса при отладке, ds₁
/dt - изменение энтропии за счет необратимых изменений структуры, потоков внутри комплекса (рассматриваемую как открытую систему), ds₂
/dt - изменение энтропии за счет усилий по отладке и тестированию, то справедливо уравнение Пригожина: ds/dt = ds₁
/dt + ds₂
/dt. Последовательность программ {x_i
}, сходится по схеме (структуре) к программе х (обозначим ), если r(x_n
,x)® 0, при n®¥, т.е. дерево программы x_n
при n®¥ стремится к дереву программы х. Последовательность {x_i
} сходится функционально к программе х (обозначим ), если F(x_n
)® F(x) при n®¥ (программная функция x_n
стремится к программной функции х). Нетрудно видеть, что из сходимости по схеме следует сходимость функциональная, но обратное неверно.

Пусть M = {x₁
, x₂
, ..., x_n
,...} - последовательность программ с общей функцией (эквивалентных функционально). На этом множестве рассмотрим множество операторов А преобразования (композиции, суперпозиции) программ. Последовательность {A_n
} сходится к А функционально (по схеме, структуре), если верно: "xÎМ:

С точки зрения исследования существования, единственности оптимальной (в каком-то смысле) программы можно рассмотреть: операторы минимизации числа операндов; операторы минимизации числа типов операторов; операторы минимизации числа вызовов процедур; минимизации числа ошибок в программе; минимизации сложности (разных способов определения) и др. При исследовании программных систем важно рассматривать пространства векторов х=(х₁
,x₂
,...,x_n
), где x_i
- характеристика ошибок в программе или структурной связностипроцедур, u_i
- количество ошибок в i-ом модуле программного комплекса P(u)=P(u₁
,u₂
,...,u_n
).

Пусть u(x,t) - количество ошибок, обнаруженных в программе (системе) в момент времени t, а х - характеристика уровня ошибок. Рассмотрим модель обнаружения ошибок при отладке, представимая уравнением (см. также [7]): Lu+Tu=f, где T - оператор, определяющий первоначальный уровень ошибок в программе или их некоторую характеристику, L - некоторый линейный ограниченный оператор отладки, L:U®V, U,V - линейные нормированные пространства D(L) ÍU, R(L)ÍV.

Теорема 2. Если R(L)=V и для каждого uÎD(L) существует постоянная c такая, что , то Lu+Tu=f имеет единственное решение uÎU.

Доказательство. Условия теоремы гарантируют существование непрерывного обратного оператора L^-1
, причем . Тогда u=L^-1
(f-Tu). Для однородного уравнения: . Отсюда следует, что , т.е. u=0. Следовательно, неоднородное уравнение имеет единственное решение.

Пример 3. Пусть u_max
- максимальный уровень синтаксических ошибок в программе Р, u(t) - их оставшееся количество к моменту времени t. Исходя из модели du/dt+lu_max
=0, u(t₀
)=u₀
можно заключить, что уровень ошибок убывает при l(c-t₀
) ¹ -1 (t₀
<c<T) по закону: u(t) = u₀
(1+ l(c-t))/(1+l(c-t₀
)).

Если задать дополнительно u(t_*
)=u_*
, (u_max
- неизвестная величина), то закон изменения уровня ошибок находится однозначно, так как: с=(u_*
t₀
-u₀
t_*
)/(lu_*
-lu₀
)-1/l.

Вопросы разрешимости некоторых уравнений Lx=y, где х - неизвестная программа, y - заданная программа, L - оператор, например, оптимизации, будут изложены в другой работе.

Список литературы

1. Алагич С., Арбиб М. Проектирование корректных структурированных программ. - М., Радио и связь, 1984.

2. Клини С.К. Представление событий в нервных сетях и конечных автоматах. - Автоматы, ИЛ, М., 1956.

3. Бондарчук В.Г. Системы уравнений в алгебре событий. - Журнал вычислительной математики и математической физики, N6, т.3, 1963.

4. Глушков В.М. О применении абстрактной теории автоматов для минимизации микропрограмм. - Изв. АН СССР, Технич. кибернетика, N1, 1964.

5. Казиев В.М. Дидактические алгоритмические единицы. - Информатика и образование, N5, 1991.

6. Холстед М. Начала науки о программах. - М., Финансы и статистика, 1981.

7. Казиев В.М. Один класс математических моделей переработки информации и некоторые его приложения. - Нелинейные эволюционные уравнения в прикладных задачах, Киев, 1991.