Ѕаза знаний студента. –еферат, курсова€, контрольна€, диплом на заказ

курсовые,контрольные,дипломы,рефераты

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

 азиев ¬.ћ.

–ассмотрим пару алгебр (A,B): алгебру X=<X,&,a(+),a{},{}a> событий - алгоритмических процедур (программ) заданную над алфавитом 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=<X, Y, M, S> - программа, определенна€ на входном алфавите ’, выходном алфавите 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<c<T) по закону: u(t) = u0(1+ l(c-t))/(1+l(c-t0)).

≈сли задать дополнительно u(t*)=u*, (umax - неизвестна€ величина), то закон изменени€ уровн€ ошибок находитс€ однозначно, так как: с=(u*t0-u0t*)/(lu*-lu0)-1/l.

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

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

1. јлагич —., јрбиб ћ. ѕроектирование корректных структурированных программ. - ћ., –адио и св€зь, 1984.

2.  лини —. . ѕредставление событий в нервных сет€х и конечных автоматах. - јвтоматы, »Ћ, ћ., 1956.

3. Ѕондарчук ¬.√. —истемы уравнений в алгебре событий. - ∆урнал вычислительной математики и математической физики, N6, т.3, 1963.

4. √лушков ¬.ћ. ќ применении абстрактной теории автоматов дл€ минимизации микропрограмм. - »зв. јЌ ———–, “ехнич. кибернетика, N1, 1964.

5.  азиев ¬.ћ. ƒидактические алгоритмические единицы. - »нформатика и образование, N5, 1991.

6. ’олстед ћ. Ќачала науки о программах. - ћ., ‘инансы и статистика, 1981.

7.  азиев ¬.ћ. ќдин класс математических моделей переработки информации и некоторые его приложени€. - Ќелинейные эволюционные уравнени€ в прикладных задачах,  иев, 1991.

 азиев ¬.ћ. –ассмотрим пару алгебр (A,B): алгебру X=&lt;X,&amp;,a(+),a{},{}a&gt; событий - алгоритмических процедур (программ) заданную над алфавитом X={x1,x2,...,xn} и ¬-трехзначную алгебру логики (0,1,2 - неопределенность). ¬ алгебре ј опре

 

 

 

¬нимание! ѕредставленный –еферат находитс€ в открытом доступе в сети »нтернет, и уже неоднократно сдавалс€, возможно, даже в твоем учебном заведении.
—оветуем не рисковать. ”знай, сколько стоит абсолютно уникальный –еферат по твоей теме:

Ќовости образовани€ и науки

«аказать уникальную работу

—вои сданные студенческие работы

присылайте нам на e-mail

Client@Stud-Baza.ru