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

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

Казиев В.М.

Рассмотрим пару алгебр (A, B): алгебру X= событий — алгоритмических процедур (программ) заданную над алфавитом X={x1,x2,…, xn} и В-трехзначную алгебру логики (0,1,2 — неопределенность). В алгебре, А определим двухместные операции конъюнкции и условной дизъюнкции и одноместную операцию итерации следующим образом: конъюнкция s1&s2 событий s1, s2 состоит из всех слов вида pq, pÎ s1, qÎ s2; a — дизъюнкция a (s1+s2) совпадает с s1(s2), если условие a истинно (ложно); итерация с постусловием {s}a состоит из пустого события s0=e и всевозможных слов вида p1p2… pk т. е. , {s}a=sm, где sm — последний из степеней s, для которого условие a выполнено; итерация с предусловием a{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 только тогда, когда eÎaij) не содержит ни одного цикла, то система 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=Æ,.

2(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),.

Aa (B+C)=a (AB+AC),.

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

(AB)a=A (Ba),.

A{B}a={BAa}A,.

a ({A}b)={Ab}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},.

Aa{A}=a{A}A={A}a .

Пример 1. Регуляризуем микропрограмму, А деления с фиксированной запятой. Для простоты считаем, что числа неотрицательны, а операция не приводит к переполнению разрядной сетки компьютера фон — Неймановского типа, операционный автомат которого состоит из регистров R1, R2 сумматора R3 и счетчика сдвигов R4. Делимое храниться на R1, делитель — на R2, частное накапливается на R3. Введем обозначения: li — микрооперация сдвига регистра Ri влево (i=1,2,3); s-1ij — микрокоманда вычитания из содержимого регистра Rj содержимого регистра Ri; ai — условие заполненности регистра Ri; gi — условие отрицательности содержимого регистра Ri; pi — микрооперация занесения единицы в младший разряд Ri; si, jмикрокоманда добавления содержимого регистра Ri к содержимому Rj.

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

.

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

x=x3+x7+x10 ,.

B=el3s-113,.

A=g3p2l2p4l3s-113+g3l2p4l3s-113.

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

s=x11l3s-113{g3(l2p4l3s13+p2 l2p4l3s13−1)}a4.

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

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

P=a (BA+CA)b (Ab{A}+e)=a (B+С)Ab (Ab{A}+e)=a (B+С)Ab ({A}b+e)=a (B+С)Ab{A}=a (B+C){A}b=T.

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

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

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

а)AX=Aa (R+SX)ÛAX=A{S}aR, б) Ag=Aa (b+Sg)ÛAg=A{S}ab,.

в)Ag=Aa (b+S )ÞAg=A{S2}ta (b+S ), t=a+Sa,.

г)Ag=A{S2}tgÞAg=At (e+S2)g, g=a (b+S), t=a+Sa.

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

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

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

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

С точки зрения исследования существования, единственности оптимальной (в каком-то смысле) программы можно рассмотреть: операторы минимизации числа операндов; операторы минимизации числа типов операторов; операторы минимизации числа вызовов процедур; минимизации числа ошибок в программе; минимизации сложности (разных способов определения) и др. При исследовании программных систем важно рассматривать пространства векторов х=(х1,x2,…, xn), где xi — характеристика ошибок в программе или структурной связностипроцедур, ui — количество ошибок в i-ом модуле программного комплекса P (u)=P (u1,u2,…, un).

Пусть 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. Пусть umax — максимальный уровень синтаксических ошибок в программе Р, u (t) — их оставшееся количество к моменту времени t. Исходя из модели du/dt+lumax=0, u (t0)=u0 можно заключить, что уровень ошибок убывает при l (c-t0) ¹ -1 (t0.