Непрерывная логика и алгоритмы решения некоторых комбинаторных задач
Сформульовано клас комбінаторних задач, еквівалентних задачі визначення взаємного розміщення n послідовностей інтервалів. Показано, що адекватною математичною моделлю розв’язку поставленої задачі є кінцевий динамічний автомат без пам'яті, а адекватним математичним апаратом — неперервна логіка....
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2009 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/44376 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Непрерывная логика и алгоритмы решения некоторых комбинаторных задач / В.И. Левин // Кибернетика и системный анализ. — 2009. — № 3. — С. 173-181. — Бібліогр.: 6 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859702324769849344 |
|---|---|
| author | Левин, В.И. |
| author_facet | Левин, В.И. |
| citation_txt | Непрерывная логика и алгоритмы решения некоторых комбинаторных задач / В.И. Левин // Кибернетика и системный анализ. — 2009. — № 3. — С. 173-181. — Бібліогр.: 6 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Сформульовано клас комбінаторних задач, еквівалентних задачі визначення взаємного розміщення n послідовностей інтервалів. Показано, що адекватною математичною моделлю розв’язку поставленої задачі є кінцевий динамічний автомат без пам'яті, а адекватним математичним апаратом — неперервна логіка. Побудовано алгоритми розв’язку.
The class of combinatorial problems equivalent to the problem of determination of relative positions of n interval sequences is formulated. It is shown that an adequate mathematical model of solving the stated problem is a finite dynamic automaton without memory and that the adequate mathematical apparatus is continuous logic. Algorithms for the solution of the problem are constructed.
|
| first_indexed | 2025-12-01T01:41:39Z |
| format | Article |
| fulltext |
Â.È. ËÅÂÈÍ
ÓÄÊ 519.715 ÍÅÏÐÅÐÛÂÍÀß ËÎÃÈÊÀ È ÀËÃÎÐÈÒÌÛ
ÐÅØÅÍÈß ÍÅÊÎÒÎÐÛÕ ÊÎÌÁÈÍÀÒÎÐÍÛÕ
ÇÀÄÀ×
Êëþ÷åâûå ñëîâà: íåïðåðûâíàÿ ëîãèêà, êîìáèíàòîðíàÿ çàäà÷à, àâòîìàòíàÿ ìîäåëü.
ÂÂÅÄÅÍÈÅ
Çàäà÷è îáðàáîòêè äàííûõ, ïëàíèðîâàíèÿ ðàáîò, ïðîåêòèðîâàíèÿ ñèñòåì óïðàâëå-
íèÿ îáúåêòàìè è ìíîãèå äðóãèå ñâîäÿòñÿ ìàòåìàòè÷åñêè ê ðåøåíèþ êîìáèíàòîð-
íîé çàäà÷è — âû÷èñëåíèþ ïîäõîäÿùèõ ïîêàçàòåëåé âçàèìîðàñïîëîæåíèÿ n ïî-
ñëåäîâàòåëüíîñòåé èíòåðâàëîâ (âðåìåííûõ èëè ïðîñòðàíñòâåííûõ) è íàõîæäå-
íèþ óñëîâèé, ïðè êîòîðûõ ýòî âçàèìîðàñïîëîæåíèå èìååò òîò èëè èíîé
êà÷åñòâåííûé õàðàêòåð. Ïðèâåäåì íåñêîëüêî ïðèìåðîâ òàêèõ çàäà÷.
1. Ïóñòü èìååòñÿ ïîñëåäîâàòåëüíîñòü A âðåìåííûõ èíòåðâàëîâ, â êîòîðûõ íå-
êîòîðîå îñíîâíîå òåõíè÷åñêîå óñòðîéñòâî ðàáîòîñïîñîáíî, è ïîñëåäîâàòåëüíîñòü B
âðåìåííûõ èíòåðâàëîâ, â êîòîðûõ ðàáîòîñïîñîáíî ðåçåðâíîå óñòðîéñòâî. Ñèñòåìà
«îñíîâíîå è ðåçåðâíîå óñòðîéñòâà» ÿâëÿåòñÿ ðàáîòîñïîñîáíîé, åñëè ðàáîòîñïîñîá-
íî õîòÿ áû îäíî èç äâóõ åå óñòðîéñòâ — îñíîâíîå èëè ðåçåðâíîå. Òàêèì îáðàçîì,
äëÿ òîãî ÷òîáû óñòàíîâèòü ïîñëåäîâàòåëüíîñòü èíòåðâàëîâ ðàáîòîñïîñîáíîñòè çà-
äàííîé ñèñòåìû, íóæíî îïðåäåëèòü âçàèìîðàñïîëîæåíèå ïîñëåäîâàòåëüíîñòåé èí-
òåðâàëîâ ðàáîòîñïîñîáíîñòè îñíîâíîãî óñòðîéñòâà (ïîñëåäîâàòåëüíîñòü A) è ðåçåð-
âíîãî óñòðîéñòâà (ïîñëåäîâàòåëüíîñòü B) è íàéòè òå ïðîìåæóòêè âðåìåíè, â êîòî-
ðûõ èìåþòñÿ èíòåðâàëû õîòÿ áû îäíîé èç ïîñëåäîâàòåëüíîñòåé — A èëè B; îíè è
áóäóò èíòåðâàëàìè ðàáîòîñïîñîáíîñòè ñèñòåìû. Äëÿ òîãî ÷òîáû, íàïðèìåð, óñòà-
íîâèòü, êîãäà ñèñòåìà ðàáîòîñïîñîáíà íà ïðîèçâîëüíîì çàäàííîì îòðåçêå âðåìåíè
T, íóæíî íàéòè óñëîâèÿ, ïðè êîòîðûõ íà ýòîì îòðåçêå èíòåðâàëû ïîñëåäîâàòåëü-
íîñòè B íàêðûâàþò ïðîìåæóòêè ìåæäó èíòåðâàëàìè ïîñëåäîâàòåëüíîñòè A.
2. Ðàññìîòðèì ïîñëåäîâàòåëüíîñòü A âðåìåííûõ èíòåðâàëîâ, â òå÷åíèå êîòî-
ðûõ íåêîòîðàÿ îðãàíèçàöèÿ (ìàãàçèí, áàíê, ðåìîíòíàÿ ìàñòåðñêàÿ è ò.ä.) âûïîëíÿåò
îáñëóæèâàíèå êëèåíòîâ, è ïîñëåäîâàòåëüíîñòü B âðåìåííûõ èíòåðâàëîâ, â òå÷åíèå
êîòîðûõ íåêîòîðûé êëèåíò ìîæåò ïîñåòèòü îáñëóæèâàþùóþ îðãàíèçàöèþ. Äëÿ
òîãî ÷òîáû óñòàíîâèòü ïîñëåäîâàòåëüíîñòü ïðîìåæóòêîâ âðåìåíè âîçìîæíîãî îá-
ñëóæèâàíèÿ êëèåíòà îðãàíèçàöèåé, íóæíî îïðåäåëèòü âçàèìîðàñïîëîæåíèå ïîñëå-
äîâàòåëüíîñòåé èíòåðâàëîâ A è B è âûÿâèòü òå ïðîìåæóòêè âðåìåíè, â êîòîðûõ
èìåþòñÿ èíòåðâàëû îáåèõ ïîñëåäîâàòåëüíîñòåé — A è B; îíè è áóäóò ïðîìåæóòêà-
ìè âðåìåíè âîçìîæíîãî îáñëóæèâàíèÿ êëèåíòà. Äëÿ òîãî ÷òîáû óñòàíîâèòü, êîãäà
îðãàíèçàöèÿ ìîæåò îáñëóæèòü êëèåíòà ïðè åãî îáðàùåíèè â ëþáîé äîñòóïíûé äëÿ
íåãî ìîìåíò âðåìåíè, íóæíî íàéòè óñëîâèÿ, ïðè êîòîðûõ èíòåðâàëû ïîñëåäîâà-
òåëüíîñòè A íàêðûâàþò âñå èíòåðâàëû ïîñëåäîâàòåëüíîñòè B.
3. Ïóñòü çàäàíû ïîñëåäîâàòåëüíîñòü A âðåìåííûõ èíòåðâàëîâ, â êîòîðûõ
ïðåäñåäàòåëü ñîâåòà ìîæåò ïðîâåñòè åãî çàñåäàíèå, è ïîñëåäîâàòåëüíîñòè
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3 173
© Â.È. Ëåâèí, 2009
B B1 10, ,� âðåìåííûõ èíòåðâàëîâ, â êîòîðûõ ÷ëåíû ñîâåòà 1 10, ,� ìîãóò ó÷àñòâî-
âàòü â ýòîì çàñåäàíèè. Çàñåäàíèå ñîâåòà âîçìîæíî òîëüêî ïðè ó÷àñòèè â íåì ïðåä-
ñåäàòåëÿ è íå ìåíåå ïÿòè ëþáûõ ÷ëåíîâ ñîâåòà. Äëÿ òîãî ÷òîáû óñòàíîâèòü ïîñëå-
äîâàòåëüíîñòü ïðîìåæóòêîâ âðåìåíè, â êîòîðûå âîçìîæíî ïðîâåäåíèå çàñåäàíèÿ
ñîâåòà, íóæíî îïðåäåëèòü âçàèìîðàñïîëîæåíèå ïîñëåäîâàòåëüíîñòåé èíòåðâàëîâ
A B B, , ,1 10� è íàéòè òå ïðîìåæóòêè âðåìåíè, â êîòîðûõ îäíîâðåìåííî èìåþòñÿ
èíòåðâàëû ïîñëåäîâàòåëüíîñòè A è èíòåðâàëû êàêèõ-íèáóäü ïÿòè èëè áîëåå èç 10
ïîñëåäîâàòåëüíîñòåé B B1 10, ,� ; îíè è áóäóò ïðîìåæóòêàìè âðåìåíè âîçìîæíîãî
ïðîâåäåíèÿ çàñåäàíèÿ ñîâåòà. Äëÿ òîãî ÷òîáû óñòàíîâèòü, êîãäà ïðîâåäåíèå çàñåäà-
íèÿ ñîâåòà âîçìîæíî íà ïðîèçâîëüíîì çàäàííîì îòðåçêå âðåìåíè T, íóæíî íàéòè
óñëîâèÿ, ïðè êîòîðûõ îòðåçîê T íàêðûâàåòñÿ êàêèì-ëèáî èíòåðâàëîì ïîñëåäîâà-
òåëüíîñòè A è êàêèìè-ëèáî ïÿòüþ èëè áîëåå èíòåðâàëàìè, âçÿòûìè èç ïÿòè èëè áî-
ëåå ñîîòâåòñòâóþùèõ ïîñëåäîâàòåëüíîñòåé B B1 10, ,� .
Çàäà÷à îïðåäåëåíèÿ ïîêàçàòåëåé âçàèìîðàñïîëîæåíèÿ n ïîñëåäîâàòåëüíîñòåé
èíòåðâàëîâ, ïðèìåðû êîòîðîé ïðèâåäåíû âûøå, ÿâëÿåòñÿ êîìáèíàòîðíîé çàäà÷åé.
Ïðè ðåøåíèè çàäà÷ äàííîãî òèïà ìîæíî èñïîëüçîâàòü ðàçëè÷íûå ïåðåáîðíûå ìåòî-
äû. Îäíàêî ñóùåñòâåííûå íåäîñòàòêè ýòèõ ìåòîäîâ (áûñòðûé ðîñò ñëîæíîñòè âû-
÷èñëåíèé ïðè óâåëè÷åíèè ðàçìåðîâ çàäà÷è; íåàíàëèòè÷åñêèé (ïîèñêîâûé) õàðàêòåð
àëãîðèòìà ðåøåíèÿ; íåâîçìîæíîñòü îáîçðèìîãî ïðåäñòàâëåíèÿ àëãîðèòìà ðåøåíèÿ
â ñëó÷àå âûñîêîðàçìåðíîé çàäà÷è) çàñòàâëÿþò èñêàòü äðóãèå ïóòè ðåøåíèÿ. Âîç-
ìîæíûé ïîäõîä çàêëþ÷àåòñÿ â òîì, ÷òîáû íàéòè äëÿ çàäà÷è ãîòîâóþ ìàòåìàòè÷åñ-
êóþ ìîäåëü, êîòîðàÿ ãëóáîêî è äåòàëüíî ðàçðàáîòàíà íà áàçå êàêîãî-íèáóäü óäîá-
íîãî àíàëèòè÷åñêîãî àïïàðàòà.  íàñòîÿùåé ñòàòüå ïîêàçàíî, ÷òî òàêîé ìîäåëüþ
ìîæåò ñëóæèòü äèíàìè÷åñêèé êîíå÷íûé àâòîìàò [1–4], à òàêèì àïïàðàòîì — íå-
ïðåðûâíàÿ ëîãèêà [1, 2, 5, 6].
1. ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È
Ïóñòü çàäàíî n êîíå÷íûõ ïîñëåäîâàòåëüíîñòåé íåïåðåñåêàþùèõñÿ èíòåðâàëîâ:
A a b a b a b
A a b
m m1 11 11 12 12 1 1
2 21 21
1 1
�
�
( , ), ( , ), , ( , );
( , ),
�
( , ), , ( , );a b a bm m22 22 2 22 2
�
� � � � � � � � � � � � � � � � � � � � � � � � � � �
�A a b a b a bn n n n n nm nmn n
( , ), ( , ), , ( , ).1 1 2 2 �
(1)
Òðåáóåòñÿ: 1) îïðåäåëèòü âçàèìîðàñïîëîæåíèå èìåþùåéñÿ ñèñòåìû ïîñëåäî-
âàòåëüíîñòåé èíòåðâàëîâ (1); 2) íàéòè óñëîâèÿ, ïðè êîòîðûõ ýòî âçàèìîðàñïîëîæå-
íèå èìååò òîò èëè èíîé êà÷åñòâåííûé õàðàêòåð. Ïîä âçàèìîðàñïîëîæåíèåì èíòåð-
âàëîâ ïîíèìàåòñÿ ñèòóàöèÿ, îïðåäåëÿåìàÿ ïåðåñå÷åíèåì îäíèõ è íåïåðåñå÷åíèåì
äðóãèõ èíòåðâàëîâ. Ïåðâàÿ çàäà÷à íàöåëåíà íà òî, ÷òîáû ïî çàäàííîìó ïîëîæåíèþ
âñåõ èíòåðâàëîâ âñåõ ïîñëåäîâàòåëüíîñòåé (1) âû÷èñëèòü âçàèìîðàñïîëîæåíèå ëþ-
áûõ êîìáèíàöèé (ïî äâå, òðè è ò.ä.) ëþáûõ ïîäïîñëåäîâàòåëüíîñòåé ïîñëåäîâà-
òåëüíîñòåé (1), âòîðàÿ — íàéòè óñëîâèÿ, íàêëàäûâàåìûå íà ïîëîæåíèå âñåõ èíòåð-
âàëîâ âñåõ ïîäïîñëåäîâàòåëüíîñòåé (1), ïðè êîòîðûõ óêàçàííîå âçàèìîðàñïîëîæå-
íèå èìååò òîò èëè èíîé òðåáóåìûé âèä. Òàêèì îáðàçîì, çàäà÷à 1 ÿâëÿåòñÿ çàäà÷åé
àíàëèçà ñèñòåìû ïîñëåäîâàòåëüíîñòåé èíòåðâàëîâ (1), à çàäà÷à 2 — çàäà÷åé ñèíòåçà
òàêîé ñèñòåìû. Çàäà÷è àíàëèçà è ñèíòåçà ñèñòåìû ïîñëåäîâàòåëüíîñòåé èíòåðâàëîâ
âèäà (1) áóäåì ðåøàòü, èñïîëüçóÿ àäåêâàòíóþ ñèñòåìå (1) ìàòåìàòè÷åñêóþ ìîäåëü
êîíå÷íîãî äèíàìè÷åñêîãî àâòîìàòà áåç ïàìÿòè è ìàòåìàòè÷åñêèé àïïàðàò íåïðå-
ðûâíîé ëîãèêè, íåîáõîäèìûé äëÿ àäåêâàòíîãî îïèñàíèÿ óêàçàííîãî àâòîìàòà. Ðå-
øåíèå ïðåäëàãàåòñÿ íàõîäèòü â àíàëèòè÷åñêîé ôîðìå ñóïåðïîçèöèè íåïðåðûâ-
íî-ëîãè÷åñêèõ îïåðàöèé, êîòîðàÿ îäíîâðåìåííî äàåò ëîãè÷åñêèé àëãîðèòì ïîëó÷å-
íèÿ ÷èñëåííîãî ðåøåíèÿ.
174 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3
2. ÄÈÍÀÌÈ×ÅÑÊÈÅ ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛ È ÍÅÏÐÅÐÛÂÍÀß ËÎÃÈÊÀ
Äèíàìè÷åñêèé êîíå÷íûé àâòîìàò (ÄÀ) áåç ïàìÿòè [1, 2, 4] ïðåäñòàâëÿåò ñîáîé
ìàòåìàòè÷åñêóþ ìîäåëü â âèäå ( , )n 1 -ïîëþñíèêà (ðèñ. 1), ðåàëèçóþùåãî íà âûõî-
äå y íåêîòîðóþ áóëåâó ôóíêöèþ ñâîèõ âõîäîâ x xn1 , ,� :
y f x x x x yn n� �( , , ), , , , { , }1 1 0 1� � . (2)
Íà âõîäû ÄÀ ðèñ. 1 ïîäàþòñÿ âõîäíûå äâîè÷íûå äèíàìè÷åñêèå ïðîöåññû
x t a b a b a bm m1 11 11 12 12 1 11 0 1 1
1 1
( ) ( , ) ( , ) ( , ) ( , );� � �
� � � �
�
� � � � � � � � � � � � � � � � � � � � � � � � � � �
� � �x t a bn n n( ) ( , ) ( , )1 0 11 1 ( , ) ( , ),a b a bn n nm nmn n2 2 1�
(3)
â êîòîðûõ 1( , )a b îçíà÷àþò èíòåðâàëû âðåìåíè åäèíè÷íûõ çíà÷åíèé ïðîöåññà
(èìïóëüñû), à 0( , )� � — ïðîìåæóòî÷íûå èíòåðâàëû âðåìåíè íóëåâûõ çíà÷åíèé
ïðîöåññà (ïàóçû). Ñ âûõîäà ÄÀ ñíèìàåòñÿ âûõîäíîé äâîè÷íûé äèíàìè÷åñêèé
ïðîöåññ
y t c d c d c dm m( ) ( , ) ( , ) ( , ) ( , )� � �1 0 1 11 1 2 2 � , (4)
ñîîòâåòñòâóþùèé ïîäàííûì âõîäíûì ïðîöåñ-
ñàì (3) ÄÀ è åãî ðåàëèçóåìîé áóëåâîé ôóíêöèè
(2). Îñíîâíîé çàäà÷åé äëÿ ÄÀ áåç ïàìÿòè ÿâëÿ-
åòñÿ çàäà÷à îòûñêàíèÿ âûõîäíîãî äèíàìè÷åñêîãî
ïðîöåññà y t( ) ïî åãî èçâåñòíûì âõîäíûì äèíà-
ìè÷åñêèì ïðîöåññàì x t x tn1 ( ), , ( )� è ðåàëèçóå-
ìîé áóëåâîé ôóíêöèè f . Â 1971–72 ãã. àâòîðîì
áûëî óñòàíîâëåíî, ÷òî ýòà çàäà÷à ìîæåò áûòü
ðåøåíà â àíàëèòè÷åñêîé ôîðìå äëÿ ëþáîãî ÄÀ
áåç ïàìÿòè, èìåþùåãî ëþáûå ÷èñëî âõîäîâ,
âõîäíûå ïðîöåññû è ðåàëèçóåìóþ ôóíêöèþ, ñ ïîìîùüþ ìàòåìàòè÷åñêîãî àïïà-
ðàòà íåïðåðûâíîé ëîãèêè (ÍË) [1, 2, 4, 5]. Îïðåäåëÿåòñÿ ÍË ñëåäóþùèì îáðà-
çîì. Ïóñòü C A B� [ , ] — ïðîèçâîëüíûé îòðåçîê íà îñè âåùåñòâåííûõ ÷èñåë. Òîã-
äà äëÿ ëþáûõ ÷èñåë a b e C, , � ìîæíî ââåñòè ñëåäóþùèå ëîãè÷åñêèå îïåðàöèè:
a b a b� � max( , ) — äèçúþíêöèÿ, (5)
a b a b� � min( , ) — êîíúþíêöèÿ, (6)
e A B e� � � — îòðèöàíèå. (7)
Îïåðàöèè ÍË (5)–(7) ïîäîáíû ñîîòâåòñòâóþùèì îïåðàöèÿì äâóçíà÷íîé ëîãè-
êè (ãäå ìíîæåñòâî C � { , }0 1) è îáîáùàþò èõ íà ñëó÷àé íåïðåðûâíîãî íåñóùåãî ìíî-
æåñòâà.  ÍË ñîõðàíÿþò ñèëó íåêîòîðûå çàêîíû äâóçíà÷íîé ëîãèêè:
a a a a a a� � � �, — òàâòîëîãèè; (8)
a b b a a b b a� � � � � �, — ïåðåìåñòèòåëüíûé; (9)
( ) ( ), ( ) ( )a b c a b c a b c a b c� � � � � � � � � � — ñî÷åòàòåëüíûé; (10)
a b c a b a c a b c a b a c� � � � � � � � � � � �( ) ( ) ( ), ( ) ( ) ( ) —
ðàñïðåäåëèòåëüíûé; (11)
a b a b a b a b� � � � � �, — äå Ìîðãàíà; (12)
a a b a a a b a� � � � � �( ) , ( ) — ïîãëîùåíèÿ. (13)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3 175
nx
1x
�
y
f
Ðèñ. 1. Ìàòåìàòè÷åñêàÿ ìîäåëü êîíå÷-
íîãî ÄÀ
Êðîìå íèõ, â ÍË äåéñòâóþò íåêîòîðûå âàæíûå ñïåöèôè÷åñêèå çàêîíû, íàïðè-
ìåð çàêîíû îöåíêè è óïðîùåíèÿ ëîãè÷åñêîãî âûðàæåíèÿ:
a b a b a b a b� � � , ; , , (14)
a a a a a a a a ai i i m i i m1 1 1 1 1 1� � � � � � � � � � � �� � � �� � � �
ïðè a a k ii k
( ) , (15)
a a a a a a a a ai i i m i i m1 1 1 1 1 1� � � � � � � � � � � �� � � �� � � �
ïðè a a k ii k�
( ) . (16)
Èäåÿ îòûñêàíèÿ âûõîäíîãî ïðîöåññà ÄÀ áåç ïàìÿòè ïî åãî çàäàííûì âõîäíûì
ïðîöåññàì è ðåàëèçóåìîé ëîãè÷åñêîé ôóíêöèè ïðîñòà. Ââåäåì ñëåäóþùèå îáîçíà-
÷åíèÿ: 1 — äâîè÷íûé äèíàìè÷åñêèé ïðîöåññ, ïðèíèìàþùèé ïîñòîÿííîå çíà÷å-
íèå 1; 0 — äâîè÷íûé äèíàìè÷åñêèé ïðîöåññ, ïðèíèìàþùèé ïîñòîÿííîå çíà÷å-
íèå 0; �1— èçìåíåíèå çíà÷åíèÿ ïðîöåññà 0 1� ; �0 — èçìåíåíèå çíà÷åíèÿ ïðîöåññà
1 0� ; �1a — èçìåíåíèå �1 â ìîìåíò âðåìåíè a; �0b — èçìåíåíèå �0 â ìîìåíò âðåìåíè
b; � �1 0a b — èìïóëüñ 1( , )a b â èíòåðâàëå âðåìåíè ( , )a b ; � �0 1a b — ïàóçà 0( , )a b â èíòåðâà-
ëå âðåìåíè ( , )a b . Ëþáîé äâîè÷íûé äèíàìè÷åñêèé ïðîöåññ ìîæíî çàïèñàòü â âèäå
ïîñëåäîâàòåëüíîñòè èìïóëüñîâ è ïàóç (êàê â (3)) ëèáî ïîñëåäîâàòåëüíîñòè èçìåíå-
íèé çíà÷åíèÿ ïðîöåññà. Íàïðèìåð, ïðîöåññ íà ðèñ. 2 ìîæíî çàïèñàòü â âèäå
x t a b e( ) ( , ) ( , ) ( , ) ( , )� �
� � �
1 0 1 0 èëè x t a b e( ) � � � �0 1 0 .
×èñëî èçìåíåíèé çíà÷åíèÿ äâîè÷íîãî ïðîöåññà íàçûâàåòñÿ åãî ãëóáèíîé. Íàïðè-
ìåð, ãëóáèíà ïðîöåññà íà ðèñ. 2 ðàâíà 3. Äëÿ ñèñòåìû (âåêòîðà) äâîè÷íûõ ïðîöåññîâ
ñîîòâåòñòâóþùèì ïîíÿòèåì ÿâëÿåòñÿ âåêòîðíàÿ ãëóáèíà. Íàïðèìåð, âåêòîðíàÿ ãëóáè-
íà ñèñòåìû äâóõ ïðîöåññîâ x t a b1 1( ) ( , ),� x t c d2 1( ) ( , )� ðàâíà ( , )2 2 .
Ïîêàæåì íà ïðèìåðàõ, êàê
ñ ïîìîùüþ ÍË îïðåäåëèòü âû-
õîäíîé ïðîöåññ ÄÀ áåç ïàìÿòè
ïî åãî âõîäíûì ïðîöåññàì è ðåà-
ëèçóåìîé ëîãè÷åñêîé ôóíêöèè.
Îãðàíè÷èìñÿ ïðîñòåéøèìè
ÄÀ — äâóõâõîäîâûìè äèçúþí-
êòîðàìè è êîíúþíêòîðàìè,
ðåàëèçóþùèìè áóëåâû ôóíêöèè
äèçúþíêöèÿ � è êîíúþíêöèÿ �:
y x x
x x
� � �
� ��
�
�
1 2
1 20 0
1
ïðè
â ïðîòèâíîì ñëó àå
,
;
y x x
x x
� � �
� ��
�
�
1 2
1 21 1
0
ïðè
â ïðîòèâíîì ñëó àå,
,
(17)
è ïðîñòåéøèìè âõîäíûìè ïðîöåññàìè ñ ãëóáèíîé íå ñâûøå 1. Ïóñòü íàäî íàéòè
âûõîäíîé ïðîöåññ êîíúþíêòîðà íà âõîäíûå ïðîöåññû x t a1 1( ) � � , x t b2 0( ) � � .
Èñêîìûé ïðîöåññ, î÷åâèäíî, ðàâåí îäèíî÷íîìó èìïóëüñó 1( , )a b èëè òîæäåñòâåí-
íîìó íóëþ, â çàâèñèìîñòè îò òîãî, ÷òî áîëüøå — b èëè a. Ïîýòîìó, èíòåðïðå-
òèðóÿ òîæäåñòâåííûé íóëü êàê îäèíî÷íûé èìïóëüñ ñ ñîâìåùåííûìè íà÷àëîì è
êîíöîì, ìîæåì çàïèñàòü èñêîìûé ïðîöåññ â âèäå
y t x t x t
a b b a
a a b
a b( ) ( ) ( )
( , ) ;
( , )
� � � � � � �
�
�1 2 1 0
1
0 1
ïðè
ïðè
�
�
� a.
(18)
Îòñþäà ñ ïîìîùüþ îïåðàöèè äèçúþíêöèè ÍË � îêîí÷àòåëüíî íàõîäèì
� � � � �1 0 1a b a a b( , ) . (19)
176 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3
x
0 a tb e
Ðèñ. 2. Âûõîäíîé ïðîöåññ ÄÀ áåç ïàìÿòè
÷ ÷
Âûõîäíûå ïðîöåññû â äèçúþíêòîðå è êîíúþíêòîðå ïðè âñåõ îñòàëüíûõ âõîäíûõ
ïðîöåññàõ ñ ãëóáèíîé íå âûøå 1 ïîëó÷àþòñÿ àíàëîãè÷íî:
0 0 0 1 0 1 0 0 0 1 1 1� � � � � � � � � � � � � � � � � � � �� �a b a a a b a b a b ax x; ; ; b a b a a b; ( , );� � � � �1 0 1
1 0 1 1 1 0 0 0 0 1 1 1� � � � � � � � � � � � � � � � � � � �� �a b a a a b a b a b ax x; ; ; b a b b a b; ( , ). ( )� � � � �1 0 0 20
Ôîðìóëû (20) íàãëÿäíî äåìîíñòðèðóþò óäîáñòâî è àäåêâàòíîñòü àïïàðàòà ÍË
êàê ñðåäñòâà îòûñêàíèÿ âûõîäíûõ ïðîöåññîâ ÄÀ áåç ïàìÿòè ïî èõ âõîäíûì ïðî-
öåññàì è ðåàëèçóåìîé ëîãè÷åñêîé ôóíêöèè.
Åñëè âõîäíûå ïðîöåññû äèçúþíêòîðà èëè êîíúþíêòîðà èìåþò ãëóáèíó ñâû-
øå 1, òî îòûñêàíèå èõ âûõîäíûõ ïðîöåññîâ òðåáóåò ïðèìåíåíèÿ ôîðìàëüíûõ ìåòî-
äîâ. Îñíîâíûå èç íèõ — ïðÿìîé ìåòîä, ìåòîä äåêîìïîçèöèè è ìåòîä èíâåðñèè.
Ïðÿìîé ìåòîä îñíîâàí íà ïîëíîì ïåðåáîðå âñåõ âîçìîæíûõ ñëó÷àåâ âçàèìíîãî
ðàñïîëîæåíèÿ âõîäíûõ ïðîöåññîâ ýëåìåíòà. Äëÿ êàæäîãî ñëó÷àÿ âûõîäíîé ïðîöåññ
ýëåìåíòà çàïèñûâàåòñÿ â ÿâíîì âèäå îòäåëüíî. Îáùåå âûðàæåíèå ýòîãî ïðîöåññà
ïîëó÷àåòñÿ èç ÷àñòíûõ ñ èñïîëüçîâàíèåì ÍË. Ìåòîä äåêîìïîçèöèè ñîñòîèò â òîì,
÷òî îäèí èç äâóõ âõîäíûõ ïðîöåññîâ ýëåìåíòà — x t1 ( ) èëè x t2 ( ), íàïðèìåð x t1 ( ),
ðàçáèâàåòñÿ íà äâà ïîñëåäîâàòåëüíûõ ïîäïðîöåññà — x t11 ( ) è x t12 ( ) . Çàòåì íàõî-
äÿòñÿ ñîñòàâëÿþùèå âûõîäíûå ïðîöåññû y t1 ( ) è y t2 ( ) — ðåàêöèè ýëåìåíòà íà ñî-
ñòàâëÿþùèå âõîäíûå ïðîöåññû { ( ), ( )}x t x t11 2 è { ( ), ( )}x t x t12 2 . Åñëè y t1 ( ) è y t2 ( )
íå ïåðåñåêàþòñÿ âî âðåìåíè ó÷àñòêàìè, ñîäåðæàùèìè âñå èçìåíåíèÿ çíà÷åíèÿ ïðî-
öåññà, òî èñêîìûé âûõîäíîé ïðîöåññ y t( ) îïðåäåëÿåòñÿ êàê ïîñëåäîâàòåëüíîñòü
ïðîöåññîâ y t1 ( ) è y t2 ( ) . Ìåòîä èíâåðñèè îñíîâàí íà ôîðìóëàõ
x t x t x t x t x t x t x t x t1 2 1 2 1 2 1 2( ) ( ) ( ) ( ), ( ) ( ) ( ) ( )� � � � � � , (21)
âûòåêàþùèõ èç çàêîíà äå Ìîðãàíà äâóçíà÷íîé (áóëåâîé) ëîãèêè è ïîçâîëÿþùèõ
ïî óæå èçâåñòíîé ðåàêöèè äèçúþíêòîðà (êîíúþíêòîðà) íà âõîäíûå ïðîöåññû
x t1 ( ) , x t2 ( ) ëåãêî îïðåäåëèòü ðåàêöèþ êîíúþíêòîðà (äèçúþíêòîðà) íà âõîäíûå
ïðîöåññû x t1 ( ), x t2 ( ) . Èñïîëüçóÿ ýòè ìåòîäû, íåòðóäíî ïîëó÷èòü ôîðìóëû äëÿ
âûõîäíûõ ïðîöåññîâ äèçúþíêòîðà è êîíúþíêòîðà ïðè ðàçëè÷íûõ âõîäíûõ ïðî-
öåññàõ ñ ãëóáèíîé (1,2):
� � � � � � � � � � �0 1 0 1 1 1 1 0a ab c a a b a c b c a b c( , ) ( , ) ( , ); ( , ) ( , ) ( , )a c� ;
� � � � � � � � � �0 0 0 1 0 0a ab c a b a c b c a b a c( , ) ( , ); ( , ) ( , ) ;
� � � � � � � � � �0 1 1 1 1 1a ab c a b a c b c a b a c( , ) ( , ); ( , ) ( , ) ; (22)
� � � � � � � � � � �0 0 0 1 1 0 1 0a ab c a b c a c b c a a b( , ) ( , ) ( , ); ( , ) ( , ) ( , )a c� ;
âõîäíûõ ïðîöåññàõ ñ ãëóáèíîé (2,2):
1 1 1 0 1( , ) ( , ) [ , ( ) ( )] ( , ) ( , )a b c d a c a d b c a c b d� � � � � � � � � � ;
1 1 1 0 0 0( , ) ( , ) [ , ( )]; ( , ) ( , ) [(a b c d a c a c b d a b c d a� � � � � � � � � d b c b d) ( ), ]� � � ;
0 0 0 1 0( , ) ( , ) [ , ( ) ( )] ( , ) ( , )a b c d a c a d b c a c b d� � � � � � � � � � ; (23)
0 1 0 1 0( , ) ( , ) ( , ) ( , ) ( , )a b c d a c b c a d b d� � � � � � � � ;
0 1 1 0 1( , ) ( , ) ( , ) ( , ) ( , )a b c d a c a d b c b d� � � � � � � �
è ò.ä. Àíàëîãè÷íî íàõîäÿòñÿ ÍË-âûðàæåíèÿ âûõîäíûõ ïðîöåññîâ ìíîãîâõîäî-
âûõ äèçúþíêòîðîâ è êîíúþíêòîðîâ, ðåàëèçóþùèõ ìíîãîìåñòíûå áóëåâû
ôóíêöèè äèçúþíêöèþ è êîíúþíêöèþ, àíàëîãè÷íûå èõ äâóìåñòíûì ïðîòîòè-
ïàì (17):
� � � � � � � � � � � � � � � �� � � � � �0 0 0 0 1 1 1 1a b d a b d a b d a b� �... ...; d ;
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3 177
� � � � � � � � � � � � � � � � � � � � � �1 1 1 0 0 0 1a b d e g f a b d a b d e g� � � �[ ; ( � �� f )];
� � � � � � � � � � � � � � � �� � � � � �0 0 0 0 1 1 1 1a b d a b d a b d a b� �... ...; d ; (24)
� � � � � � � � � � � � � � � � � � � � � �1 1 1 0 0 0 0a b d e g f e g f e g f a b� � � �[ ; ( � �� d )] .
3. ÈÄÅß È ÌÅÒÎÄ ÐÅØÅÍÈß
Èíòåðïðåòèðóåì èíòåðâàëû â ñèñòåìå ïîñëåäîâàòåëüíîñòåé èíòåðâàëîâ (1) êàê
âðåìåííûå èíòåðâàëû. Òîãäà ñèñòåìå (1) ìîæíî ïîñòàâèòü âî âçàèìíî îäíîçíà÷-
íîå ñîîòâåòñòâèå ñîâîêóïíîñòü äâîè÷íûõ äèíàìè÷åñêèõ ïðîöåññîâ x ti ( ) (3).
Èìåííî, i-é ïðîöåññ ýòîé ñîâîêóïíîñòè ñîîòâåòñòâóåò i-é ïîñëåäîâàòåëüíîñòè
ñèñòåìû ( , )i n� 1 , ïðè÷åì k-é èìïóëüñ ïðîöåññà ñîîòâåòñòâóåò k-ìó èíòåðâàëó ïî-
ñëåäîâàòåëüíîñòè ( , )k mi� 1 . Äðóãèìè ñëîâàìè, äâîè÷íàÿ ïåðåìåííàÿ x i ni ( , )� 1
ÿâëÿåòñÿ èíäèêàòîðîì ïðèñóòñòâèÿ êàêîãî-òî èíòåðâàëà i-é ïîñëåäîâàòåëüíîñòè
èíòåðâàëîâ (1): xi � 1 îçíà÷àåò ïðèñóòñòâèå, à xi � 0 — îòñóòñòâèå èíòåðâàëà. Ïî-
äàäèì îïðåäåëåííóþ îïèñàííûì îáðàçîì ñîâîêóïíîñòü äâîè÷íûõ äèíàìè÷åñêèõ
ïðîöåññîâ x ti ( ) (3) íà âõîäû x xn1 , ,� ÄÀ áåç ïàìÿòè (ðèñ. 1), êîòîðûé ðåàëèçó-
åò íåêîòîðóþ âûáðàííóþ áóëåâó ôóíêöèþ âõîäîâ y f x xn� ( , , )1 � âèäà (2). Òîã-
äà ÄÀ âûäàñò íà âûõîäå y íåêîòîðûé äâîè÷íûé äèíàìè÷åñêèé ïðîöåññ y t( )
âèäà (4). ×òî õàðàêòåðèçóåò ýòîò ïðîöåññ? Êàê èçâåñòíî, ëþáàÿ áóëåâà ôóíêöèÿ
îïðåäåëÿåòñÿ çàäàííûì ìíîæåñòâîì åäèíè÷íûõ íàáîðîâ çíà÷åíèé àðãóìåíòîâ,
íà êîòîðûõ ôóíêöèÿ ïðèíèìàåò çíà÷åíèå 1. Òàêèì îáðàçîì, âûáðàííàÿ îïðåäå-
ëåííàÿ áóëåâà ôóíêöèÿ f , ïðåäíàçíà÷åííàÿ äëÿ ðåàëèçàöèè â ÄÀ áåç ïàìÿòè
(ðèñ. 1), çàñòàâëÿåò ýòîò ÄÀ âûðàáàòûâàòü íà âûõîäå îïðåäåëåííûé äâîè÷íûé
äèíàìè÷åñêèé ïðîöåññ y t( ) âèäà (4), èìïóëüñû êîòîðîãî ñîîòâåòñòâóþò èíòåðâà-
ëàì âðåìåíè, ãäå âõîäíûå ïðîöåññû x ti ( ) (3) ÄÀ ïðèíèìàþò íàáîð çíà÷åíèé,
ñîâïàäàþùèé ñ îäíèì èç åäèíè÷íûõ íàáîðîâ ôóíêöèè f . Ïîñëåäíåå îçíà÷àåò,
÷òî ïðè ïîäà÷å íà âõîäû ÄÀ áåç ïàìÿòè ñîâîêóïíîñòè äâîè÷íûõ ïðîöåññîâ
x ti ( ) (3), âçàèìíî îäíîçíà÷íî ñîîòâåòñòâóþùèõ ñèñòåìå ïîñëåäîâàòåëüíîñòåé
èíòåðâàëîâ (1), âûáîð äëÿ ðåàëèçàöèè â ýòîì ÄÀ íåêîòîðîé áóëåâîé ôóíêöèè
y f x xn� ( , , )1 � îçíà÷àåò âûáîð ñîîòâåòñòâóþùåãî ÷àñòíîãî ïîêàçàòåëÿ âçàè-
ìîðàñïîëîæåíèÿ ñèñòåìû ïîñëåäîâàòåëüíîñòåé èíòåðâàëîâ (1), à ðåàëèçóåìûé íà
âûõîäå ÄÀ äâîè÷íûé ïðîöåññ y t( ) (4) — ÷èñëîâîå çíà÷åíèå ýòîãî ïîêàçàòåëÿ. Íàï-
ðèìåð, åñëè â êà÷åñòâå ôóíêöèè f âûáðàíà ìíîãîìåñòíàÿ áóëåâà êîíúþíêöèÿ, ýòî
îçíà÷àåò (ïîñêîëüêó ó òàêîé ôóíêöèè åñòü òîëüêî îäèí åäèíè÷íûé íàáîð ( , , , )11 1� )
âûáîð ÷àñòíîãî ïîêàçàòåëÿ âçàèìîðàñïîëîæåíèÿ ñèñòåìû ïîñëåäîâàòåëüíîñòåé èí-
òåðâàëîâ (1) â âèäå âûäåëåíèÿ âñåõ ñëó÷àåâ, êîãäà èíòåðâàëû âñåõ n ïîñëåäîâàòåëü-
íîñòåé (1) ïåðåñåêàþòñÿ. Ïðè ýòîì ÷èñëîâîå çíà÷åíèå äàííîãî ïîêàçàòåëÿ èìååò
âèä äâîè÷íîãî ïðîöåññà y t( ) (4), èìïóëüñû êîòîðîãî ñîîòâåòñòâóþò îòðåçêàì âðå-
ìåíè, â êîòîðûõ èíòåðâàëû âñåõ n ïîñëåäîâàòåëüíîñòåé (1) ïåðåñåêàþòñÿ.
Òàêèì îáðàçîì, â êà÷åñòâå àäåêâàòíîé ìàòåìàòè÷åñêîé ìîäåëè äëÿ ðåøåíèÿ
çàäà÷è àíàëèçà ñèñòåìû ïîñëåäîâàòåëüíîñòåé èíòåðâàëîâ (1) ìîæíî âûáðàòü ÄÀ
áåç ïàìÿòè íà ðèñ. 1. Âõîäíûìè äâîè÷íûìè äèíàìè÷åñêèìè ïðîöåññàìè ýòîãî ÄÀ
ÿâëÿåòñÿ ñîâîêóïíîñòü ïðîöåññîâ (3), âçàèìíî îäíîçíà÷íî ñîîòâåòñòâóþùàÿ ñèñòå-
ìå ïîñëåäîâàòåëüíîñòåé èíòåðâàëîâ (1), ò.å. ñîâîêóïíîñòü ïðîöåññîâ, ìîäåëèðóþ-
ùàÿ ýòó ñèñòåìó. ÄÀ ðåàëèçóåò íåêîòîðóþ, âûáðàííóþ áóëåâó ôóíêöèþ
y f x xn� ( , , )1 � , ÿâëÿþùóþñÿ íåêîòîðûì ÷àñòíûì ïîêàçàòåëåì âçàèìîðàñïîëîæå-
íèÿ ñèñòåìû ïîñëåäîâàòåëüíîñòåé èíòåðâàëîâ. Òîãäà íà âûõîäå ÄÀ âûðàáàòûâàåò-
ñÿ äâîè÷íûé äèíàìè÷åñêèé ïðîöåññ y t( ) (4), äàþùèé ÷èñëîâîå çíà÷åíèå
âûáðàííîãî ÷àñòíîãî ïîêàçàòåëÿ âçàèìîðàñïîëîæåíèÿ èíòåðâàëîâ (áîëåå òî÷íî,
âûäåëÿþùèé îòðåçêè âðåìåíè, â êîòîðûõ èíòåðâàëû ñèñòåìû (1) íàõîäÿòñÿ â äàí-
íîì âçàèìîðàñïîëîæåíèè). Èíà÷å ãîâîðÿ, âûõîäíîé ïðîöåññ (4) ÄÀ-ìîäåëè ðèñ. 1
ìîäåëèðóåò ÷èñëîâîå çíà÷åíèå òîãî èëè èíîãî ÷àñòíîãî ïîêàçàòåëÿ âçàèìîðàñïîëî-
æåíèÿ ñèñòåìû ïîñëåäîâàòåëüíîñòåé èíòåðâàëîâ (1), ñîîòâåòñòâóþùåãî âûáðàííîé
áóëåâîé ôóíêöèè f , ðåàëèçóåìîé ÄÀ.
Àëãîðèòì ðåøåíèÿ çàäà÷è àíàëèçà ñèñòåìû ïîñëåäîâàòåëüíîñòåé èíòåðâàëîâ
(1) â ñîîòâåòñòâèè ñ èçëîæåííîé èäååé èìååò ñëåäóþùèé âèä.
178 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3
Øàã 1. Âûáèðàåòñÿ íåêîòîðûé ÷àñòíûé ïîêàçàòåëü �, õàðàêòåðèçóþùèé âçàè-
ìîðàñïîëîæåíèå èíòåðâàëîâ ñèñòåìû (1) (åñëè ïîêàçàòåëü � óæå çàäàí óñëîâèÿìè
çàäà÷è, øàã 1 îïóñêàåòñÿ).
Øàã 2. Ñòðîèòñÿ áóëåâà ôóíêöèÿ y f x xn� ( , , )1 � , ñîîòâåòñòâóþùàÿ ïîêàçàòåëþ � .
Øàã 3. Ñòðîèòñÿ ìàòåìàòè÷åñêàÿ ìîäåëü çàäà÷è — ñõåìà (ðèñ. 1) ÄÀ áåç ïàìÿ-
òè, ðåàëèçóþùàÿ ôóíêöèþ f è ïîëó÷àþùàÿ íà n ñâîèõ âõîäàõ äâîè÷íûå äèíàìè-
÷åñêèå ïðîöåññû x ti ( ) (3), ñîâîêóïíîñòü êîòîðûõ âçàèìíî îäíîçíà÷íî ñîîòâåòñòâó-
åò çàäàííîé ñèñòåìå ïîñëåäîâàòåëüíîñòåé èíòåðâàëîâ (1). Âûõîäíîé äâîè÷íûé
ïðîöåññ ÄÀ y t( ) (4) ìîäåëèðóåò ïîêàçàòåëü âçàèìîðàñïîëîæåíèÿ ñèñòåìû èíòåðâà-
ëîâ (1) (âûäåëÿåò ïåðèîäû, â òå÷åíèå êîòîðûõ èíòåðâàëû íàõîäÿòñÿ â äàííîì âçàè-
ìîðàñïîëîæåíèè).
Øàã 4. Ìåòîäàìè òåîðèè ÄÀ [1–4] ïî âõîäíûì ïðîöåññàì ÄÀ-ìîäåëè
x t x tn1 ( ), , ( )� è eãî ðåàëèçóåìîé ôóíêöèè f íàõîäèòñÿ åãî âûõîäíîé ïðîöåññ y t( )
(4). Ïàðàìåòðû (ìîìåíòû èçìåíåíèÿ çíà÷åíèé) ýòîãî ïðîöåññà âûðàæàþòñÿ ÷åðåç
àíàëîãè÷íûå ïàðàìåòðû âõîäíûõ ïðîöåññîâ ÄÀ-ìîäåëè â àíàëèòè÷åñêîé ôîðìå
ñ ïîìîùüþ îïåðàöèé äèçúþíêöèè � è êîíúþíêöèè � ÍË.
Øàã 5. Ðàçâåðíóâ íàéäåííûå íà øàãå 4 àíàëèòè÷åñêèå âûðàæåíèÿ ïàðàìåòðîâ
âûõîäíîãî ïðîöåññà ÄÀ-ìîäåëè y t( ), ïîëó÷àåì àëãîðèòìû âû÷èñëåíèÿ ýòèõ ïàðà-
ìåòðîâ â òåðìèíàõ îïåðàöèé ÍË � è �.
Øàã 6. Âû÷èñëèâ ïàðàìåòðû âûõîäíîãî ïðîöåññà ÄÀ-ìîäåëè y t( ) ïî àëãîðèò-
ìàì, íàéäåííûì íà øàãå 5, ïîëó÷àåì ÷èñëîâîå çíà÷åíèå ýòîãî ïðîöåññà, ÿâëÿþùå-
åñÿ ÷èñëîâûì çíà÷åíèåì âûáðàííîãî ÷àñòíîãî ïîêàçàòåëÿ � (èëè f) âçàèìîðàñïî-
ëîæåíèÿ ñèñòåìû ïîñëåäîâàòåëüíîñòåé èíòåðâàëîâ.
Êîíåö àëãîðèòìà.
Çàìåòèì, ÷òî â îáùåì ñëó÷àå ðåøåíèå çàäà÷è àíàëèçà ñèñòåìû ïîñëåäîâàòåëü-
íîñòåé èíòåðâàëîâ (1) ìîæåò ïîòðåáîâàòü èñïîëüçîâàíèÿ íå îäíîãî, à íåñêîëüêèõ
÷àñòíûõ ïîêàçàòåëåé âçàèìîðàñïîëîæåíèÿ èíòåðâàëîâ äàííîé ñèñòåìû (1).  ýòîì
ñëó÷àå ïîëó÷àåòñÿ îáùàÿ çàäà÷à àíàëèçà, ðàñïàäàþùàÿñÿ íà íåñêîëüêî ÷àñòíûõ çà-
äà÷, ñîîòâåòñòâóþùèõ óêàçàííûì ÷àñòíûì ïîêàçàòåëÿì. Äëÿ ðåøåíèÿ îáùåé çàäà-
÷è àíàëèçà ñëåäóåò ðåøèòü ñ ïîìîùüþ îïèñàííîãî àëãîðèòìà âñå ÷àñòíûå çàäà÷è è
îáúåäèíèòü ïîëó÷åííûå ðåøåíèÿ.
Àëãîðèòì ðåøåíèÿ çàäà÷è ñèíòåçà ñèñòåìû ïîñëåäîâàòåëüíîñòåé èíòåðâàëîâ
(1), ñîîòâåòñòâóþùåé çàäàííûì òðåáîâàíèÿì ê âçàèìîðàñïîëîæåíèþ èíòåðâàëîâ,
ñòðîèòñÿ ñ èñïîëüçîâàíèåì îïèñàííîãî àëãîðèòìà ðåøåíèÿ çàäà÷è àíàëèçà ñèñòåìû
(1). Îí ñîñòîèò èç ñëåäóþùèõ øàãîâ.
Øàã 1. Ðåøåíèå ÷àñòè÷íîé çàäà÷è àíàëèçà (ïóòåì âûïîëíåíèÿ øàãîâ 1–4 àëãî-
ðèòìà àíàëèçà) äëÿ ïîäëåæàùåé ñèíòåçó ñèñòåìû ïîñëåäîâàòåëüíîñòåé èíòåðâàëîâ (1)
â ïðåäïîëîæåíèè, ÷òî çàäàí ïîêàçàòåëü âçàèìîðàñïîëîæåíèÿ èíòåðâàëîâ, à âñå ïàðà-
ìåòðû ñèñòåìû (1) (êîîðäèíàòû íà÷àëà è êîíöà âñåõ èíòåðâàëîâ) çàäàíû â áóêâåííîé
ôîðìå.  ðåçóëüòàòå ïîëó÷àåòñÿ äâîè÷íûé ïðîöåññ y t( ), ìîäåëèðóþùèé çàäàííûé ïî-
êàçàòåëü âçàèìîðàñïîëîæåíèÿ èíòåðâàëîâ (1) (òî÷íåå, ñîäåðæàùèé èìïóëüñû-ïåðèî-
äû, â òå÷åíèå êîòîðûõ èíòåðâàëû íàõîäÿòñÿ â çàäàííîì âçàèìîðàñïîëîæåíèè).
Øàã 2. Ñîñòàâëåíèå ñèñòåìû óðàâíåíèé è íåðàâåíñòâ, âûðàæàþùèõ â ìàòåìà-
òè÷åñêîé ôîðìå çàäàííûå òðåáîâàíèÿ ê âçàèìîðàñïîëîæåíèþ èíòåðâàëîâ (1). Äàí-
íàÿ ñèñòåìà ïîëó÷àåòñÿ ïóòåì âûïèñûâàíèÿ òðåáóåìûõ ñîîòíîøåíèé ( , )� � ìåæäó
êîîðäèíàòàìè íà÷àëà è êîíöà ñîîòâåòñòâóþùèõ èìïóëüñîâ ïðîöåññà y t( ). Ïîñêîëü-
êó ýòè êîîðäèíàòû âûðàæàþòñÿ ÷åðåç ïàðàìåòðû èíòåðâàëîâ (1) ñ ïîìîùüþ îïåðà-
öèé ÍË, ïîëó÷åííàÿ ñèñòåìà ÿâëÿåòñÿ ñèñòåìîé óðàâíåíèé è íåðàâåíñòâ ÍË.
Øàã 3. Ðåøåíèå ñèñòåìû óðàâíåíèé è íåðàâåíñòâ ÍË, ïîëó÷åííîé íà øàãå 2,
ñ ïîìîùüþ ñïåöèàëüíûõ ìåòîäîâ [1, 2, 5, 6], îñíîâàííûõ íà ïðèíöèïå ïîñëåäîâàòåëü-
íîãî ðàñ÷ëåíåíèÿ îòäåëüíîãî óðàâíåíèÿ (íåðàâåíñòâà) ÍË íà íåñêîëüêî áîëåå ïðîñòûõ
óðàâíåíèé (íåðàâåíñòâ). Â ðåçóëüòàòå ðåøåíèÿ óêàçàííîé ñèñòåìû óðàâíåíèé (íåðà-
âåíñòâ) ÍË íàõîäÿòñÿ óñëîâèÿ íà ïàðàìåòðû îòäåëüíûõ èíòåðâàëîâ (1), ïðè âûïîëíå-
íèè êîòîðûõ âçàèìîðàñïîëîæåíèå ýòèõ èíòåðâàëîâ îòâå÷àåò çàäàííûì òðåáîâàíèÿì.
Êîíåö àëãîðèòìà.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3 179
4. ÏÐÈÌÅÐ
Ìàãàçèí îòêðûò â òå÷åíèå äíÿ ñ a11 äî b11 è ñ a12 äî b12 ÷àñîâ ( )b a11 12� .
Äâîå ñîòðóäíèêîâ ñîáèðàþòñÿ âìåñòå åãî ïîñåòèòü. Ïåðâûé èç íèõ ñâîáîäåí è
ìîæåò ýòî ñäåëàòü â ïðîìåæóòêå âðåìåíè ñ a21 äî b21 ÷àñîâ, àíàëîãè÷íî âòî-
ðîé — â ïðîìåæóòêå ñ a31 äî b31 ÷àñîâ. Òðåáóåòñÿ îïðåäåëèòü ïåðèîäû âðåìå-
íè, â êàæäîì èç êîòîðûõ îíè ìîãóò ðåàëèçîâàòü ïëàí ïîñåùåíèÿ ìàãàçèíà, è
óñòàíîâèòü, ïðè êàêèõ óñëîâèÿõ ýòî ïîñåùåíèå âîçìîæíî, ò.å. óêàçàííûå ïåðèî-
äû ñóùåñòâóþò (íå âûðîæäåíû).
Ñîòðóäíèêè ìîãóò ðåàëèçîâàòü ñâîé ïëàí ïîñåùåíèÿ ìàãàçèíà â òå è òîëüêî òå
ïåðèîäû âðåìåíè, êîãäà îí îòêðûò, à îáà îíè ñâîáîäíû. Ñëåäîâàòåëüíî, äëÿ îòâåòà
íà ïåðâûé âîïðîñ íóæíî ðåøèòü çàäà÷ó àíàëèçà ñèñòåìû ïîñëåäîâàòåëüíîñòåé
èíòåðâàëîâ
A a b a b1 11 11 12 12� ( , ), ( , ) ; A a b2 21 21� ( , ) ; A a b3 31 31� ( , ) ,
ò.å. îïðåäåëèòü íóæíîå âçàèìîðàñïîëîæåíèå èíòåðâàëîâ ýòîé ñèñòåìû. Êîíêðåò-
íî, ïðåäñòàâëÿþò èíòåðåñ òå ïåðèîäû âðåìåíè, â òå÷åíèå êîòîðûõ âçàèìîðàñïî-
ëîæåíèå òàêîâî, ÷òî ïðèñóòñòâóþò èíòåðâàëû âñåõ òðåõ ïîñëåäîâàòåëüíîñòåé:
A A A1 2 3, , . Äëÿ ðåøåíèÿ çàäà÷è ïðèìåíèì àëãîðèòì àíàëèçà ðàçä. 3.
Øàã 1. Ïîêàçàòåëü �, õàðàêòåðèçóþùèé íóæíîå âçàèìîðàñïîëîæåíèå èíòåð-
âàëîâ ñèñòåìû A A A1 2 3, , , ñîäåðæàòåëüíî óæå çàäàí óñëîâèÿìè çàäà÷è.
Øàã 2. Áóëåâà ôóíêöèÿ y f x x x� ( , , )1 2 3 , ñîîòâåòñòâóþùàÿ ïîêàçàòåëþ �,
åñòü òðåõìåñòíàÿ êîíúþíêöèÿ y x x x� � �1 2 3 .
Øàã 3. Ìàòåìàòè÷åñêàÿ ìîäåëü çàäà÷è — ÄÀ áåç ïàìÿòè ñ 3 âõîäàìè è 1 âû-
õîäîì, ðåàëèçóþùèé íà âûõîäå óêàçàííóþ ôóíêöèþ f ñâîèõ âõîäîâ (ðèñ. 3). Íà
âõîäû ÄÀ-ìîäåëè ïîñòóïàþò äâîè÷íûå ïðîöåññû
x t a b a b x t a b1 11 11 12 12 2 21 211 0 1 1( ) ( , ) ( , ) ( , ), ( ) ( , ),� � � � x t a b3 31 311( ) ( , )� ,
âçàèìíî îäíîçíà÷íî ñîîòâåòñòâóþùèå çàäàííîé
ñèñòåìå èíòåðâàëîâ ( , , )A A A1 2 3 . Ñ âûõîäà ÄÀ
ñíèìàåòñÿ äâîè÷íûé ïðîöåññ y t( ) âèäà (4), ìî-
äåëèðóþùèé ïîêàçàòåëü � âçàèìîðàñïîëîæåíèÿ
ñèñòåìû èíòåðâàëîâ ( , , )A A A1 2 3 .
Øàã 4. Ïî âõîäíûì ïðîöåññàì
x t x t x t1 2 3( ), ( ), ( ) ÄÀ-ìîäåëè è åãî ðåàëèçóåìîé
ôóíêöèè f � � íàõîäèì åãî âûõîäíîé ïðîöåññ
y t( ) [1, 2, 4], èñïîëüçóÿ ãîòîâóþ ôîðìóëó
1 1 1( , ) ( , ) [ , ( )]a b c d a c a c b d� � � � � � :
y t x t x t x t x t x t x t a( ) ( ) ( ) ( ) ( ) [ ( ) ( )] [ ( ,� � � � � � �1 2 3 1 2 3 111 b a b11 12 120 1) ( , ) ( , )]� � �
� � � � �[ ( , ) ( )] [ ( , ) ( , ) ( ,,1 1 1 0 121 21 31 31 11 11 12 1a b a b a b a b 2 )]�
� �� � � � � � � � � �1 1 1 021 31 21 31 21 31 11 11[ , ( )] ( , ) [ ] ( ,a a a a b b a b � �) ( , ) [ ]1 112 12a b � � �
� � � � � � � � � �1 11 21 31 11 21 31 11 21 31 21 31a a a a a a b a a b b, [ ( ( ))� � �] ( , )0 1 12� � �a
�� � � � � � � � �a a a a a b a a b b21 31 12 21 31 12 21 31 21 31, [ ( ( ))] .
Øàã 5. Íàéäåííûå íà øàãå 4 àíàëèòè÷åñêèå âûðàæåíèÿ ïàðàìåòðîâ A B C D, , ,
âûõîäíîãî ïðîöåññà y t A B C D( ) ( , ) ( , ) ( , )� � �1 0 1 ÄÀ-ìîäåëè äàþò àëãîðèòìû âû÷èñ-
ëåíèÿ ýòîãî ïðîöåññà â òåðìèíàõ îïåðàöèé ÍË � (max) è � (min). Íàïðèìåð,
A a a a� max( , , )11 21 31 , B A b a a b b� max( , min ( ,max( , ,min ( , ))))11 21 31 21 31 è ò.ä.
Øàã 6. Ïî àëãîðèòìàì, íàéäåííûì íà øàãå 5, îïðåäåëÿåì ïàðàìåòðû âûõîä-
íîãî ïðîöåññà y t( ) ÄÀ-ìîäåëè, ñîîòâåòñòâóþùèå êîíêðåòíûì çíà÷åíèÿì ïàðàìåò-
ðîâ a bij ij, âõîäíûõ ïðîöåññîâ x t x t x t1 2 3( ), ( ), ( ) . Íàïðèìåð, ïðè a11 9� , a12 14� ,
b11 13� , b12 20� , a21 12� , b21 16� , a31 11� , b31 15� íàõîäèì A � 12, B � 13, C � 14,
D � 15. Òàêèì îáðàçîì, èìåþòñÿ äâà ïåðèîäà âðåìåíè, â òå÷åíèå êîòîðûõ îáà ñî-
òðóäíèêà ìîãóò ñîâìåñòíî ïîñåòèòü ìàãàçèí: ( , )12 13 è ( , )14 15 .
180 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3
3x
1x
y
��f
2x
Ðèñ. 3. ÄÀ áåç ïàìÿòè, ðåàëèçóþùèé
3-ìåñòíóþ êîíúþíêöèþ
Äëÿ òîãî ÷òîáû óñòàíîâèòü, ïðè êàêèõ îáùèõ óñëîâèÿõ âîçìîæíî ñîâìåñòíîå
ïîñåùåíèå ìàãàçèíà äâóìÿ ñîòðóäíèêàìè, íóæíî îïðåäåëèòü, êîãäà ñóùåñòâóþò
ïåðèîäû âðåìåíè, â êîòîðûå îíè ìîãóò ñîâìåñòíî ïîñåòèòü ìàãàçèí. Òàêèì îáðà-
çîì, äëÿ îòâåòà íà âòîðîé âîïðîñ íóæíî ðåøèòü çàäà÷ó ñèíòåçà ñèñòåìû ïîñëåäîâà-
òåëüíîñòåé èíòåðâàëîâ ( , , )A A A1 2 3 , ò.å. íàéòè óñëîâèÿ, ïðè êîòîðûõ âçàèìîðàñïî-
ëîæåíèå èíòåðâàëîâ ýòîé ñèñòåìû èìååò íóæíûé êà÷åñòâåííûé õàðàêòåð, áëàãîäà-
ðÿ ÷åìó è îáåñïå÷èâàåòñÿ ñóùåñòâîâàíèå óêàçàííûõ ïåðèîäîâ âðåìåíè. Äëÿ
ðåøåíèÿ çàäà÷è ïðèìåíèì àëãîðèòì ñèíòåçà èç ðàçä. 3.
Øàã 1. Óæå âûïîëíåí è ñîäåðæèòñÿ â øàãàõ 1–4 àëãîðèòìà àíàëèçà ñèñòåìû
( , , )A A A1 2 3 , âûïîëíåííûõ âûøå.
Øàã 2. Ñèñòåìó óðàâíåíèé è íåðàâåíñòâ ÍË, âûðàæàþùèõ òðåáîâàíèÿ ê âçàè-
ìîðàñïîëîæåíèþ èíòåðâàëîâ ñèñòåìû ( , , )A A A1 2 3 , îáåñïå÷èâàþùèå íóæíûå ïå-
ðèîäû âðåìåíè, ïîëó÷àåì, ïîòðåáîâàâ, ÷òîáû íàéäåííûé â ïðîöåññå àíàëèçà ñèñòå-
ìû ( , , )A A A1 2 3 âûõîäíîé ïðîöåññ y t A B C D( ) ( , ) ( , ) ( , )� � �1 0 1 ÄÀ-ìîäåëè, ìîäåëè-
ðóþùèé çàäàííûé ïîêàçàòåëü âçàèìîðàñïîëîæåíèÿ èíòåðâàëîâ, èìåë
íåâûðîæäåííûå èìïóëüñû, ìîäåëèðóþùèå òðåáóåìûå ïåðèîäû âðåìåíè: B A� èëè
D C� . Ïîäñòàâèâ ñþäà âûðàæåíèÿ äëÿ A B C D, , , èç ðàçâåðíóòîãî âûðàæåíèÿ ïðî-
öåññà y t( ), ïðèâåäåííîãî âûøå, ïîëó÷èì
a a a b a a b b a a a11 21 31 11 21 31 21 31 11 21 31� � � � � � � � � �[ ( ( ))]
èëè
a a a b a a b b a a a12 21 31 12 21 31 21 31 12 21 31� � � � � � � � � �[ ( ( ))] .
Øàã 3. Óïðîñòèâ ïîëó÷åííûå íà øàãå 2 íåðàâåíñòâà ÍË, ïîëó÷èì
b a a b b a a a11 21 31 21 31 11 21 31� � � � � � �[ ( )]
èëè
b a a b b a a a12 21 31 21 31 12 21 31� � � � � � �[ ( )] .
Âçàèìîðàñïîëîæåíèå èíòåðâàëîâ ñèñòåìû ( , , )A A A1 2 3 , îòâå÷àþùåå õîòÿ áû
îäíîìó èç âûïèñàííûõ íåðàâåíñòâ, îáåñïå÷èâàåò íàëè÷èå ïåðèîäîâ âðåìåíè, â òå-
÷åíèå êîòîðûõ ñîòðóäíèêè ìîãóò ñîâìåñòíî ïîñåòèòü ìàãàçèí. Åùå ðàç îáðàòèì
âíèìàíèå, ÷òî îáå ÷àñòè âûïèñàííûõ íåðàâåíñòâ (óñëîâèé) ïðåäñòàâëÿþò ñîáîé
âûðàæåíèÿ, ïîñòðîåííûå èç ïàðàìåòðîâ èíòåðâàëîâ ñèñòåìû ( , , )A A A1 2 3 ñ ïî-
ìîùüþ îïåðàöèé ÍË — äèçúþíêöèè � è êîíúþíêöèè �.
ÇÀÊËÞ×ÅÍÈÅ
 íàñòîÿùåé ðàáîòå ïîêàçàíî, ÷òî èçó÷åíèå êëàññà êîìáèíàòîðíûõ çàäà÷, ýêâè-
âàëåíòíûõ êîìáèíàòîðíîé çàäà÷å îïðåäåëåíèÿ âçàèìîðàñïîëîæåíèÿ n ïîñëåäîâà-
òåëüíîñòåé èíòåðâàëîâ, ìîæíî îñóùåñòâëÿòü ñ ïîìîùüþ ìàòåìàòè÷åñêîé ìîäåëè
äèíàìè÷åñêîãî êîíå÷íîãî àâòîìàòà áåç ïàìÿòè è ìàòåìàòè÷åñêîãî àïïàðàòà íå-
ïðåðûâíîé ëîãèêè. Òàêîé ïîäõîä ïîçâîëÿåò ôîðìàëüíî íàõîäèòü àëãîðèòìû ðå-
øåíèÿ óêàçàííûõ çàäà÷, à òàêæå ôîðìàëüíî àíàëèçèðîâàòü ýòè ðåøåíèÿ, íàïðè-
ìåð, íàõîäèòü íåîáõîäèìûå è äîñòàòî÷íûå óñëîâèÿ èõ ñóùåñòâîâàíèÿ. Äðóãèì
ïðåèìóùåñòâîì ïðåäëîæåííîãî ïîäõîäà ÿâëÿåòñÿ åãî ïðèìåíèìîñòü ê ðåøåíèþ
çàäà÷ ïðîèçâîëüíî âûñîêîé ðàçìåðíîñòè.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ë å â è í  . È . Ââåäåíèå â äèíàìè÷åñêóþ òåîðèþ êîíå÷íûõ àâòîìàòîâ. — Ðèãà: Çèíàòíå, 1975. —
376 ñ.
2. B o c h m a n n D . , R o g i n s k i j V . N . , L e v i n V . I . Dinamische Processe in Automaten. — Berlin:
Technik, 1977. — 280 ñ.
3. Ë å â è í  . È . Äèíàìèêà ëîãè÷åñêèõ óñòðîéñòâ è ñèñòåì. — Ì.: Ýíåðãèÿ, 1980. — 230 ñ.
4. Ë å â è í  . È . Òåîðèÿ äèíàìè÷åñêèõ àâòîìàòîâ. — Ïåíçà: Èçä-âî Ïåíç. ãîñ. óí-òà, 1995. — 407 ñ.
5. Ë å â è í  . È . Áåñêîíå÷íîçíà÷íàÿ ëîãèêà â çàäà÷àõ êèáåðíåòèêè. — Ì.: Ðàäèî è ñâÿçü, 1982. —
176 ñ.
6. Ë å â è í  . È . Ñòðóêòóðíî-ëîãè÷åñêèå ìåòîäû èññëåäîâàíèÿ ñëîæíûõ ñèñòåì. — Ì.: Íàóêà, 1987.
— 304 ñ.
Ïîñòóïèëà 04.07.2007
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3 181
|
| id | nasplib_isofts_kiev_ua-123456789-44376 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-01T01:41:39Z |
| publishDate | 2009 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Левин, В.И. 2013-05-31T16:37:55Z 2013-05-31T16:37:55Z 2009 Непрерывная логика и алгоритмы решения некоторых комбинаторных задач / В.И. Левин // Кибернетика и системный анализ. — 2009. — № 3. — С. 173-181. — Бібліогр.: 6 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/44376 519.715 Сформульовано клас комбінаторних задач, еквівалентних задачі визначення взаємного розміщення n послідовностей інтервалів. Показано, що адекватною математичною моделлю розв’язку поставленої задачі є кінцевий динамічний автомат без пам'яті, а адекватним математичним апаратом — неперервна логіка. Побудовано алгоритми розв’язку. The class of combinatorial problems equivalent to the problem of determination of relative positions of n interval sequences is formulated. It is shown that an adequate mathematical model of solving the stated problem is a finite dynamic automaton without memory and that the adequate mathematical apparatus is continuous logic. Algorithms for the solution of the problem are constructed. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Новые средства кибернетики, информатики, вычислительной техники и системного анализа Непрерывная логика и алгоритмы решения некоторых комбинаторных задач Неперервна логіка та алгоритми розв’язку деяких комбінаторних задач Continuous logic and algorithms of solution of some combinatory problems Article published earlier |
| spellingShingle | Непрерывная логика и алгоритмы решения некоторых комбинаторных задач Левин, В.И. Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| title | Непрерывная логика и алгоритмы решения некоторых комбинаторных задач |
| title_alt | Неперервна логіка та алгоритми розв’язку деяких комбінаторних задач Continuous logic and algorithms of solution of some combinatory problems |
| title_full | Непрерывная логика и алгоритмы решения некоторых комбинаторных задач |
| title_fullStr | Непрерывная логика и алгоритмы решения некоторых комбинаторных задач |
| title_full_unstemmed | Непрерывная логика и алгоритмы решения некоторых комбинаторных задач |
| title_short | Непрерывная логика и алгоритмы решения некоторых комбинаторных задач |
| title_sort | непрерывная логика и алгоритмы решения некоторых комбинаторных задач |
| topic | Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| topic_facet | Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/44376 |
| work_keys_str_mv | AT levinvi nepreryvnaâlogikaialgoritmyrešeniânekotoryhkombinatornyhzadač AT levinvi neperervnalogíkataalgoritmirozvâzkudeâkihkombínatornihzadač AT levinvi continuouslogicandalgorithmsofsolutionofsomecombinatoryproblems |