О некоторых задачах анализа гибридных автоматов
Определен класс 1-мерных гибридных автоматов, в которых в каждом дискретном состоянии для различных множеств начальных значений непрерывного состояния динамика может быть представлена различными дифференциальными уравнениями, и задана конечная продолжительность этой динамики, которая может быть разл...
Збережено в:
| Дата: | 2018 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2018
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/161365 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | О некоторых задачах анализа гибридных автоматов / В.В. Скобелев, В.Г. Скобелев // Кибернетика и системный анализ. — 2018. — Т. 54, № 4. — С. 3–15. — Бібліогр.: 13назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-161365 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1613652019-12-08T01:25:46Z О некоторых задачах анализа гибридных автоматов Скобелев, В.В. Скобелев, В.Г. Кібернетика Определен класс 1-мерных гибридных автоматов, в которых в каждом дискретном состоянии для различных множеств начальных значений непрерывного состояния динамика может быть представлена различными дифференциальными уравнениями, и задана конечная продолжительность этой динамики, которая может быть различной для разных множеств начальных значений непрерывного состояния. Предложены алгоритмы решения задач устранения противоречия в объектах, определяющих гибридный автомат, согласования этих объектов один с другим, нахождения минимального числа переключений и оценки минимального времени, за которое дискретные состояния достижимы из множества начальных дискретных состояний . Визначено клас 1-вимірних гібридних автоматів, у яких у кожному дискретному стані для різних множин початкових значень неперервного стану динаміка може бути представлена різними диференціальними рівняннями, та задано скінченну тривалість цієї динаміки, яка може бути різною для різних множин початкових значень неперервного стану. Запропоновано алгоритми розв’язання задач вилучення суперечностей в об’єктах, які визначають гібридний автомат, узгодження цих об’єктів один з одним, знаходження мінімального числа перемикань та оцінки мінімального часу, за який дискретні стани досяжні з множини початкових дискретних станів . A class of 1-dimensional hybrid automata is defined, such that in each discrete state, the dynamics can be presented by different differential equations for different sets of initial values of continuous state, each dynamics duration is finite, and can be different for different sets of initial values of continuous state. Algorithms are proposed to solve problems of eliminating contradictions in objects that define the hybrid automata, of coordinating these objects with each other, calculating the minimum number of switchings, and estimating the minimum time for reachability of discrete states from the set of initial discrete states. 2018 Article О некоторых задачах анализа гибридных автоматов / В.В. Скобелев, В.Г. Скобелев // Кибернетика и системный анализ. — 2018. — Т. 54, № 4. — С. 3–15. — Бібліогр.: 13назв. — рос. 1019-5262 http://dspace.nbuv.gov.ua/handle/123456789/161365 519.68+681.3 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Кібернетика Кібернетика |
| spellingShingle |
Кібернетика Кібернетика Скобелев, В.В. Скобелев, В.Г. О некоторых задачах анализа гибридных автоматов Кибернетика и системный анализ |
| description |
Определен класс 1-мерных гибридных автоматов, в которых в каждом дискретном состоянии для различных множеств начальных значений непрерывного состояния динамика может быть представлена различными дифференциальными уравнениями, и задана конечная продолжительность этой динамики, которая может быть различной для разных множеств начальных значений непрерывного состояния. Предложены алгоритмы решения задач устранения противоречия в объектах, определяющих гибридный автомат, согласования этих объектов один с другим, нахождения минимального числа переключений и оценки минимального времени, за которое дискретные состояния достижимы из множества начальных дискретных состояний . |
| format |
Article |
| author |
Скобелев, В.В. Скобелев, В.Г. |
| author_facet |
Скобелев, В.В. Скобелев, В.Г. |
| author_sort |
Скобелев, В.В. |
| title |
О некоторых задачах анализа гибридных автоматов |
| title_short |
О некоторых задачах анализа гибридных автоматов |
| title_full |
О некоторых задачах анализа гибридных автоматов |
| title_fullStr |
О некоторых задачах анализа гибридных автоматов |
| title_full_unstemmed |
О некоторых задачах анализа гибридных автоматов |
| title_sort |
о некоторых задачах анализа гибридных автоматов |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2018 |
| topic_facet |
Кібернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/161365 |
| citation_txt |
О некоторых задачах анализа гибридных автоматов / В.В. Скобелев, В.Г. Скобелев // Кибернетика и системный анализ. — 2018. — Т. 54, № 4. — С. 3–15. — Бібліогр.: 13назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT skobelevvv onekotoryhzadačahanalizagibridnyhavtomatov AT skobelevvg onekotoryhzadačahanalizagibridnyhavtomatov |
| first_indexed |
2025-07-14T13:57:27Z |
| last_indexed |
2025-07-14T13:57:27Z |
| _version_ |
1837630958644232192 |
| fulltext |
Â.Â. ÑÊÎÁÅËÅÂ, Â.Ã. ÑÊÎÁÅËÅÂ
ÓÄÊ 519.68+681.3 Î ÍÅÊÎÒÎÐÛÕ ÇÀÄÀ×ÀÕ ÀÍÀËÈÇÀ
ÃÈÁÐÈÄÍÛÕ ÀÂÒÎÌÀÒÎÂ
Àííîòàöèÿ. Îïðåäåëåí êëàññ 1-ìåðíûõ ãèáðèäíûõ àâòîìàòîâ, â êîòîðûõ
â êàæäîì äèñêðåòíîì ñîñòîÿíèè äëÿ ðàçëè÷íûõ ìíîæåñòâ íà÷àëüíûõ çíà÷å-
íèé íåïðåðûâíîãî ñîñòîÿíèÿ äèíàìèêà ìîæåò áûòü ïðåäñòàâëåíà ðàçëè÷íûìè
äèôôåðåíöèàëüíûìè óðàâíåíèÿìè, è çàäàíà êîíå÷íàÿ ïðîäîëæèòåëüíîñòü
ýòîé äèíàìèêè, êîòîðàÿ ìîæåò áûòü ðàçëè÷íîé äëÿ ðàçíûõ ìíîæåñòâ íà÷àëü-
íûõ çíà÷åíèé íåïðåðûâíîãî ñîñòîÿíèÿ. Ïðåäëîæåíû àëãîðèòìû ðåøåíèÿ çà-
äà÷ óñòðàíåíèÿ ïðîòèâîðå÷èÿ â îáúåêòàõ, îïðåäåëÿþùèõ ãèáðèäíûé àâòîìàò,
ñîãëàñîâàíèÿ ýòèõ îáúåêòîâ îäèí ñ äðóãèì, íàõîæäåíèÿ ìèíèìàëüíîãî ÷èñëà
ïåðåêëþ÷åíèé è îöåíêè ìèíèìàëüíîãî âðåìåíè, çà êîòîðîå äèñêðåòíûå ñî-
ñòîÿíèÿ äîñòèæèìû èç ìíîæåñòâà íà÷àëüíûõ äèñêðåòíûõ ñîñòîÿíèé.
Êëþ÷åâûå ñëîâà: ãèáðèäíûå àâòîìàòû, âåðèôèêàöèÿ.
ÂÂÅÄÅÍÈÅ
Ñîâðåìåííûå èíôîðìàöèîííûå òåõíîëîãèè èíèöèèðîâàëè âíåäðåíèå êè-
áåð-ôèçè÷åñêèõ ñèñòåì (ÊÔÑ) ïðàêòè÷åñêè âî âñå ñôåðû æèçíåäåÿòåëüíîñòè
÷åëîâåêà [1–3]. Ãîâîðÿ íåôîðìàëüíî, ÊÔÑ — ýòî ñèñòåìû, â êîòîðûõ êîì-
ïüþòåðû è âñòðîåííûå êîíòðîëëåðû óïðàâëÿþò ôèçè÷åñêèìè ïðîöåññàìè ïî-
ñðåäñòâîì îáðàòíûõ ñâÿçåé, ò.å. ôèçè÷åñêèå ïðîöåññû âëèÿþò íà âû÷èñëåíèÿ,
à âû÷èñëåíèÿ — íà âûáîð è õîä ôèçè÷åñêèõ ïðîöåññîâ [4, 5]. Êàê ïðàâèëî,
òàêèå ñèñòåìû èìåþò êðèòè÷åñêóþ îáëàñòü ïðèìåíåíèÿ. Ïîýòîìó ïðè ïðîåê-
òèðîâàíèè ïðåäúÿâëÿþòñÿ ïîâûøåííûå òðåáîâàíèÿ ê èõ íàäåæíîñòè è áåçî-
ïàñíîñòè. Ðåòðîñïåêòèâíûé àíàëèç è ñîâðåìåííîå ñîñòîÿíèå òåîðèè ÊÔÑ
ïðåäñòàâëåíû â [6].  íàñòîÿùåå âðåìÿ îñíîâíîé ìàòåìàòè÷åñêîé ìîäåëüþ,
èñïîëüçóåìîé ïðè èññëåäîâàíèè ÊÔÑ, ÿâëÿåòñÿ ãèáðèäíûé àâòîìàò (ÃÀ).
Èíòåíñèâíîå ðàçâèòèå òåîðèè ÃÀ íà÷àëîñü ñ ðàáîòû [7].
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È
Ñîãëàñíî [7, 8] ãèáðèäíûé àâòîìàò — ýòî ñèñòåìà H� ( , , , , , ,V E X� Init Inv
Flow Jump, ), ãäå V — êîíå÷íîå ìíîæåñòâî âåðøèí, ñîîòâåòñòâóþùèõ íåïðå-
ðûâíûì ðåæèìàì ðàáîòû; � — êîíå÷íîå ìíîæåñòâî èìåí äèñêðåòíûõ ñîáû-
òèé; E V V� � �� — ìíîæåñòâî äèñêðåòíûõ ïåðåõîäîâ (v v1 2
�� �� — ïåðåõîä
èç âåðøèíû v1 â âåðøèíó v2 ïîä äåéñòâèåì ñîáûòèé �); X x xn� { }1, ,� —
ìíîæåñòâî äåéñòâèòåëüíûõ ïåðåìåííûõ, ãäå n — ðàçìåðíîñòü ÃÀ ( �X �
= { }� , , �x xn1 � — ìíîæåñòâî ïðîèçâîäíûõ ïî âðåìåíè ïåðåìåííûõ èç X ,
à � � � �X x xn{ }1, ,� — ìíîæåñòâî ïåðåäàâàåìûõ ïðè äèñêðåòíûõ ïåðåõîäàõ çíà-
÷åíèé ïåðåìåííûõ èç X ); Init, Inv, Flow — îòîáðàæåíèÿ ìíîæåñòâà âåðøèí V
âî ìíîæåñòâà òàêèõ ïðåäèêàòîâ, ÷òî äëÿ êàæäîé âåðøèíû v V ñâîáîäíûå ïå-
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 4 3
Â.Â. Ñêîáåëåâ, Â.Ã. Ñêîáåëåâ, 2018
ðåìåííûå ïðåäèêàòîâ Init( )v è Inv( )v ïðèíàäëåæàò ìíîæåñòâó X , à ñâîáîäíûå
ïåðåìåííûå ïðåäèêàòà Flow ( )v — ìíîæåñòâó X X� � (Init( )v îïðåäåëÿåò çíà÷å-
íèÿ ïåðåìåííûõ, èç êîòîðûõ ÃÀ ìîæåò ñòàðòîâàòü â v, Inv( )v îïðåäåëÿåò îãðà-
íè÷åíèÿ íà çíà÷åíèÿ ïåðåìåííûõ, ïðè êîòîðûõ ðåàëèçóåòñÿ íåïðåðûâíàÿ äè-
íàìèêà ÃÀ â v, à Flow ( )v îïðåäåëÿåò óðàâíåíèÿ äèíàìèêè ÃÀ â v); Jump —
îòîáðàæåíèå ìíîæåñòâà E âî ìíîæåñòâî ïðåäèêàòîâ, ñâîáîäíûå ïåðåìåííûå
êîòîðûõ ïðèíàäëåæàò X X� ' (Jump ( )e ( )e v v� � ��1 2
�
îïðåäåëÿåò, êîãäà âîç-
ìîæåí äèñêðåòíûé ïåðåõîä, ñîîòâåòñòâóþùèé ñîáûòèþ �, à òàêæå êàêèå çíà-
÷åíèÿ ïåðåìåííûõ è êàêèì îáðàçîì èçìåíÿþòñÿ ïðè ýòîì ïåðåõîäå).
Òàêîå îïðåäåëåíèå ÃÀ ÿâëÿåòñÿ óäîáíîé êîíöåïòóàëüíîé ìîäåëüþ, íî ñî-
âåðøåííî íå ïðåäíàçíà÷åíî äëÿ ðàçðàáîòêè àëãîðèòìîâ âåðèôèêàöèè è òåñòèðî-
âàíèÿ ïðîåêòðóåìîé ÊÔÑ. Ïðè òàêîì ïîäõîäå ïðè ðåøåíèè êîíêðåòíûõ çàäà÷
ñ ïîìîùüþ òåõ èëè èíûõ èíñòðóìåíòàëüíûõ ñðåäñòâ èññëåäîâàòåëþ ïðèõîäèòñÿ
ñàìîñòîÿòåëüíî äîîïðåäåëÿòü, äåòàëèçèðîâàòü è ïåðåôîðìóëèðîâàòü ðàññìàòðè-
âàåìûå îáúåêòû è ïîíÿòèÿ.  ðåçóëüòàòå ïîëó÷åííóþ ìîäåëü âåñüìà ïðîáëåìà-
òè÷íî âòèñíóòü â èçëîæåííîå âûøå îïðåäåëåíèå ÃÀ. Ïðèâåäåííûé â [9] àíàëèç
ñóùåñòâóþùèõ ÿçûêîâ è ñðåäñòâ, ïðåäíàçíà÷åííûõ äëÿ ïðîåêòèðîâàíèÿ ÃÀ,
ïîêàçûâàåò, ÷òî äëÿ ðàçðàáîòêè àëãîðèòìîâ èõ âåðèôèêàöèè è òåñòèðîâàíèÿ
áîëåå óäîáíûì ÿâëÿåòñÿ ñëåäóþùåå îïðåäåëåíèå.
Ñëåäóÿ [10], ÃÀ — ýòî ñèñòåìà H� ( , , , , , , , )Q X I D f E G R , ãäå Q — ìíîæåñòâî
äèñêðåòíûõ ñîñòîÿíèé; X n� � — ìíîæåñòâî íåïðåðûâíûõ ñîñòîÿíèé; Q X� —
ìíîæåñòâî ñîñòîÿíèé; I Q X� � — ìíîæåñòâî íà÷àëüíûõ ñîñòîÿíèé;
D Q X: ( )� B — îáëàñòü äîïóñòèìûõ çíà÷åíèé íåïðåðûâíîãî ñîñòîÿíèÿ â äàííîì
äèñêðåòíîì ñîñòîÿíèè; f q D q
q Q
n: ( ( )){ }� �
� � — âåêòîðíîå ïîëå; E Q Q� � —
ìíîæåñòâî äóã; G E X: ( )� B — îõðàííîå âûðàæåíèå, îïðåäåëÿþùåå óñëîâèå ïå-
ðåêëþ÷åíèÿ; R E X X: ( )� � B — îòîáðàæåíèå ñáðîñà, îïðåäåëÿþùåå ïåðåäàâàå-
ìûå çíà÷åíèÿ íåïðåðûâíîãî ñîñòîÿíèÿ ïðè äèñêðåòíîì ïåðåõîäå.
Áåçóñëîâíîå ïðåèìóùåñòâî îïðåäåëåíèÿ ÃÀ â [10] ïåðåä îïðåäåëåíèåì â [7, 8]
ñîñòîèò â òîì, ÷òî â ýòó ìîäåëü åñòåñòâåííî âñòðàèâàþòñÿ êîíñòðóêöèè âðåìåí-
íûõ ìíîæåñòâ (â êîòîðûõ äîïóñêàþòñÿ ìãíîâåííûå ïåðåêëþ÷åíèÿ) è ãèáðèäíûå
òðàåêòîðèè (ñëåäóåò îòìåòèòü, ÷òî áîëåå òîíêèé àíàëèç ýòèõ êîíñòðóêöèé ìîæåò
áûòü ðåàëèçîâàí â òåðìèíàõ ïîëóãðóïïîâîãî ÃÀ, ââåäåííîãî â [11]). Â íàñòîÿ-
ùåé ñòàòüå çà îñíîâó ïðèíÿòî îïðåäåëåíèå ÃÀ, ïðèâåäåííîå â [10].
Ïðè ïîñòðîåíèè ÃÀ H� ( , , , , , , , )Q X I D f E G R âî âõîäÿùèå â íåãî îáúåêòû
ìîæåò áûòü âíåñåíà êàê ïðîòèâîðå÷èâàÿ èíôîðìàöèÿ, òàê è èíôîðìàöèÿ, êîòî-
ðàÿ íèêîãäà íå áóäåò ðåàëèçîâàíà ïðè êîððåêòíîì ôóíêöèîíèðîâàíèè. Î÷åâèä-
íî, ÷òî âñå ïðîòèâîðå÷èÿ â îáúåêòàõ ÃÀ íåîáõîäèìî óñòðàíèòü, òàê êàê îíè ìî-
ãóò ïðèâåñòè ê íåïðåäñêàçóåìûì ïîñëåäñòâèÿì. Èíôîðìàöèÿ, êîòîðàÿ íèêîãäà
íå áóäåò ðåàëèçîâàíà ïðè êîððåêòíîì ôóíêöèîíèðîâàíèè ÃÀ, ìîæåò ñóùåñòâåí-
íî óñëîæíèòü åãî àíàëèç. Ïîýòîìó âîçíèêàåò ñëåäóþùàÿ çàäà÷à.
Çàäà÷à 1. Óñòðàíèòü ïðîòèâîðå÷èÿ â îáúåêòàõ, îïðåäåëÿþùèõ ÃÀ, è ñîãëà-
ñîâàòü ýòè îáúåêòû îäèí ñ äðóãèì.
Çàìå÷àíèå 1. Ñëîæíîñòü ðåøåíèÿ çàäà÷è 1 ñóùåñòâåííî âîçðàñòàåò ïðè íà-
ëè÷èè â ÃÀ óïðàâëÿåìûõ ïàðàìåòðîâ, ò.å. èõ çíà÷åíèÿ ìîæíî èçìåíÿòü â ïðîöåñ-
ñå ôóíêöèîíèðîâàíèÿ ÊÔÑ. Âûáîð îïòèìàëüíûõ çíà÷åíèé òàêèõ ïàðàìåòðîâ
ïðåäñòàâëÿåò, ïî ñóòè, çàäà÷ó ìíîãîôàêòîðíîé îïòèìèçàöèè è òðåáóåò ðàçðàáîò-
êè ñïåöèàëüíûõ ìåòîäîâ åå ðåøåíèÿ. Ïîýòîìó âîïðîñû, ñâÿçàííûå ñ óïðàâëåíè-
åì ïàðàìåòðàìè, íå ðàññìàòðèâàþòñÿ â íàñòîÿùåé ðàáîòå.
4 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 4
Ðåçóëüòàòîì ðåøåíèÿ çàäà÷è 1 ÿâëÿåòñÿ ÃÀ, ïðåäñòàâëÿþùèé ìàòåìàòè÷åñ-
êóþ ìîäåëü, êîòîðàÿ ïðåäíàçíà÷åíà äëÿ ïðîöåññà âåðèôèêàöèè ñèñòåìû óïðàâëå-
íèÿ ðàçðàáàòûâàåìîé ÊÔÑ. Ýòîò ïðîöåññ îñíîâàí íà èñïîëüçîâàíèè ðåçóëüòàòîâ
ðåøåíèÿ òîé èëè èíîé äåòàëèçàöèè ñëåäóþùåé çàäà÷è.
Çàäà÷à 2. Îõàðàêòåðèçîâàòü ìíîæåñòâî äèñêðåòíûõ ñîñòîÿíèé, äîñòèæèìûõ
èç ìíîæåñòâà íà÷àëüíûõ äèñêðåòíûõ ñîñòîÿíèé ñëàáîèíèöèàëüíîãî ÃÀ ïðè çà-
äàííîì êîìïëåêñå îãðàíè÷åíèé.
Èññëåäóåì çàäà÷è 1 è 2.
ÀÍÀËÈÇ ÑÒÐÓÊÒÓÐÛ ÎÐÃÐÀÔÀ G� ( , )Q E ÃÈÁÐÈÄÍÎÃÎ ÀÂÒÎÌÀÒÀ
Îïðåäåëåííûå ôðàãìåíòû ðåøåíèÿ çàäà÷è 1 ìîãóò áûòü ïîëó÷åíû íà îñíîâå
àíàëèçà îðãðàôà G � ( , )Q E ãèáðèäíîãî àâòîìàòà H� ( , , , , ,Q X I D f E G R, , )
îáû÷íûìè ìåòîäàìè òåîðèè ãðàôîâ. Ðàññìîòðèì êðàòêî ýòè ìåòîäû.
Îäíî èç òðåáîâàíèé çàêàç÷èêà, íå âñåãäà èçëîæåííîå â ÿâíîì âèäå, ìîæåò
ñîñòîÿòü â íåîáõîäèìîñòè ïîñòðîåíèÿ èìåííî ñëàáîèíèöèàëüíîãî ÃÀ ( , )H Qin ,
ãäå Qin ( )�
�Q Qin — ìíîæåñòâî äîïóñòèìûõ íà÷àëüíûõ äèñêðåòíûõ ñîñòîÿ-
íèé. Ïîëîæèì
~
| ( \ )(( , ) )Q q Q q Q q q q E� � � � �{ { } }. Î÷åâèäíî, ÷òî íè îäíî
äèñêðåòíîå ñîñòîÿíèå q Q Qin
~
\ íèêîãäà íå âîçíèêàåò ïðè êîððåêòíîì ôóíêöèî-
íèðîâàíèè ñëàáîèíèöèàëüíîãî ÃÀ ( , )H Qin . Ïðîâåðêà óñëîâèÿ
~
\Q Qin �� äîñòà-
òî÷íî ïðîñòî âûïîëíÿåòñÿ ïðè ëþáîì ñïîñîáå çàäàíèÿ îðãðàôà G . Ïîýòîìó åñëè
~
\Q Qin
�, òî òðåáîâàíèÿ çàêàç÷èêà íåîáõîäèìî óòî÷íèòü òàê, ÷òîáû èìåëî ìåñòî
ðàâåíñòâî
~
\Q Qin ��.  äàëüíåéøåì áóäåì ñ÷èòàòü, ÷òî ýòî ðàâåíñòâî èñòèííî.
Ðàññìîòðèì ñåìåéñòâî VQ q q Qin in
V� { } , ãäå Vq — ìíîæåñòâî äèñêðåòíûõ ñî-
ñòîÿíèé, äîñòèæèìûõ èç äèñêðåòíîãî ñîñòîÿíèÿ q Qin (ïî îïðåäåëåíèþ q Vq ).
Ïîñòðîåíèå ìíîæåñòâà Vq ( )q Qin äîñòàòî÷íî ïðîñòî âûïîëíÿåòñÿ ïðè ëþáîì
ñïîñîáå çàäàíèÿ îðãðàôà G . Î÷åâèäíî, ÷òî íè îäíî äèñêðåòíîå ñîñòîÿíèå
�
q Q Vq
q Qin
\ ( )� íèêîãäà íå ïîÿâèòñÿ ïðè êîððåêòíîì ôóíêöèîíèðîâàíèè ñëàáî-
èíèöèàëüíîãî ÃÀ ( , )H Qin . Ñëåäîâàòåëüíî, åñëè Q Vq
q Qin
\ ( )
�� , òî òðåáîâàíèÿ
çàêàç÷èêà íåîáõîäèìî óòî÷íèòü òàê, ÷òîáû èìåëî ìåñòî ðàâåíñòâî Q Vq
q Qin
�
� .
 äàëüíåéøåì áóäåì ñ÷èòàòü, ÷òî ýòî ðàâåíñòâî èñòèííî, ò.å. VQin
— ïîêðûòèå
ìíîæåñòâà Q.
Îáîçíà÷èì �Qin
òàêîå íàèìåíüøåå ðàçáèåíèå ìíîæåñòâà Q, ÷òî äëÿ êàæäîãî
Vq Qin
V ñóùåñòâóåò òàêîé áëîê B Qin
� , ïðè êîòîðîì èñòèííî âêëþ÷åíèå
V Bq � . Åñëè �Q Qin
1 , òî ( , )H Qin — ìíîæåñòâî ïîïàðíî íèêàê íå ñâÿçàííûõ
îäèí ñ äðóãèì ñëàáîèíèöèàëüíûõ ÃÀ ( , | )HB inq q Q B{ } � ( )B Qin
� , ãäå HB —
ÃÀ ñ ìíîæåñòâîì B äèñêðåòíûõ ñîñòîÿíèé. Ïîñêîëüêó èññëåäîâàíèå ýòèõ ÃÀ ìî-
æåò áûòü îñóùåñòâëåíî íåçàâèñèìî îäèí îò äðóãîãî, òî âîçìîæíî ðàñïàðàëëåëè-
âàíèå âû÷èñëåíèé.  äàëüíåéøåì ñ÷èòàåì, ÷òî ðàâåíñòâî �Q Qin
� 1 èñòèííî.
Àíàëèç îðãðàôà G � ( , )Q E îáû÷íûìè ìåòîäàìè òåîðèè ãðàôîâ äàåò òàêæå âîç-
ìîæíîñòü âûäåëèòü òî÷êè ñî÷ëåíåíèÿ è ìîñòû, à òàêæå ïîñòðîèòü áàçèñû öèêëîâ.
ÀÍÀËÈÇ ÎÁÚÅÊÒÎÂ, ÎÏÐÅÄÅËßÞÙÈÕ ÃÀ
Ðàññìîòðèì çàäà÷ó 1. Îáîçíà÷èì H0 ìíîæåñòâî òàêèõ îäíîìåðíûõ (ò.å. X � �)
ãèáðèäíûõ àâòîìàòîâ H , ÷òî äëÿ êàæäîãî äèñêðåòíîãî ñîñòîÿíèÿ q Q âûïîë-
íåíû ñëåäóþùèå óñëîâèÿ.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 4 5
Óñëîâèå 1. Ìíîæåñòâîì äîïóñòèìûõ çíà÷åíèé íåïðåðûâíîãî ñîñòîÿíèÿ ÿâ-
ëÿåòñÿ êîíå÷íûé ïðîìåæóòîê X Xq � .
Óñëîâèå 2. Ìíîæåñòâî íà÷àëüíûõ çíà÷åíèé íåïðåðûâíîãî ñîñòîÿíèÿ ÿâëÿåòñÿ
ïîïàðíî íåïåðåñåêàþùèìèñÿ îòðåçêàìè [ , ], ,� q h q h qXA � ( , , )h rq�1 � , ãäå
� q h q h, ,� � .
Óñëîâèå 3. Îõðàííûì âûðàæåíèåì, ñîîòâåòñòâóþùèì ìíîæåñòâó íà÷àëü-
íûõ çíà÷åíèé [ , ], ,� q h q h� íåïðåðûâíîãî ñîñòîÿíèÿ, ÿâëÿåòñÿ îòðåçîê
[ , ], ,� q h q h qXB � ( ), ,� q h q h� B , ïðè÷åì îòðåçêè [ , ], ,� q h q hB ( , , )h rq�1 � ïîïàð-
íî íå ïåðåñåêàþòñÿ.
Óñëîâèå 4. Äëÿ ìíîæåñòâà íà÷àëüíûõ çíà÷åíèé [ , ], ,� q h q hA ( , , )h rq�1 � íå-
ïðåðûâíîãî ñîñòîÿíèÿ äèíàìèêà ïðåäñòàâëåíà äèôôåðåíöèàëüíûì óðàâíåíèåì
� ( ),x f xq h� , (1)
ãäå f q h, — òàêàÿ ãëàäêàÿ ôóíêöèÿ, ÷òî Dom ( ),f Xq h q� .
Óñëîâèå 5. Äëÿ ìíîæåñòâà íà÷àëüíûõ çíà÷åíèé [ , ], ,� q h q hA ( , , )h rq�1 � íå-
ïðåðûâíîãî ñîñòîÿíèÿ äëèòåëüíîñòüþ äèíàìèêè ìîæåò áûòü òîëüêî ÷èñëî, ïðè-
íàäëåæàùåå çàäàííîìó îòðåçêó [ , ], ,�q h q h� , ãäå ëèáî �q h q h, ,� �� 0, ëèáî
0� ��q h q h, ,� , à ïåðåêëþ÷åíèå ìîæåò ïðîèçîéòè òîëüêî â ëþáîé òàêîé ìîìåíò
âðåìåíè t q h q h [ , ], ,� � , ÷òî x t q h q h( ) [ , ], , � B , ãäå x t( ) — ðåøåíèå äèôôåðåíöè-
àëüíîãî óðàâíåíèÿ (1) ñ íà÷àëüíûì óñëîâèåì x q h q h( ) [ , ], ,0 � A .
Óñëîâèå 6. Êàæäîìó îõðàííîìó âûðàæåíèþ [ , ], ,� q h q hB ( , , )h rq�1 � ñîîò-
âåòñòâóþò åäèíñòâåííàÿ äóãà ( , )q q E� è åäèíñòâåííîå ìíîæåñòâî íà÷àëüíûõ
çíà÷åíèé íåïðåðûâíîãî ñîñòîÿíèÿ [ , ], ,� � �q m q mA ( , , )m rq �{ }1 � , äëÿ êîòîðûõ
èñòèííî âêëþ÷åíèå
R q q q h q h q m q m( , ) , , , ,([ , ]) [ , ]� � ��� �B A , (2)
ãäå R R q qq q( , ) ( ) (( , ), )� � � � � .
Çàìå÷àíèå 2.  îòëè÷èå îò ÃÀ, îïðåäåëåííîãî â [10], äëÿ ÃÀ H H0 äî-
ïóñêàåòñÿ, ÷òî â êàæäîì äèñêðåòíîì ñîñòîÿíèè q Q äëÿ ðàçëè÷íûõ ìíîæåñòâ
íà÷àëüíûõ çíà÷åíèé íåïðåðûâíîãî ñîñòîÿíèÿ äèíàìèêà ïðîöåññà ìîæåò áûòü
ïðåäñòàâëåíà ðàçëè÷íûìè äèôôåðåíöèàëüíûìè óðàâíåíèÿìè (óñëîâèå 4). Ïðè
ýòîì çàäàíà êîíå÷íàÿ ïðîäîëæèòåëüíîñòü ýòîé äèíàìèêè, êîòîðàÿ ìîæåò áûòü
ðàçíîé äëÿ ðàçíûõ ìíîæåñòâ íà÷àëüíûõ çíà÷åíèé íåïðåðûâíîãî ñîñòîÿíèÿ. Åñëè
�q h, � 0 ( , , )h rq�1 � (óñëîâèå 5) äëÿ âñåõ q Q , òî ïðè ôóíêöèîíèðîâàíèè ÃÀ
H H0 íå âîçíèêàåò ýôôåêòà Çåíîíà.
Èññëåäóåì çàäà÷ó 1 äëÿ ÃÀ H H0 .
Îïðåäåëåíèå 1. Íàçîâåì ìíîæåñòâà S
q h
in
q h q h, , ,[ , ]� � A è S
q h
fin
q h q h, , ,[ , ]� � B
ñîãëàñîâàííûìè, åñëè ëèáî �q h q h, ,� �� 0 è S S
q h
in
q h
fin
, ,
� , ëèáî 0� ��q h q h, ,� è
âûïîëíåíû ñëåäóþùèå äâà óñëîâèÿ.
Óñëîâèå 7. Äëÿ êàæäîãî ðåøåíèÿ x t( ) äèôôåðåíöèàëüíîãî óðàâíåíèÿ
� ( ),x f xq h� ñ íà÷àëüíûì óñëîâèåì x S
q h
in( )
,
0 èñòèííà ôîðìóëà
( [ , ])( ( ) )& ( [ , ]) ( ( ), , , ,� � t x t S t x tq h q h q h
fin
q h� � �0 X q ). (3)
Óñëîâèå 8. Äëÿ êàæäîãî ÷èñëà b Sq h q h
fin
, ,
ñóùåñòâóåò òàêîå ðåøåíèå x t( )
äèôôåðåíöèàëüíîãî óðàâíåíèÿ � ( ),x f xq h� ñ íà÷àëüíûì óñëîâèåì x S
q h
in( )
,
0 , ÷òî
èñòèííà ôîðìóëà ( [ , ]) ( ( ) ), , ,� �t x t bq h q h q h� � .
6 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 4
Ïîñêîëüêó ìíîæåñòâà [ , ], ,� q h q hA è [ , ], ,� q h q hB ìîãóò íå áûòü ñîãëàñîâàí-
íûìè, òî âîçíèêàåò ñëåäóþùàÿ çàäà÷à.
Çàäà÷à 1.1. Äëÿ çàäàííûõ q Q , h rq { }1, ,� è îòðåçêà [ , ], ,�q h q h� ïîñòðîèòü
ìàêñèìàëüíûå ñîãëàñîâàííûå ìíîæåñòâà S
q h
in
q h q h, , ,[ , ]� � A è S
q h
fin
q h q h, , ,[ , ]� � B .
Ðàññìîòðèì ðåøåíèå ýòîé çàäà÷è. Âîçìîæíû ñëåäóþùèå äâà ñëó÷àÿ.
Ñëó÷àé 1. Ïóñòü �q h q h, ,� �� 0. Òîãäà äëÿ ëþáîãî íà÷àëüíîãî çíà÷åíèÿ íåïðå-
ðûâíîãî ñîñòîÿíèÿ, ïðèíàäëåæàùåãî ìíîæåñòâó [ , ], ,� q h q hA , îñóùåñòâëÿåòñÿ ìãíî-
âåííîå ïåðåêëþ÷åíèå è ïðè ýòîì íåïðåðûâíàÿ äèíàìèêà ôàêòè÷åñêè íå çàäåéñòâîâàíà.
Ïðåäïîëîæèì, ÷òî ìíîæåñòâà [ , ], ,� q h q hA è [ , ], ,� q h q hB íå ñîãëàñîâàíû, ò.å.
[ , ] [ , ], , , ,� �q h q h q h q hA B
. Åñëè [ , ] \ [ , ], , , ,� �q h q h q h q hA B
�, òî âîçìîæíî íå-
êîððåêòíîå ôóíêöèîíèðîâàíèå ÃÀ. Åñëè [ , ] [ , ], , , ,� �q h q h q h q hA B� , òî ïðèñó-
òñòâóåò èíôîðìàöèÿ, êîòîðàÿ íèêîãäà íå áóäåò èñïîëüçîâàíà ïðè êîððåêòíîì
ôóíêöèîíèðîâàíèè ÃÀ. Òàêèì îáðàçîì, åñëè [ , ] [ , ], , , ,� �q h q h q h q hA B� ��, òî
íåîáõîäèìî ïîñòàâèòü â èçâåñòíîñòü çàêàç÷èêà îá îøèáêå ïðè âûáîðå ìíîæåñòâ
[ , ], ,� q h q hA è [ , ], ,
� q h q h
B , à åñëè[ , ] [ , ], , , ,� �q h q h q h q hA B�
�, òî äîñòàòî÷íî ïîëî-
æèòü S S
q h
in
q h
fin
q h q h q h q h, , , , , ,[ , ] [ , ]� � �� �A B è îáñóäèòü ýòî èçìåíåíèå ñ çàêàç÷èêîì.
Ñëó÷àé 2. Ïóñòü 0� ��q h q h, ,� . Òîãäà äëÿ ëþáîãî íà÷àëüíîãî çíà÷åíèÿ íå-
ïðåðûâíîãî ñîñòîÿíèÿ, ïðèíàäëåæàùåãî ìíîæåñòâó [ , ], ,� q h q hA , àêòèâèðóåòñÿ
íåïðåðûâíàÿ äèíàìèêà, ïðåäñòàâëåííàÿ äèôôåðåíöèàëüíûì óðàâíåíèåì (1).
Îòìåòèì, ÷òî óñëîâèå 7 íåîáõîäèìî äëÿ îáåñïå÷åíèÿ ôóíêöèîíàëüíîé áåçîïàñ-
íîñòè ÊÔÑ, è ïðè åãî íàðóøåíèè âûáîð ìíîæåñòâ [ , ], ,� q h q hA , [ , ], ,� q h q hB è
óðàâíåíèÿ äèíàìèêè � ( ),x f xq h� ñëåäóåò îáñóäèòü ñ çàêàç÷èêîì, à óñëîâèå 8 ãà-
ðàíòèðóåò îòñóòñòâèå èíôîðìàöèè, êîòîðàÿ íèêîãäà íå áóäåò èñïîëüçîâàíà ïðè
êîððåêòíîì ôóíêöèîíèðîâàíèè ÃÀ.
Ðàññìîòðèì ðåøåíèå çàäà÷è 1.1 ìåòîäîì êîìïüþòåðíîãî ìîäåëèðîâàíèÿ.
Çàôèêñèðóåì äîñòàòî÷íî áîëüøîå íàòóðàëüíîå ÷èñëî Lq h, . Ïåðåéäåì îò
äèôôåðåíöèàëüíîãî óðàâíåíèÿ (1) ê êîíå÷íî-ðàçíîñòíîìó óðàâíåíèþ
x x f x ti i q h i� � �1 , ( )� ( , , , ),i Lq h� �0 1 1� , (4)
ãäå � �t L
q h q h� �
, ,
1 . Ïðåäïîëîæèì, ÷òî ñóùåñòâóåò òàêîå íàòóðàëüíîå ÷èñëî
l Lq h q h, ,� , ÷òî �q h q hl t, ,� � (ýòî íå îãðàíè÷èâàåò îáùíîñòè ðàññóæäåíèé, íî
óïðîùàåò èçëîæåíèå).
Êàæäîìó ðåøåíèþ x t( ) ( [ , ]),t q h 0 � äèôôåðåíöèàëüíîãî óðàâíåíèÿ (1) ñî-
îòâåòñòâóåò ïîñëåäîâàòåëüíîñòü x x xL hq0 1, , , ,� , âû÷èñëåííàÿ ñîãëàñíî ôîðìó-
ëå (4), ãäå x x0 0� ( ). Òàê êàê f q h, — ãëàäêàÿ ôóíêöèÿ, òî ëþáûå ðåøåíèÿ x t( ) ( )1 è
x t( ) ( )2 äèôôåðåíöèàëüíîãî óðàâíåíèÿ (1) ñ íà÷àëüíûìè óñëîâèÿìè x ( ) ( )1 0 ,
x Aq h q h
( )
, ,( ) [ , ]2 0 � óäîâëåòâîðÿþò óñëîâèþ
x x t q h
( ) ( )
,( ) ( ) ( [ , ])1 20 0 0� � � � ( ( ) ( ))( ) ( )x t x t1 2� .
Çíà÷èò, äëÿ ïîñëåäîâàòåëüíîñòåé x x xi i
L
i
q h0 1
( ) ( ) ( ), , ,
,
� ( , )i �1 2 , ñîîòâåòñòâóþùèõ
ýòèì ðåøåíèÿì x ti( ) ( ) ( , )i �1 2 , èñòèííà ôîðìóëà
x x j L x xq h j j0
1
0
2 1 20 1( ) ( )
,
( ) ( )( , , , ) ( )� � � � �� . (5)
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 4 7
Åñëè � q h q hA, ,� , òî ïîëîæèì kq h, � 0 è îáîçíà÷èì x x x
L hq0
0
1
0 0( ) ( )
,
( ), , ,� ïîñëå-
äîâàòåëüíîñòü, ñîîòâåòñòâóþùóþ ðåøåíèþ äèôôåðåíöèàëüíîãî óðàâíåíèÿ (1)
ñ íà÷àëüíûì óñëîâèåì x q h
( )
,( )0 0 � � . Åñëè � q h q hA, ,� , òî çàôèêñèðóåì äîñòà-
òî÷íî áîëüøîå íàòóðàëüíîå ÷èñëî kq h, è îáîçíà÷èì x ti( ) ( ) ( , , , ),i kq h� 0 1 � ðå-
øåíèå äèôôåðåíöèàëüíîãî óðàâíåíèÿ (1) ñ íà÷àëüíûì óñëîâèåì x i( ) ( )0 �
� � ��� �q h q h q h q hk i, , , ,( )1 A , à x x xi i
L h
i
q0 1
( ) ( )
,
( ), , ,� — ñîîòâåòñòâóþùóþ ýòîìó ðå-
øåíèþ ïîñëåäîâàòåëüíîñòü. Èç (3) è (5) âûòåêàåò, ÷òî ìíîæåñòâà S
q h
in
,
è S
q h
fin
,
ÿâëÿþòñÿ òàêèìè îòðåçêàìè, ÷òî
( , , , )( ( , , )(,
( )
, ,
( )� � � � � i k x S j L x Xq h
i
q h
in
q h j
i0 1 1
0
� � q )&
& ( )( & )), ,
( )
,
� � � j l j L x Sq h q h j
i
q h
fin
� .
Òàêèì îáðàçîì, â ñëó÷àå, êîãäà 0� ��q h q h, ,� , ïîñòðîåíèå ìíîæåñòâ S
q h
in
,
è
S
q h
fin
,
ìîæíî îñóùåñòâèòü â ñîîòâåòñòâèè ñî ñëåäóþùèì àëãîðèòìîì (U — ìàññèâ
ðàçìåðà ( ), ,k Lq h q h� �1 , ñòðîêè êîòîðîãî çàíóìåðîâàíû ÷èñëàìè 0 1, , , ,� kq h ,
à ñòîëáöû — ÷èñëàìè 0 1 1, , , ,� Lq h � ; a i
i i
k
ia a a
q h
� ( , , , )( ) ( ) ( )
,0 1
� ( , , )i �1 2 3 —
äâîè÷íûå âåêòîðû).
Àëãîðèòì 1
Øàã 1. a 11:
,
� kq h
, a 02 :
,
� kq h
, a 03 :
,
� kq h
, i:� 0, j:� 0, U i j q h[ , ]: ,� � .
/ * 1kq h,
— äâîè÷íûé âåêòîð äëèíû kq h, �1, âñå êîìïîíåíòû êîòîðîãî ðàâíû1* /
/ * 0kq h,
— äâîè÷íûé âåêòîð äëèíû kq h, �1, âñå êîìïîíåíòû êîòîðîãî ðàâíû 0* /
Øàã 2. i i:� �1.
Øàã 3. Åñëè i kq h� , , òî U i j U i j k
q h q h q h[ , ]: [ , ] ( )
, , ,� � � ��1 1 A � è ïåðåõîä
ê øàãó 2, èíà÷å — ê øàãó 4.
Øàã 4. i:� 0, j j:� �1.
Øàã 5. Åñëè j lq h� , , òî ïåðåõîä ê øàãó 6, èíà÷å — ê øàãó 10.
Øàã 6. Åñëè ai
( )1 1� , òî U i j U i j f U i j tq h[ , ]: [ , ] ( [ , ]),� � � �1 1 � è ïåðåõîä ê
øàãó 7, èíà÷å — ê øàãó 8.
Øàã 7. Åñëè U i j X q[ , ]� , òî ai
( ) :1 0� .
Øàã 8. i i:� �1.
Øàã 9. Åñëè i kq h� , , òî ïåðåõîä ê øàãó 6, èíà÷å ê øàãó 4.
Øàã 10. Åñëè ai
( )1 1� , òî U i j U i j f U i j tq h[ , ]: [ , ] ( [ , ]),� � � �1 1 � è ïåðåõîä
ê øàãó 11, èíà÷å — ê øàãó 13.
Øàã 11. Åñëè U i j X q[ , ]� , òî ai
( ) :1 0� , ai
( ) :2 0� è ïåðåõîä ê øàãó 13.
Øàã 12. Åñëè U i j q h q h[ , ] [ , ], , � B , òî ai
( ) :2 1� .
Øàã 13. i i:� �1.
Øàã 14. Åñëè i kq h� , , òî ïåðåõîä ê øàãó 10, èíà÷å i:� 0, j j:� �1 è ïåðåõîä
ê øàãó 15.
8 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 4
Øàã 15. Åñëè j Lq h� , , òî ïåðåõîä ê øàãó 10, èíà÷å — ê øàãó 16.
Øàã 16. a a a3 1 2:� � .
Øàã 17. Åñëè a 03 � , òî S
q h
in
,
:��, S
q h
fin
,
:�� è ÊÎÍÅÖ.
Øàã 18. r i aimin
( ): min |� �{ }3 1 , r i aimax
( ): max |� �{ }3 1 ;
� � �
min
( )
, , , , min: ( )1 1� � ��
q h q h q h q hk rA , � � �max
( )
, , , , max: ( )1 1� � ��
q h q h q h q hk rA ,
� �
min
( )
min , , min ,: min [ , ] | & [ , ] [2 � � � {U r j l j L U r jq h q h q h , ],B }q h ,
� �max
( )
max , , max ,: max [ , ]| & [ , ] [2 � � � {U r j l j L U r jq h q h q h , ],B }q h .
Øàã 19. S
q h
in
, min
( )
max
( ): [ , ]� � �1 1 , S
q h
fin
, min
( )
max
( ): [ , ]� � �2 2 è ÊÎÍÅÖ.
Ïóñòü àëãîðèòì 1 çàâåðøèë ðàáîòó íà øàãå 17. Òîãäà â äèñêðåòíîì ñîñòîÿ-
íèè q ïðè ìíîæåñòâå [ , ], ,� q h q hA äîïóñòèìûõ íà÷àëüíûõ çíà÷åíèé íåïðåðûâíî-
ãî ñîñòîÿíèÿ äîñòèãàþòñÿ ëèáî íåäîïóñòèìûå çíà÷åíèÿ íåïðåðûâíîãî ñîñòîÿíèÿ
(åñëè a 01 � ), ëèáî îõðàííîå âûðàæåíèå, óðàâíåíèå äèíàìèêè è åå ïðîäîëæè-
òåëüíîñòü áëîêèðóþò âîçìîæíîñòü ïåðåêëþ÷åíèÿ (åñëè a 01
è a 02 � ). Ïîýòî-
ìó íåîáõîäèìî ïîñòàâèòü â èçâåñòíîñòü çàêàç÷èêà îá îøèáêå ïðè âûáîðå ìíî-
æåñòâ [ , ], ,� q h q hA , [ , ], ,� q h q hB , [ , ], ,�q h q h� è óðàâíåíèÿ äèíàìèêè � ( ),x f xq h� .
Ïóñòü àëãîðèòì 1 çàâåðøèë ðàáîòó íà øàãå 19. Åñëè S
q h
in
q h q h, , ,[ , ]
� A (ñîîòâåò-
ñòâåííî S
q h
fin
q h q h, , ,[ , ]
� B ), òî äîñòàòî÷íî ïîëîæèòü [ , ]:, , ,
� q h q h q h
inSA � (ñîîò-
âåòñòâåííî [ , ]:, , ,
� q h q h q h
finSB � ) è îáñóäèòü ýòî èçìåíåíèå ñ çàêàç÷èêîì.
Èç ðåçóëüòàòîâ, ïîëó÷åííûõ ïðè èññëåäîâàíèè ñëó÷àåâ 1 è 2, âûòåêàåò, ÷òî
äëÿ ôèêñèðîâàííîãî äèñêðåòíîãî ñîñòîÿíèÿ q Q ñîãëàñîâàíèå ìíîæåñòâ íà-
÷àëüíûõ çíà÷åíèé íåïðåðûâíîãî ñîñòîÿíèÿ è ñîîòâåòñòâóþùèõ èì îõðàííûõ âû-
ðàæåíèé ìîæíî îñóùåñòâèòü ñîãëàñíî ñëåäóþùåìó àëãîðèòìó.
Àëãîðèòì 2
Øàã 1. h:�1.
Øàã 2. Åñëè èñòèííû ðàâåíñòâà �q h q h, ,� �� 0, òî ïåðåõîä ê øàãó 3,
èíà÷å — ê øàãó 4.
Øàã 3. Åñëè [ , ] [ , ], , , ,� �q h q h q h q hA B
, òî óòî÷íÿåì òðåáîâàíèÿ çàêàç÷èêà
òàê, ÷òîáû èìåëî ìåñòî ðàâåíñòâî [ , ] [ , ], , , ,� �q h q h q h q hA B� , è ïåðåõîä ê øàãó 10.
Øàã 4. Ïðèìåíÿåì àëãîðèòì 1 ê ìíîæåñòâàì [ , ], ,� q h q hA è [ , ], ,� q h q hB .
Øàã 5. Åñëè S S
q h
in
q h
fin
, ,
� ��, òî óòî÷íÿåì ñ çàêàç÷èêîì âûáîð ìíîæåñòâ
[ , ], ,� q h q hA , [ , ], ,� q h q hB , [ , ], ,�q h q h� è óðàâíåíèÿ äèíàìèêè � ( ),x f xq h� , è ïåðå-
õîä ê øàãó 4.
Øàã 6. Åñëè S
q h
in
q h q h, , ,[ , ]� � A è S
q h
fin
q h q h, , ,[ , ]� � B , òî ïåðåõîä ê øàãó 10.
Øàã 7. Åñëè S
q h
in
q h q h, , ,[ , ]
� A , òî [ , ]:, , ,
� q h q h q h
inSA � .
Øàã 8. Åñëè S
q h
fin
q h q h, , ,[ , ]
� B , òî [ , ]:, , ,
� q h q h q h
finSB � .
Øàã 9. Îáñóæäàåì ñ çàêàç÷èêîì èçìåíåíèÿ ìíîæåñòâ [ , ], ,� q h q hA è
[ , ], ,� q h q hB .
Øàã 10. h h:� �1.
Øàã 11. Åñëè h rq� , òî ïåðåõîä ê øàãó 2, èíà÷å ÊÎÍÅÖ.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 4 9
Ïðèìåíèâ àëãîðèòì 2 ê êàæäîìó äèñêðåòíîìó ñîñòîÿíèþ q Q , ñîãëàñóåì
âñå ñîîòâåòñòâóþùèå ìíîæåñòâà äîïóñòèìûõ íà÷àëüíûõ çíà÷åíèé íåïðåðûâíîãî
ñîñòîÿíèÿ è îõðàííûå âûðàæåíèÿ äëÿ âñåõ äèñêðåòíûõ ñîñòîÿíèé èññëåäóåìîãî ÃÀ.
 ðåçóëüòàòå ïðèìåíåíèÿ àëãîðèòìà 2 ìîæåò íàðóøèòüñÿ óñëîâèå 6. Òîãäà
äëÿ íåêîòîðîãî äèñêðåòíîãî ñîñòîÿíèÿ q Q ñóùåñòâóþò òàêèå îõðàííîå âûðà-
æåíèå [ , ], ,� q h q hB ( , , )h rq { }1 � , ñîîòâåòñòâóþùèå åìó äóãà ( , )q q E� è ìíîæå-
ñòâî [ , ], ,� � �q m q mA ( , , )m rq �{ }1 � äîïóñòèìûõ íà÷àëüíûõ çíà÷åíèé íåïðåðûâíî-
ãî ñîñòîÿíèÿ, ÷òî âêëþ÷åíèå (2) ëîæíîå (ò.å. èñòèííà ôîðìóëà
R q q q h q h q m q m( , ') , , , ,([ , ]) \ [ , ]� �B A� � � ). Ýòî ìîæåò ïðèâåñòè ê íåêîððåêòíîìó
ôóíêöèîíèðîâàíèþ ÃÀ. Ïîýòîìó âîçíèêàåò ñëåäóþùàÿ çàäà÷à.
Çàäà÷à 1.2. Äëÿ êàæäîãî äèñêðåòíîãî ñîñòîÿíèÿ q Q âûïîëíèòü óòî÷íåíèÿ
îòîáðàæåíèÿ ïåðåêëþ÷åíèÿ R q q( , ') òàê, ÷òîáû êàæäîå îõðàííîå âûðàæåíèå
[ , ], ,� q h q hB ( , , )h rq { }1 � , ñîîòâåòñòâóþùèå åìó äóãà ( , )q q E� è ìíîæåñòâî
[ , ], ,� � �q m q mA ( , , )m rq �{ }1 � äîïóñòèìûõ íà÷àëüíûõ çíà÷åíèé íåïðåðûâíîãî ñî-
ñòîÿíèÿ óäîâëåòâîðÿëè âêëþ÷åíèþ (2).
 ïðåäïîëîæåíèè íåäîïóñòèìîñòè èçìåíåíèÿ íè îõðàííûõ âûðàæåíèé, íè
ìíîæåñòâ äîïóñòèìûõ íà÷àëüíûõ çíà÷åíèé íåïðåðûâíîãî ñîñòîÿíèÿ ðåøåíèå çà-
äà÷è 1.2 ìåòîäîì êîìïüþòåðíîãî ìîäåëèðîâàíèÿ ìîæíî îñóùåñòâèòü
ñëåäóþùèì îáðàçîì.
Àëãîðèòì 3
Øàã 1. V Q:� .
Øàã 2. Åñëè V
�, òî ïåðåõîä ê øàãó 3, èíà÷å ÊÎÍÅÖ.
Øàã 3. Âûáðàòü ýëåìåíò q V , V V q: \� { }, h:�1.
Øàã 4. Åñëè äëÿ îõðàííîãî âûðàæåíèÿ [ , ], ,� q h q hB , ñîîòâåòñòâóþùåé åìó
äóãè ( , )q q E� è ìíîæåñòâà [ , ], ,� � �q m q mA ( , , )m rq �{ }1 � äîïóñòèìûõ íà÷àëü-
íûõ çíà÷åíèé íåïðåðûâíîãî ñîñòîÿíèÿ âêëþ÷åíèå (2) èñòèííî, òî h h:� �1 è ïå-
ðåõîä ê øàãó 5, èíà÷å — ê øàãó 6.
Øàã 5. Åñëè h rq� , òî ïåðåõîä ê øàãó 4, èíà÷å — ê øàãó 2.
Øàã 6. Óòî÷íèòü òðåáîâàíèÿ çàêàç÷èêà ê îòîáðàæåíèþ ïåðåêëþ÷åíèÿ
R q q( , )� , ÷òîáû âêëþ÷åíèå (2) ñòàëî èñòèííûì, h h:� �1 è ïåðåõîä ê øàãó 5.
Åñëè äîïóñêàåòñÿ èçìåíåíèå îòîáðàæåíèÿ ïåðåêëþ÷åíèÿ, îõðàííûõ âûðàæå-
íèé è ìíîæåñòâ äîïóñòèìûõ íà÷àëüíûõ çíà÷åíèé íåïðåðûâíîãî ñîñòîÿíèÿ, òî
ñèòóàöèÿ ñóùåñòâåííî óñëîæíÿåòñÿ â ðåçóëüòàòå íåîáõîäèìîñòè ìíîãîêðàòíîãî
àíàëèçà ìíîæåñòâà Q äèñêðåòíûõ ñîñòîÿíèé ñ ïðèìåíåíèåì àëãîðèòìà 2. Â ýòîì
ñëó÷àå ðåøåíèå çàäà÷è 1.2 ìåòîäîì êîìïüþòåðíîãî ìîäåëèðîâàíèÿ ìîæíî
îñóùåñòâèòü ñëåäóþùèì îáðàçîì.
Àëãîðèòì 4
Øàã 1. V Q:� , � q h, :� 0 äëÿ âñåõ q Q è h rq { }1, ,� .
Øàã 2. Åñëè V
�, òî ïåðåõîä ê øàãó 3, èíà÷å ÊÎÍÅÖ.
Øàã 3. Âûáðàòü ýëåìåíò q V , V V q: \� { }, h:�1.
Øàã 4. Åñëè äëÿ îõðàííîãî âûðàæåíèÿ [ , ], ,� q h q hB , ñîîòâåòñòâóþùåé åìó
äóãè ( , )q q E� è ìíîæåñòâà [ , ], ,� � �q m q mA ( , , )m rq �{ }1 � äîïóñòèìûõ íà÷àëü-
íûõ çíà÷åíèé íåïðåðûâíîãî ñîñòîÿíèÿ âêëþ÷åíèå (2) èñòèííî, òî h h:� �1 è ïå-
ðåõîä ê øàãó 5, èíà÷å — ê øàãó 6.
Øàã 5. Åñëè h rq� , òî ïåðåõîä ê øàãó 4, èíà÷å — ê øàãó 12.
Øàã 6. Åñëè âîçìîæíî óòî÷íèòü òðåáîâàíèÿ çàêàç÷èêà ê îòîáðàæåíèþ ïåðå-
êëþ÷åíèÿ R q q( , )� òàê, ÷òîáû âêëþ÷åíèå (2) ñòàëî èñòèííûì, òî âûïîëíèòü ýòî
óòî÷íåíèå è ïåðåõîä ê øàãó 7, èíà÷å — ê øàãó 8.
10 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 4
Øàã 7. h h:� �1 è ïåðåõîä ê øàãó 5.
Øàã 8. Åñëè R q q q h q h q m q m( , ) , , , ,([ , ]) [ , ]� � �� ��� �B A , òî óòî÷íèòü òðåáîâà-
íèÿ çàêàç÷èêà ê îòîáðàæåíèþ ïåðåêëþ÷åíèÿ R q q( , )� òàê, ÷òîáû íåðàâåíñòâî
R q q q h q h q m q m( , ) , , , ,([ , ]) [ , ]� � ��
�� �B A ñòàëî èñòèííûì.
Øàã 9. [ , ]: ([ , ]) [ , ], , ( , ) , , , ,� � �q h q h q q q m q m q h q hRB A B� �
�
�
� �
1 .
Øàã 10. Åñëè ïðîèçîøëî èçìåíåíèå ìíîæåñòâà [ , ], ,� q h q hB , òî � q h, :�1.
Øàã 11. Ïåðåõîä ê øàãó 7.
Øàã 12. Åñëè ñóùåñòâóåò òàêîå h rq { }1, ,� , ÷òî � q h, �1, òî ïåðåõîä
ê øàãó 13, èíà÷å — ê øàãó 2.
Øàã 13. Ïðèìåíèòü àëãîðèòì 2 ê äèñêðåòíîìó ñîñòîÿíèþ q è ïåðåõîä
ê øàãó 1.
Çàìå÷àíèå 3. Î÷åâèäíî, ÷òî â ðåçóëüòàòå ïðèìåíåíèÿ àëãîðèòìà 4 äëÿ íåêî-
òîðûõ äèñêðåòíûõ ñîñòîÿíèé ìíîæåñòâà äîïóñòèìûõ íà÷àëüíûõ çíà÷åíèé íå-
ïðåðûâíîãî ñîñòîÿíèÿ è îõðàííûå âûðàæåíèÿ ìîãóò ñòÿãèâàòüñÿ ê òî÷êå.
ÄÎÑÒÈÆÈÌÎÑÒÜ ÄÈÑÊÐÅÒÍÛÕ ÑÎÑÒÎßÍÈÉ ÑËÀÁÎÈÍÈÖÈÀËÜÍÎÃÎ ÃÀ
Èññëåäóåì ñëåäóþùèå äâå äåòàëèçàöèè çàäà÷è 2.
Çàäà÷à 2.1. Äëÿ êàæäîãî äèñêðåòíîãî ñîñòîÿíèÿ q Q ñëàáîèíèöèàëüíîãî
ÃÀ ( , )H Qin ( , )H �
�H0 Q Qin íàéòè ìèíèìàëüíîå ÷èñëî ïåðåêëþ÷åíèé, çà
êîòîðîå ýòî ñîñòîÿíèå äîñòèæèìî èç ìíîæåñòâà Qin .
Çàäà÷à 2.2. Äëÿ êàæäîãî äèñêðåòíîãî ñîñòîÿíèÿ q Q ñëàáîèíèöèàëüíîãî
ÃÀ ( , )H Qin ( , )H �
�H0 Q Qin íàéòè îöåíêó ìèíèìàëüíîãî âðåìåíè, çà êîòî-
ðîå ýòî ñîñòîÿíèå äîñòèæèìî èç ìíîæåñòâà Qin .
Ïóñòü s ( ,[ , ]), ,q q h q h1 1 1 1 1
� A ( , , , )q Q h rq1 1
1
1
{ }� — òàêàÿ áåñêîíå÷íàÿ èñòîðèÿ
( , [ , ]) ( , [, ,
[ , ], ,q qq h q h q
q h q h
1 11 1 1 1
1 1 1 1
1
� �
�
A
�
� ������ , ,
[ , ]
,, ]) ( , [ ,h q h q hq
1 1 1 2 2
0 0
2B � ��� �
Aq h
q h q h
2 2
2 2 2 2
,
[ , ]
]) , ,� �
� ������ � ,
÷òî ( , [ , ]) ( , [ ,, ,
[ , ]
,q qi q h q h i q h qi i i i i i i
� �B A
0 0
1 1 1
� ��� � � � � �1 1, ])hi
( )i � òîãäà è
òîëüêî òîãäà, êîãäà îõðàííîìó âûðàæåíèþ [ , ], ,
� q h q hi i i i
B ñîîòâåòñòâóþò äóãà
( , )q q Ei i� 1 è ìíîæåñòâî [ , ], ,� q h q hi i i i� � � �1 1 1 1
A äîïóñòèìûõ íà÷àëüíûõ çíà÷å-
íèé íåïðåðûâíîãî ñîñòîÿíèÿ. Î÷åâèäíî, ÷òî ýòà èñòîðèÿ ïîëíîñòüþ îïèñûâà-
åò ïîâåäåíèå ÃÀ H, ñòàðòóþùåãî èç äèñêðåòíîãî ñîñòîÿíèÿ q1 ïðè íà÷àëüíîì
çíà÷åíèè íåïðåðûâíîãî ñîñòîÿíèÿ, ïðèíàäëåæàùåì ìíîæåñòâó [ , ], ,� q h q h1 1 1 1
A .
Èñòèííî ñëåäóþùåå óòâåðæäåíèå.
Óòâåðæäåíèå 1. Äëÿ êàæäîé èñòîðèè s ( ,[ , ]), ,q q h q h1 1 1 1 1
� A ( ,q Q1 h rq1 1
1
{ }, , )�
ñóùåñòâóåò òàêîå íàèìåíüøåå ÷èñëî �( , [ , ]), ,q q h q h1 1 1 1 1
A { }2 1, ,� rq
q Q
� � , ÷òî
äëÿ íåêîòîðîãî íàòóðàëüíîãî ÷èñëà j q q h {1 1 1 1
, , ( , [ ,,� � A }q h1 1
1, ]) � èñòèííû
îáà ðàâåíñòâà:
q qq jq h q h �( ,[ , ]), ,1 1 1 1 1
A �
è
[ ,
( ,[ , , , ]) ( ,[ , , , ],�
� � q h qq q h q h q q h q h1 1 1 1 1 1 1 1 1 1
A A
A
( ,[ , , , ]) ( ,[ , , , ]), ]
q q h q h q q h q h
h
1 1 1 1 1 1 1 1 1 1
� �A A
�
� [ , ], ,
� q h q hj j j j
A .
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 4 11
 ñèëó óòâåðæäåíèÿ 1 ìíîæåñòâî S q q h q h1 1 1 1 1
,[ , ], ,� A âñåõ äèñêðåòíûõ ñîñòîÿ-
íèé ÃÀ H H0 , äîñòèæèìûõ èç äèñêðåòíîãî ñîñòîÿíèÿ q Q1 ïðè íà÷àëüíîì
çíà÷åíèè íåïðåðûâíîãî ñîñòîÿíèÿ, ïðèíàäëåæàùåì ìíîæåñòâó [ , ], ,� q h q h1 1 1 1
A ,
îïðåäåëÿåòñÿ ðàâåíñòâîì
S q Q j qq q h qq h q h1 1 1 1 1 1 1 1
1 1, [ , ] ,, ,
| ( , , ( , [ ,� �A { { A� � � , ]) ) ( )h jq q
1
1� �} }, (6)
à S Sq q
h
r
q h q h
q
1 1 1 1 1 1
1
1
1
�
�
, [ , ], ,� A� — ìíîæåñòâî âñåõ äèñêðåòíûõ ñîñòîÿíèé ÃÀ
H H0 , äîñòèæèìûõ èç q Q1 . Ïðè ýòîì èç ïðåäïîëîæåíèÿ î òîì, ÷òî VQin
ÿâ-
ëÿåòñÿ ïîêðûòèåì ìíîæåñòâà Q, âûòåêàåò èñòèííîñòü ðàâåíñòâà
S Q
q
q Qin
1
1
�� . (7)
Äëÿ äèñêðåòíîãî ñîñòîÿíèÿ q Q1 ïîëîæèì
n
q q h q h
q
1 1 1 1 1
, [ , ]
min
, ,
( )
� A
�
�
� � �min , , ( ,[ , ]) | ,, ,{ { A } } åñëèj q q q qq h q h j1 1 11 1 1 1 1
� �
��
S
q Q S
q
q
q h q h
q h q h
1 1 1 1 1
1 1 1 1 1
, [ , ]
, [ ,
, ,
, ,
,
, \
�
�
A
Aåñëè ] ;
!
"
#"
(8)
t q
q
q h
jq h q h
j j
q q h q
1 1 1 1 1
1 1 1 1
1,[ , ]
min ,
, ,
, [ , ,
( )
�
�
�
A
A
�
�
n
, ]
, ,
( )
, [ , ]
,
, ,
, \
h
q h q h
q
q
q
q S
q Q S
1
1 1 1 1 1
1
�
��
åñëè
åñëè
A�
[ , ], ,
;�q h q h1 1 1 1
A
!
"
#
"
(9)
t q
q
q h
jq h q h
j j
q q h q
1 1 1 1 1
1 1 1 1
1, [ , ]
max ,
, ,
, [ , ,
( )
�
�
A
A
�
�
�
n
, ]
, ,
( )
, [ , ]
,
, ,
, \
h
q h q h
q
q
q
q S
q Q S
1
1 1 1 1 1
1
�
��
åñëè
åñëè
A�
[ , ], ,
.�q h q h1 1 1 1
A
!
""
#
"
"
(10)
Ñðàâíèâàÿ ðàâåíñòâà (8)–(10), ïîëó÷àåì èñòèííîñòü ôîðìóëû
n
q qq h q h q h q h
q t
1 1 1 1 1 1 1 1 1 1
,[ , ]
min
,[ , ]
mi
, , , ,
( )
� �A A
� �� � n ( )q � �� �
� � �� � t q q Q S
q q
q h q h q h q1 1 1 1 1
1 1 1 1,[ , ]
max
,[ ,
, , , ,
( ) \
� �A A h1
] .
Èç (6) è (8) âûòåêàåò, ÷òî n
q q h q h
q
1 1 1 1 1
,[ , ]
min
, ,
( )
� A
( , )q q Q1 — ýòî ìèíèìàëüíîå
êîëè÷åñòâî ïåðåêëþ÷åíèé, çà êîòîðîå äèñêðåòíîå ñîñòîÿíèå q äîñòèæèìî èç
äèñêðåòíîãî ñîñòîÿíèÿ q1 ïðè íà÷àëüíîì çíà÷åíèè íåïðåðûâíîãî ñîñòîÿíèÿ,
ïðèíàäëåæàùåì ìíîæåñòâó [ , ], ,� q h q h1 1 1 1
A . Ïðè ýòîì n
q q h q h
q
1 1 1 1 1
,[ , ]
min
, ,
( )
� A
� ��
òîãäà è òîëüêî òîãäà, êîãäà äèñêðåòíîå ñîñòîÿíèå q íå äîñòèæèìî èç äèñêðåòíî-
ãî ñîñòîÿíèÿ q1 ïðè íà÷àëüíîì çíà÷åíèè íåïðåðûâíîãî ñîñòîÿíèÿ, ïðèíàäëåæà-
ùåì ìíîæåñòâó [ , ], ,� q h q h1 1 1 1
A .
Ñëåäîâàòåëüíî, ìèíèìàëüíîå êîëè÷åñòâî ïåðåêëþ÷åíèé, çà êîòîðîå äèñêðåò-
íîå ñîñòîÿíèå q äîñòèæèìî èç äèñêðåòíîãî ñîñòîÿíèÿ q1, îïðåäåëÿåòñÿ ðàâåíñòâîì
n n
q h r q
q q
q
q h q h1
1 1
1 1 1 1 11
min
, , ,[ , ]
min( ) min ( )
, ,
�
{ } A� �
( , )q q Q1 . (11)
12 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 4
Òàêèì îáðàçîì, ìèíèìàëüíîå ÷èñëî ïåðåêëþ÷åíèé, çà êîòîðîå äèñêðåòíîå
ñîñòîÿíèå q Q äîñòèæèìî èç ìíîæåñòâà Qin , îïðåäåëÿþòñÿ êàê
n n
Q q Q qin
in
q qmin min( ) min ( )�
1
1
( )q Q . (12)
Îòìåòèì, ÷òî â ñèëó ðàâåíñòâà (7) äëÿ êàæäîãî äèñêðåòíîãî ñîñòîÿíèÿ q Q
èñòèííî íåðàâåíñòâî n
Qin
qmin ( )� ��.
Èç (6), (9) è (10) âûòåêàåò, ÷òî îöåíêà ìèíèìàëüíîãî âðåìåíè, çà êîòîðîå
äèñêðåòíîå ñîñòîÿíèå q äîñòèæèìî èç äèñêðåòíîãî ñîñòîÿíèÿ q1 ïðè íà÷àëüíîì
çíà÷åíèè íåïðåðûâíîãî ñîñòîÿíèÿ, ïðèíàäëåæàùåì ìíîæåñòâó [ , ], ,� q h q h1 1 1 1
A ,
îïðåäåëÿåòñÿ ôîðìóëîé
t
q qq h q h q h q h
q t
1 1 1 1 1 1 1 1 1 1
, [ , ]
min
, [ , ]
min
, , , ,
( ) [ (
� �A A
q t q
q q h q h
), ( )]
, [ , ]
max
, ,1 1 1 1 1
� A
( , )q q Q1 .(13)
Ïðè ýòîì t
q q h q h
q
1 1 1 1 1
, [ , ]
min
, ,
( ) [ , ]
� A
�� �� òîãäà è òîëüêî òîãäà, êîãäà äèñêðåò-
íîå ñîñòîÿíèå q íå äîñòèæèìî èç äèñêðåòíîãî ñîñòîÿíèÿ q1 ïðè íà÷àëüíîì
çíà÷åíèè íåïðåðûâíîãî ñîñòîÿíèÿ, ïðèíàäëåæàùåì ìíîæåñòâó [ , ], ,� q h q h1 1 1 1
A .
Ñëåäîâàòåëüíî, îöåíêà ìèíèìàëüíîãî âðåìåíè, çà êîòîðîå äèñêðåòíîå ñîñòîÿ-
íèå q äîñòèæèìî èç äèñêðåòíîãî ñîñòîÿíèÿ q1, èìååò âèä
t
q q q
q t q t q
1 1 1
min min max( ) [ ( ), ( )] ( , )q q Q1 , (14)
ãäå
t q t q
q q
h rq
q h q h1
1 1
1
1 1 1 1 1
min
, [ , ]
min( ) min ( )
, ,
, ,
�
{ }
A
�
�
( , )q q Q1 , (15)
t q
q1
max ( ) �
�
�� max ( ) | , , ,
, [ , ]
max
, ,
{ { }} åñ
A
t q h r
q q
q h q h1 1 1 1 1
11 1
�
� ëè
åñëè
q S
q Q S
q
q
��
!
"
#"
1
1
,
, \
( , ).q q Q1
(16)
Òàêèì îáðàçîì, îöåíêà ìèíèìàëüíîãî âðåìåíè, çà êîòîðîå äèñêðåòíîå ñî-
ñòîÿíèå q äîñòèæèìî èç ìíîæåñòâà Qin , âû÷èñëÿåòñÿ êàê
t
Q Q Qin in in
q t q t qmin min max( ) [ ( ), ( )] ( )q Q , (17)
ãäå
t q t q
Q q Q
q
in
in
min min( ) min ( )�
1
1
( )q Q , (18)
t q t q q Q
Q q in
in
max min( ) max ( ) |�
�� { }
1
1 ( )q Q . (19)
Îòìåòèì, ÷òî â ñèëó ðàâåíñòâà (7) äëÿ êàæäîãî äèñêðåòíîãî ñîñòîÿíèÿ q Q
èñòèííû íåðàâåíñòâà t q
Qin
min ( )� �� è t q
Qin
max ( )� ��.
Èç ïîëó÷åííûõ âûøå ðåçóëüòàòîâ âûòåêàåò, ÷òî ðåøåíèå çàäà÷è 2.1 îïðåäå-
ëÿåòñÿ ôîðìóëàìè (8), (11) è (12), à ðåøåíèå çàäà÷è 2.2 — ôîðìóëàìè (9), (10),
(13)–(19).
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 4 13
ÇÀÊËÞ×ÅÍÈÅ
 íàñòîÿùåé ðàáîòå îïðåäåëåí êëàññ 1-ìåðíûõ ÃÀ, â êàæäîì äèñêðåòíîì ñî-
ñòîÿíèè êîòîðûõ äëÿ ðàçëè÷íûõ ìíîæåñòâ íà÷àëüíûõ çíà÷åíèé íåïðåðûâíîãî
ñîñòîÿíèÿ äèíàìèêà ìîæåò áûòü ïðåäñòàâëåíà ðàçëè÷íûìè äèôôåðåíöèàëüíû-
ìè óðàâíåíèÿìè, ïðè÷åì äëÿ êàæäîé äèíàìèêè çàäàíà ñâîÿ êîíå÷íàÿ ïðîäîë-
æèòåëüíîñòü. Íåòðèâèàëüíîñòü ýòîãî êëàññà ÃÀ ñîñòîèò â òîì, ÷òî ìíîãîôóí-
êöèîíàëüíûå îáúåêòû (òàêèå êàê êîíäèöèîíåð, ïðåäíàçíà÷åííûé êàê äëÿ
îõëàæäåíèÿ, òàê è äëÿ îáîãðåâà ïîìåùåíèÿ) ìîãóò áûòü ïðåäñòàâëåíû îäíèì
äèñêðåòíûì ñîñòîÿíèåì.
Çàäà÷è óñòðàíåíèÿ ïðîòèâîðå÷èÿ â îáúåêòàõ, îïðåäåëÿþùèõ ÃÀ, à òàêæå ñî-
ãëàñîâàíèÿ ýòèõ îáúåêòîâ îäèí ñ äðóãèì âîçíèêàåò íà ýòàïå ïîñòðîåíèÿ ôîð-
ìàëüíîé ìîäåëè ïðîåêòèðóåìîé ñèñòåìû. Îíè ïðåäíàçíà÷åíû äëÿ íèâåëèðîâà-
íèÿ íåïðåäñêàçóåìûõ ïîñëåäñòâèé è óäàëåíèÿ ëèøíåé èíôîðìàöèè. Çàäà÷è
íàõîæäåíèÿ ìèíèìàëüíîãî ÷èñëà ïåðåêëþ÷åíèé, à òàêæå îöåíêè ìèíèìàëüíîãî
âðåìåíè, çà êîòîðîå äèñêðåòíûå ñîñòîÿíèÿ äîñòèæèìû èç ìíîæåñòâà íà÷àëüíûõ
äèñêðåòíûõ ñîñòîÿíèé, ÿâëÿþòñÿ ìîäåëüíûìè äëÿ ïðîöåññà âåðèôèêàöèè ïðîåê-
òèðóåìîé ñèñòåìû. Ïðåäëîæåííûå â ðàáîòå àëãîðèòìû ðåøåíèÿ ïåðå÷èñëåííûõ
çàäà÷ äîñòàòî÷íî ëåãêî ìîãóò áûòü ðåàëèçîâàíû â òàêèõ ñèñòåìàõ
ìîäåëèðîâàíèÿ, êàê IMS [12, 13].
Äëÿ ìíîæåñòâà H0,n ( )n � n-ìåðíûõ ÃÀ, ÿâëÿþùèõñÿ ïðÿìîé ñóììîé n
ãèáðèäíûõ àâòîìàòîâ, êîòîðûå ïðèíàäëåæàò ìíîæåñòâó H0 , èìååì H0 0 1� H , è
H H0 0 1, ,n n� � äëÿ âñåõ n �. Ïðåäëîæåííûå â íàñòîÿùåé ðàáîòå àëãîðèòìû
ïðèìåíèìû ê ÃÀ H H0,n ( )n � , òàê êàê äîñòàòî÷íî â îòäåëüíîñòè èñïîëüçî-
âàòü èõ äëÿ êàæäîãî ÃÀ, âõîäÿùåãî â ïðÿìóþ ñóììó. Ýòî îçíà÷àåò, ÷òî ïðè ðåøå-
íèè çàäà÷ 1 è 2 äëÿ ÃÀ H H0,n ( )n � âîçìîæíî ðàñïàðàëëåëèâàíèå âû÷èñëåíèé.
Èññëåäîâàíèå ðåøåííûõ â íàñòîÿùåé ñòàòüå çàäà÷ äëÿ ðàçëè÷íûõ êîìïîçè-
öèé ÃÀ, ïðèíàäëåæàùèõ ìíîæåñòâó H0 , ÿâëÿåòñÿ âîçìîæíûì íàïðàâëåíèåì
äàëüíåéøèõ èññëåäîâàíèé. Äðóãîå íàïðàâëåíèå ñîñòîèò â îáîáùåíèè ïîëó÷åí-
íûõ ðåçóëüòàòîâ íà îïðåäåëåííûå êëàññû ìíîãîìåðíûõ ÃÀ.
Íàä³éøëà äî ðåäàêö³¿ 09.01.2018
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Cyber-Physical European Roadmap&Strategy, 2015. URL: www.cyphers.eu.
2. Foundations for innovation. Strategic R&D opportunities for the 21st century cyber-physical
systems. 2016. URL: http:// bookprem.com/gd-ebooks/B00U7SUBG.
3. Giraldo J., Sarkar E., Cardenas A.A., Maniatakos M., Murat Kantarcioglu M. Security and Privacy in
Cyber-Physical Systems: A Survey of Surveys. IEEE Design & Test. 2017. Vol. 34, Iss. 4. P. 7–17.
4. Lee E.A. Cyber physical systems: Design challenges. Proc. of the 11th IEEE Int. Symp. on Object
Oriented Real-Time Distributed Computing (ISORC) (May 6, 2008, Orlando, Fl., USA), 2008.
P. 363–369.
5. Lee E.A., Seshia S.A. Introduction to embedded systems: A cyber-physical systems approach. Sec.
Ed. Cambridge, Mass.: MIT Press, 2017. 568 p.
6. Ëåòè÷åâñêèé À.À., Ëåòè÷åâñêèé À.À. ìë., Ñêîáåëåâ Â.Ã., Âîëêîâ Â.À. Êèáåð-ôèçè÷åñêèå ñèñ-
òåìû. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 2017. Ò. 53, ¹ 6. Ñ. 3–19.
7. Henzinger T.A. The theory of hybrid automata. Proc. of the 11th Annual IEEE Symposium on Logic
in Computer Science (LICS 96), 1996. P. 278–292.
8. Raskin J.F. An introduction to hybrid automata. Handbook of Networked and Embedded Control
Systems. NY: Springer-Verlag, 2005. P. 491–518.
14 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 4
9. Carloni L.P., Passerone R., Pinto A., Sangiovanni-Vincentelli A.L. Languages and tools for hybrid
systems design. Foundations and Trends in Electronic Design Automation. 2006. Vol. 1, Iss. 1, 2.
P. 1–193.
10. Lygeros J. Lecture notes on hybrid systems. Cambridge: University of Cambridge, 2003.
URL: https://fenix.tecnico.ulisboa.pt/downloadFile/3779579688470/lygeros.pdf.
11. Ëåòè÷åâñêèé À.À. Àëãåáðàè÷åñêàÿ òåîðèÿ âçàèìîäåéñòâèÿ è êèáåð-ôèçè÷åñêèå ñèñòåìû.
Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêè. 2017. ¹ 5. Ñ. 3–15.
12. Letichevsky A.A., Letichevskyi O.A., Peschanenko V.S. Insertion modeling system. LNCS. 2015.
Vol. 7162. P. 262–272.
13. Letichevsky A.A., Letichevskyi O.A., Peschanenko V.S., Weigert T. Insertion modeling and
symbolic verification of large systems. LNCS. 2015. Vol. 9369. P. 3–18.
Íàä³éøëà äî ðåäàêö³¿ 09.01.2018
Â.Â. Ñêîáåëºâ, Â.Ã. Ñêîáåëºâ
ÏÐÎ ÄÅßʲ ÇÀÄÀײ ÀÍÀ˲ÇÓ Ã²ÁÐÈÄÍÈÕ ÀÂÒÎÌÀÒ²Â
Àíîòàö³ÿ. Âèçíà÷åíî êëàñ 1-âèì³ðíèõ ã³áðèäíèõ àâòîìàò³â, ó ÿêèõ ó êîæíî-
ìó äèñêðåòíîìó ñòàí³ äëÿ ð³çíèõ ìíîæèí ïî÷àòêîâèõ çíà÷åíü íåïåðåðâíîãî
ñòàíó äèíàì³êà ìîæå áóòè ïðåäñòàâëåíà ð³çíèìè äèôåðåíö³àëüíèìè ð³âíÿí-
íÿìè, òà çàäàíî ñê³í÷åííó òðèâàë³ñòü ö³º¿ äèíàì³êè, ÿêà ìîæå áóòè ð³çíîþ
äëÿ ð³çíèõ ìíîæèí ïî÷àòêîâèõ çíà÷åíü íåïåðåðâíîãî ñòàíó. Çàïðîïîíîâàíî
àëãîðèòìè ðîçâ’ÿçàííÿ çàäà÷ âèëó÷åííÿ ñóïåðå÷íîñòåé â îá’ºêòàõ, ÿê³ âèçíà-
÷àþòü ã³áðèäíèé àâòîìàò, óçãîäæåííÿ öèõ îá’ºêò³â îäèí ç îäíèì,
çíàõîäæåííÿ ì³í³ìàëüíîãî ÷èñëà ïåðåìèêàíü òà îö³íêè ì³í³ìàëüíîãî ÷àñó,
çà ÿêèé äèñêðåòí³ ñòàíè äîñÿæí³ ç ìíîæèíè ïî÷àòêîâèõ äèñêðåòíèõ ñòàí³â.
Êëþ÷îâ³ ñëîâà: ã³áðèäí³ àâòîìàòè, âåðèô³êàö³ÿ.
V.V. Skobelev, V.G. Skobelev
SOME PROBLEMS FROM THE ANALYSIS OF HYBRID AUTOMATA
Abstract. A class of 1-dimensional hybrid automata is defined, such that in each
discrete state, the dynamics can be presented by different differential equations for
different sets of initial values of continuous state, each dynamics duration is finite,
and can be different for different sets of initial values of continuous state.
Algorithms are proposed to solve problems of eliminating contradictions in objects
that define the hybrid automata, of coordinating these objects with each other,
calculating the minimum number of switchings, and estimating the minimum time
for reachability of discrete states from the set of initial discrete states.
Keywords: hybrid automata, verification.
Ñêîáåëåâ Âëàäèìèð Âëàäèìèðîâè÷,
äîêòîð ôèç.-ìàò. íàóê, ñòàðøèé íàó÷íûé ñîòðóäíèê Èíñòèòóòà êèáåðíåòèêè èì. Â.Ì. Ãëóøêîâà ÍÀÍ
Óêðàèíû, Êèåâ,
å-mail: skobelevvg@gmail.com.
Ñêîáåëåâ Âëàäèìèð Ãåííàäèåâè÷,
äîêòîð ôèç.-ìàò. íàóê, äîêòîð òåõí. íàóê, ïðîôåññîð, âåäóùèé íàó÷íûé ñîòðóäíèê Èíñòèòóòà
êèáåðíåòèêè èì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðàèíû, Êèåâ,
å-mail: skobelevvg@gmail.com.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 4 15
|