Формализация взаимосвязей операторов и данных в рамках расширенной алгебры алгоритмов
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2008 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2008
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/44285 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Формализация взаимосвязей операторов и данных в рамках расширенной алгебры алгоритмов / В.Г. Акуловский // Кибернетика и системный анализ. — 2008. — № 6. — С. 170-182. — Бібліогр.: 11 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860252992167477248 |
|---|---|
| author | Акуловский, В.Г. |
| author_facet | Акуловский, В.Г. |
| citation_txt | Формализация взаимосвязей операторов и данных в рамках расширенной алгебры алгоритмов / В.Г. Акуловский // Кибернетика и системный анализ. — 2008. — № 6. — С. 170-182. — Бібліогр.: 11 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| first_indexed | 2025-12-07T18:45:30Z |
| format | Article |
| fulltext |
ÓÄÊ 519.681
Â.Ã. ÀÊÓËÎÂÑÊÈÉ
ÔÎÐÌÀËÈÇÀÖÈß ÂÇÀÈÌÎÑÂßÇÅÉ ÎÏÅÐÀÒÎÐÎÂ È ÄÀÍÍÛÕ
 ÐÀÌÊÀÕ ÐÀÑØÈÐÅÍÍÎÉ ÀËÃÅÁÐÛ ÀËÃÎÐÈÒÌÎÂ
Êëþ÷åâûå ñëîâà: ñèñòåìà àëãîðèòìè÷åñêèõ àëãåáð, ðåãóëÿðíûå ñõåìû, ôîð-
ìàëèçàöèÿ äàííûõ, ðàçðàáîòêà è ïðåîáðàçîâàíèå àëãîðèòìîâ.
ÂÂÅÄÅÍÈÅ
Äîñòàòî÷íî èçâåñòíûì è ïåðñïåêòèâíûì ñðåäñòâîì ðàçðàáîòêè àëãîðèòìîâ ÿâ-
ëÿåòñÿ ñèñòåìà àëãîðèòìè÷åñêèõ àëãåáð (ÑÀÀ) [1–4]. Íà áàçå ýòîãî ôîðìàëü-
íîãî àïïàðàòà ïîñòðîåí ìåòîä ñòðóêòóðíîãî ïðîåêòèðîâàíèÿ ïðîãðàìì
(ÌÑÏÏ) [5, 6], â ðàìêàõ êîòîðîãî ñòðóêòóðà óïðàâëåíèÿ àëãîðèòìîì îòîæäå-
ñòâëÿåòñÿ ñ ðåãóëÿðíîé ñõåìîé, ñîñòîÿùåé èç îïåðàòîðîâ è ëîãè÷åñêèõ óñëî-
âèé ðàçëè÷íîé ñòåïåíè äåòàëèçàöèè. Äàííûå ñïåöèôèöèðóþòñÿ ñðåäñòâàìè àë-
ãåáðû ñòðóêòóð äàííûõ [5]. Îñíîâíûì ïîäõîäîì ìåòîäà ÿâëÿåòñÿ äåêîìïîçè-
öèÿ îïåðàòîðîâ, îáðàçóþùèõ àëãîðèòì, ñ ïîñëåäîâàòåëüíûì ïîíèæåíèåì
óðîâíÿ àáñòðàêöèè îïåðàòîðîâ è äàííûõ.
Ïðåæäå ÷åì ñôîðìóëèðîâàòü öåëü äàííîé ðàáîòû, ïðèâåäåì ñëåäóþùóþ öè-
òàòó [7]: «Õîòÿ îïåðàöèè è äàííûå, ýòè àêòèâíûå è ïàññèâíûå ïðîãðàììíûå êîì-
ïîíåíòû, èãðàþò ñîâåðøåííî ðàçëè÷íûå ðîëè â êàæäîé êîíêðåòíîé ïðîãðàììå,
ñîâåðøåííî íåâîçìîæíî ðàññìàòðèâàòü îäíè â îòðûâå îò äðóãèõ». Ìûñëü, âû-
ñêàçàííóþ â öèòàòå, ìîæíî ðàññìàòðèâàòü êàê óêàçàíèå íà îáùåìåòîäîëîãè÷åñ-
êóþ ïðîáëåìó ðàçðàáîòêè àëãîðèòìîâ è ïðîãðàìì.
 ðàìêàõ ýòîé ïðîáëåìû áóäåì ðåøàòü çàäà÷ó ôîðìàëèçàöèè âçàèìîñâÿçåé
îïåðàòîðîâ è äàííûõ.  êà÷åñòâå ñðåäñòâà ðåøåíèÿ âîñïîëüçóåìñÿ ðàñøèðåííîé
ñèñòåìîé àëãîðèòìè÷åñêèõ àëãåáð (ÑÀÀ–Ð) [8], ÷òî ÿâëÿåòñÿ î÷åðåäíûì øàãîì â
ðàçâèòèè ôîðìàëüíîãî àïïàðàòà.
1. ÄÀÍÍÛÅ Â ÐÀÑØÈÐÅÍÍÎÉ ÀËÃÅÁÐÅ ÀËÃÎÐÈÒÌÎÂ
Äëÿ âêëþ÷åíèÿ â ðàññìîòðåíèå äàííûõ âîñïîëüçóåìñÿ àáñòðàêòíîé ìîäåëüþ
ÝÂÌ [1, 2] â òðàêòîâêå, ïðåäëîæåííîé â [3].  êà÷åñòâå óïðàâëÿþùåãî àâòî-
ìàòà (ÓÀ) ðàññìàòðèâàåòñÿ ïðîèçâîëüíûé àëãîðèòì, â êà÷åñòâå îïåðàöèîííîãî
àâòîìàòà (ÎÀ) — îáðàáàòûâàåìàÿ ýòèì àëãîðèòìîì èíôîðìàöèÿ (ìíîæåñòâî
äàííûõ �). Âûõîäíûå ñèãíàëû ÓÀ îòîæäåñòâëÿþòñÿ ñ îïåðàòîðàìè, êîòîðûå
èçìåíÿþò äàííûå, ò.å. ñîñòîÿíèå ÎÀ. Âûõîäíûå ñèãíàëû ÎÀ ïðåäñòàâëÿþò
ñîáîé çíà÷åíèÿ ðàçëè÷íûõ ýëåìåíòàðíûõ ëîãè÷åñêèõ óñëîâèé,
õàðàêòåðèçóþùèõ çíà÷åíèÿ äàííûõ è/èëè ñîîòíîøåíèÿ ìåæäó íèìè.
Ðàçîáüåì ìíîæåñòâî � íà äâà íåïåðåñåêàþùèõñÿ ïîäìíîæåñòâà:
� � �DS DD, ãäå DS — ñòàòè÷åñêèå äàííûå, êîòîðûå ìîæíî èíòåðïðåòèðîâàòü
êàê äàííûå, ðàñïîëîæåííûå â îïåðàòèâíîé ïàìÿòè; DD — äèíàìè÷åñêèå äàííûå,
êîòîðûå ìîæíî èíòåðïðåòèðîâàòü êàê äàííûå, ðàñïîëîæåííûå â ðåãèñòðîâîé ïà-
ìÿòè, ò.å. äèíàìè÷åñêè èçìåíÿåìûå äàííûå, íå ôèêñèðóåìûå â ïàìÿòè. Ýòè äàí-
íûå îïðåäåëåíû (äîñòóïíû äëÿ àíàëèçà) òîëüêî ñðàçó ïîñëå âûïîëíåíèÿ
íåêîòîðûõ îïåðàòîðîâ è íå îïðåäåëåíû â îñòàëüíîå âðåìÿ.
Äëÿ îïèñàíèÿ àëãîðèòìîâ ðàññìîòðèì äâóõîñíîâíóþ àëãåáðàè÷åñêóþ ñèñòå-
ìó, îñíîâàìè êîòîðîé ÿâëÿþòñÿ ìíîæåñòâî îïåðàöèé è ìíîæåñòâî ëîãè÷åñêèõ
óñëîâèé. Ïðè ýòîì áóäåì èíòåðïðåòèðîâàòü èçâåñòíûå îñíîâíûå ïîíÿòèÿ (îïåðà-
òîð, îïåðàöèÿ, ëîãè÷åñêîå óñëîâèå), ââåäåííûå â ÑÀÀ [1–3], ìîäèôèöèðîâàííûå
è ðàñøèðåííûå â ÑÀÀ–Ð [8], â ñîîòâåòñòâèè ñ ðàññìàòðèâàåìîé òðàêòîâêîé
àáñòðàêòíîé ìîäåëè ÝÂÌ.
170 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
© Â.Ã. Àêóëîâñêèé, 2008
Ïóñòü � �U W, , � — ÑÀÀ–Ð, ãäå U — ìíîæåñòâî îïåðàòîðîâ, W — ìíîæåñ-
òâî ëîãè÷åñêèõ óñëîâèé, � — ñèãíàòóðà îïåðàöèé, ñîñòîÿùàÿ èç ëîãè÷åñêèõ îïå-
ðàöèé �1, ïðèíèìàþùèõ çíà÷åíèÿ íà ìíîæåñòâå W, è îïåðàöèé � 2 , ïðèíèìàþ-
ùèõ çíà÷åíèÿ íà ìíîæåñòâå îïåðàòîðîâ U .
Âûäåëèì íà ìíîæåñòâå îïåðàòîðîâ äâà ïîäìíîæåñòâà: U U U� � � � �, ãäå
îïåðàòîðû èç ìíîæåñòâà U � èçìåíÿþò ñòàòè÷åñêèå (èç ìíîæåñòâà DS), îïåðàòî-
ðû èç ìíîæåñòâà U � � — äèíàìè÷åñêèå (èç ìíîæåñòâà DD) äàííûå.
Îïåðàòîðû èç ìíîæåñòâà U � îïðåäåëèì ñëåäóþùèì îáðàçîì:
A D D( )� � � � (1)
�
� � � � �A D U D D DS( ) , , .
Ìíîæåñòâî äàííûõ D � — îáëàñòü îïðåäåëåíèÿ, à ìíîæåñòâî äàííûõ D � � —
îáëàñòü çíà÷åíèé îïåðàòîðà A D( )� . Ýòè ìíîæåñòâà íåçàâèñèìû, ò.å. äëÿ íèõ ìî-
æåò âûïîëíÿòüñÿ ëþáîå èç ñëåäóþùèõ ñîîòíîøåíèé:
D D� � � �, D D� � � �, D D�
� � � �, D D�
� � � �, D D� � � �.
Äàëåå ââåäåì ïîíÿòèå èíâåðñíîãî îïåðàòîðà:
A D D( )� � � �. (2)
Çäåñü îïåðàòîð A D( )� � âûïîëíÿåò äåéñòâèÿ, îáðàòíûå ïî îòíîøåíèþ ê îïåðà-
òîðó A D( )� , ðåàëèçóÿ òàêèì îáðàçîì îïåðàöèþ «îòêàò». Åñòåñòâåííîå îãðàíè-
÷åíèå íà èñïîëüçîâàíèå ýòîãî îïåðàòîðà ñëåäóþùåå. Äëÿ ëþáîãî îïåðàòîðà
B D D( � ) �� �, ãäå B D U( � )
�, � , �D D DS� � , íà èíòåðâàëå àëãîðèòìà îò A D( )� äî
A D( )� � âûïîëíÿåòñÿ óñëîâèå �D D�
� � � �.
Îïðåäåëèì îïåðàòîðû èç ìíîæåñòâà U � � ñëåäóþùèì îáðàçîì:
A D D� � � � �( ) (3)
� � � � � � �
� �D DS D DD A D U, , ( ) .
Òîëüêî ïîñëå âûïîëíåíèÿ ýòèõ îïåðàòîðîâ ìíîæåñòâî DD îïðåäåëåíî, ò.å.
äàííûå äîñòóïíû äëÿ àíàëèçà. Ìíîæåñòâî D � — îáëàñòü îïðåäåëåíèÿ, ìíî-
æåñòâî D � � — îáëàñòü çíà÷åíèé îïåðàòîðà A D� �( ), è äëÿ ýòèõ ìíîæåñòâ, î÷å-
âèäíî, âûïîëíÿåòñÿ ñîîòíîøåíèå D D�
� � � �.
Ìîæíî ñêàçàòü, ÷òî îïåðàòîð A D U( )�
� îòëè÷àåòñÿ îò îïåðàòîðà
A D U� �
� �( ) òåì, ÷òî ïåðâûé èçìåíÿåò äàííûå ìíîæåñòâà DS (âûïîëíÿåò îïåðà-
öèè ïðèñâàèâàíèÿ), ò.å. èçìåíÿåò äàííûå â îïåðàòèâíîé ïàìÿòè, à âòîðîé íà ýòè
äàííûå íå âëèÿåò (îïåðàöèé ïðèñâàèâàíèÿ íå ñîäåðæèò).
Äëÿ îïåðàòîðîâ èç ìíîæåñòâà U � � ââåäåì ÷àñòè÷íî èíâåðñíûé îïåðàòîð â
âèäå
A D D� � � � �( ) (4)
� � � � � � � �
� �D DS D DD A D U, , ( ) ,
ãäå îïåðàòîð A D D� � � � �( ) ÷àñòè÷íî èíâåðñíûé ïî îòíîøåíèþ ê îïåðàòîðó
A D D( )� � � �, òàê êàê äàííûå ìíîæåñòâà D DD� � ïîñëå âûïîëíåíèÿ îïåðàòîðà
A D� � �( ) ñóùåñòâóþò òîëüêî â äèíàìè÷åñêîé ïàìÿòè, à â ñòàòè÷åñêîé ïàìÿòè
íå ôèêñèðóþòñÿ. Íà âûïîëíåíèå ýòîãî îïåðàòîðà íàêëàäûâàþòñÿ îãðàíè÷åíèÿ,
òàêèå æå, êàê è íà èíâåðñíûé îïåðàòîð.
Ìíîæåñòâî îïåðàòîðîâ U âêëþ÷àåò òîæäåñòâåííûé îïåðàòîð, íå èçìåíÿþ-
ùèé ìíîæåñòâà äàííûõ �, êîòîðûé îïðåäåëèì êàê
E D D( ) � �D �. (5)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 171
Îïðåäåëåíèå îïåðàöèè íà ìíîæåñòâå W . Ìíîæåñòâî ëîãè÷åñêèõ óñëîâèé
ðàçîáüåì íà äâà ïîäìíîæåñòâà: W P� � �. Ìíîæåñòâî ïðåäèêàòîâ P, îïðåäåëåí-
íûõ íà ìíîæåñòâå �, ââåäåì ñëåäóþùèì îáðàçîì:
p D D D( ) ( )� �� (6)
�p P D, �, D � �.
Ðåçóëüòàòîì âû÷èñëåíèÿ ïðåäèêàòà ÿâëÿåòñÿ ëîãè÷åñêîå óñëîâèå � ( )D , õà-
ðàêòåðèçóþùåå òåêóùåå ñîñòîÿíèå ìíîæåñòâà äàííûõ D, ñîñòîÿíèå êîòîðîãî
(ñîñòîÿíèå ÎÀ) ïðè âû÷èñëåíèè ïðåäèêàòà p íå èçìåíÿåòñÿ.
Ìíîæåñòâî ëîãè÷åñêèõ óñëîâèé � � DS òàêîâî, ÷òî âûïîëíåíèå ëþáîãî
îïåðàòîðà X D U( )�
íå èçìåíÿåò � �( )D äëÿ ëþáîãî � �
( )D �. Äðóãèìè ñëîâà-
ìè, óñëîâèÿ ìíîæåñòâà � õàðàêòåðèçóþò ñîñòîÿíèå äàííûõ ìíîæåñòâà D � � �,
ñîõðàíÿþòñÿ â îïåðàòèâíîé ïàìÿòè, íå çàâèñÿò îò äåéñòâèÿ îïåðàòîðîâ ìíîæåñ-
òâà U è íàçûâàþòñÿ ôèêñèðóþùèìè, òàê êàê ïîçâîëÿþò ñîõðàíèòü (çàôèêñèðî-
âàòü) íåêîòîðûå õàðàêòåðèñòèêè òåêóùåãî ñîñòîÿíèÿ ÎÀ, ò.å. çíà÷åíèÿ è
ñîîòíîøåíèÿ ìåæäó äàííûìè ìíîæåñòâà D �.
Ýëåìåíòû ìíîæåñòâ P è � ïðèíèìàþò èñòèííûå çíà÷åíèÿ òðåõçíà÷íîé ëîãèêè
E3 0 1� { }, , � , ãäå 0 — ëîæü, 1 — èñòèíà, � — ïðîìåæóòî÷íîå çíà÷åíèå. Íà ìíîæåñ-
òâå E3 ââåäåíî îòíîøåíèå ïîðÿäêà òàêèì îáðàçîì, ÷òî 0 1� �� è èçâåñòíû îáîá-
ùåííûå ëîãè÷åñêèå îïåðàöèè (äèçúþíêöèÿ, êîíúþíêöèÿ, îòðèöàíèå, öèêëè÷åñêîå
îòðèöàíèå) ñî ñâîèìè òàáëèöàìè èñòèííîñòè [8–10].
Êðîìå ýòèõ îïåðàöèé îïðåäåëèì îïåðàöèè, ïîçâîëÿþùèå îñóùåñòâëÿòü ïðî-
ãíîçèðîâàíèå âû÷èñëèòåëüíîãî ïðîöåññà. Âïåðâûå ïîäîáíàÿ îïåðàöèÿ (îïåðàöèÿ
ëåâîãî óìíîæåíèÿ óñëîâèÿ íà îïåðàòîð) áûëà ââåäåíà Â.Ì. Ãëóøêîâûì [1, 2], è
èìåííî îíà ÿâëÿåòñÿ îòëè÷èòåëüíîé îñîáåííîñòüþ ïîñòðîåííîé èì àëãåáðû [4].
 ïðåäëàãàåìîé ðàáîòå ðåàëèçóåì âîçìîæíîñòü ïðîãíîçèðîâàíèÿ ñëåäóþ-
ùèì îáðàçîì. Îïåðàöèþ ëåâîãî óìíîæåíèÿ ïðåäèêàòà íà îïåðàòîð (ïðåäëîæåí-
íóþ â [8]) â îáùåì ñëó÷àå ñ ó÷åòîì îïðåäåëåíèé (1)–(4), (6) è îãðàíè÷åíèé
D D, � � �, D D� �
� � çàïèøåì â âèäå
X D p D p D X D p D D D( ) ( ) ( ( )) ( ) (
~
)� � � � � � � � � � . (7)
Çäåñü p D P( )
, X D U( )�
, D D D, ,� � � � �,
~
D D D� � � �, D X D� � � �( ).
Ðåçóëüòàòîì âûïîëíåíèÿ ýòîé îïåðàöèè ÿâëÿåòñÿ ëîãè÷åñêîå óñëîâèå � (
~
)D ,
õàðàêòåðèçóþùåå ñîñòîÿíèå ìíîæåñòâà äàííûõ
~
D .
Ðàññìîòðèì äâà âàðèàíòà åå ðåàëèçàöèè.
1.  ñëó÷àå, êîãäà îïåðàòîð ïðèíàäëåæèò ìíîæåñòâó U � �, îïåðàöèþ ëåâîãî
óìíîæåíèÿ ñ ó÷åòîì (3), (6), (7) îïðåäåëèì ñëåäóþùèì îáðàçîì:
A D p D p D A D p D D D� � � � � � � � � � �( ) ( ) ( ( ( ))) ( ) (
~
)� (8)
� � � � �D D DS D DD, , ,
~
, ( )D D D D A D� � � � � � � � � .
Ðåçóëüòàòîì âûïîëíåíèÿ îïåðàöèè ÿâëÿåòñÿ óñëîâèå � (
~
)D , õàðàêòåðèçóþ-
ùåå ñîñòîÿíèå ìíîæåñòâà äàííûõ
~
D , êîòîðîå áûëî áû ïîëó÷åíî ïîñëå âûïîë-
íåíèÿ îïåðàòîðà A D U( )�
�, îäíàêî ìíîæåñòâî DS â äàííîì ñëó÷àå îñòàåòñÿ íå-
èçìåííûì, òàê êàê D DD� � � . Ñìûñë îïåðàöèè ñîñòîèò â ïðîãíîçèðîâàíèè
âû÷èñëèòåëüíîãî ïðîöåññà.
 ÷àñòíîì ñëó÷àå, êîãäà â îïðåäåëåíèè (8) ìíîæåñòâî D D� � � , ýòó îïåðàöèþ
çàïèøåì â âèäå
p A D p D D( ( )) ( ) ( )� � � � � � � �� (9)
� � � � �D DS D DD, , D A D� � � � �( ).
172 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
Ðåçóëüòàòîì âûïîëíåíèÿ òàêîãî îïåðàòîðà ÿâëÿåòñÿ ëîãè÷åñêîå óñëîâèå � ( )D � �
— ïðîãíîç âûïîëíåíèÿ îïåðàòîðà A D U( )�
�, òàê êàê ðåçóëüòàò âûïîëíåíèÿ îïåðà-
òîðà A D� �( ) íå èçìåíÿåò ñîñòîÿíèÿ ìíîæåñòâà DS .  äàííîì ñëó÷àå ïîëó÷èëè îïå-
ðàöèþ, àäåêâàòíóþ îïåðàöèè, ââåäåííîé Â.Ì. Ãëóøêîâûì.
Ïðè èñïîëüçîâàíèè ÷àñòè÷íî èíâåðñíîãî îïåðàòîðà ýòó îïåðàöèþ ñ ó÷åòîì
îïðåäåëåíèÿ (4) çàïèøåì â âèäå
p A D p D D( ( )) ( ) ( )� � � � � � ��
� � � � �D DS D DD, , D A D� � � � �( ).
 ðåçóëüòàòå ïîëó÷àåì âîçìîæíîñòü íå òîëüêî ïðîãíîçèðîâàòü ðàçâèòèå âû-
÷èñëèòåëüíîãî ïðîöåññà, íî è ó÷èòûâàòü åãî ïðåäûñòîðèþ. Î÷åâèäíî, ÷òî àäåê-
âàòíîñòü âûïîëíåíèÿ òàêîé îïåðàöèè çàâèñèò îò âûïîëíåíèÿ îãðàíè÷åíèé íà èñ-
ïîëüçîâàíèå ÷àñòè÷íî èíâåðñíûõ îïåðàòîðîâ.
2.  ñëó÷àå, êîãäà îïåðàòîð ïðèíàäëåæèò ìíîæåñòâó U �, îïåðàöèþ ëåâîãî
óìíîæåíèÿ çàïèøåì ñ ó÷åòîì îïðåäåëåíèé (1), (6), (7):
A D p D P D A D p D D D( ) ( ) ( ( ( ))) ( ) (
~
)� � � � � � � � � � (10)
� � � �D D D DS, , ,
~
, ( )D D D D A D� � � � � � � � .
Ðåçóëüòàòîì âûïîëíåíèÿ ýòîé îïåðàöèè ÿâëÿåòñÿ ëîãè÷åñêîå óñëîâèå
� (
~
)D , çíà÷åíèå êîòîðîãî õàðàêòåðèçóåò ñîñòîÿíèå äàííûõ ìíîæåñòâà
~
D, ñ ó÷å-
òîì èçìåíåíèé, âûçâàííûõ âûïîëíåíèåì îïåðàòîðà A D( )� .
 ÷àñòíîì ñëó÷àå, êîãäà â (10) D D� � � , äàííóþ îïåðàöèþ çàïèøåì â âèäå
p A D p D D( ( )) ( ) ( )� � � � � � �� (11)
� � � �D D DS, , D A D� � � �( ).
Ðåçóëüòàòîì âûïîëíåíèÿ òàêîãî îïåðàòîðà ÿâëÿåòñÿ ëîãè÷åñêîå óñëîâèå
� ( )D � � , õàðàêòåðèçóþùåå èçìåíåíèÿ äàííûõ, âûçâàííûå âûïîëíåíèåì
îïåðàòîðà A D( )� .
 ñëó÷àå èñïîëüçîâàíèÿ èíâåðñíîãî îïåðàòîðà ýòó îïåðàöèþ çàïèøåì â ñî-
îòâåòñòâèè ñ îïðåäåëåíèåì (2) â âèäå
p A D p D D( ( )) ( ) ( )� � � � � �� (12)
� � �
D D DS, , D A D� � � �( ).
Ðåçóëüòàò åå âûïîëíåíèÿ — ëîãè÷åñêîå óñëîâèå � ( )D � , õàðàêòåðèçóþùåå
ñîñòîÿíèå äàííûõ ïîñëå îòêàòà.
Çàìåòèì, ÷òî îïåðàòîðû âòîðîé ãðóïïû íå ÿâëÿþòñÿ ñðåäñòâîì ïðîãíîçèðîâà-
íèÿ âû÷èñëèòåëüíîãî ïðîöåññà, è â ýòîì ñìûñëå áåç íèõ ìîæíî îáîéòèñü. Îäíàêî
ýòè êîíñòðóêöèè ìîãóò íàéòè ïðàêòè÷åñêîå ïðèìåíåíèå, ÷òî áóäåò ïîêàçàíî â ðàçä.
2 ïðè ðàññìîòðåíèè îïåðàöèé �-äèçúþíêöèè è �-èòåðàöèè.
Êðîìå ïðèâåäåííûõ îïåðàöèé â [8] ââåäåíû ñëåäóþùèå îïåðàöèè ëåâîãî
óìíîæåíèÿ, êîòîðûå áóäåì òàêæå ðàññìàòðèâàòü â êîíòåêñòå äàííîé ðàáîòû.
Ëåâîå óìíîæåíèå ôèêñèðóþùåãî óñëîâèÿ íà ïðåäèêàò. Îïåðàöèÿ èñ-
ïîëüçóåòñÿ äëÿ ôèêñàöèè òåêóùèõ õàðàêòåðèñòèê äàííûõ íåêîòîðîãî ìíîæåñòâà
D � è çàïèñûâàåòñÿ ñëåäóþùèì îáðàçîì:
p D D D( ) ( ) ( )� � � � � � ��
� � � �
D D� �, ( ) , p D P DS( ) ,�
�� .
Ëîãè÷åñêîå óñëîâèå � ( )D � , õàðàêòåðèçóþùåå òåêóùåå ñîñòîÿíèå ýëåìåíòîâ
ìíîæåñòâà D �, çàïîìèíàåòñÿ â âèäå ôèêñèðóþùåãî ëîãè÷åñêîãî óñëîâèÿ � �( )D êàê
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 173
ýëåìåíò ìíîæåñòâà DS , ïîçâîëÿÿ ñîõðàíÿòü èñòîðèþ âû÷èñëèòåëüíîãî ïðîöåññà.
Ó÷èòûâàÿ æåñòêèå îãðàíè÷åíèÿ, íàêëàäûâàåìûå íà èñïîëüçîâàíèå èíâåðñíûõ
îïåðàòîðîâ, ìîæíî çàêëþ÷èòü, ÷òî âîçìîæíîñòè, ïðåäîñòàâëÿåìûå äàííîé îïå-
ðàöèåé, äîñòàòî÷íî âàæíû, à â íåêîòîðûõ ñëó÷àÿõ ïðîñòî íåîáõîäèìû.
Ëåâîå óìíîæåíèå ôèêñèðóþùåãî óñëîâèÿ íà îïåðàòîð.Äëÿ óïðàâëåíèÿ
ñîñòîÿíèåì ôèêñèðóþùèõ óñëîâèé ïðèñîåäèíèì ê ìíîæåñòâó U ýëåìåíòàðíûé
îïåðàòîð bx , êîòîðûé èçìåíÿåò ñîñòîÿíèå óñëîâèÿ �
� â ðåçóëüòàòå ïðèìåíå-
íèÿ îïåðàöèè ëåâîãî óìíîæåíèÿ ýòîãî îïåðàòîðà íà ôèêñèðóþùåå óñëîâèå:
bx� � � (13)
�
�, � �
�x x E DS, ,3 � .
Òàêèì îáðàçîì, ìîæåò áûòü óñòàíîâëåíî ïðîèçâîëüíîå ñîñòîÿíèå ôèêñèðóþùå-
ãî ëîãè÷åñêîãî óñëîâèÿ â ãðàíèöàõ, îïðåäåëÿåìûõ çíà÷íîñòüþ ëîãèêè. Âîçìîæíîñòü
óïðàâëåíèÿ ñîñòîÿíèåì ôèêñèðóþùèõ ëîãè÷åñêèõ óñëîâèé ÿâëÿåòñÿ äîïîëíèòåëüíûì
ñðåäñòâîì óïðàâëåíèÿ õîäîì âñåãî âû÷èñëèòåëüíîãî ïðîöåññà.
Îòìåòèì, ÷òî õîòÿ ïîñëåäíÿÿ îïåðàöèÿ íå èìååò íåïîñðåäñòâåííîãî îòíîøå-
íèÿ ê òåìå äàííîé ðàáîòû, îíà ïðèâåäåíà â ñâÿçè ñ èñïîëüçîâàíèåì â äàëüíåé-
øåì èçëîæåíèè (ðàçä. 5).
Îïåðàöèè, îïðåäåëåííûå íà ìíîæåñòâå îïåðàòîðîâ èçU , ââåäåì ñëåäóþùèì
îáðàçîì.
Êîìïîçèöèÿ A D B D( � ) * (
~
) (ïîñëåäîâàòåëüíîå âûïîëíåíèå). Êîìïîçèöèÿ
îïåðàòîðîâ A D( � ) è B D(
~
)
A D B D U( � ), (
~
) ,
� ,
~
D D DS îçíà÷àåò, ÷òî îïåðàòîð
A D( � ) ïðåäøåñòâóåò îïåðàòîðó B D(
~
), à îïåðàòîð B D(
~
) ñëåäóåò çà îïåðàòîðîì
A D( � ), ò.å. ïîñëåäîâàòåëüíî âûïîëíÿþòñÿ ñíà÷àëà îïåðàòîð A D( � ), çàòåì îïåðàòîð
B D(
~
). Ïðè ýòîì ñîñòîÿíèå ìíîæåñòâà DS , ïîëó÷åííîå ïîñëå âûïîëíåíèÿ îïåðà-
òîðà A D( � ), ïîñòóïàåò (ïåðåäàåòñÿ) îïåðàòîðó B D(
~
). Ìíîæåñòâà � ,
~
D D ÿâëÿþò-
ñÿ îáëàñòÿìè îïðåäåëåíèÿ îïåðàòîðîâ A D( � ) è B D(
~
) ñîîòâåòñòâåííî, à ìíîæåñ-
òâà
�
D A D� ( � ) è
�
D B D� (
~
) — îáëàñòÿìè èõ çíà÷åíèé. Ïðè ýòîì îáëàñòè îïðåäå-
ëåíèÿ îïåðàòîðîâ âçàèìíî íåçàâèñèìû, ò.å. äëÿ íèõ äîïóñòèìû ëþáûå èç
ñîîòíîøåíèé:
� ~
D D� ,
~ �D D� , � ~
D D
� �, � ~
D D
� �, � ~
D D� .
 ðàññìàòðèâàåìîé òðàêòîâêå ýòà îïåðàöèÿ ìîæåò áûòü ïðèíöèïèàëüíî
óòî÷íåíà è äåòàëèçèðîâàíà. Ââåäåì ïîíÿòèå íåçàâèñèìûõ è ñâÿçàííûõ îïåðàòî-
ðîâ è îïðåäåëèì èõ ñëåäóþùèì îáðàçîì.
Íåçàâèñèìûìè íàçîâåì îïåðàòîðû A D( � ) è B D(
~
), åñëè äëÿ íèõ âûïîëíÿåòñÿ
ñîîòíîøåíèå
�
D D
� �
~
. Ìíîæåñòâî äàííûõ
�
D, îáðàçóþùèõ îáëàñòü çíà÷åíèé
îïåðàòîðà A D( � ) ( ( � ))
�
D A D� , íå ïåðåñåêàåòñÿ ñ ìíîæåñòâîì äàííûõ
~
D, îáðàçóþ-
ùèõ îáëàñòü îïðåäåëåíèÿ îïåðàòîðà B D(
~
), è ðåçóëüòàòû âûïîëíåíèÿ îïåðàòîðà
A D( � ) íå âëèÿþò íà âûïîëíåíèå îïåðàòîðà B D(
~
).
Äëÿ òàêèõ îïåðàòîðîâ îïåðàöèÿ êîìïîçèöèè ðåàëèçóåòñÿ ñëåäóþùèì îáðà-
çîì: A D B D D( � ) * (
~
) � , D D D� �
� �
.
Åñëè ââåäåì äâà äîïîëíèòåëüíûõ îãðàíè÷åíèÿ:
� �
D D
� �, ò.å. ïîòðåáóåì,
÷òîáû îáëàñòü çíà÷åíèé
�
D îïåðàòîðà B D(
~
) íå ïåðåñåêàëàñü ñ îáëàñòüþ çíà÷åíèé
�
D îïåðàòîðà A D( � ); �D D
� �
�
, ò.å. ïîòðåáóåì, ÷òîáû îáëàñòü çíà÷åíèé
�
D îïåðà-
òîðà B D(
~
) íå ïåðåñåêàëàñü ñ îáëàñòüþ îïðåäåëåíèÿ �D îïåðàòîðà A D( � ), òî, òàêèì
îáðàçîì, ââåäåì ïîíÿòèå — ïîëíîñòüþ íåçàâèñèìûå îïåðàòîðû.
Äëÿ ïîëíîñòüþ íåçàâèñèìûõ îïåðàòîðîâ âûïîëíÿåòñÿ ñëåäóþùåå òîæäåñ-
òâåííîå ñîîòíîøåíèå:
A D B D B D A D( � ) * (
~
) (
~
) * ( � )� . (14)
174 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
Ñâÿçàííûìè íàçîâåì îïåðàòîðû A D( � ) è B D(
~
), åñëè äëÿ íèõ âûïîëíÿåòñÿ ñî-
îòíîøåíèå
�
D D
� �
~
, ò.å. îáëàñòü çíà÷åíèé
�
D îïåðàòîðà A D( � ) ïåðåñåêàåòñÿ ñ
îáëàñòüþ îïðåäåëåíèÿ
~
D îïåðàòîðà B D(
~
).
Ðàññìîòðèì òðè ÷àñòíûõ ñëó÷àÿ ýòîé îïåðàöèè, îáîçíà÷àÿ ðåçóëüòèðóþùóþ
îáëàñòü çíà÷åíèé â âèäå
��
D.
1. Ïðè
�
D D�
~
, ò.å. êîãäà îáëàñòü çíà÷åíèé
�
D îïåðàòîðà A D( � ) ñîâïàäàåò ñ îá-
ëàñòüþ îïðåäåëåíèÿ
~
D îïåðàòîðà B D(
~
), îïåðàöèþ êîìïîçèöèè çàïèøåì â âèäå
A D B D B A D B D D( � ) * (
~
) ( ( � )) ( )� � �
� ��
..
 ýòîì ÷àñòíîì ñëó÷àå ðåàëèçóåòñÿ âàðèàíò îïåðàöèè êîìïîçèöèè, êîòîðûé
ðàññìàòðèâàåòñÿ â ÑÀÀ.
2. Ïðè
�
D D�
~
, ò.å. êîãäà îáëàñòü çíà÷åíèé îïåðàòîðà A D( � ) ïîëíîñòüþ âêëþ-
÷åíà â îáëàñòü îïðåäåëåíèÿ îïåðàòîðà B D(
~
), îïåðàöèþ êîìïîçèöèè çàïèøåì â
âèäå
A D B D B D D D( � ) * (
~
) (
~
)� � �
� ��
.
3. Ïðè
~
D D�
�
, ò.å. êîãäà îáëàñòü îïðåäåëåíèÿ îïåðàòîðà B D(
~
) ïîëíîñòüþ
âêëþ÷åíà â îáëàñòü çíà÷åíèé îïåðàòîðà A D( � ), îïåðàöèþ êîìïîçèöèè çàïèøåì â
âèäå
A D B D D B D D( � ) * (
~
) ( )� � � �
� � ��
,
�
D D� �
~
. ,
�
D D� �
~
.
 îáùåì ñëó÷àå ýòó îïåðàöèþ çàïèøåì â âèäå
A D B D D B D B D D D D D( � ) * (
~
) (
~
) (
~
)� � � � � � � � � � � � �
� � � � ��
,
~ ~
,
~
D D D D D� �
� �
� �
� �
.,
Ïðè ðàññìîòðåíèè îïåðàöèè êîìïîçèöèè â äàííîé èíòåðïðåòàöèè óäàëîñü
ïîëó÷èòü åå äåòàëüíîå è äîñòàòî÷íî ñòðîãîå îïèñàíèå, ïîçâîëèâøåå ó÷åñòü íþ-
àíñû åå âûïîëíåíèÿ. Ïðè ýòîì âûäåëåíî ïîäìíîæåñòâî äàííûõ (îáëàñòü çíà÷å-
íèé), ïîëó÷åííûõ â ðåçóëüòàòå ïîñëåäîâàòåëüíîãî âûïîëíåíèÿ äâóõ îïåðàòîðîâ,
ò.å. äàííûõ, ñâÿçûâàþùèõ îïåðàòîðû. Ýòîò ðåçóëüòàò áóäåò èñïîëüçîâàí â ïðî-
öåññå ðàññìîòðåíèÿ âîïðîñà î ïðåîáðàçîâàíèè îïåðàöèè êîìïîçèöèè â ðàçä. 4.
Îïåðàöèÿ � 3-äèçúþíêöèè. Äàííóþ îïåðàöèþ [8], îðèåíòèðîâàííóþ íà èñ-
ïîëüçîâàíèå òðåõçíà÷íûõ ëîãè÷åñêèõ óñëîâèé, çàïèøåì â âèäå
[ (
~
)]( ( ) ( ) ( ))
( ), (
~
) ,
(�
�
D A D B D C D
A D D
B� � � � � � � � �
� �åñëè 1
D D
C D D
� � �
� � � �
�
�
��
�
�
�
), (
~
) ,
( ), (
~
) ,
åñëè
åñëè
�
� �
0
( )15
ãäå D D D DS� � � � � � �, , ,
~
D � �,
~
D � �.
Ðåçóëüòàòîì ðåàëèçàöèè ýòîé êîíñòðóêöèè ÿâëÿåòñÿ âûïîëíåíèå îäíîãî èç
òðåõ âîçìîæíûõ îïåðàòîðîâ, êîòîðûé âûáèðàåòñÿ â ñîîòâåòñòâèè ñî çíà÷åíèåì
ëîãè÷åñêîãî óñëîâèÿ � (
~
)D , ïðèíèìàþùåãî èñòèííûå çíà÷åíèÿ òðåõçíà÷íîé
ëîãèêè E3 .
Îïåðàöèÿ �-èòåðàöèè:
� ( ) ( )D A D� � �{ } (16)
(ñîîòâåòñòâóåò ïðîãðàììíîé êîíñòðóêöèè WHILE). Îïåðàöèÿ �-èòåðàöèè îïåðà-
òîðà A D( )� � ñîñòîèò â ïðîâåðêå óñëîâèÿ � ( )D � , çàòåì, åñëè � ( )D � èñòèííî, âû-
ïîëíÿåòñÿ îïåðàòîð A D( )� � è âíîâü ïðîâåðÿåòñÿ óñëîâèå � ( )D � . Ýòîò öèêëè÷åñ-
êèé ïðîöåññ îñóùåñòâëÿåòñÿ äî òåõ ïîð, ïîêà óñëîâèå � ( )D � íå ñòàíåò ëîæíûì.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 175
Íåîáõîäèìûì óñëîâèåì çàâåðøåíèÿ îïåðàöèè ÿâëÿåòñÿ âûïîëíåíèå ñëåäóþùåãî
ñîîòíîøåíèÿ: D D�
� � � � �, ãäå D A D� � � � � �( ).
 êà÷åñòâå ëîãè÷åñêîãî óñëîâèÿ � ( )D � â îïåðàöèÿõ � 3-äèçúþíêöèè è
�-èòåðàöèè ìîãóò âûñòóïàòü: ïðåäèêàò, ôèêñèðóþùåå óñëîâèå è îïåðàöèè
ëåâîãî óìíîæåíèÿ.
Ïðåäëàãàåìûé ïîäõîä ïîçâîëèë â ðàìêàõ ÑÀÀ–Ð ñïåöèôèöèðîâàòü âçàèìîñ-
âÿçè ìåæäó îïåðàòîðàìè è äàííûìè è îò÷àñòè ñîáñòâåííî äàííûå. Ïðè ýòîì íå
òîëüêî ñîõðàíèëèñü âñå âîçìîæíîñòè ïî ïîñòðîåíèþ ïðîèçâîäíûõ àëãîðèòìè-
÷åñêèõ êîíñòðóêöèé è ïðåîáðàçîâàíèþ ðåãóëÿðíûõ ñõåì, îïèñûâàþùèõ ïðîèç-
âîëüíûé àëãîðèòì, íî è îòêðûëèñü ñóùåñòâåííûå äîïîëíèòåëüíûå âîçìîæíîñòè,
÷òî áóäåò ðàññìîòðåíî â ñëåäóþùèõ ðàçäåëàõ.
2. ÏÐÎÈÇÂÎÄÍÛÅ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅ ÊÎÍÑÒÐÓÊÖÈÈ
Êà÷åñòâî ðàçðàáàòûâàåìûõ àëãîðèòìîâ, ó÷èòûâàÿ èõ ìíîãîîáðàçèå, ñóùåñòâåí-
íî çàâèñèò îò èçîáðàçèòåëüíûõ âîçìîæíîñòåé, ïðåäîñòàâëÿåìûõ ñðåäñòâàìè èõ
ðàçðàáîòêè. Â ðàìêàõ ðàññìàòðèâàåìîãî ïîäõîäà ñîõðàíÿþòñÿ âñå âîçìîæíîñ-
òè ñîçäàâàòü ïðîèçâîäíûå àëãîðèòìè÷åñêèå êîíñòðóêöèè. Ïðîäåìîíñòðèðóåì
ýòî íà ïðèìåðå ñëåäóþùèõ ïðèíöèïèàëüíî âàæíûõ îïåðàöèé:
�-äèçúþíêöèÿ, êîòîðàÿ ÿâëÿåòñÿ ÷àñòíûì ñëó÷àåì � 3-äèçúþíêöèè
â ñîîòâåòñòâèè ñ (5), (15),
[ (
~
)]( ( ) ( )) [ (
~
)]( ( ) ( ) ( ))� �D A D B D D A D B D E D� � � � � � � � � � �
�
� �
� � �
�
�
�
��
A D D
B D D
( ), (
~
) ,
( ), (
~
) ,
åñëè
åñëè
�
�
1
0
îáåñïå÷èâàåò âûáîð îäíîãî èç äâóõ îïåðàòîðîâ â çàâèñèìîñòè îò çíà÷åíèÿ ëî-
ãè÷åñêîãî óñëîâèÿ � (
~
)D ;
�-ôèëüòðàöèÿ (ïîñëåäîâàòåëüíàÿ ôèëüòðàöèÿ), êîòîðàÿ ÿâëÿåòñÿ ÷àñòíûì
ñëó÷àåì �-äèçúþíêöèè,
[ (
~
)]( ( )) [ (
~
)]( ( ) ( ))� �D A D D A D E D� � � � , (17)
îáåñïå÷èâàåò âûïîëíåíèå îïåðàòîðà A D( )� òîëüêî ïðè èñòèííîì çíà÷åíèè
� ( )
~
D .
Äëÿ ýòèõ îïåðàöèé, êàê è äëÿ îïåðàöèé � 3-äèçúþíêöèè è �-èòåðàöèè, â êà-
÷åñòâå ëîãè÷åñêîãî óñëîâèÿ ìîãóò âûñòóïàòü: ïðåäèêàò, ôèêñèðóþùåå óñëîâèå è
îïåðàöèè ëåâîãî óìíîæåíèÿ.
Äàëåå ðàññìîòðèì âîçìîæíîñòè èñïîëüçîâàíèÿ îïåðàöèè ëåâîãî óìíîæåíèÿ
â ñëó÷àÿõ (10)–(12), î ÷åì óïîìèíàëîñü â ðàçä. 1.
Îïðåäåëåíèå (10) ìîæåò áûòü èñïîëüçîâàíî ïðè ïîñòðîåíèè ïðîèçâîäíîé
îïåðàöèè � 3-äèçúþíêöèè (ñì. îïðåäåëåíèå (15)), äëÿ êîòîðîé ïðèâåäåì òîæäåñ-
òâåííîå ñîîòíîøåíèå
A D p D B D C D G D(
~
) * [ ( )]( ( ) ( ) ( ))� � � � � � � � �
� � � � � � � � �[ (
~
) ( )]( ( ) ( ) ( ))A D p D B D C D G D .
Çäåñü óñëîâèåì âûáîðà îäíîé èç âåòâåé âû÷èñëåíèé áóäåò � (
~
)D D� � , ãäå
~
(
~
)D A D� � . Åñòåñòâåííûì òðåáîâàíèåì ê òàêîé êîíñòðóêöèè ÿâëÿåòñÿ
~
D D�
� 0.
 ÷àñòíîì ñëó÷àå â ñîîòâåòñòâèè ñ îïðåäåëåíèåì (11) ýòó êîíñòðóêöèþ ìîæ-
íî çàïèñàòü â âèäå
176 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
A D p D B D C D G D(
~
) * [ ( )]( ( ) ( ) ( ))� � � � � � � � �
� � � � � � � � �[ ( (
~
))]( ( ) ( ) ( ))p A D B D C D G D .
Àíàëîãè÷íûå ñîîòíîøåíèÿ âûïîëíÿþòñÿ äëÿ îïåðàöèé �-äèçúþíêöèè è
�-ôèëüòðàöèè.
Èñïîëüçóÿ ñîîòíîøåíèå (10), ìîæíî ìîäåðíèçèðîâàòü îïåðàöèþ �-èòåðàöèè, çà-
ïèñàâ åå â ñîîòâåòñòâèè ñ îïðåäåëåíèåì (16) â âèäå A D p D B D(
~
) ( ) ( )� ��{ }.  ýòîì ñëó÷àå
óñëîâèå çàâåðøåíèÿ öèêëà çàäàåòñÿ ñîîòíîøåíèÿìè: D D�
� � � � � è/èëè D D�
� � �
~
,
ãäå D B D� � � � � �( ), à
~
(
~
)D A D� � .
 ÷àñòíîì ñëó÷àå â ñîîòâåòñòâèè ñ (11) ýòîò îïåðàòîð çàïèøåì â âèäå
p A D B D( (
~
)) ( ){ }�� . Òîãäà äëÿ âûõîäà èç öèêëà íåîáõîäèìî âûïîëíåíèå ñîîòíîøå-
íèÿ
~
D D�
� � � � �, ãäå
~
(
~
)D A D� � , D B D� � � � � �( ), ëèáî, åñëè óêàçàííîå óñëî-
âèå íå âûïîëíÿåòñÿ, âûõîä èç öèêëà áóäåò îïðåäåëÿòü òîëüêî çíà÷åíèå ëîãè÷åñ-
êîãî óñëîâèÿ � (
~
) ( (
~
))D p A D� � .
 ðåçóëüòàòå ïîëó÷èëè âîçìîæíîñòü ñòðîèòü îïåðàöèè �-èòåðàöèè, â êîòî-
ðûõ âûõîä èç öèêëà ìîæåò áûòü îðãàíèçîâàí êàê â çàâèñèìîñòè, òàê è íåçàâèñè-
ìî îò âûïîëíåíèÿ îïåðàòîðà B D( )� � .
Ïðèâåäåííûìè ïðèìåðàìè âîçìîæíîñòè ïîñòðîåíèÿ ìîäèôèöèðîâàííûõ
îïåðàöèé �-èòåðàöèè äàëåêî íå èñ÷åðïûâàþòñÿ. Ìîæíî ïðåäëîæèòü ñëåäóþ-
ùóþ, äîñòàòî÷íî ýêçîòè÷åñêóþ êîíñòðóêöèþ (ñì. (12)): p B D B D( ( )) ( )� � � ��{ }.
Çäåñü B D( )� � è B D( )� � � — âçàèìíî èíâåðñíûå îïåðàòîðû. Òàêàÿ êîíñòðóêöèÿ
ïîçâîëÿåò ïðîñëåäèòü ïåðñïåêòèâó èñïîëüçîâàíèÿ îïåðàòîðà B D( )� � áåç èçìå-
íåíèÿ çíà÷åíèé îáðàáàòûâàåìûõ äàííûõ.
Òàêèì îáðàçîì, ñîçäàâàÿ ðàçëè÷íûå ìîäèôèêàöèè îïåðàöèè �-èòåðàöèè,
ìîæíî ðåàëèçîâûâàòü íàèáîëåå óäîáíûå â êàæäîì êîíêðåòíîì ñëó÷àå óñëîâèÿ
çàâåðøåíèÿ îïåðàöèè.
Êðîìå òîãî, ïîñòðîèì øèðîêî ïðèìåíÿåìóþ àëãîðèòìè÷åñêóþ êîíñòðóê-
öèþ, àíàëîãè÷íóþ îïåðàòîðó for â ÿçûêàõ ïðîãðàììèðîâàíèÿ. Èçâåñòíî, ÷òî îíà
ëåãêî ðåàëèçóåòñÿ êàê ÷àñòíûé ñëó÷àé �-èòåðàöèè, ò.å. öèêëè÷åñêîé êîíñòðóêöèè
òèïà WHILE:
I D A D S Dp D( ) ( ) ( )( )� � �{ }.
Çäåñü I D( ) — îïåðàòîð èíèöèàëèçàöèè ïåðåìåííûõ öèêëà; A D( )� � — òåëî
öèêëà; S D( ) — îïåðàòîð, èçìåíÿþùèé ïåðåìåííûå öèêëà; � ( ) ( )D p D� � � —
óñëîâèå çàâåðøåíèÿ öèêëà, ïðè ýòîì D I D� � ( ) â íà÷àëå è D S D� � ( ) â
ïðîöåññå âûïîëíåíèÿ öèêëà.
Âîñïîëüçîâàâøèñü âîçìîæíîñòÿìè ïîñòðîåííîãî àëãåáðàè÷åñêîãî àïïàðàòà,
ðåàëèçóåì ïðåäëàãàåìóþ êîíñòðóêöèþ áîëåå, ïî ìíåíèþ àâòîðà, èçÿùíî. Åñëè
ýòî ðåøåíèå ïîêàæåòñÿ èçëèøíå èçîùðåííûì, ìîæíî ðàññìàòðèâàòü åãî êàê åùå
îäíó äåìîíñòðàöèþ îáøèðíûõ âîçìîæíîñòåé ïî ñîçäàíèþ íîâûõ
àëãîðèòìè÷åñêèõ êîíñòðóêöèé.
Îïåðàòîð èíèöèàëèçàöèè I D( ) è îïåðàòîð èçìåíåíèÿ ïåðåìåííûõ öèêëà
S D( ) ìîæíî ðàññìàòðèâàòü êàê îïåðàöèè ëåâîãî óìíîæåíèÿ îïåðàòîðà íà ïðåäè-
êàò, îäíàêî îñîáåííîñòü ñîñòîèò â òîì, ÷òî îïåðàòîð èíèöèàëèçàöèè I D( ) âû-
ïîëíÿåòñÿ òîëüêî îäèí (ïåðâûé) ðàç, à â îñòàëüíîå âðåìÿ ðàáîòû öèêëà âûïîëíÿ-
åòñÿ îïåðàòîð S D( ), èçìåíÿþùèé ïåðåìåííûå öèêëà. Äëÿ ðàçðåøåíèÿ ýòîé ïðî-
áëåìû ââåäåì âñïîìîãàòåëüíîå ôèêñèðóþùåå óñëîâèå � è ñ ó÷åòîì (11), (13),
(16), (17) ðåàëèçóåì òðåáóåìóþ êîíñòðóêöèþ ñëåäóþùèì îáðàçîì:
b A Dp I D b S D
1 0� � �
*
([ ]( ( ) * ) ( )) ( )� � �{ }.
 äàííîì ñëó÷àå ôèêñèðóþùåå óñëîâèå �, èñõîäíî óñòàíîâëåííîå
â ñîñòîÿíèå èñòèííîñòè, ïîçâîëÿåò ñ ïîìîùüþ îïåðàöèè �-äèçúþíêöèè ïðè ïåð-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 177
âîì âõîæäåíèè â öèêë âûïîëíèòü îïåðàòîð I D( ) â êà÷åñòâå îïåðàòîðà â îïåðà-
öèè ëåâîãî óìíîæåíèÿ îïåðàòîðà íà ïðåäèêàò, ïîñëå ÷åãî óñëîâèå � ñáðàñûâàåò-
ñÿ â 0. Â îñòàëüíîå âðåìÿ ôóíêöèîíèðîâàíèÿ öèêëà ñ ïîìîùüþ òîé æå îïåðàöèè
�-äèçúþíêöèè ïðè ëîæíîì ôèêñèðóþùåì óñëîâèè � âûïîëíÿåòñÿ îïåðàöèÿ
ëåâîãî óìíîæåíèÿ îïåðàòîðà S D( ) íà ïðåäèêàò.
Ïîñòðîåííóþ êîíñòðóêöèþ çàïèøåì â âèäå
� � ��I D p S D A D( ) ( ( )) ( ){ }. (18)
Çàìåòèì, ÷òî îïåðàòîð I D( )� çàêëþ÷åí â óãëîâûå ñêîáêè, ÷òîáû îòìåòèòü
òîò ôàêò, ÷òî îí âûïîëíÿåòñÿ îäíîêðàòíî è òîëüêî â ïåðâûé ðàç.
 äàííîì ðàçäåëå ïîêàçàíî, ÷òî â ðàìêàõ ðàññìàòðèâàåìîãî ïîäõîäà ñîõðàíÿ-
þòñÿ è â èçâåñòíîé ìåðå ðàñøèðÿþòñÿ âñå âîçìîæíîñòè ôîðìàëèçîâàííîãî ïîñòðîå-
íèÿ ïðîèçâîäíûõ àëãîðèòìè÷åñêèõ êîíñòðóêöèé, îðèåíòèðîâàííûõ êàê íà êëàññ ðå-
øàåìûõ çàäà÷, òàê è íà îñîáåííîñòè ÿçûêà ðåàëèçàöèè àëãîðèòìà.
3. ÐÅÀËÈÇÀÖÈß ÌÅÕÀÍÈÇÌÀ ÏÎÄÏÐÎÃÐÀÌÌ
 ÐÀÌÊÀÕ ÔÎÐÌÀËÜÍÎÃÎ ÀÏÏÀÐÀÒÀ
Íè îäíà äîñòàòî÷íî áîëüøàÿ ïðîãðàììà íå îáõîäèòñÿ áåç òàêîé ìîùíîé àëãî-
ðèòìè÷åñêîé êîíñòðóêöèè, êàê ïîäïðîãðàììà. Ðåøåíèå î ñîçäàíèè ïîäïðîãðàì-
ìû â ïðîöåññå ïðîåêòèðîâàíèÿ ïðîãðàììû ïðèíèìàåòñÿ â äâóõ ñëó÷àÿõ [7]:
— âûÿâëåíû äåéñòâèÿ, êîòîðûå â õîäå ðàáîòû ïðîãðàììû äîëæíû íåîäíîê-
ðàòíî âûïîëíÿòüñÿ â ðàçíûõ åå ìåñòàõ;
— ñïåöèôèöèðîâàíà íåêîòîðàÿ ÷àñòíàÿ çàäà÷à, ðåàëèçàöèÿ êîòîðîé îòêëà-
äûâàåòñÿ èëè ïåðåäàåòñÿ äðóãîìó èñïîëíèòåëþ.
×àñòî èìåþò ìåñòî îáà ñëó÷àÿ, íî ëþáîé èç íèõ ÿâëÿåòñÿ äîñòàòî÷íîé ïðè-
÷èíîé äëÿ ñîçäàíèÿ ïîäïðîãðàììû.
Îïðåäåëèì ïîäïðîãðàììó ñëåäóþùèì îáðàçîì. Îïåðàòîð, ñíàáæåííûé ñðå-
äñòâàìè âûçîâà, ïåðåäà÷è ïàðàìåòðîâ è ìåõàíèçìîì âîçâðàòà â òî÷êó âûçîâà,
ÿâëÿåòñÿ ïîäïðîãðàììîé.
Ïîëàãàÿ, ÷òî ñðåäñòâà âûçîâà ïîäïðîãðàììû è âîçâðàòà èç íåå ðåàëèçóþòñÿ íà
àïïàðàòíîì óðîâíå, è â ñâÿçè ñ ýòèì àáñòðàãèðóÿñü îò íèõ, îñòàíîâèìñÿ íà âîïðîñàõ,
ñâÿçàííûõ ñ ïåðåäà÷åé ïàðàìåòðîâ â ïîäïðîãðàììû. Ñ öåëüþ îáåñïå÷åíèÿ óíèâåð-
ñàëüíîñòè è íåçàâèñèìîñòè îò ÿçûêà ðåàëèçàöèè àëãîðèòìà ðàññìîòðèì íåêîòîðûé
îáîáùåííûé ìåõàíèçì ïåðåäà÷è ïàðàìåòðîâ (èíòåðôåéñ).
Äëÿ ýòîãî íà îñíîâàíèè ýëåìåíòàðíîãî àíàëèçà ëèòåðàòóðíûõ èñòî÷íèêîâ (íà-
ïðèìåð, [11]) îïðåäåëèì òðè âîçìîæíûõ òèïà ïåðåäàâàåìûõ ïàðàìåòðîâ: âõîäíûå,
âûõîäíûå è ïàðàìåòðû, êîòîðûå èñïîëüçóþòñÿ êàê â êà÷åñòâå âõîäíûõ, òàê è â êà-
÷åñòâå âûõîäíûõ. Ïîñëåäíèé òèï íàçîâåì ïðîõîäíûìè ïàðàìåòðàìè. Áóäåì ðàçëè-
÷àòü äâà òèïà ïîäïðîãðàìì — ïðîöåäóðû è ôóíêöèè.
Âûçîâ ïðîöåäóðû çàïèøåì â âèäå
� ( ; ; )D D D� � � � � � (19)
� � � � � � �D D D DS, , ,
ãäå D � — ìíîæåñòâî âõîäíûõ, D � � — ìíîæåñòâî âûõîäíûõ, D � � � — ìíîæåñ-
òâî ïðîõîäíûõ ôàêòè÷åñêèõ ïàðàìåòðîâ. Îáëàñòüþ îïðåäåëåíèÿ ïðîöåäóðû
ÿâëÿåòñÿ ìíîæåñòâî âõîäíûõ è ïðîõîäíûõ ïàðàìåòðîâ D D� � � �, à îáëàñòüþ
çíà÷åíèé — ìíîæåñòâî âûõîäíûõ è ïðîõîäíûõ ïàðàìåòðîâ D D� � � � � �. Ïðè
ýòîì, êàê ëþáîå èç ìíîæåñòâ D D D� � � � � �, , , òàê è âñå îíè ìîãóò áûòü ïóñòû-
ìè, íàïðèìåð, åñëè ïðîöåäóðà âûâîäèò íà ýêðàí èëè ïå÷àòü íåêîòîðûé
çàðàíåå çàäàííûé òåêñò.
Âûçîâ ôóíêöèè çàïèøåì â âèäå
~
( ; ; ) , , ,
~
DF D D D D D D DS D DD� � � � � � � � � � � � � � ,
178 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
ãäå D � — ìíîæåñòâî âõîäíûõ, D � � — ìíîæåñòâî âûõîäíûõ, D � � � — ìíîæåñ-
òâî ïðîõîäíûõ ïàðàìåòðîâ,
~
D — ìíîæåñòâî äàííûõ, âîçâðàùàåìûõ ôóíêöè-
åé â êà÷åñòâå ðåçóëüòàòà, äëÿ êîòîðîãî âûïîëíÿåòñÿ óñëîâèå
~
D � �. Ìíîæåñ-
òâà D D D� � � � � �, , ìîãóò áûòü ïóñòûìè ïî ïðè÷èíå, àíàëîãè÷íîé ïðèâåäåííîé
äëÿ ïðîöåäóðû.
Îòìåòèì, ÷òî îïðåäåëåíèå ïîäïðîãðàììû çàïèñûâàåòñÿ â âèäå äåêîìïîçè-
öèè îïåðàòîðà âûçîâà ïîäïðîãðàììû, ïîëíîñòüþ àíàëîãè÷íîé ñëó÷àþ äåêîìïî-
çèöèè îáû÷íîãî îïåðàòîðà, çà òåì èñêëþ÷åíèåì, ÷òî ïðè ýòîì óêàçûâàþòñÿ ôîð-
ìàëüíûå ïàðàìåòðû. Òàêîå îïðåäåëåíèå áóäåò âûïîëíåíî â ðàçä. 5 ïðè
ðàññìîòðåíèè êîíêðåòíîãî ïðèìåðà.
Ôóíêöèÿ ïîçâîëÿåò ðàñøèðèòü âîçìîæíîñòè îïåðàöèè ëåâîãî óìíîæåíèÿ
ïðåäèêàòà íà îïåðàòîð (8), êîòîðóþ çàïèøåì â âèäå
~
( ; ; ) ( � ) (
~ � ) (
~
) (
~
)
^ ^
DF D D D p D p D D p D D� � � � � � � � � � � .
Çàìåòèì, ÷òî âîçìîæíîñòü èñïîëüçîâàíèÿ ôóíêöèè â îïåðàöèè ëåâîãî óìíî-
æåíèÿ îïåðàòîðà íà ïðåäèêàò îáóñëîâëåíà òåì, ÷òî
~
D DD
, è, òàêèì îáðàçîì,
äàííûå ìíîæåñòâà DS íå èçìåíÿþòñÿ.
 ÷àñòíîì ñëó÷àå, êîãäà
~ �D D� , ýòî âûðàæåíèå â ñîîòâåòñòâèè ñ îïðåäåëå-
íèåì (9) çàïèøåì â âèäå
p DF D D D p D D(
~
( ; ; )) (
~
) (
~
)� � � � � � � � � .
Ôîðìàëèçàöèÿ àïïàðàòà ïîäïðîãðàìì, ïîìèìî ñîêðàùåíèÿ îáúåìà ðåãóëÿð-
íîé ñõåìû, îïèñûâàþùåé òðåáóåìûé àëãîðèòì, ïîçâîëÿåò ðåàëèçîâàòü îäèí èç
ïîäõîäîâ ê ðåøåíèþ âàæíåéøèõ çàäà÷ ìåòîäîëîãèè ïðîãðàììèðîâàíèÿ —
ìîäóëÿðèçàöèè àëãîðèòìà.
4. ÏÐÅÎÁÐÀÇÎÂÀÍÈÅ ÊÎÌÏÎÇÈÖÈÈ ÎÏÅÐÀÒÎÐÎÂ
Äàëåå ðàññìîòðèì âîçìîæíîñòè ïðåîáðàçîâàíèÿ êîìïîçèöèè ñâÿçàííûõ îïåðà-
òîðîâ, ñäåëàâ ñëåäóþùèå ïðåäâàðèòåëüíûå çàìå÷àíèÿ.
Âî-ïåðâûõ, äëÿ ëþáûõ äâóõ îïåðàòîðîâ, î÷åâèäíî, âûïîëíÿåòñÿ òîæäåñ-
òâåííîå ñîîòíîøåíèå
A D B D C D( � ) * (
~
) (
~
)
^
� , (20)
ãäå B D A D U(
~
), ( � )
�, îáëàñòü îïðåäåëåíèÿ
~� � ~
D D D� � , à îáëàñòü çíà÷åíèé
�� � �
D D D� � . Èíûìè ñëîâàìè, îïåðàòîðû A D( � ) è B D(
~
) ìîãóò áûòü îáúåäèíåíû
â îäèí îïåðàòîð C D(
~�
), êîòîðûé, âûïîëíÿÿ äåéñòâèÿ, àäåêâàòíûå ïîñëåäîâà-
òåëüíîìó âûïîëíåíèþ îïåðàòîðà A D( � ), à çàòåì B D(
~
), ïîçâîëèò ïîëó÷èòü òà-
êîé æå ðåçóëüòàò.
Âî-âòîðûõ, äîïóñòèì, ÷òî íåêîòîðûé îïåðàòîð A D U( � )
� ìîæíî ïðåäñòà-
âèòü â âèäå äâóõ íåçàâèñèìûõ îïåðàòîðîâ
A D K D G D( � ) ( � ) * ( � )� � � � , (21)
îáëàñòü îïðåäåëåíèÿ êîòîðûõ � � �D D D� � � � �, à îáëàñòü çíà÷åíèé
�
D � � � � �
� �
D D ,
ãäå
�
D A D� ( � ) ,
�
D K D� � �( � ),
�
D G D� � � � �( � ) .
Îòìåòèì, ÷òî âûñêàçàííîå äîïóùåíèå íå ÿâëÿåòñÿ îñîáåííî âîëüíûì, òàê êàê
íà ïðàêòèêå âîçìîæíîñòü ïðåäñòàâèòü îïåðàòîð ïîäîáíûì îáðàçîì âñòðå÷àåòñÿ äîñ-
òàòî÷íî ÷àñòî. Çàòðóäíåíèÿ äëÿ òàêîãî ïðåäñòàâëåíèÿ îïåðàòîðîâ ìîãóò âîçíèêíóòü
òîëüêî íà çàâåðøàþùèõ ñòàäèÿõ äåêîìïîçèöèè àëãîðèòìà.
Âîçìîæíîñòü ïðåîáðàçîâàíèÿ êîìïîçèöèè îïåðàòîðîâ áóäåì ðàññìàòðèâàòü
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 179
â ðàìêàõ äàííîãî äîïóùåíèÿ. Íà÷íåì ðàññìîòðåíèå ïðåîáðàçîâàíèÿ êîìïîçèöèè
îïåðàòîðîâ A D B D( � ) * (
~
) ñ ÷àñòíûõ ñëó÷àåâ, â òîì æå ïîðÿäêå, êîòîðûé áûë ïðè-
íÿò ïðè ðàññìîòðåíèè îïåðàöèè êîìïîçèöèè â ðàçä. 1.
1.  ïåðâîì ïðîñòåéøåì ñëó÷àå, êîãäà
�
D D�
~
, ñâÿçàííûå îïåðàòîðû A D( � ) è
B D(
~
) ìîãóò áûòü åñòåñòâåííî â ñîîòâåòñòâèè ñ (20) ïðåäñòàâëåíû â âèäå îäíîãî
îïåðàòîðà:
A D B D C D D( � ) * (
~
) (
~�
)� �
��
.
2.  ñëó÷àå, êîãäà
�
D D�
~
, äëÿ ïðåîáðàçîâàíèÿ îïåðàöèè êîìïîçèöèè ïðåä-
ñòàâèì â ñîîòâåòñòâèè ñ (21) îïåðàòîð B D(
~
) â âèäå äâóõ íåçàâèñèìûõ îïåðàòî-
ðîâ B D G D K D(
~
) ( ) * (
~
)� �
�
, îáðàáàòûâàþùèõ ñîîòâåòñòâåííî äàííûå, ïîëó÷åí-
íûå ïîñëå âûïîëíåíèÿ îïåðàòîðà A D( � ), è íåçàâèñèìóþ îò A D( � ) ÷àñòü äàííûõ.
Äàëåå â ñîîòâåòñòâèè ñ (20) îáúåäèíÿåì äâà ñâÿçàííûõ îïåðàòîðà:
A D G D C D( � ) * ( ) (
~�
)
�
� .  ðåçóëüòàòå ïîëó÷èì
A D B D C D K D( � ) * (
~
) (
~�
) * (
~
)� � .
3.  ñëó÷àå, êîãäà
~
D D�
�
, ïðåäñòàâèì (ñì. (21)) îïåðàòîð A D( � ) â âèäå
A D K D G D( � ) ( � ) * ( � )� � � � , ãäå îïåðàòîð K D( � )� ïðîäóöèðóåò «íåçàâèñèìóþ» ÷àñòü
äàííûõ (íå ïîñòóïàþùèõ íà âõîä B D(
~
)), à îïåðàòîð G D D D( � )
~
� � � � �
�
âûðàáàòû-
âàåò ìíîæåñòâî äàííûõ, ïåðåäàâàåìûõ îïåðàòîðó B D(
~
). Î÷åâèäíûì ñëåäóþùèì
øàãîì ÿâëÿåòñÿ îáúåäèíåíèå (ñì. (20)) ñâÿçàííûõ îïåðàòîðîâ
G D B D C D( � ) * (
~
) (
~�
)� � � , â ðåçóëüòàòå ÷åãî ïîëó÷èì
A D B D K D C D( � ) * (
~
) ( � ) * (
~
)
^
� � .
 îáùåì ñëó÷àå êîìïîçèöèþ ñâÿçàííûõ îïåðàòîðîâ ðàññìîòðèì àíàëîãè÷íî
÷àñòíûì ñëó÷àÿì 2 è 3. Îïåðàòîð A D( � ) ïðåäñòàâèì â âèäå
A D K D G D( � ) ( � ) * ( � )� � � � ,
ãäå G D D D( � )
~
� � � � � �
�
îáðàáàòûâàåò ìíîæåñòâî äàííûõ, ïîñòóïàþùèõ íà âõîä
îïåðàòîðà B D(
~
), à K D( � )� — íåçàâèñèìóþ ÷àñòü äàííûõ.
Îïåðàòîð B D(
~
) ïðåäñòàâèì â âèäå
B D H D M D(
~
) (
~
) * (
~
)� � � � ,
ãäå H D(
~
)� îáðàáàòûâàåò äàííûå, ïåðåäàííûå îïåðàòîðîì G D( � )� � , à M D(
~
)� �
— íåçàâèñèìûå äàííûå.
Äàëåå, îáúåäèíèâ ñâÿçàííûå îïåðàòîðû G D H D C D( � ) * (
~
) (
~�
)� � � � ,
ïîëó÷èì
A D B D K D C D M D( � ) * (
~
) ( � ) * (
~�
) * (
~
)� � � � .
 òîì ñëó÷àå, êîãäà ïðè ðàçáèåíèè îïåðàòîðîâ óäàñòñÿ îáåñïå÷èòü èõ ïî-
ëíóþ íåçàâèñèìîñòü, ïîðÿäîê ñëåäîâàíèÿ ýòèõ îïåðàòîðîâ íå èìååò çíà÷åíèÿ â
ñîîòâåòñòâèè ñ òîæäåñòâåííûì ñîîòíîøåíèåì (14).
Çàâåðøàÿ ðàññìîòðåíèå âîçìîæíîñòåé ïðåîáðàçîâàíèÿ ñâÿçàííûõ îïåðàòî-
ðîâ, ñäåëàåì íåáîëüøîå îòñòóïëåíèå ìåòîäîëîãè÷åñêîãî õàðàêòåðà. Ìîäóëÿðèçà-
öèÿ ïðîãðàìì ïðåäïîëàãàåò, ÷òî ìîäóëü — ýòî íåáîëüøîé îáúåì êîäà, ïðåäíàç-
íà÷åííûé äëÿ ðåøåíèÿ ëîêàëüíîé çàäà÷è [7, 11]. Âîçìîæíîñòü îáúåäèíåíèÿ ñâÿ-
çàííûõ è âûäåëåíèå íåçàâèñèìûõ îïåðàòîðîâ ïîçâîëÿåò ðåøàòü çàäà÷ó
ìîäóëÿðèçàöèè (ïî êðàéíåé ìåðå, â íåêîòîðûõ ñëó÷àÿõ) íà äîñòàòî÷íî ôîðìàëü-
180 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
íîì óðîâíå. Âûñêàçàííîå ñîîáðàæåíèå â ïîëíîé ìåðå îòíîñèòñÿ è ê ïîäïðîãðàì-
ìàì, â òîì ñìûñëå, ÷òî îòêðûâàåòñÿ âîçìîæíîñòü óäàëÿòü èç ïîäïðîãðàììû îïå-
ðàòîðû, íå ñâÿçàííûå ðåøåíèåì îáùåé çàäà÷è, ìèíèìèçèðóÿ, òàêèì îáðàçîì,
îáúåì ïîäïðîãðàììû è îáåñïå÷èâàÿ åå ôóíêöèîíàëüíóþ çàâåðøåííîñòü
(çàìêíóòîñòü).
5. ÏÐÅÎÁÐÀÇÎÂÀÍÈÅ ÐÅÃÓËßÐÍÛÕ ÑÕÅÌ ÀËÃÎÐÈÒÌÎÂ
 îòíîøåíèè ïðåîáðàçîâàíèÿ àëãîðèòìè÷åñêèõ êîíñòðóêöèé â ðàìêàõ ðàññìàò-
ðèâàåìîé èíòåðïðåòàöèè ôîðìàëüíûé àïïàðàò íè÷åãî íå óòðàòèë. Ìíîãèå ïðå-
îáðàçîâàíèÿ ìîãóò áûòü ðåàëèçîâàíû áîëåå ôîðìàëüíî. Ïîêàæåì ýòî íà ïðè-
ìåðå ðàçëîæåíèÿ îïåðàöèè �-äèçúþíêöèè íà ïîñëåäîâàòåëüíûå ôèëüòðû, ÷òî
áûëî âûïîëíåíî â [8], ãäå îãðàíè÷åíèÿ íà èñïîëüçîâàíèå àíàëîãè÷íîãî ïðåîá-
ðàçîâàíèÿ ïðèâîäèëèñü íà ñîäåðæàòåëüíîì óðîâíå.  äàííîì ñëó÷àå çàïèøåì
òàêîå ïðåîáðàçîâàíèå â âèäå
[ (
~
)]( ( ) ( )) [ (
~
)]( ( )) * [ (
~
)]( (a D A D B D D A D D B D� � � � � � � �� � � )).
 ñâÿçè ñ òåì, ÷òî ëîãè÷åñêîå óñëîâèå � (
~
)D â ïðàâîé ÷àñòè âûðàæåíèÿ ïðî-
âåðÿåòñÿ äâàæäû, äëÿ ýêâèâàëåíòíîñòè ïðåîáðàçîâàíèÿ íåîáõîäèìî, ÷òîáû âû-
ïîëíÿëîñü ñîîòíîøåíèå
~
D D
� � � �, ãäå D A D� � � �( ). Åñëè äàííîå ñîîòíîøå-
íèå íå âûïîëíÿåòñÿ, îïåðàòîð ìîæíî ïåðåïèñàòü â âèäå
[ (
~
)]( ( ) ( )) [ (
~
)]( ( )) * [ (
~
)]( (� � �D A D B D D B D D A D� � � � � � � � � )),
ïîòðåáîâàâ, ÷òîáû âûïîëíÿëîñü ñîîòíîøåíèå
~
D D
� � � � �, ãäå D B D� � � � � �( ).
 ðåçóëüòàòå ìîæíî ñäåëàòü âûâîä î òîì, ÷òî â íåêîòîðûõ ñëó÷àÿõ îãðàíè÷å-
íèå íà äàííîå ïðåîáðàçîâàíèå ìîæåò áûòü ñíÿòî çà ñ÷åò âûáîðà ïîðÿäêà
ñëåäîâàíèÿ îïåðàòîðîâ.
Ïîñêîëüêó íàèáîëåå íàãëÿäíûì ñïîñîáîì ïðîäåìîíñòðèðîâàòü âîçìîæíîñòè
ïðåîáðàçîâàíèÿ ðåãóëÿðíûõ ñõåì â ðàìêàõ ïðåäëàãàåìîãî ïîäõîäà ÿâëÿåòñÿ ðåøå-
íèå êîíêðåòíîé çàäà÷è, ðàññìîòðèì ñëåäóþùóþ ýëåìåíòàðíóþ çàäà÷ó.
Èìååòñÿ äâà ìàññèâà ðàçíîé äëèíû:
X x x x Y y y yk n� �1 2 1 2, , . . . , , , , . . . , .
Íåîáõîäèìî âû÷èñëèòü ñóììó ýëåìåíòîâ ìàññèâà X , â òîì ñëó÷àå, åñëè îí
ñîäåðæèò ìåíüøå èëè ðîâíî 100 ýëåìåíòîâ.  ïðîòèâíîì ñëó÷àå, ïðè óñëî-
âèè, ÷òî ìàññèâ Y ñîäåðæèò ìåíüøå èëè ðîâíî 200 ýëåìåíòîâ, âûïîëíèòü òî
æå âû÷èñëåíèå. Åñëè ïîñëåäíåå óñëîâèå íå âûïîëíÿåòñÿ, âû÷èñëèòü ñóììó
ýëåìåíòîâ ìàññèâà Y .
Çàïèøåì àëãîðèòì, êîòîðûé íàçîâåì ÑÓÌÌ, â âèäå ðåãóëÿðíîé ñõåìû
SUMM sum sum sum( , ) [ ( )]( ( ) [ ( )]( ( ) ( )))X Y k X n X Y� � �� � ,
ãäå � — óñëîâèå k � 100; � — óñëîâèå n � 200; sum sum( ), ( )X Y — îïåðàòî-
ðû, ñóììèðóþùèå ýëåìåíòû ìàññèâîâ X è Y ñîîòâåòñòâåííî.
Ó÷èòûâàÿ, ÷òî îïåðàöèÿ ñóììèðîâàíèÿ ïîâòîðÿåòñÿ, îôîðìèì åå â âèäå ïðî-
öåäóðû â ñîîòâåòñòâèè ñ îïðåäåëåíèåì (19) è çàïèøåì î÷åðåäíîé âàðèàíò
àëãîðèòìà â âèäå
SUÌÌ sum( , ) [ ( )]( ( , ; ; )X Y k X k A� �� �
� � � �([ ( )]( ( , ; ; ) ( , ; ; )))� n X k A Y n A� �sum sum ,
ãäå X k Y n, , , — ôàêòè÷åñêèå âõîäíûå ïàðàìåòðû, A — ôàêòè÷åñêèé âûõîä-
íîé ïàðàìåòð, ìíîæåñòâî ôàêòè÷åñêèõ ïðîõîäíûõ ïàðàìåòðîâ ïóñòî.
Äàëåå, âîñïîëüçîâàâøèñü ïîñòðîåííîé îïåðàöèåé èòåðàöèè òèïà for (18),
îïðåäåëèì ïîäïðîãðàììó (î ÷åì óïîìèíàëîñü â ðàçä. 3) ñëåäóþùèì îáðàçîì:
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 181
� sum { }( , ; ; ) ( )( ) ( ( ), )Z m L s zI j p S j m j� � � � .
Çäåñü s z j( ) — îïåðàòîð, îñóùåñòâëÿþùèé ñóììèðîâàíèå ýëåìåíòîâ ìàññèâà,
Z m, — âõîäíûå ôîðìàëüíûå ïàðàìåòðû, L — âûõîäíîé ôîðìàëüíûé ïàðà-
ìåòð, à ìíîæåñòâî ïðîõîäíûõ ôîðìàëüíûõ ïàðàìåòðîâ ïóñòî.
Íàêîíåö, âîñïîëüçîâàâøèñü òîæäåñòâåííûì ñîîòíîøåíèåì [8] âèäà
[ ( )]( ( � )) [ ( )]( ( � ) (
~
))� �D A D D A D B D� � � � � � �[ ( ) ( )]( ( � ) (
~
))� �D D A D B D ,
ìîæíî, îñóùåñòâèâ íàèáîëåå ýôôåêòèâíîå ïðåîáðàçîâàíèå, ñâåñòè ðåãóëÿðíóþ
ñõåìó ê âèäó
SUMM sum sum( , ) [ ( ) ( )]( ( , ; ; ) ( , ; ; ))X Y k n X k A Y n A� � � � �� � � � .
ÇÀÊËÞ×ÅÍÈÅ
Îñíîâíûì ðåçóëüòàòîì äàííîé ðàáîòû ÿâëÿåòñÿ î÷åðåäíîé øàã â íàïðàâëåíèè
ðàçâèòèÿ ôîðìàëüíîãî àïïàðàòà, îðèåíòèðîâàííîãî íà ðàçðàáîòêó àëãîðèòìîâ
è ïðîãðàìì.  ÷àñòíîñòè, óäàëîñü íà äîñòàòî÷íî ôîðìàëüíîì óðîâíå ñïåöè-
ôèöèðîâàòü âçàèìîñâÿçü îïåðàòîðîâ è äàííûõ, ÷òî, ïðè ñîõðàíåíèè ñóùåñòâó-
þùèõ, îòêðûëî íîâûå âîçìîæíîñòè ïî ïîñòðîåíèþ ïðîèçâîäíûõ àëãîðèòìè-
÷åñêèõ êîíñòðóêöèé è ïðåîáðàçîâàíèþ ðåãóëÿðíûõ ñõåì. Ïðè ýòîì íîâûå àë-
ãîðèòìè÷åñêèå êîíñòðóêöèè ìîãóò ñòðîèòüñÿ îðèåíòèðîâàííûìè êàê íà êëàññ
ðåøàåìûõ çàäà÷, òàê è íà âîçìîæíîñòè ÿçûêà, íà êîòîðîì ðàçðàáàòûâàåìûé
àëãîðèòì áóäåò ðåàëèçîâûâàòüñÿ. Äîñòàòî÷íî âàæíûì ðåçóëüòàòîì ÿâëÿþòñÿ
íîâûå ñðåäñòâà ðåøåíèÿ òàêîé àêòóàëüíîé ìåòîäîëîãè÷åñêîé çàäà÷è, êàê
ìîäóëÿðèçàöèÿ àëãîðèòìà.
Äàëüíåéøåå ðàçâèòèå ïîëó÷åííûõ ðåçóëüòàòîâ ïðåäïîëàãàåòñÿ ïðîâîäèòü â
íàïðàâëåíèè ðàñøèðåíèÿ âîçìîæíîñòåé ôîðìàëüíîãî àïïàðàòà ïî ïîñòðîåíèþ è
ïðåîáðàçîâàíèþ ðåãóëÿðíûõ ñõåì àëãîðèòìîâ, à òàêæå ðåøåíèÿ çàäà÷
ìåòîäîëîãè÷åñêîãî õàðàêòåðà.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ã ë ó ø ê î â Â . Ì . Òåîðèÿ àâòîìàòîâ è ôîðìàëüíûå ïðåîáðàçîâàíèÿ ìèêðîïðîãðàìì //
Êèáåðíåòèêà. — 1965. — ¹ 5. — Ñ. 1–10.
2. Ã ë ó ø ê î â Â . Ì . , Ö å é ò ë è í Ã . Å . , Þ ù å í ê î Å . Ë . Àëãåáðà. ßçûêè.
Ïðîãðàììèðîâàíèå. — Ê.: Íàóê. äóìêà, 1978. — 319 ñ.
3. Þ ù å í ê î Å . Ë . , Ö å é ò ë è í Ã . Å . , Ã ð è ö à é Â . Ï . , Ò å ð ç ÿ í Ò . Ê .
Ìíîãîóðîâíåâîå ñòðóêòóðíîå ïðîåêòèðîâàíèå ïðîãðàìì: Òåîðåòè÷åñêèå îñíîâû,
èíñòðóìåíòàðèé. — Ì.: Ôèíàíñû è ñòàòèñòèêà, 1989. — 208 ñ.
4. Ö å é ò ë è í Ã . Å . Ââåäåíèå â àëãîðèòìèêó. — Ê.: Ñôåðà, 1998. — 310 ñ.
5. Ö å é ò ë è í à . Å . Àëãîðèòìè÷åñêàÿ àëãåáðà ñòðóêòóð äàííûõ è ìíîãîóðîâíåâîå
ïðîåêòèðîâàíèå ïðîãðàìì // Ïðîãðàììèðîâàíèå. — 1986. — ¹ 3. — Ñ. 8–16.
6. Ö å é ò ë è í Ã . Å . , Á à ê ó ë è í À . Â . Ìíîãîóðîâíåâûå ñòðóêòóðèðîâàííûå ïðîåêòû ïðîãðàìì
è èõ îáîñíîâàíèå // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 1991. — ¹ 5. — Ñ. 98–107.
7. Ò ó ð ñ ê è é Â . Ìåòîäîëîãèÿ ïðîãðàììèðîâàíèÿ. — Ì.: Ìèð, 1981. — 264 ñ.
8. À ê ó ë î â ñ ê è é Â . Ã . Ðàñøèðåííàÿ àëãåáðà àëãîðèòìîâ // Ïðîáëåìè ïðîãðàìóâàííÿ. —
2007. — ¹ 3. — C. 3–15.
9. À ê ó ë î â ñ ü ê è é  . à . , Ê î ñ ò å í ê î  .  . Òðèçíà÷íà ëîãŸêà â àëãåáðŸ àëãîðèòìŸâ //
Ÿñí. Àêàä. ìèòí. ñëóæáè ÓêðàÂíè. — 2007. — ¹ 1. — Ñ. 83–88.
10. Ï î ñ ï å ë î â Ä . À . Ëîãè÷åñêèå ìåòîäû àíàëèçà è ñèíòåçà ñõåì. — Èçä. 3-å, ïåðåðàá. è äîï.
— Ì.: Ýíåðãèÿ, 1974. — 368 ñ.
11. Ì å é å ð Á . , Á î ä ó ý í Ê . Ìåòîäû ïðîãðàììèðîâàíèÿ. — Ì.: Ìèð, 1982. — Ò. 1. — 356 ñ.
Ïîñòóïèëà 27.07.2007
182 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
|
| id | nasplib_isofts_kiev_ua-123456789-44285 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T18:45:30Z |
| publishDate | 2008 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Акуловский, В.Г. 2013-05-27T18:11:30Z 2013-05-27T18:11:30Z 2008 Формализация взаимосвязей операторов и данных в рамках расширенной алгебры алгоритмов / В.Г. Акуловский // Кибернетика и системный анализ. — 2008. — № 6. — С. 170-182. — Бібліогр.: 11 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/44285 519.681 ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Программно-технические комплексы Формализация взаимосвязей операторов и данных в рамках расширенной алгебры алгоритмов Article published earlier |
| spellingShingle | Формализация взаимосвязей операторов и данных в рамках расширенной алгебры алгоритмов Акуловский, В.Г. Программно-технические комплексы |
| title | Формализация взаимосвязей операторов и данных в рамках расширенной алгебры алгоритмов |
| title_full | Формализация взаимосвязей операторов и данных в рамках расширенной алгебры алгоритмов |
| title_fullStr | Формализация взаимосвязей операторов и данных в рамках расширенной алгебры алгоритмов |
| title_full_unstemmed | Формализация взаимосвязей операторов и данных в рамках расширенной алгебры алгоритмов |
| title_short | Формализация взаимосвязей операторов и данных в рамках расширенной алгебры алгоритмов |
| title_sort | формализация взаимосвязей операторов и данных в рамках расширенной алгебры алгоритмов |
| topic | Программно-технические комплексы |
| topic_facet | Программно-технические комплексы |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/44285 |
| work_keys_str_mv | AT akulovskiivg formalizaciâvzaimosvâzeioperatorovidannyhvramkahrasširennoialgebryalgoritmov |