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

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.