Некоторые аспекты преобразования алгоритмов на основе формализации информационных связей
У рамках алгебраїчного апарату здійснено формалізацію інформаційних зв’язків між операторами, що входять в регулярні схеми, за допомогою яких описуються алгоритми. На основі проведеної формалізації показано можливість специфікації таких зв’язків і доведено можливість перетворення регулярних схем з м...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2009 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/44482 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Некоторые аспекты преобразования алгоритмов на основе формализации информационных связей / В.Г. Акуловский // Кибернетика и системный анализ. — 2009. — № 6. — С. 50-54. — Бібліогр.: 5 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860085173507325952 |
|---|---|
| author | Акуловский, В.Г. |
| author_facet | Акуловский, В.Г. |
| citation_txt | Некоторые аспекты преобразования алгоритмов на основе формализации информационных связей / В.Г. Акуловский // Кибернетика и системный анализ. — 2009. — № 6. — С. 50-54. — Бібліогр.: 5 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | У рамках алгебраїчного апарату здійснено формалізацію інформаційних зв’язків між операторами, що входять в регулярні схеми, за допомогою яких описуються алгоритми. На основі проведеної формалізації показано можливість специфікації таких зв’язків і доведено можливість перетворення регулярних схем з метою зменшення довжини зв’язків між операторами.
Algebraic tools are used to formalize information connections between operators that appear in regular circuits and describe algorithms. Based on the formalization, it is shown that such connections can be specified and regular circuits can be transformed to reduce the length of connections between operators.
|
| first_indexed | 2025-12-07T17:19:12Z |
| format | Article |
| fulltext |
ÓÄÊ 519.683
Â.Ã. ÀÊÓËÎÂÑÊÈÉ
ÍÅÊÎÒÎÐÛÅ ÀÑÏÅÊÒÛ ÏÐÅÎÁÐÀÇÎÂÀÍÈß ÀËÃÎÐÈÒÌÎÂ
ÍÀ ÎÑÍÎÂÅ ÔÎÐÌÀËÈÇÀÖÈÈ ÈÍÔÎÐÌÀÖÈÎÍÍÛÕ ÑÂßÇÅÉ
Êëþ÷åâûå ñëîâà: àëãåáðà àëãîðèòìîâ, ðåãóëÿðíûå ñõåìû, ôîðìàëèçàöèÿ äàí-
íûõ, èíôîðìàöèîííûå ñâÿçè, ïðåîáðàçîâàíèå àëãîðèòìîâ.
Ââåäåíèå. Â íàñòîÿùåå âðåìÿ ïðèçíàíà ïðèíöèïèàëüíî âàæíàÿ ðîëü äàííûõ, îá-
ðàçóþùèõ èíôîðìàöèîííûå ñâÿçè â àëãîðèòìàõ è ïðîãðàììàõ, [1], îäíàêî â ñî-
âðåìåííûõ ñðåäñòâàõ ðàçðàáîòêè (íàïðèìåð, â òàêîì èçâåñòíîì ñðåäñòâå êàê
UML [2]) ïîòîêè óïðàâëåíèÿ è èíôîðìàöèîííûå ñâÿçè â àëãîðèòìàõ ðàññìàòðè-
âàþòñÿ íåçàâèñèìî.  ðåçóëüòàòå íå îáåñïå÷èâàåòñÿ ïîëíîòà îïèñàíèÿ àëãîðèò-
ìîâ è âîçíèêàåò âåðîÿòíîñòü ïîÿâëåíèÿ îøèáîê, âûçâàííûõ íåñîãëàñîâàííîñòüþ
ñïåöèôèêàöèé ýòèõ àñïåêòîâ àëãîðèòìèçàöèè, ïðè÷åì èñïîëüçóþòñÿ ãðàôè÷åñ-
êèå, ò.å. íåäîñòàòî÷íî ôîðìàëèçîâàííûå ñðåäñòâà îïèñàíèÿ àëãîðèòìîâ.
Âìåñòå ñ òåì ñîãëàñîâàííîå ðàññìîòðåíèå ïîòîêîâ óïðàâëåíèÿ è èíôîðìàöè-
îííûõ ñâÿçåé â àëãîðèòìàõ ïîçâîëÿåò íå òîëüêî óñòðàíèòü (ïî êðàéíåé ìåðå, îñëà-
áèòü) îòìå÷åííûå íåäîñòàòêè, íî è, ñïåöèôèöèðîâàâ èíôîðìàöèîííûå ñâÿçè â àë-
ãîðèòìàõ, îñóùåñòâèòü èõ îïòèìèçèðóþùèå ïðåîáðàçîâàíèÿ. Îòìåòèì, ÷òî â ðàì-
êàõ àëãåáðû àëãîðèòìîâ ýòè âîïðîñû ðàíåå íå ðàññìàòðèâàëèñü.
Ñôîðìóëèðóåì ñâîéñòâà àëãîðèòìîâ, íà äîñòèæåíèå êîòîðûõ íàïðàâëåíû ïîëó-
÷åííûå ðåçóëüòàòû. Íàèáîëåå êà÷åñòâåííûì (÷èòàáåëüíûì, ëåãêî îòëàæèâàåìûì è ñî-
ïðîâîæäàåìûì), î÷åâèäíî, ÿâëÿåòñÿ àëãîðèòì, ñîäåðæàùèé ìèíèìàëüíîå ÷èñëî êîðîò-
êèõ ñâÿçåé. Ðåàëüíûå àëãîðèòìû òàêèìè ñâîéñòâàìè îáëàäàþò äîñòàòî÷íî ðåäêî.
 ñâÿçè ñ ýòèì öåëü äàííîé ðàáîòû — ôîðìàëèçàöèÿ (â ðàìêàõ àëãåáðàè-
÷åñêîãî àïïàðàòà) è ñïåöèôèêàöèÿ èíôîðìàöèîííûõ ñâÿçåé â àëãîðèòìå è äîêà-
çàòåëüñòâî âîçìîæíîñòè íåêîòîðûõ îïòèìèçèðóþùèõ ïðåîáðàçîâàíèé àëãîðèòìîâ.
Ïðè ýòîì îãðàíè÷èìñÿ òåì, ÷òî ïîêàæåì âîçìîæíîñòü ñîêðàùåíèÿ äëèíû èíôîð-
ìàöèîííûõ ñâÿçåé â ðåçóëüòàòå ïðåîáðàçîâàíèÿ àëãîðèòìîâ.
50 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
� Â.Ã. Àêóëîâñêèé, 2009
Èñõîäíûå îïðåäåëåíèÿ.  êà÷åñòâå ôîðìàëüíîãî àïïàðàòà èñïîëüçóåì ðàñøè-
ðåííóþ àëãåáðó àëãîðèòìîâ (ÑÀÀ-Ð) [3], â êîòîðîé ââåäåíî ïîíÿòèå âçàèìîñâÿçè
îïåðàòîðîâ è äàííûõ, îïåðàòîðû îïðåäåëåíû â âèäå ( ) ( )D A D� , ÷òî ïîçâîëèëî ñïå-
öèôèöèðîâàòü âõîäíûå D è âûõîäíûå �D äàííûå äëÿ êàæäîãî îïåðàòîðà.  êà÷åñòâå
ìåòîäà ðàçðàáîòêè èñïîëüçîâàí ìåòîä ñòðóêòóðíîãî ïðîåêòèðîâàíèÿ ïðîãðàìì
(ÌÑÏÏ) [4], â ðàìêàõ êîòîðîãî àëãîðèòìû çàïèñûâàþòñÿ â âèäå ðåãóëÿðíûõ ñõåì
(ÐÑ). Â êîíòåêñòå äàííîé ðàáîòû ÐÑ îïðåäåëèì ñëåäóþùèì îáðàçîì.
Îïðåäåëåíèå 1. ÐÑ áóäåì íàçûâàòü âûðàæåíèå âèäà
( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) (D A D D A D D A D D A Di i i� � � � � � � � � �
1 1 1 2 2 2 � � D A Dn n n) ( )� , (1)
ãäå ( ) ( )D A D� — èñõîäíûé îïåðàòîð, ëþáîé îïåðàòîð ( ) ( )D A Di i i� , ðåçóëüòèðóþ-
ùèé íèæíèé èíäåêñ — ïîðÿäêîâûé íîìåð îïåðàòîðà. Â äàííîì âûðàæåíèè ðå-
çóëüòèðóþùèå îïåðàòîðû âûïîëíÿþòñÿ ïîñëåäîâàòåëüíî è èõ ñóììàðíàÿ ôóíê-
öèîíàëüíîñòü àäåêâàòíà ôóíêöèîíàëüíîñòè èñõîäíîãî îïåðàòîðà.
Ïåðåõîäÿ ê ôîðìàëèçàöèè èíôîðìàöèîííûõ ñâÿçåé, ââåäåì ñ ó÷åòîì îïðåäå-
ëåíèÿ 1 ïîíÿòèå ñâÿçàííûõ îïåðàòîðîâ.
Îïðåäåëåíèå 2. Îïåðàòîðû ( ) ( )D A Di i i� è ( ) ( )D A Dj j j� (ãäå i j� ), âõîäÿùèå â
ÐÑ (1), ñâÿçàíû, åñëè äëÿ íèõ âûïîëíÿåòñÿ ñîîòíîøåíèå � � � �D Di j , ò.å. íåêîòî-
ðîå ïîäìíîæåñòâî âûõîäíûõ äàííûõ îïåðàòîðà ( ) ( )D A Di i i� ïîñòóïàåò íà âõîä
îïåðàòîðà ( ) ( )D A Dj j j� . Áóäåì ãîâîðèòü, ÷òî ìíîæåñòâî äàííûõ i j i jD D D
�
� � �
( i j iD D
�
� è i j iD D
�
) ñâÿçûâàåò îïåðàòîðû A
i
è A
j
(íà ÷òî óêàçûâàþò èñïîëüçó-
åìûå èíäåêñû) è ýòè äàííûå áóäåì íàçûâàòü ñâÿçûâàþùèìè.
Èç îïðåäåëåíèÿ 2 ñëåäóåò, ÷òî äàííûå ìîãóò ïåðåäàâàòüñÿ îò ëþáîãî îïåðàòî-
ðà ê îäíîìó èëè íåñêîëüêèì ñëåäóþùèì îïåðàòîðàì, ò.å. ñëåâà íàïðàâî è èìåííî
ñâÿçûâàþùèå äàííûå îáðàçóþò èíôîðìàöèîííûå ñâÿçè â ÐÑ. Ïðè ýòîì â îáùåì
ñëó÷àå íåêîòîðûé îïåðàòîð ìîæåò áûòü ñâÿçàí ñî âñåìè ñëåäóþùèìè çà íèì è âñå-
ìè ïðåäøåñòâóþùèìè åìó îïåðàòîðàìè.
Èñïîëüçóÿ îïðåäåëåíèÿ 1 è 2, ñïåöèôèöèðóåì â ÐÑ (1) èíôîðìàöèîííûå ñâÿçè.
Äåòàëèçèðóåì âõîäíûå è âûõîäíûå äàííûå îïåðàòîðîâ è äîïîëíèì ñèñòåìó îáîçíà-
÷åíèé. Äàííûå íà âõîäå j-ãî îïåðàòîðà, ñâÿçûâàþùèå åãî ñ k-ì, îáîçíà÷èì k jD
�
(ãäå k — «àäðåñ èñòî÷íèêà», j — «àäðåñ ïðèåìíèêà» äàííûõ), à íà âûõîäå, ñâÿçûâàþ-
ùèå åãî ñ p-ì, — j pD
�
(ãäå j — «àäðåñ èñòî÷íèêà», p — «àäðåñ ïðèåìíèêà» äàííûõ).
Ïåðåïèøåì ÐÑ (1) ñ ó÷åòîì ââåäåííûõ îáîçíà÷åíèé:
( ) ( ) ( ) ( , , , , , , )*D A D D A D D D D Dj n� � �1 1 1 1 2 1 3 1 1
� �
�
�
�
�
* ( , ) ( , , , , , )*D D A D D D Dj n2 1 2 2 2 2 3 2 2
� �
�
�
�
�
��
�
�
�
�
�
� �
�
�
�* ( , , , , , ) ( , , , , ,D D D D A D D Dj j l j j j j j j j j p1 1 1
�� n nD
�
�)*
�
�
�
�
�
�
* ( , , , , , ) ( )D D D D A Dn n j n n n n n1 1
� . (2)
 ïîñòðîåííîé ÐÑ íå òîëüêî ñïåöèôèöèðîâàíû äàííûå è ñâÿçè ìåæäó îïåðà-
òîðàìè, íî è âñå «èñòî÷íèêè» è «ïðèåìíèêè» äàííûõ ïîñòàâëåíû â îäíîçíà÷íîå
ñîîòâåòñòâèå, ò.å. ëþáîìó l pD
�
ñîîòâåòñòâóåò l pD
�
. Ïîñêîëüêó â ÐÑ, êàê ïðàâèëî,
íå âñå îïåðàòîðû ñâÿçàíû äðóã ñ äðóãîì, ëþáîå èç ìíîæåñòâ l pD
�
ìîæåò áûòü ïóñ-
òûì è ñîîòâåòñòâåííî ïóñòûì áóäåò è ìíîæåñòâî l pD
�
.
Íà îñíîâå ñïåöèôèöèðîâàííûõ ñâÿçåé ðåøàåì çàäà÷ó îïòèìèçèðóþùåãî ïðå-
îáðàçîâàíèÿ àëãîðèòìîâ.
Ïðåîáðàçîâàíèå àëãîðèòìîâ. Íà÷íåì ñ îïðåäåëåíèÿ ïîíÿòèÿ ñâÿçåé ìåæäó
îïåðàòîðàìè â ÐÑ (2).
Îïðåäåëåíèå 3. Ìíîæåñòâî S D D D Dj j j l j j j
ë �
1 2 1
� �
�
�
�
�
, , , , , íàçîâåì ìíî-
æåñòâîì ëåâûõ ñâÿçåé j-ãî îïåðàòîðà, à ìíîæåñòâî S D D
j j j j j
ïð � � �
� �
�1 2, ,
�
�
�
�
, , ,j p j nD D — ìíîæåñòâîì åãî ïðàâûõ ñâÿçåé è áóäåì ðàçëè÷àòü òðè òèïà îïå-
ðàòîðîâ:
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 51
� ñâÿçàííûå, ó êîòîðûõ S j
ë
� è S
j
ïð
�;
� ñâÿçàííûå ñëåâà (ñïðàâà), ó êîòîðûõ S j
ë
�, à S
j
ïð � � (S
j
ïð
�, à S j
ë � �);
� íå ñâÿçàííûå, ó êîòîðûõ S j
ë
� è S
j
ïð � �.
Ìíîæåñòâî S D D D D D Dj j n j n j j j
o � � �
�
1 1 1 2 1 2 1 1 1
�
�
� �
�
�
�
�
�
�
, , , , , , , , , n íàçî-
âåì ìíîæåñòâîì ñâÿçåé, îõâàòûâàþùèõ (îãèáàþùèõ) j-é îïåðàòîð. Êîëè÷åñòâî
îãèáàþùèõ ñâÿçåé îïåðàòîðà A j îïðåäåëèì êàê K Sj j
o o� | | . Ëþáîå èç ìíîæåñòâ
j lD
�
( r sD
�
), âõîäÿùèõ â ìíîæåñòâà S j
ë , S
j
ïð , S j
î , ìîæåò áûòü ïóñòûì è â ýòîì ñëó-
÷àå îíî èç ðàññìîòðåíèÿ èñêëþ÷àåòñÿ. Îòñþäà ñëåäóåò, ÷òî ìíîæåñòâà S j
ë , S
j
ïð , S j
î
òàêæå ìîãóò áûòü ïóñòûìè.
Òåïåðü ââåäåì è îïðåäåëèì ïîíÿòèå äëèíû èíôîðìàöèîííûõ ñâÿçåé.
Îïðåäåëåíèå 4. Äëèíó ïðîèçâîëüíîé ñâÿçè ìåæäó îïåðàòîðàìè Ai è A j îïðå-
äåëèì äëÿ ñëó÷àÿ i j� êàê i jd j i�
, à äëÿ ñëó÷àÿ j i� — êàê i jd i j�
.
Èñõîäÿ èç îïðåäåëåíèé 3 è 4, îáùóþ (ñóììàðíóþ) äëèíó ëåâûõ (ïðàâûõ) ñâÿ-
çåé îïåðàòîðà Ak çàïèøåì L d
k p k
p
k
ë �
�
�
1
1
(L d
k k p
p k
n
ïð �
� �
�
1
), à îáùóþ äëèíó îãèáàþ-
ùèõ k-é îïåðàòîð ñâÿçåé — â âèäå L d
k l r
p k
n
l
k
o �
� ��
��
11
1
. Âî âñåõ ñëó÷àÿõ ëþáîé èç ýëå-
ìåíòîâ i jd , âõîäÿùèõ â ïðèâåäåííûå âûðàæåíèÿ (â ñîîòâåòñòâèè ñ îïðåäåëåíè-
åì 3), ìîæåò áûòü ðàâåí íóëþ.
Ó÷èòûâàÿ, ÷òî êðîìå ðàññìîòðåííûõ ñâÿçåé ñóùåñòâóþò è äðóãèå èõ âèäû, êîòî-
ðûå â [5] íàçâàíû îáðàòíûìè, ïðèâåäåì îïðåäåëåíèÿ ëîêàëüíî íåçàâèñèìûõ îïåðàòîðîâ.
Îïðåäåëåíèå 5. Ëîêàëüíî íåçàâèñèìûìè íàçîâåì ëþáûå äâà íå ñâÿçàííûõ
(ñì. îïðåäåëåíèå 2) îïåðàòîðà ( ) ( )* ( � ) ( � )D A D D B D� � , åñëè äëÿ íèõ âûïîëíÿþòñÿ
ñëåäóþùèå îãðàíè÷åíèÿ: D D� � �� , D D� � � �� , � � � � �D D� , ò.å. ýòè îïåðàòîðû íå
èìåþò íèêàêèõ èíôîðìàöèîííûõ ñâÿçåé ìåæäó ñîáîé. Â ðåçóëüòàòå äëÿ íèõ âûïîë-
íÿåòñÿ òîæäåñòâåííîå ñîîòíîøåíèå ( ) ( )* ( � ) ( � ) ( � ) ( � )* ( ) ( )D A D D B D D B D D A D� � � � � ,
ò.å. îïåðàòîðû ìîãóò ïåðåìåùàòüñÿ â ðàìêàõ ÐÑ.
Äàëåå, îáîáùàÿ îïðåäåëåíèÿ 5, ââåäåì ïîíÿòèå îáëàñòè íåçàâèñèìîñòè.
Îïðåäåëåíèå 6. Îáëàñòüþ íåçàâèñèìîñòè ñëåâà îò îïåðàòîðà ( ) ( )D A Di i i� ,
âõîäÿùåãî â ÐÑ (1), íàçîâåì íåïðåðûâíóþ ïîñëåäîâàòåëüíîñòü îïåðàòîðîâ
( ) ( )* * ( ) ( )D A D D A Dm m m i i i� �
� 1 1 1 , ãäå îïåðàòîð íå ñâÿçàí ñ äàííûì (ñì. îïðå-
äåëåíèå 2) è ïðåäøåñòâóåò åìó (ñì. îïðåäåëåíèå 1) è äëÿ êàæäîãî âûïîëíÿþòñÿ ñî-
îòíîøåíèÿ èç îïðåäåëåíèÿ 5.  ðàññìàòðèâàåìîì (áîëåå îáùåì) ñëó÷àå ýòè ñîîòíî-
øåíèÿ ïðåäñòàâëÿþò
D DP
p m
i
i
�
�
�
�
�
�
�
�
�
� �
1
� � , D DP
p m
i
i
�
�
�
�
�
�
�
�
�
� � �
1
� � , �
�
�
�
�
�
�
�
�
� � �
�
D DP
p m
i
i
1
� � , (3)
ãäå m i�
1. Îáëàñòü íåçàâèñèìîñòè ñïðàâà îò îïåðàòîðà ( ) ( )D A Di i i� îïðåäåëÿ-
åòñÿ àíàëîãè÷íî è ôîðìàëüíî çàïèñûâàåòñÿ â âèäå ñîîòíîøåíèé
D Di P
p i
r
� �
� �
�
�
�
�
�
�
�
�
� �
1
, D Di P
p i
r
� � �
�
�
�
�
�
�
�
�
� �
� �1
, � �
�
�
�
�
�
�
�
�
� �
� �
D Di P
p i
r
� �
1
, (4)
ãäå r i� � 1. Áóäåì ãîâîðèòü, ÷òî îïåðàòîð ( ) ( )D A Di i i� îáëàäàåò îáëàñòüþ íåçà-
âèñèìîñòè, åñëè äëÿ íåãî âûïîëíÿþòñÿ ñîîòíîøåíèÿ (3) è/èëè (4).
Èñõîäÿ èç îïðåäåëåíèé 5 è 6, áóäåì óòâåðæäàòü, ÷òî êàæäûé îïåðàòîð â ñâîåé
îáëàñòè íåçàâèñèìîñòè íå èìååò íèêàêèõ èíôîðìàöèîííûõ ñâÿçåé è ìîæåò áûòü
ïåðåìåùåí â ðàìêàõ ýòîé îáëàñòè.
Äîêàæåì, ÷òî ïåðåìåùåíèå îïåðàòîðîâ â ðàìêàõ èõ çîíû íåçàâèñèìîñòè ìî-
æåò îáåñïå÷èòü ñîêðàùåíèå äëèíû èíôîðìàöèîííûõ ñâÿçåé â ÐÑ.
52 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
Òåîðåìà. Â ëþáîé ÐÑ, ñîäåðæàùåé îïåðàòîðû, îáëàäàþùèå îáëàñòÿìè íåçàâè-
ñèìîñòè, äëèíà èíôîðìàöèîííûõ ñâÿçåé ñîêðàòèòñÿ â ðåçóëüòàòå ïåðåìåùåíèÿ ýòèõ
îïåðàòîðîâ â ðàìêàõ èõ îáëàñòåé íåçàâèñèìîñòè ïðè âûïîëíåíèè ñëåäóþùèõ óñëî-
âèé. Åñëè íåêîòîðûé îïåðàòîð Ai â ðåçóëüòàòå ïåðåìåùåíèÿ è ïåðåíóìåðàöèè îïåðà-
òîðîâ ñòàíîâèòñÿ j-ì (A j ), òî â çàâèñèìîñòè îò åãî òèïà (ñì. îïðåäåëåíèå 3) äëèíà
èíôîðìàöèîííûõ ñâÿçåé â ÐÑ ñîêðàòèòñÿ ïðè óñëîâèè âûïîëíåíèÿ ñîîòíîøåíèé:
1) äëÿ íå ñâÿçàííûõ îïåðàòîðîâ ïðè ïåðåìåùåíèè â ïðîèçâîëüíîì íàïðàâëå-
íèè L Lj i
o o� � , ïðè ýòîì ïåðåìåùåíèå 1- è n-ãî (ïîñëåäíåãî) îïåðàòîðîâ ê ñîêðàùå-
íèþ ñâÿçåé íå ïðèâåäåò;
2) äëÿ ñâÿçàííûõ ñëåâà (ñïðàâà) îïåðàòîðîâ ïðè ïåðåìåùåíèÿ èõ âëåâî (âïðà-
âî) L Lj i j
o o ë� �� � (L Lj i j
o o ïð� �� � ), à äëÿ 1- è n-ãî ñîîòâåòñòâåííî L j
o ïð� �
1
è L j n
o ë� � ;
3) äëÿ ñâÿçàííûõ îïåðàòîðîâ ïðè ïåðåìåùåíèÿ âëåâî (âïðàâî) L j j
o ïð� ��
� ��Li j
o ë� (L Lj j i j
o ë o ï� � �� �� ð
).
Âî âñåõ ïðèâåäåííûõ ñëó÷àÿõ L j
o — äëèíà ñâÿçåé, îãèáàþùèõ îïåðàòîð A j (â íî-
âîì ìåñòå ðàñïîëîæåíèÿ), à �L j
o — äëèíà ýòèõ ñâÿçåé â èñõîäíîì ìåñòå ðàñïîëîæåíèÿ,
ïîñëå óäàëåíèÿ îïåðàòîðà Ai , � �
j j
ïð ë( ) — âåëè÷èíà, íà êîòîðóþ ñîêðàòèòñÿ îáùàÿ
äëèíà ïðàâûõ (ëåâûõ) ñâÿçåé, � �
j j
ïð ë
( ) — ïðèðîñò îáùåé äëèíû ïðàâûõ (ëåâûõ) ñâÿ-
çåé â ðåçóëüòàòå ïåðåìåùåíèÿ îïåðàòîðà â åãî íîâîå ìåñòî ðàñïîëîæåíèÿ.
Äîêàçàòåëüñòâî. Ïðè ïåðåìåùåíèè îïåðàòîðîâ â èõ îáëàñòè íåçàâèñèìîñòè íà
èçìåíåíèå äëèíû ñâÿçåé â ÐÑ âëèÿþò òðè (è òîëüêî òðè) ôàêòîðà: ñîêðàùåíèå îáùåé
äëèíû îãèáàþùèõ ñâÿçåé â ìåñòå óäàëåíèÿ îïåðàòîðà è åå óâåëè÷åíèå â ìåñòå âñòàâêè
îïåðàòîðà, ñîêðàùåíèå ëåâûõ (ïðàâûõ) ñâÿçåé ïðè ïåðåìåùåíèè îïåðàòîðà âëåâî
(âïðàâî), óäëèíåíèå ëåâûõ (ïðàâûõ) ñâÿçåé ïðè ïåðåìåùåíèè îïåðàòîðà âïðàâî (âëå-
âî). Íèêàêèì äðóãèì èçìåíåíèÿì èíôîðìàöèîííûå ñâÿçè íå ïîäâåðãàþòñÿ.
Ïåðâûé ôàêòîð. Ðàçîáüåì åãî íà äâà ýòàïà.
Ýòàï 1. Âî âñåõ ñëó÷àÿõ, êîãäà íåêîòîðûé îïåðàòîð Ai èçâëåêàåòñÿ èç ïîñëå-
äîâàòåëüíîñòè îïåðàòîðîâ, îáðàçóþùèõ åãî îáëàñòü íåçàâèñèìîñòè, à îïåðàòîðû,
âõîäÿùèå â ÐÑ, ïåðåíóìåðîâûâàþòñÿ, äëèíà êàæäîé îòäåëüíîé, îãèáàþùåé ýòîò
îïåðàòîð ñâÿçè, ñîêðàòèòñÿ íà åäèíèöó. Ýòî ñëåäóåò èç îïðåäåëåíèÿ 4 è òîãî ôàêòà,
÷òî âñå èíäåêñû â äèàïàçîíå îò i � 1äî n óìåíüøàòñÿ íà åäèíèöó. Ñóììàðíóþ äëèíó
îãèáàþùèõ ñâÿçåé, ïîëó÷åííóþ ïîñëå èçâëå÷åíèÿ i-ãî îïåðàòîðà, çàïèøåì
�L L Ki i i
o o o�
(ãäå Li
o — èñõîäíàÿ äëèíà ýòèõ ñâÿçåé, à K i
o — èõ êîëè÷åñòâî).
Ýòàï 2. Âî âñåõ ñëó÷àÿõ, êîãäà èçâëå÷åííûé ðàíåå îïåðàòîð Ai âñòàâëÿåòñÿ â ïî-
ñëåäîâàòåëüíîñòü îïåðàòîðîâ, îáðàçóþùèõ åãî îáëàñòü íåçàâèñèìîñòè, è ïîñëå ïåðåíó-
ìåðàöèè ïîëó÷àåò íîìåð j (A j ) , óâåëè÷èòñÿ íà 1 êàæäàÿ îòäåëüíàÿ èñõîäíàÿ ñâÿçü, êî-
òîðàÿ ïîñëå âñòàâêè îïåðàòîðà A j áóäåò åãî îõâàòûâàòü. Ýòî ñëåäóåò èç îïðåäåëåíèÿ 4
è òîãî ôàêòà, ÷òî âñå èíäåêñû â äèàïàçîíå îò j � 1äî n
1óâåëè÷àòñÿ íà 1. Ñóììàðíóþ
äëèíó îãèáàþùèõ ñâÿçåé, ïîëó÷åííóþ ïîñëå âñòàâêè j-ãî îïåðàòîðà, çàïèøåì
L L Kj j j
o o o� �
~
(ãäå
~
L j
o — èñõîäíàÿ äëèíà ñâÿçåé, à K j
o — èõ êîëè÷åñòâî).
Âëèÿíèå ïåðâîãî ôàêòîðà íà îáùóþ äëèíó ñâÿçåé â ÐÑ (óâåëè÷åíèå èëè ñîêðàùå-
íèå) çàâèñèò îò êîëè÷åñòâà îãèáàþùèõ ñâÿçåé â èñõîäíîì è ðåçóëüòèðóþùèõ ìåñòàõ
ðàçìåùåíèÿ îïåðàòîðà, ò.å. îò âûáîðà ìåñòà, â êîòîðîå ïåðåìåùàåì îïåðàòîð Ai .
Âòîðîé ôàêòîð. Â ðåçóëüòàòå ïåðåìåùåíèÿ îïåðàòîðà âëåâî (âïðàâî) äëèíà åãî
ëåâûõ (ïðàâûõ) ñâÿçåé ñî âñåìè ïðåäøåñòâóþùèìè (ïîñëåäóþùèìè) îïåðàòîðàìè ñî-
êðàòèòñÿ íà âåëè÷èíó ïåðåìåùåíèÿ, ÷òî äîêàæåì, îñíîâûâàÿñü íà îïðåäåëåíèè 4.
Ïðè ïåðåìåùåíèè îïåðàòîðà Ai âëåâî íà j-å ìåñòî (âïðàâî íà p-å ìåñòî), ãäå
j i� ( p i� ) — äëèíà íåêîòîðîé ëåâîé (ïðàâîé) ñâÿçè ìåæäó îïåðàòîðàìè A j (A p ) è
Ak (Al ), ãäå k j� (1� p), áóäåò îïðåäåëÿòüñÿ ñîîòíîøåíèåì k j k i i jd d d�
( p ld �
�
i l i pd d ). Îáùàÿ äëèíà ëåâûõ (ïðàâûõ) ñâÿçåé îïåðàòîðà A j (A p ) â ýòîì ñëó÷àå áó-
äåò îïðåäåëÿòüñÿ ñîîòíîøåíèåì L L dj i m j
m i
j
ë ë�
�
�
1
(L L dp i m p
m i
p
ïð ïð�
�
�
1
) è îíà, î÷åâèä-
íî, ìåíüøå ëåâûõ (ïðàâûõ) ñâÿçåé èñõîäíîãî îïåðàòîðà. Ïîýòîìó âåëè÷èíó, íà êîòîðóþ
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6 53
ñîêðàòèòñÿ ñóììàðíàÿ äëèíà ëåâûõ (ïðàâûõ) ñâÿçåé, çàïèøåì �ë ë ë�
L Li j
(�ïð ïð ïð�
L L
i p ).
Òðåòèé ôàêòîð. Ïðè ïåðåìåùåíèè îïåðàòîðà Ai âëåâî íà j-å ìåñòî (âïðàâî íà
p-å ìåñòî), ãäå j i� ( p i� ) — äëèíà ñâÿçè ìåæäó îïåðàòîðàìè A j (A p ) è Ar (As),
ãäå r i� (s i� ), áóäåò îïðåäåëÿòüñÿ ñîîòíîøåíèåì j r i r j id d d� � ( p sd �
� �i s p id d ), ò.å. â îáîèõ ñëó÷àÿõ ñâÿçè óäëèíÿþòñÿ íà âåëè÷èíó ïåðåìåùåíèÿ.
Îáùàÿ äëèíà ëåâûõ (ïðàâûõ) ñâÿçåé îïåðàòîðà A j (A p ) â ýòîì ñëó÷àå áóäåò îïðå-
äåëÿòüñÿ ñîîòíîøåíèåì L L dj i m j
m i
j
ë ë�
�
�
1
(L L dp i m p
m i
p
ïð ïð� �
�
�
1
) è îíà, î÷åâèäíî,
áîëüøå äëèíû ëåâûõ (ïðàâûõ) ñâÿçåé èñõîäíîãî îïåðàòîðà. Îòñþäà ïðèðîñò îáùåé
äëèíû ëåâûõ (ïðàâûõ) ñâÿçåé çàïèøåì �ë ë ë�
L Lj i (�ïð ïð ïð�
L Lp i
).
Ïåðâûé è ïîñëåäíèé îïåðàòîðû ÐÑ ñîãëàñíî îïðåäåëåíèÿì 3, 4 è âûðàæåíèþ
(2) îáëàäàþò òàêèìè ñâîéñòâàìè. Ó ïåðâîãî A1 (ïîñëåäíåãî An ) îïåðàòîðà ÐÑ ìíî-
æåñòâà S
1
ë è S
1
î (S n
ïð è S n
î ) ïóñòû è ñîîòâåòñòâåííî L
1
0ë � , L
1
0î � (Ln
ïð � 0 è Ln
î � 0).
Ïîäâîäÿ èòîã èçëîæåííîìó, ñäåëàåì ñëåäóþùèå âûâîäû. Ïåðâûé ôàêòîð âëè-
ÿåò íà äëèíó ñâÿçåé âî âñåõ ñëó÷àÿõ, íî â ñëó÷àå íåçàâèñèìûõ îïåðàòîðîâ îí åäèí-
ñòâåííûé, ÷òî è îòðàæåíî â ñîîòíîøåíèè 1, ïðè÷åì ïåðåìåùåíèå ïåðâîãî è ïî-
ñëåäíåãî îïåðàòîðîâ â ñâÿçè ñ ïðèâåäåííûìè ñâîéñòâàìè L
1
0o � è Ln
î � 0 (ò.å. íè
îäíà ñâÿçü èõ íå îõâàòûâàåò) ê ñîêðàùåíèþ äëèíû ñâÿçåé íå ïðèâåäåò.
Íàðÿäó ñ ïåðâûì ôàêòîðîì äëÿ ñâÿçàííûõ ñëåâà (ñïðàâà) îïåðàòîðîâ â ñîîòíîøåíèè 2
ó÷òåíî âëèÿíèå âòîðîãî ôàêòîðà, à äëÿ ñâÿçàííûõ — âëèÿíèå âòîðîãî è òðåòüåãî â ñîîòíî-
øåíèè 3. Ïðè ýòîì ïåðâûé è ïîñëåäíèé îïåðàòîðû íå ìîãóò áûòü ñâÿçàííûìè â ñîîòâåò-
ñòâèè ñî ñâîéñòâàìè L
1
0ë � è Ln
ïð � 0 è â êà÷åñòâå òàêîâûõ íå ðàññìàòðèâàþòñÿ.  ñëó÷àå
ñâÿçàííûõ ñëåâà (ñïðàâà) îïåðàòîðîâ èç ñâîéñòâà L
1
0î � (Ln
î � 0) ñëåäóåò ñâîéñòâî �L
1
0î �
( �Ln
î � 0), ÷òî è âåäåò ê òðàíñôîðìàöèè ñîîòíîøåíèÿ 2 ê ñîîòâåòñòâóþùèì ÷àñòíûì ñëó÷àÿì.
Ïîñêîëüêó â ïðèâåäåííûõ ñîîòíîøåíèÿõ âëèÿíèå âñåõ ôàêòîðîâ ó÷òåíî äëÿ êàæäî-
ãî òèïà îïåðàòîðîâ, òî, î÷åâèäíî, âûáîð íîâîãî ìåñòà ðàñïîëîæåíèÿ îïåðàòîðîâ (åñëè îíî
ñóùåñòâóåò) ñ ó÷åòîì ýòèõ ñîîòíîøåíèé íåèçáåæíî ïðèâåäåò ê ñîêðàùåíèþ ñóììàðíîé
äëèíû èíôîðìàöèîííûõ ñâÿçåé â ÐÑ. Òåîðåìà, òàêèì îáðàçîì, äîêàçàíà.
Ïðåæäå ÷åì çàâåðøèòü äàííóþ ðàáîòó, ñäåëàåì ñëåäóþùåå çàìå÷àíèå. Õîòÿ âîç-
ìîæíîñòü ïåðåìåùåíèÿ îïåðàòîðîâ îãðàíè÷åíà îáëàñòÿìè íåçàâèñèìîñòè è, òàêèì îáðà-
çîì, èñêëþ÷åíî èõ âçàèìíîå âëèÿíèå, íà òàêîå ïåðåìåùåíèå ñëåäóåò íàëîæèòü åùå îäíî
äîñòàòî÷íî ñèëüíîå îãðàíè÷åíèå. Îíî ñâÿçàíî ñ íåîáõîäèìîñòüþ îáåñïå÷åíèÿ òðåáóå-
ìîé àëãîðèòìîì ïîñëåäîâàòåëüíîñòè äåéñòâèé, íàïðèìåð ïîñëåäîâàòåëüíîñòè ââîäà–âû-
âîäà äàííûõ, âûïîëíÿåìûõ îïåðàòîðàìè. Îäíàêî ïîêà ýòî îãðàíè÷åíèå íå ôîðìàëèçîâà-
íî, êîíòðîëü çà åãî óäîâëåòâîðåíèåì îñòàâëÿåì çà ðàçðàáîò÷èêîì.
Çàêëþ÷åíèå. Ïîñòàâëåííàÿ â ðàáîòå öåëü äîñòèãíóòà, ïîñêîëüêó ïîêàçàíà âîç-
ìîæíîñòü ðåàëèçàöèè (â ðàìêàõ àëãåáðàè÷åñêîãî àïïàðàòà) îïòèìèçèðóþùèõ ïðåîáðà-
çîâàíèÿ àëãîðèòìîâ, â ÷àñòíîñòè ñîêðàùåíèÿ äëèíû èíôîðìàöèîííûõ ñâÿçåé íà îñíî-
âå èõ ôîðìàëèçàöèè. Äàëüíåéøàÿ ôîðìàëèçàöèÿ èíôîðìàöèîííûõ ñâÿçåé öåëåñîîá-
ðàçíà äëÿ ðàñøèðåíèÿ âîçìîæíîñòåé ïðåîáðàçîâàíèÿ àëãîðèòìîâ, â ÷àñòíîñòè
ðàññìîòðåííûõ ïîñëåäîâàòåëüíûõ àëãîðèòìîâ â ïàðàëëåëüíûå (êâàçèïàðàëëåëüíûå).
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ò ó ð ñ ê è é Â . Ìåòîäîëîãèÿ ïðîãðàììèðîâàíèÿ. — Ì.: Ìèð, 1981. — 264 ñ.
2. Ë å î í å í ê î â À .  . Ñàìîó÷èòåëü UML. — ÑÏá.: ÁÕÂ-Ïåòåðáóðã, 2001. — 304 ñ.
3. À ê ó ë î â ñ ê è é Â . Ã . Ôîðìàëèçàöèÿ âçàèìîñâÿçåé îïåðàòîðîâ è äàííûõ â ðàìêàõ ðàñøèðåííîé
àëãåáðû àëãîðèòìîâ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2008. — ¹ 6. — C. 170–182.
4. Þ ù å í ê î Å . Ë . , Ö å é ò ë è í Ã . Å . , Ã ð è ö à é Â . Ï . , Ò å ð ç ÿ í Ò . Ê . Ìíîãîóðîâíåâîå ñòðóêòóð-
íîå ïðîåêòèðîâàíèå ïðîãðàìì: Òåîðåòè÷åñêèå îñíîâû, èíñòðóìåíòàðèé. — Ì.: Ôèíàíñû è ñòàòèñòèêà,
1989. — 208 ñ.
5. À ê ó ë î â ñ ê è é Â . Ã . Íåêîòîðûå ïîäõîäû ê êîíòðîëþ è ïðåîáðàçîâàíèþ àëãîðèòìîâ íà îñíîâå
àíàëèçà ñïåöèôèöèðóåìûõ äàííûõ // Ïðîáëåìè ïðîãðàìóâàííÿ. — 2008. — ¹ 4. — Ñ. 84–93.
Ïîñòóïèëà 07.07.2009
54 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 6
|
| id | nasplib_isofts_kiev_ua-123456789-44482 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T17:19:12Z |
| publishDate | 2009 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Акуловский, В.Г. 2013-06-02T08:15:11Z 2013-06-02T08:15:11Z 2009 Некоторые аспекты преобразования алгоритмов на основе формализации информационных связей / В.Г. Акуловский // Кибернетика и системный анализ. — 2009. — № 6. — С. 50-54. — Бібліогр.: 5 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/44482 519.683 У рамках алгебраїчного апарату здійснено формалізацію інформаційних зв’язків між операторами, що входять в регулярні схеми, за допомогою яких описуються алгоритми. На основі проведеної формалізації показано можливість специфікації таких зв’язків і доведено можливість перетворення регулярних схем з метою зменшення довжини зв’язків між операторами. Algebraic tools are used to formalize information connections between operators that appear in regular circuits and describe algorithms. Based on the formalization, it is shown that such connections can be specified and regular circuits can be transformed to reduce the length of connections between operators. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Некоторые аспекты преобразования алгоритмов на основе формализации информационных связей Деякі аспекти перетворення алгоритмів на основі формалізації інформаційних зв’язків Some aspects of algorithm transformation based on the formalization of information connections Article published earlier |
| spellingShingle | Некоторые аспекты преобразования алгоритмов на основе формализации информационных связей Акуловский, В.Г. Кибернетика |
| title | Некоторые аспекты преобразования алгоритмов на основе формализации информационных связей |
| title_alt | Деякі аспекти перетворення алгоритмів на основі формалізації інформаційних зв’язків Some aspects of algorithm transformation based on the formalization of information connections |
| title_full | Некоторые аспекты преобразования алгоритмов на основе формализации информационных связей |
| title_fullStr | Некоторые аспекты преобразования алгоритмов на основе формализации информационных связей |
| title_full_unstemmed | Некоторые аспекты преобразования алгоритмов на основе формализации информационных связей |
| title_short | Некоторые аспекты преобразования алгоритмов на основе формализации информационных связей |
| title_sort | некоторые аспекты преобразования алгоритмов на основе формализации информационных связей |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/44482 |
| work_keys_str_mv | AT akulovskiivg nekotoryeaspektypreobrazovaniâalgoritmovnaosnoveformalizaciiinformacionnyhsvâzei AT akulovskiivg deâkíaspektiperetvorennâalgoritmívnaosnovíformalízacííínformacíinihzvâzkív AT akulovskiivg someaspectsofalgorithmtransformationbasedontheformalizationofinformationconnections |