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

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

Казиев В.М.

Рассмотрим пару алгебр (A,B): алгебру X=<X,,_>>(+),_>>{},{}_>>> событий - алгоритмических процедур (программ) заданную над алфавитом X={x_>1>,x_>2>,...,x_>n>} и В-трехзначную алгебру логики (0,1,2 - неопределенность). В алгебре А определим двухместные операции конъюнкции и условной дизъюнкции и одноместную операцию итерации следующим образом: конъюнкция s_>1>s_>2> событий s_>1>, s_>2> состоит из всех слов вида pq, p s_>1>, q s_>2>;  - дизъюнкция _>>(s_>1>+s_>2>) совпадает с s_>1>(s_>2>), если условие  истинно (ложно); итерация с постусловием {s}_>> состоит из пустого события s_>0>=e и всевозможных слов вида p_>1>p_>2>...p_>k> т.е. , {s}_>>=s^m, где s^m - последний из степеней s, для которого условие  выполнено; итерация с предусловием _>>{s} определяется аналогично. В алгебре А задается событие называемое неопределенным и обозначаемое символом . Элементарные события в А - события е, x_>1>, x_>2>,..., x_>n>. Аксиомы алгебры А ниже рассмотрены. Все аксиомы алгебры B и правила вывода в ней сохраняются. Правила вывода, используемые в алгебре А включают правила вывода, принятые в программировании - см., например, [1]. Событие, получаемое применением конечного числа операций алгебры А над элементарными, называется регулярным.

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

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

Шаг 1. Задается произвольное событие s=s_>0 >s_>1> s_>2>...s_>n+1>, где s_>i> - событие номер i, начальное событие - s_>0>, конечное - 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, (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}_>>={B_>A>_>>}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. Регуляризуем микропрограмму А деления с фиксированной запятой. Для простоты считаем, что числа неотрицательны, а операция не приводит к переполнению разрядной сетки компьютера фон - Неймановского типа, операционный автомат которого состоит из регистров R_>1>, R_>2> сумматора R_>3> и счетчика сдвигов R_>4>. Делимое храниться на R_>1>, делитель - на R_>2>, частное накапливается на R_>3>. Введем обозначения: l_>i> - микрооперация сдвига регистра R_>i> влево (i=1,2,3); s^-1_>ij> - микрокоманда вычитания из содержимого регистра R_>j> содержимого регистра R_>i>; _>i> - условие заполненности регистра R_>i>; _>i> - условие отрицательности содержимого регистра R_>i>; p_>i> - микрооперация занесения единицы в младший разряд R_>i>; s_>i,j>- микрокоманда добавления содержимого регистра R_>i> к содержимому R_>j>.

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

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

x=x_>3>+x_>7>+x_>10 >,

B=el_>3>s^-1_>13>,

A=_>3>p_>2>l_>2>p_>4>l_>3>s^-1_>13>+_>3>l_>2>p_>4>l_>3>s^-1_>13>

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

s=x_>11>l_>3>s^-1_>13>{_>>_>3>(l_>2>p_>4>l_>3>s_>13>+p_>2> l_>2>p_>4>l_>3>s_>13>^-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{S²}_>>(+S ),=+S,

г)A=A{S²}_>>A=A_>>(e+S²), =_>>(+S), =+S.

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

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

Отметим метризуемость пространства и по некоторым характеристикам качества программ Холстеда [6], а также с помощью понятия интеллектуальной работы программы, оцениваемой как разность энтропии до работы (статической формы программы) и после работы (динамической формы). У идеальной программы энтропия равна нулю. Отметим, что если ds/dt - общее изменение энтропии программного комплекса при отладке, ds_>1>/dt - изменение энтропии за счет необратимых изменений структуры, потоков внутри комплекса (рассматриваемую как открытую систему), ds_>2>/dt - изменение энтропии за счет усилий по отладке и тестированию, то справедливо уравнение Пригожина: ds/dt = ds_>1>/dt + ds_>2>/dt. Последовательность программ {x_>i>}, сходится по схеме (структуре) к программе х (обозначим ), если (x_>n>,x) 0, при n, т.е. дерево программы x_>n> при n стремится к дереву программы х. Последовательность {x_>i>} сходится функционально к программе х (обозначим ), если F(x_>n>) F(x) при n (программная функция x_>n> стремится к программной функции х). Нетрудно видеть, что из сходимости по схеме следует сходимость функциональная, но обратное неверно.

Пусть M = {x_>1>, x_>2>, ..., x_>n>,...} - последовательность программ с общей функцией (эквивалентных функционально). На этом множестве рассмотрим множество операторов А преобразования (композиции, суперпозиции) программ. Последовательность {A_>n>} сходится к А функционально (по схеме, структуре), если верно: xМ:

С точки зрения исследования существования, единственности оптимальной (в каком-то смысле) программы можно рассмотреть: операторы минимизации числа операндов; операторы минимизации числа типов операторов; операторы минимизации числа вызовов процедур; минимизации числа ошибок в программе; минимизации сложности (разных способов определения) и др. При исследовании программных систем важно рассматривать пространства векторов х=(х_>1>,x_>2>,...,x_>n>), где x_>i> - характеристика ошибок в программе или структурной связностипроцедур, u_>i> - количество ошибок в i-ом модуле программного комплекса P(u)=P(u_>1>,u_>2>,...,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+u_>max>=0, u(t_>0>)=u_>0> можно заключить, что уровень ошибок убывает при (c-t_>0>)  -1 (t_>0><c<T) по закону: u(t) = u_>0>(1+ (c-t))/(1+(c-t_>0>)).

Если задать дополнительно u(t_>*>)=u_>*>, (u_>max> - неизвестная величина), то закон изменения уровня ошибок находится однозначно, так как: с=(u_>*>t_>0>-u_>0>t_>*>)/(u_>*>-u_>0>)-1/.

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

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

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

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

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

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

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

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

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