Об оптимизационных проблемах включения треков
Показано поліноміальну складність оптимізаційних проблем для кінцевої множини треків Т: 1) знайти трек найбільшої довжини, вкладений в кожен трек з множини Т; 2) знайти найкоротший трек, не вкладений в кожен трек з множини Т; 3) знайти найкоротший трек, в який вкладено кожен трек з множини Т; 4) зна...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2010 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/45643 |
| 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: | Об оптимизационных проблемах включения треков / К.В. Шахбазян, Ю.Г. Шукурян // Кибернетика и системный анализ. — 2010. — № 6. — С. 17–26. — Бібліогр.: 22 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859902067244531712 |
|---|---|
| author | Шахбазян, К.В. Шукурян, Ю.Г. |
| author_facet | Шахбазян, К.В. Шукурян, Ю.Г. |
| citation_txt | Об оптимизационных проблемах включения треков / К.В. Шахбазян, Ю.Г. Шукурян // Кибернетика и системный анализ. — 2010. — № 6. — С. 17–26. — Бібліогр.: 22 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Показано поліноміальну складність оптимізаційних проблем для кінцевої множини треків Т: 1) знайти трек найбільшої довжини, вкладений в кожен трек з множини Т; 2) знайти найкоротший трек, не вкладений в кожен трек з множини Т; 3) знайти найкоротший трек, в який вкладено кожен трек з множини Т; 4) знайти трек найбільшої довжини, в який не вкладено кожен трек з множини T.
Four optimization problems for a finit set of traces are considered: (i) find the longest trace that is included in each trace from a given finite set T of traces, (ii) find the shortest trace that is not included in every trace from a given finite set T of traces, (iii) find the shortest trace that includes every trace from a given finite set T of traces, (iv) find the longest trace that does not include each trace from a given finite set T of traces.
|
| first_indexed | 2025-12-07T15:57:43Z |
| format | Article |
| fulltext |
ÓÄÊ 519.6
Ê.Â. ØÀÕÁÀÇßÍ, Þ.Ã. ØÓÊÓÐßÍ
ÎÁ ÎÏÒÈÌÈÇÀÖÈÎÍÍÛÕ ÏÐÎÁËÅÌÀÕ ÂÊËÞ×ÅÍÈß ÒÐÅÊÎB
Êëþ÷åâûå ñëîâà: òåîðèÿ òðåêîâ, îáðàáîòêà ñòðîê, îïòèìèçàöèÿ, ïðîáëåìà
âêëþ÷åíèÿ.
ÂÂÅÄÅÍÈÅ
Îñíîâíûìè ñòðóêòóðàìè, â êîòîðûõ õðàíèòñÿ è ïåðåäàåòñÿ èíôîðìàöèÿ, ÿâëÿþò-
ñÿ ñòðîêè. Ïîýòîìó ýôôåêòèâíàÿ îáðàáîòêà ñòðîê ñ öåëüþ èçâëå÷åíèÿ èç íèõ ïî-
ëåçíîé èíôîðìàöèè ñòàëà ïðåäìåòîì èçó÷åíèÿ öåëîé âåòâè êîìïüþòåðíîé íàóêè
(computer science) — ñòðèíãîëîãèè (stringology).
×àñòî ñòðîêè îáëàäàþò ñëåäóþùèì âàæíûì ñâîéñòâîì: íåêîòîðûå ïàðû ñî-
ñåäíèõ áóêâ â ñòðîêå ìîãóò áûòü ïåðåñòàâëåíû áåç ïîòåðè èíôîðìàöèè. Â ýòîì
ñëó÷àå èñõîäíàÿ ñòðîêà ìîæåò ñ÷èòàòüñÿ ýêâèâàëåíòíîé ñòðîêå, ïîëó÷åííîé ïðè
ïåðåñòàíîâêå áóêâ. Èçâåñòíûì ïðèìåðîì ÿâëÿþòñÿ êîäû ïðîãðàìì, ãäå ñîñåäíèå
êîìàíäû ìîãóò áûòü ïåðåñòàâëåíû ïðè èçâåñòíûõ óñëîâèÿõ. Ýòî ñâîéñòâî ýêâèâà-
ëåíòíîñòè øèðîêî èñïîëüçóåòñÿ ïðè êîìïàêòàöèè êîäîâ. Ïîýòîìó èìååò ñìûñë ðàñ-
ñìàòðèâàòü çàäà÷è èçâëå÷åíèÿ èíôîðìàöèè èç ñòðîê ñ ó÷åòîì òàêîãî ðîäà ýêâèâàëåí-
òíîñòåé. Ýòó âîçìîæíîñòü ïðåäîñòàâëÿåò òåîðèÿ òðåêîâ.
Ïîíÿòèå òðåêà [1] áûëî ïðåäëîæåíî â êà÷åñòâå ìîäåëè ïàðàëëåëüíûõ ïðîöåñ-
ñîâ â âû÷èñëèòåëüíûõ ñèñòåìàõ, è òåîðèÿ òðåêîâ ÿâëÿåòñÿ óäîáíûì àïïàðàòîì äëÿ
àíàëèçà ïàðàëëåëüíûõ ïðîöåññîâ [1–3]. Ðåøåíèå çàäà÷ ñðàâíåíèÿ òðåêîâ âàæíî
òàì, ãäå âàæíî èçó÷åíèå ñòðîê ñ êîììóòèðóþùèìè áóêâàìè, íàïðèìåð â îáðàáîòêå
ñîîáùåíèé, êîäèðîâàíèè, èñêóññòâåííîì èíòåëëåêòå.
Òðåê åñòü êëàññ ýêâèâàëåíòíîñòè ñòðîê â àëôàâèòå � , ïîðîæäàåìoé çàäàííûì
íà àëôàâèòå � ñèììåòðè÷íûì îòíîøåíèåì I íåçàâèñèìîñòè (êîììóòàòèâíîñòè)
áóêâ. Äâå ñòðîêè ñ÷èòàþòñÿ ýêâèâàëåíòíûìè, åñëè îäíà èç íèõ ìîæåò áûòü ïîëó÷å-
íà èç äðóãîé ïóòåì ïîñëåäîâàòåëüíûõ ïåðåñòàíîâîê ñîñåäíèõ êîììóòèðóþùèõ
áóêâ. Ìíîæåñòâî òðåêîâ îáðàçóåò ñâîáîäíûé ÷àñòè÷íî-êîììóòàòèâíûé ìîíîèä
M D( , )� , ãäå D I� �( ) \� � — îòíîøåíèå çàâèñèìîñòè íà àëôàâèòå � .
Ïóñòü T t t k�{ }1 , ,� — êîíå÷íîå ìíîæåñòâî òðåêîâ, ïðèíàäëåæàùèõ ìîíîèäó
M D( , )� . Âàæíûìè õàðàêòåðèñòèêàìè âçàèìíîé áëèçîñòè òðåêîâ èç T ÿâëÿþòñÿ
íàèáîëüøèé ïîäòðåê, îáùèé äëÿ âñåõ t T� , è íàèìåíüøèé îáùèé íàäòðåê, ò.å. òðåê,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6 17
© Ê.Â. Øàõáàçÿí, Þ.Ã. Øóêóðÿí, 2010
ñîäåðæàùèé â ñåáå âñå òðåêè t T� â êà÷åñòâå ïîäòðåêîâ. (Òðåê s íàçûâàåòñÿ ïîäòðå-
êîì òðåêà t , åñëè ñóùåñòâóþò ñòðîêè y t� , x s� òàêèå, ÷òî x åñòü ïîäïîñëåäîâà-
òåëüíîñòü y .)  ýòîì ñëó÷àå t íàçûâàåòñÿ íàäòðåêîì òðåêà s . Ñîîòâåòñòâåííî êðàò-
÷àéøèé îáùèé íåïîäòðåê è äëèííåéøèé îáùèé íåíàäòðåê ÿâëÿþòñÿ õàðàêòåðèñ-
òèêàìè ðàçëè÷èÿ ìåæäó òðåêàìè ìíîæåñòâà T . Åñëè çàäàíû äâà ìíîæåñòâà òðå-
êîâ: U è S , òî âàæíîé õàðàêòåðèñòèêîé ýòîé ïàðû ìíîæåñòâ ÿâëÿåòñÿ êðàò÷àéøèé
òðåê, ðàçëè÷àþùèé ýòè ìíîæåñòâà, à èìåííî îí ëèáî ÿâëÿåòñÿ ïîäòðåêîì êàæäîãî
òðåêà èç U , íî íå ÿâëÿåòñÿ ïîäòðåêîì êàæäîãî òðåêà èç S , ëèáî, íàîáîðîò, íå ÿâëÿ-
åòñÿ ïîäòðåêîì êàæäîãî òðåêà èçU, íî ÿâëÿåòñÿ ïîäòðåêîì êàæäîãî òðåêà èç S .
 íàñòîÿùåé ñòàòüå ðàññìàòðèâàþòñÿ ñëåäóþùèå îïòèìèçàöèîííûå ïðîáëåìû
äëÿ êîíå÷íîãî ìíîæåñòâà òðåêîâ T. Íàéòè:
1) íàèáîëüøèé îáùèé ïîäòðåê,
2) êðàò÷àéøèé îáùèé íåïîäòðåê,
3) êðàò÷àéøèé îáùèé íàäòðåê,
4) íàèáîëüøèé îáùèé íåíàäòðåê.
Öåëü ñòàòüè — äîêàçàòåëüñòâî ïîëèíîìèàëüíîé ñëîæíîñòè ðåøåíèÿ ýòèõ ïðî-
áëåì äëÿ êîíå÷íûõ ìíîæåñòâ òðåêîâ. Ìîæåò ïîêàçàòüñÿ, ÷òî ýòî NP-ïîëíûå çàäà÷è
äàæå äëÿ ìíîæåñòâ T , ñîñòîÿùèõ èç äâóõ òðåêîâ. Ïðîñòåéøåå ðåøåíèå óêàçàííûõ
çàäà÷ ìîæíî ïðåäñòàâèòü ñåáå òàê (íàïðèìåð, çàäà÷à 1): ïåðåáðàòü âñå ïàðû ñòðîê
( , )y y1 2 , ïðåäñòàâëÿþùèõ òðåêè ìíîæåñòâà T t t�{ }1 2, . Äëÿ êàæäîé ïàðû èçâåñò-
íûì ìåòîäîì [10] íàéòè íàèáîëüøóþ îáùóþ ïîäïîñëåäîâàòåëüíîñòü (ò.å. òðåê,
ïðåäñòàâëåííûé ýòîé ïîäïîñëåäîâàòåëüíîñòüþ), à çàòåì èç íàéäåííûõ ïîäïîñëåäî-
âàòåëüíîñòåé âûáðàòü íàèáîëüøóþ (àíàëîãè÷íûå ðàññóæäåíèÿ äëÿ çàäà÷ 2–4).
Äëÿ êîíå÷íîãî | |T ïðåäëàãàþòñÿ àëãîðèòìû ïîëèíîìèàëüíîé ñëîæíîñòè ðåøå-
íèÿ ýòèõ çàäà÷. Çàìåòèì, ÷òî ïîëó÷åííûå îöåíêè ñëîæíîñòè ñóùåñòâåííî çàâèñÿò
îò ñòðóêòóðû àëôàâèòà çàâèñèìîñòè, ïîñêîëüêó â íèõ âõîäèò ïàðàìåòð m — ÷èñëî
êëèê â ìèíèìàëüíîì ïîêðûòèè êëèêàìè ãðàôà àëôàâèòà çàâèñèìîñòè ( , )� D .
Óïîìÿíóòûå ïðîáëåìû øèðîêî èçâåñòíû â ôîðìóëèðîâêå äëÿ ñòðîê: 1) çàäà÷à
î äëèííåéøåé îáùåé äëÿ ìíîæåñòâà ñòðîê ïîäïîñëåäîâàòåëüíîñòè, 2) çàäà÷à
î êðàò÷àéøåé îáùåé äëÿ ìíîæåñòâà ñòðîê íåïîäïîñëåäîâàòåëüíîñòè, 3) çàäà÷à
î êðàò÷àéøåé îáùåé íàäïîñëåäîâàòåëüíîñòè, 4) çàäà÷à î äëèííåéøåé îáùåé íåíàä-
ïîñëåäîâàòåëüíîñòè.
Ýòè çàäà÷è äëÿ ìíîæåñòâ ñòðîê ðàññìàòðèâàëèñü ìíîãèìè àâòîðàìè [4–19].
Äëÿ ñëó÷àÿ ôèêñèðîâàííîé ñòðîêè Baeza-Yates [4] ââåë àöèêëè÷åñêèé ãðàô
ïîäïîñëåäîâàòåëüíîñòåé — DASG, ò.å. ìèíèìàëüíûé ÷àñòè÷íûé àâòîìàò,
îïðåäåëÿåìûé çàäàííîé ñòðîêîé è ðàñïîçíàþùèé ÿçûê ïîäïîñëåäîâàòåëüíîñòåé
ýòîé ñòðîêè. Ñ èñïîëüçîâàíèåì àâòîìàòà DASG [8–11] áûëè ðåøåíû ìíîãèå çàäà÷è
ñðàâíåíèÿ ìíîæåñòâ ñòðîê. Ïåðå÷èñëåííûå çàäà÷è äàæå äëÿ ñòðîê ÿâëÿþòñÿ
NP-òðóäíûìè â èõ îáùåé ïîñòàíîâêå [12, 18, 19].
Ïðè ðåøåíèè çàäà÷, ïîñòàâëåííûõ äëÿ òðåêîâ, èñïîëüçóåì ñïîñîá, ïðåäëîæåí-
íûé Baeza-Yates è Crochemore [10] äëÿ ñòðîê. Â îñíîâå ýòîãî ñïîñîáà ëåæèò ìèíè-
ìàëüíûé àöèêëè÷åñêèé àâòîìàò A t( ) , îïðåäåëÿåìûé òðåêîì t , àíàëîãè÷íûé DASG
è ðàñïîçíàþùèé ÿçûê ïîäòðåêîâ òðåêà t. Àâòîìàò A t( ) ìîæåò áûòü ïîñòðîåí çà âðå-
ìÿ O m nm( | | )� �1 , ãäå n — äëèíà òðåêà t, m — ÷èñëî êëèê â ìèíèìàëüíîì ïîêðûòèè
êëèêàìè ãðàôà àëôàâèòà çàâèñèìîñòè ( , )� D .
Àâòîìàò A t( ) ñëóæèò îñíîâîé äëÿ ïîëèíîìèàëüíûõ àëãîðèòìîâ ðåøåíèÿ ñëå-
äóþùèõ çàäà÷.
1. Íàéòè îáùèé íàèáîëüøèé ïîäòðåê äëÿ ìíîæåñòâà òðåêîâ T t t k�{ }1 , ,� .
2. Íàéòè îáùèé êðàò÷àéøèé íåïîäòðåê äëÿ ìíîæåñòâà òðåêîâ T t t k�{ }1 , ,� .
Àâòîìàò A t( ) èñïîëüçóåòñÿ òàêæå äëÿ íàõîæäåíèÿ êðàò÷àéøåãî ðàçëè÷àþùåãî òðåêà.
Çàäà÷è 3 è 4, îòíîñÿùèåñÿ ê íàäòðåêàì è íåíàäòðåêàì, ðåøåíû ïîñòðîåíèåì
ãðàôîâ, ñðåäè ïóòåé êîòîðûõ åñòü ïóòè, íåñóùèå èñêîìûå ðåøåíèÿ.
Ïðèìåðîì îáëàñòè, â êîòîðîé âîçíèêàåò çàäà÷à î íàäòðåêàõ, ÿâëÿåòñÿ êîì-
ïàêòàöèÿ (îïòèìèçàöèÿ) êîäîâ.  ÷àñòíîñòè, ïðè âûïîëíåíèè ïðîöåäóðàëüíîé
àáñòðàêöèè [22], èñïîëüçóåìîé ïðè êîìïàêòàöèè êîäîâ äëÿ ïðîöåññîðîâ ñ ïðåäè-
18 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6
êàòíûìè èíñòðóêöèÿìè (òèïà ïðîöåññîðîâ ARM, îðèåíòèðîâàííûõ íà èñïîëüçîâà-
íèå â ïîðòàòèâíûõ óñòðîéñòâàõ), ïðîèñõîäèò ïîèñê íàèìåíüøåé îáùåé íàäñòðîêè
èíñòðóêöèé äëÿ ìíîæåñòâà êîäîâ-ñòðîê. Îäíàêî åñòåñòâåííî ðàññìàòðèâàòü êîäû
êàê ñòðîêè (èíñòðóêöèé), ïðèíàäëåæàùèå òðåêó, àëôàâèò íåçàâèñèìîñòè êîòîðîãî
ïîðîæäàåòñÿ êîììóòèðóþùèìè èíñòðóêöèÿìè.  ýòîì ñëó÷àå ïîèñê îáùåé íàäñòðîêè
ìîæåò áûòü çàìåíåí ïîèñêîì íàäòðåêà, ÷òî ìîæåò ïðèâåñòè ê ëó÷øåé êîìïàêòàöèè.
Ñòðóêòóðà ñòàòüè òàêîâà: ïîñëå ïðåäâàðèòåëüíûõ ñâåäåíèé (ðàçä. 1) â ðàçä. 2
ïðåäëàãàåòñÿ àëãîðèòì ïîñòðîåíèÿ ïî çàäàííîé ñòðîêå y t� ìèíèìàëüíîãî ÷àñòè÷-
íîãî àöèêëè÷åñêîãî àâòîìàòà A t( ) , ðàñïîçíàþùåãî ïîäòðåêè òðåêà t è àíàëîãè÷íî-
ãî ãðàôó DASG äëÿ ñòðîê.
Ðàçä. 3 ïîñâÿùåí àëãîðèòìàì íàõîæäåíèÿ íàèáîëüøåãî îáùåãî ïîäòðåêà,
êðàò÷àéøåãî îáùåãî íåïîäòðåêà è íàèìåíüøåãî ðàçëè÷àþùåãî ïîäòðåêà. Ñ ýòîé
öåëüþ ïî íàáîðó ñòðîê y t1 1� ,� , y tk k� — ïðåäñòàâèòåëåé òðåêîâ ìíîæåñòâà
T t t k�{ }1 , ,� ñòðîèòñÿ ãðàô G T( ) , â êîòîðîì ïóòè, èñõîäÿùèå èç êîðíÿ, íåñóò ñëî-
âà, ïðåäñòàâëÿþùèå ïîäòðåêè, îáùèå äëÿ ïîäìíîæåñòâ òðåêîâ ìíîæåñòâà T. Ñëîæ-
íîñòü ïðåäëàãàåìûõ àëãîðèòìîâ ñîñòàâëÿåò O m nkm( | | )� �1 .
 ðàçä. 4 ðåøàþòñÿ çàäà÷è î íàèìåíüøåì îáùåì íàäòðåêå è íàèáîëüøåì îá-
ùåì íåíàäòðåêå. Äëÿ ðåøåíèÿ ïåðâîé çàäà÷è ñòðîèòñÿ ãðàô B t t( , )1 2 , êàæäûé ïóòü
êîòîðîãî, íà÷èíàþùèéñÿ â êîðíå, íåñåò ñëîâî, ïðåäñòàâëÿþùåå íàäòðåê äëÿ ïàðû
ïðåôèêñîâ p t1 1�Pref ( ) , p t2 2�Pref ( ) . Íà îñíîâàíèè ýòîãî çàäà÷à ñâîäèòñÿ ê íà-
õîæäåíèþ ñëîâà, íåñîìîãî êðàò÷àéøèì ïóòåì â ýòîì ãðàôå. Ñëîæíîñòü ïðåäëàãàå-
ìîãî àëãîðèòìà ñîñòàâëÿåò O m n m( | | )� 2 1� . Ïðè ïîñòðîåíèè èñïîëüçîâàíû îöåíêà
÷èñëà ïðåôèêñîâ òðåêà è ñòðóêòóðà ãðàôà ïðåôèêñîâ, îïèñàííûå â [13] .
Äëÿ ðåøåíèÿ âòîðîé çàäà÷è (ïðè óñëîâèè ñóùåñòâîâàíèÿ ðåøåíèÿ) ñòðîèòñÿ ãðàô
G T( ) , â êîòîðîì ïóòè, íà÷èíàþùèåñÿ â êîðíå, íåñóò âñå ñëîâà, ïðåäñòàâëÿþùèå
íåíàäòðåêè äëÿ T . Òåì ñàìûì çàäà÷à ñâîäèòñÿ ê íàõîæäåíèþ ñëîâà, íåñîìîãî
äëèííåéøèì ïóòåì â ýòîì ãðàôå. Ñëîæíîñòü àëãîðèòìà ñîñòàâëÿåò O mk( | | )� � .
1. ÏÐÅÄÂÀÐÈÒÅËÜÍÛÅ ÑÂÅÄÅÍÈß
Íèæå èñïîëüçóþòñÿ ñëåäóþùèå îáîçíà÷åíèÿ.
Ïóñòü y y yn� 1 � — ñòðîêà â ïðîèçâîëüíîì êîíå÷íîì àëôàâèòå � ; | |y n� —
äëèíà ñòðîêè y . Ìíîæåñòâî J y n( ) , ,�{ }1 � áóäåì íàçûâàòü ìíîæåñòâîì ïîçèöèé
ñòðîêè y . ×èñëî j J y� ( ) íàçîâåì ïîçèöèåé áóêâû a â ñòðîêå y , åñëè y aj � . ×èñëî
ïîçèöèé áóêâû a â ñòðîêå y îáîçíà÷èì | |y a , ò.å. | | | | ,y j y a j na j� � �{ }| . Ïîçèöèÿ
j J y� ( ) íàçûâàåòñÿ k-é ïîçèöèåé áóêâû a â ñòðîêå y , åñëè y aj � è ïðåôèêñ
y y j1 ... ñòðîêè y ñîäåðæèò k ïîçèöèé áóêâû a, ò.å. | ... |y y kj a1 � . Îáîçíà÷èì k-þ
ïîçèöèþ áóêâû a â ñòðîêå y ÷åðåç pos ( , , )y a k . Ïîçèöèÿ pos ( , , )y a k îïðåäåëåíà
òîëüêî äëÿ k y a�| | .
Ïóñòü � — êîíå÷íûé àëôàâèò, D � �� � — ðåôëåêñèâíîå è ñèììåòðè÷íîå îò-
íîøåíèå çàâèñèìîñòè, I D� �( ) \� � — îòíîøåíèå íåçàâèñèìîñòè èëè ïåðåñòàíî-
âî÷íîñòè. Îòíîøåíèå I èíäóöèðóåò îòíîøåíèå ýêâèâàëåíòíîñòè íà �* . Äâå ñòðî-
êè x y, *�� ÿâëÿþòñÿ ýêâèâàëåíòíûìè îòíîñèòåëüíî , åñëè ñóùåñòâóåò ïîñëåäîâà-
òåëüíîñòü z zn1 , ,� ñòðîê òàêèõ, ÷òî x z� 1 , y zn� è äëÿ âñåõ i i n( )1�
ñóùåñòâóþò ñòðîêè � ��z zi i, è áóêâû ai , bi , óäîâëåòâîðÿþùèå óñëîâèÿì
z z a b z
z z b a z a b I
i i i i i
i i i i i i i
� � ��
� � �� �
�
� �
,
, ( , ) ,1 ãäå
ò.å. äâe ñòðîêè ýêâèâàëåíòíû ïî îòíîøåíèþ òîãäà è òîëüêî òîãäà, êîãäà îäía
ñòðîêà ìîæåò áûòü ïîëó÷åía èç äðóãîé ïåðåñòàíîâêîé ñîñåäíèõ íåçàâèñèìûõ
áóêâ. Òîãäà ìíîæåñòâî M M D� ( , )� êëàññîâ ýêâèâàëåíòíûõ ñòðîê èç �* ïî îò-
íîøåíèþ íàçûâàåòñÿ òðåêîâûì ìîíîèäîì, åãî ýëåìåíòû íàçûâàþòñÿ òðåêàìè.
Íà ýëåìåíòàõ M îïðåäåëåíî óìíîæåíèå — êîíêàòåíàöèÿ. Òðåê t îáîçíà÷àåòñÿ [ ]x
äëÿ ëþáîé ïðåäñòàâëÿþùåé ñòðîêè x t� . Äëèíà òðåêà t åñòü äëèíà ëþáîãî åãî
ïðåäñòàâëåíèÿ x t� è îáîçíà÷àåòñÿ | |t .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6 19
Äëÿ çàäàííûõ äâóõ òðåêîâ p t M D, ( , )� � ñ÷èòàþò, ÷òî p åñòü ïðåôèêñ t , åñëè
t pq� , ãäå q M D� ( , )� . Îáîçíà÷èì Pref ( )t ìíîæåñòâî ïðåôèêñîâ òðåêà t .
Ïóñòü ( , , )� �1 � m — ïîêðûòèå àëôàâèòà çàâèñèìîñòè ( , )� D êëèêàìè, ò.å. ñå-
ìåéñòâî ïîäìíîæåñòâ � òàêèõ, ÷òî
� �i
i
m
�
� 1
� , � �i i D� � (i m�1 2, , ,� ), ( , ) : ,a b D i a b i� � � �� .
Äàëåå âåçäå áóäåì ñ÷èòàòü � �1 , ,� m íàèìåíüøèì ïîêðûòèåì êëèêàìè àëôàâèòà çà-
âèñèìîñòè ( , )� D . Òîãäà m — ÷èñëî êëèê â íàèìåíüøåì ïîêðûòèè. Çàìåòèì, ÷òî m � � , ãäå
� — ðàçìåð íàèáîëüøåé êëèêè â ãðàôå íåçàâèñèìîñòè ( , )� I àëôàâèòà ìîíîèäà.
Ëþáîé òðåê t M D� ( , )� ìîæåò áûòü ïðåäñòàâëåí m-êîé ñòðîê [1], êîòîðóþ îáî-
çíà÷èì � � �( ) { ( ), ... . ( )}t t tm� 1 . Çäåñü � i it( ) *�� — ïðîåêöèÿ ñòðîêè y t� íà � i .
Îáîçíà÷èì r ti ( ) äëèíó ïðîåêöèè � i t( ) . Ïðîèçâåäåíèå äëèí âñåõ ïðîåêöèé, óâåëè-
÷åííûõ íà åäèíèöó, îáîçíà÷èì r t r ti
i
m
( ) ( ( ) )� �
�
�
1
1 .
Äëÿ êàæäîãî çàäàííîãî t M D� ( , )� ëþáîé ïðåôèêñ p t�Pref ( ) ìîæåò áûòü
ïðåäñòàâëåí m-é öåëûõ ÷èñåë p r p r pm� ( ( ),... , ( ))1 [13, 21]. Âû÷èñëåíèå p a[ ] ïî çà-
äàííîìó p òðåáóåò O m( ) øàãîâ.
Îïðåäåëåíèå 1. Ïóñòü s t M D, ( , )� � . Áóäåì ñ÷èòàòü, ÷òî òðåê s ÿâëÿåòñÿ ïîä-
òðåêîì òðåêà t , åñëè ñóùåñòâóþò ñòðîêè x s y t� �, òàêèå, ÷òî ñòðîêà x ÿâëÿåòñÿ
ïîäïîñëåäîâàòåëüíîñòüþ ñòðîêè y .  ýòîì ñëó÷àå áóäåì ïèñàòü s t� , à òàêæå ñ÷è-
òàòü, ÷òî òðåê t ÿâëÿåòñÿ íàäòðåêîì òðåêà s . �
 [20, 21] ïðèâåäåíî ñëåäóþùåå ýêâèâàëåíòíîå îïðåäåëåíèå îòíîøåíèÿ s t� .
Îïðåäåëåíèå 1� . Ïóñòü s t M D, ( , )� � . Òðåê s âëîæåí â òðåê t (s ÿâëÿåòñÿ ïîä-
òðåêîì òðåêà t), åñëè ñóùåñòâóþò òðåêè t t l0 , ,� , s s M Dl1 , , ( , )� � � òàêèå, ÷òî
t t s t s tl l� 0 1 1 � è s s sl� 1 � . �
Äàëåå áóäåì èñïîëüçîâàòü òåðìèí «ïîäòðåê» è «íàäòðåê» ïî àññîöèàöèè ñ
«ïîäïîñëåäîâàòåëüíîñòüþ» è «íàäïîñëåäîâàòåëüíîñòüþ». Ñóùåñòâåííî, ÷òî s t�
òîãäà è òîëüêî òîãäà, êîãäà äëÿ ëþáîé ñòðîêè y t� ñóùåñòâóåò ñòðîêà x s� òàêàÿ,
÷òî x åñòü ïîäïîñëåäîâàòåëüíîñòü ñòðîêè y . Îäíàêî îáðàòíîå íåâåðíî, è èç s t� íå
ñëåäóåò, ÷òî äëÿ êàæäîé ñòðîêè x s� ñóùåñòâóåò ñòðîêà y t� òàêàÿ, ÷òî x åñòü ïîä-
ïîñëåäîâàòåëüíîñòü ñòðîêè y . Ïðèâåäåì ïðèìåð.
Ïðèìåð 1. Ðàññìîòðèì ìîíîèä M D( , )� , ãäå � �{ }a b c, , , D a b b c�{ }( , ), ( , ) .
Ïóñòü t abc� [ ] . Òðåê t ñîñòîèò èç åäèíñòâåííîé ñòðîêè y abc� . Åñëè s ac� [ ] , òî
ñòðîêà ca s� , íî ca íå ÿâëÿåòñÿ ïîäïîñëåäîâàòåëüíîñòüþ ñòðîêè y abc� . �
2. ÀÂÒÎÌÀÒ ÏÎÄÒÐÅÊÎÂ A t( )
Óòâåðæäåíèå 1. Äëÿ êàæäîãî òðåêà t M D� ( , )� ñóùåñòâóåò M-àâòîìàò A t( ) ,
ðàñïîçíàþùèé ÿçûê L x x tA t( ) { | [ ] }� � , ò.å. ÿçûê ïîäòðåêîâ òðåêà t òàêîé, ÷òî:
à) A t( ) — ÷àñòè÷íûé àöèêëè÷åñêèé àâòîìàò, ÷èñëî ñîñòîÿíèé A t( ) íå ïðåâîñ-
õîäèò r t r ti
i
m
( ) ( ( ) )� �
�
� 1
1
;
á) îöåíêà r t( ) ÷èñëà ñîñòîÿíèé àâòîìàòà A t( ) äîñòèæèìà ïðè D �� , ò.å. ïðè
m � | |� , êîãäà âñå áóêâû àëôàâèòà êîììóòèðóþò;
â) ïðè m �1, ò.å. ïðè I �� , àöèêëè÷åñêèé àâòîìàò A t( ) ñîâïàäàåò ñ àâòîìàòîì
DASG äëÿ ñòðîêè y t� ; çàìåòèì, ÷òî â ýòîì ñëó÷àå êàæäûé òðåê t M D� ( , )� ñîäåð-
æèò åäèíñòâåííóþ ñòðîêó;
ã) ïî ëþáîé ñòðîêå y t� ìîæíî ïîñòðîèòü àâòîìàò A t( ) çà âðåìÿ
O m t O tm( | | | | ) ( | | | | )� �� ��1 1� � , ãäå � — ðàçìåð íàèáîëüøåé êëèêè â ãðàôå íåçàâè-
ñèìîñòè ( , )� I àëôàâèòà ìîíîèäà.
Äîêàçàòåëüñòâî. Ïóñòü òðåê t çàäàí ñòðîêîé y y y y� �1 � | |
*� . Äëÿ ïðîèç-
âîëüíîé ñòðîêè x x x x� 1 � | | âûïîëíÿåòñÿ [ ] [ ]x y� â ìîíîèäå M D( , )� òîãäà è òîëü-
20 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6
êî òîãäà, êîãäà ñóùåñòâóåò âëîæåíèå �x : J x x J y y( ) , , | | ( ) , , | |� � �{ } { }1 1� � ìíî-
æåñòâà ïîçèöèé ñòðîêè x â ìíîæåñòâî ïîçèöèé ñòðîêè y , ñîõðàíÿþùåå áóêâó è ïî-
ðÿäîê:
x yi ix
� � ( ) , ( , )x x Di j � , i j J x, ( )� , i j i jx x
�
� �( ) ( ) . (1)
Óñëîâèÿ (1) íå îïðåäåëÿþò îäíîçíà÷íî âëîæåíèå �x . Äàëåå áóäåì ñ÷èòàòü, ÷òî
âëîæåíèå �x êîíêðåòèçèðîâàíî ñëåäóþùèìè ðåêóððåíòíûìè ñîîòíîøåíèÿìè.
1. Äëÿ ïóñòîãî ñëîâà e èìååì �e �� .
2. Åñëè ïîñòðîåíî âëîæåíèå �x äëÿ ñòðîêè x x x x� 1 � | | , òî äëÿ ëþáîãî a��
âëîæåíèå �xa äëÿ ñòðîêè xà x x x� �1 1� | | îïðåäåëÿåòñÿ êàê
� �
� �
xa x
xa i
i i i x
x i y a i F
( ) ( ), | | ,
(| | ) min | , (
� �
� � � �
åñëè
{1 x )},
�
�
(2)
ãäå F x( )� — ìíîæåñòâî çàïðåùåííûõ äëÿ �xa x(| | )�1 ïîçèöèé ñòðîêè y, îïðåäå-
ëÿåìîå ðàâåíñòâîì
F J x i j i j J x y y Dx x x i j( ) ( ( )) | : ( ( )), ( , )� � �� � � � � �{ }.
Ìíîæåñòâî F x( )� , êðîìå ïîçèöèé �x J x( ( )) , ñîäåðæèò ïîçèöèè áóêâ, çàâèñÿùèõ
îò áóêâ ìíîæåñòâà �x J x( ( )) è ðàñïîëîæåííûõ â ñòðîêå y ñëåäóþùèì îáðàçîì:
åñëè i F x� ( )� , òî ëèáî i J xx�� ( ( )) , ëèáî ñóùåñòâóåò ïîçèöèÿ j J y� ( ) òàêàÿ,
÷òî i j
, j J xx�� ( ( )) è yi çàâèñèò îò y j .
Î÷åâèäíî, ÷òî åñëè äëÿ ñòðîê x è y âëîæåíèÿ �x , ïîñòðîåííîãî ïî ïðàâèëó (2),
íå ñóùåñòâóåò, òî íå ñóùåñòâóåò íèêàêîãî äðóãîãî âëîæåíèÿ, óäîâëåòâîðÿþùåãî
óñëîâèþ (1) . Eñëè èçâåñòíî ìíîæåñòâî F x( )� , òî
F F j j xxa x xa( ) ( ) | (| | )� � �� � � �{ 1 , ( , )a y Dj � �}
� � � � �F j j i y a i Fx i x( ) | min | , (� �{ { )}, ( , )a y Dj � }. (3)
Ïîñòàâèì â ñîîòâåòñòâèå âëîæåíèþ �x : J x J y( ) ( )� íàáîð öåëûõ ÷èñåë
P P Px x m x( ) ( ( ), , ( ))� � ��� � , êîòîðûé îïðåäåëèì ðåêóððåíòíî êàê
P Ps( ) ( , , )� � �0 0 0� ,
P
P a
y a k ai xa
i x i
i
( )
( ) , ,
( ( ), , ) ,max
�
�
�
�
�
� �
åñëè
pos åñëè
�
1 � i ,
�
�
i m�{ }1, ,� , (4)
ãäå ÷èñëî k P xmax ( ( ))� — íîìåð ìàêñèìàëüíîãî âõîæäåíèÿ áóêâû a â ñòðîêàõ
{� i y( ) , i m�1, ,� } â ïîçèöèè, íå ïðåâîñõîäÿùåé ñîîòâåòñòâóþùåãî Pi x( )� :
k P k y a k Px i m i i xmax , ,( ( )) max max | ( ( ), , ) ( )� � �� �� 1 � { { pos }}.
Åñëè k P yxmax ( ( )) | |� � �1 , òî íàáîð Pi xa( )� íå îïðåäåëåí. Ëåãêî âèäåòü, ÷òî
ñîãëàñíî (3) ñóùåñòâóåò âçàèìíî îäíîçíà÷íîå ñîîòâåòñòâèå ìåæäó Pi x( )� è F x( )� ,
îïðåäåëÿåìîå ôîðìóëîé
pos { } pos( , , ) ( , , : ( ( ), , ) ( )y a k F i m y a k Px i i x� �� � �� � � �1 � .
Ïîýòîìó ìîæíî ñ÷èòàòü, ÷òî íàáîð P x( )� ïðåäñòàâëÿåò ìíîæåñòâî ïîçèöèé F x( )� .
Äàëåå îïðåäåëèì àâòîìàò A t Pt t t( ) ( , , , , )� � �� � 0 . Ìíîæåñòâîì ñîñòîÿíèé àâòî-
ìàòa A t( ) ÿâëÿåòñÿ �t m i i iP P P P y r� � � �{ ( , , ) | | ( )|1 � � , P Ni � }. Ïåðåõîäû àâòîìà-
òà A t( ) ñóòü ïðàâèëà (4), ñîãëàñíî êîòîðûì âûïîëíÿåòñÿ ïåðåõîä P Px
a
xa( ) ( )� �� � . Íà-
÷àëüíîå ñîñòîÿíèå åñòü P0 0 0� ( , , )� , êàæäîå äîñòèæèìîå P t�� ÿâëÿåòñÿ ôèíàëüíûì
ñîñòîÿíèåì àâòîìàòà A t( ) . Î÷åâèäíî: P P
a
x0 � ( )� òîãäà è òîëüêî òîãäà, êîãäà [ ] [ ]x y� .
Çàìåòèì, ÷òî åñëè P P
a
� � è P P Pm� ( , , ).1 � , P P Pm� � � �( , , ).1 � , òî ñóùåñòâóåò
i m�{ }1, ,� , äëÿ êîòîðîãî P Pi i
�. Îòñþäà ñëåäóåò àöèêëè÷íîñòü ãðàôà ïåðåõîäîâ
àâòîìàòà A t( ) . Ëåãêî óâèäåòü, ÷òî � �t tP ab P ba( , ) ( , )� äëÿ êàæäîãî P t�� , îòêóäà
ñëåäóåò, ÷òî A t( ) åñòü M-àâòîìàò.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6 21
1. Äîêàæåì òåïåðü ìèíèìàëüíîñòü àâòîìàòa A t Pt t t( ) ( , , ), ,� � �� � 0 . Íåîáõî-
äèìî ïîêàçàòü, ÷òî åñëè P, P t��� è P P� � , òî àâòîìàò A PP t t t� ( , , , , )� �� � íå ýê-
âèâàëåíòåí àâòîìàòó A PP t t t� � �( , , , , )� �� � . Äëÿ êàæäîé áóêâû a�� è êàæäîãî
íàáîðà P P Pm t� �( , , )1 � � îïðåäåëèì ÷èñëî k a P i
i
i iP a ii
( , ) max | | |� �{ }� �1 � � ,
a�� , ò.å. ìàêñèìàëüíîå ÷èñëî ïîçèöèé áóêâû a â ïðåôèêñàõ ïðîåêöèé � i t( )
äëèíû Pi . Åñëè P P� � , íàéäåòñÿ áóêâà a�� òàêàÿ, ÷òî k a P k a P( , ) ( , )� � .
Ïðåäïîëîæèì k a P a P( , ) ( , )
� . Òîãäà ñòðîêà a y k a Pa| | ( , )�
äîïóñêàåòñÿ àâòîìà-
òîì AP è íå äîïóñêàåòñÿ àâòîìàòîì AP � . Ìèíèìàëüíîñòü àâòîìàòà A t( ) äîêàçàíà.
2. Î÷åâèäíî, ÷òî äëÿ ÷èñëà ñîñòîÿíèé àâòîìàòà A t( ) âåðíà îöåíêà | | ( )�t r t� .
Åñëè D �� , ò.å. m � �� | |� , è êëèêè ïîêðûòèÿ ñîäåðæàò ïî îäíîé áóêâå, òî äîñòè-
æèìî êàæäîå ñîñòîÿíèå ( , , )P Pm1 � , ãäå äëÿ � i i aa P t� �{ } | | .
3. Åñëè D — ïîëíûé ãðàô, a m� �1, òî êàæäûé òðåê t M D� ( , )� ñîäåðæèò
åäèíñòâåííóþ ñòðîêó y.  ýòîì ñëó÷àå ÷èñëî ñîñòîÿíèé ìíîæåñòâà �t , ãäå [ ]y t� ,
åñòü | | | |t y� � �1 1 è àâòîìàò A t( ) ñîâïàäàåò ñ àâòîìàòîì DASG [4].
4. Âû÷èñëåíèå êàæäîãî ïåðåõîäà èìååò âðåìåííóþ ñëîæíîñòü O m t O a t( | | ) ( | | )� ,
ïîñêîëüêó òðåáóåò ïðîñìîòðà âñåõ ïðîåêöèé � i . Ñëåäîâàòåëüíî, ïîñòðîåíèå ãðàôà
ïåðåõîäîâ A t( ) èìååò ñëîæíîñòü O m t O tm( | | | | ) ( | | | | )� �� ��1 1� � .
Óòâåðæäåíèå 1 äîêàçàíî. �
Ïðèìåð 2. Ðàññìîòðèì ìîíîèä M D( , )� , ãäå � �{ }a b c, , , D a b b c�{ }( , ), ( , ) ,
òðåê t aabcbc� [ ] . Òîãäà �1 �{ }a b, , �2 �{ }b c, — êëèêè ïîêðûòèÿ ( , )� D ,
�1 ( )t aabb� , � 2 ( )t bcbc� — ïðîåêöèè t íà êëèêè � �1 2, .
Îïðåäåëèì, âëîæåíû ëè â t òðåêè s cac1 � [ ] , s cacb2 � [ ] .
Èìååì
�b �� F b( )� �� P b( ) ( , )� � 0 0
�c �{ }( , )14 F c( ) ,� �{ }3 4 P c( ) ( , )� � 0 2 [ ]c t�
�ca �{ }( , ), ( , )14 21 F ca( ) , ,� �{ }13 4 P ca( ) ( , )� � 12 [ ]ca t�
�cac �{ }( , ), ( , ), ( , )14 21 3 6 F cac( ) , , , ,� �{ }13 4 5 6 P cac( ) ( , )� � 14 s cac t1 � �[ ]
�cacb íå îïðåäåëåíî, F cacb( )� íå îïðåäåëåíî, ñëåäîâàòåëüíî, s cacb t2 � �[ ] .
Ëåãêî óâèäåòü, ÷òî ( , ) ( , ) ( , ) ( , )0 0 0 2 12 14� � �
c a c
. �
Ïðèìåð 3. Ðàññìîòðèì ìîíîèä M D( , )� :
� �{ }a b c, , , D a b b c�{ }( , ), ( , ) . Ïîñòðîèì àâòîìàò
A t( ) äëÿ t abc� [ ] . Íà ðèñ. 1 èçîáðàæåí ãðàô ïåðåõî-
äîâ àâòîìàòà A t( ) . Â âåðøèíàõ çàïèñàíû äîñòèæè-
ìûå ñîñòîÿíèÿ èç �t äëÿ y abc� . �
3. ÇÀÄÀ×È Î ÏÎÄÒÐÅÊÀÕ È ÍÅÏÎÄÒÐÅÊÀÕ
ÄËß ÌÍÎÆÅÑÒÂÀ T M D� ( , )�
Ïóñòü çàäàíî ìíîæåñòâî òðåêîâ T t t k� �{ }1 , ,�
� M D( , )� . Ïðåäïîëîæèì e T t ti j� ��, ïðè i j� ,
i j k, , ,�{ }1 � .
Ââåäåì â ðàññìîòðåíèå ãðàô ïîäòðåêîâ äëÿ ìíî-
æåñòâà T, êîòîðûé ïîñëóæèò îñíîâîé àëãîðèòìîâ
ñðàâíåíèÿ òðåêîâ êîíå÷íîãî ìíîæåñòâà T.
Ïîñòðîèì îðèåíòèðîâàííûé ãðàô G T( ) � ( , , , )Q U q0 , ãäå Q — âåðøèíû, U —
äóãè ãðàôà G t( ) , q0 — eãî êîðåíü, — ôóíêöèÿ, ìåòÿùàÿ äóãè G T( ) .
Èñïîëüçóÿ îáîçíà÷åíèÿ, ââåäåííûå â ðàçä. 2 äëÿ àâòîìàòà A t( ) , ïîëîæèì
Q t tk
� � � � �( # ) ( # )� �
1
{ } { }� , q P P P
T
0
0 0 0� � � �( )� .
22 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6
b
b
c
c a
ca
1,2
2,2
2,1
0,2
0,0
1,0
Ðèñ. 1. Ãðàô ïåðåõîäîâ àâòîìàòà
A abc([ ])
Äàëåå, ïóñòü q q qk� ( , ),1 � , � � � � �q q q Qk( , ),1 � . Ïàðà ( , )q q U� � è åå ìåòêà
( , )q q a� � òîãäà è òîëüêî òîãäà, êîãäà äëÿ âñåõ i k�1, ,� èìååò ìåñòî
� �q a qi t ii
� ( , ) , åñëè ïåðåõîä � �q a qi t ii
� ( , ) îïðåäåëåí â àâòîìàòå A t i( ) ;
� �qi # , åñëè ýòîò ïåðåõîä íå îïðåäåëåí èëè åñëè qi � # .
Èòàê, ãðàô G T( ) ïîñòðîåí. Îí èìååò O nmk( ) âåðøèí, ãäå n ti i�max | |{ }, k —
÷èñëî òðåêîâ ìíîæåñòâà T, m — ÷èñëî êëèê â íàèìåíüøåì ïîêðûòèè êëèêàìè ãðà-
ôà çàâèñèìîñòè àëôàâèòà � . Àöèêëè÷íîñòü è ìèíèìàëüíîñòü àâòîìàòà A T( ) ñ ãðà-
ôîì ïåðåõîäîâ G T( ) î÷åâèäíà. Ñëîæíîñòü ïîñòðîåíèÿ îäíîãî ïåðåõîäà ñîñòàâëÿåò
O kmn( ) , îòêóäà ñëåäóåò ïîëèíîìèàëüíàÿ ñëîæíîñòü O km nmk( | | )� �1 ïîñòðîåíèÿ
ãðàôà G T( ) .
Ïðèìåð 4. Ïóñòü � �{ }a b c, , , D a b b c�{ }( , ), ( , ) , t abc1 � [ ] , t cba2 � [ ] . Ðàññìîò-
ðèì ïðîåêöèè �1 1( )t ab� , � 2 1( )t bc� , �1 2( )t ba� , � 2 2( )t cb� íà êëèêè
�1 �{ }a b, , �2 �{ }b c, . Ïóñòü òàêæå T t t�{ }1 2, — ìíîæåñòâî, ñîñòîÿùåå èç äâóõ
òðåêîâ. Ïîñòðîèì ãðàô ïåðåõîäîâ
àâòîìàòà G t( ) (ðèñ. 2). �
Ïîñòðîåííûé ãðàô G T( ) ìîæ-
íî èñïîëüçîâàòü äëÿ ðåøåíèÿ ðàç-
íûõ çàäà÷ ïîèñêà ïîäòðåêîâ è íå-
ïîäòðåêîâ ìíîæåñòâà T .
Ïóñòü â ãðàôå G T( ) ïóòü, íå-
ñóùèé ñòðîêó x , íà÷èíàåòñÿ
â êîðíå q0 è çàêàí÷èâàåòñÿ â âåð-
øèíå q q qk� ( , , )1 � . Îïðåäåëèì
ïîäìíîæåñòâî K q i qi( ) | #� �{ ,
i k�1, ,� }. Òîãäà [ ]x t i� äëÿ âñåõ
i K q� ( ) è [ ]x t i�� äëÿ âñåõ
i K q� ( ) . Ñëåäîâàòåëüíî, x ÿâëÿåò-
ñÿ îáùèì ïîäòðåêîì äëÿ t i ïðè
i K q� ( ) è îáùèì íåïîäòðåêîì
äëÿ âñåõ t i ïðè i K q� ( ) .
Îòñþäà âûòåêàåò ðåøåíèå ñëåäóþùèõ çàäà÷ ïî ïîñòðîåííîìó ãðàôó G T( ) .
Çàäà÷à î íàèáîëüøåì îáùåì ïîäòðåêå. Çàäàíî êîíå÷íîå ìíîæåñòâî òðåêîâ
T t t M Dk� �( , , ) ( , )1 � � . Êàæäûé òðåê t i çàäàí ñòðîêîé y ti i� . Òðåáóåòñÿ íàéòè â
M D( , )� ïîäòðåê íàèáîëüøåé äëèíû, îáùèé äëÿ âñåõ òðåêîâ ìíîæåñòâà T .
Çàäà÷à ðåøàåòñÿ ïóòåì ïîñòðîåíèÿ ãðàôà G T( ) è ïîèñêà â íåì äëèííåéøåãî ñðå-
äè ïóòåé, âåäóùèõ ê âåðøèíàì q q qk� ( , , )1 � , êîòîðûå íå ñîäåðæàò ñèìâîëîâ # .
Òàê êàê ñóùåñòâóåò ïîëèíîìèàëüíûé àëãîðèòì äëÿ ïîèñêà òàêîãî ïóòè, òî çàäà÷à î
íàèáîëüøåì îáùåì ïîäòðåêå ìîæåò áûòü ðåøåíà çà âðåìÿ O m nmk( | | )� �1 . �
Çàäà÷à î êðàò÷àéøåì îáùåì íåïîäòðåêå. Çàäàíî êîíå÷íîå ìíîæåñòâî òðå-
êîâ: T t t M Dk� �( , , ) ( , )1 � � . Êàæäûé òðåê t i çàäàí ñòðîêîé y ti i� . Òðåáóåòñÿ
íàéòè â M D( , )� êðàò÷àéøèé òðåê, íå ÿâëÿþùèéñÿ ïîäòðåêîì äëÿ âñåõ òðåêîâ ìíî-
æåñòâà T .
Çàäà÷à ðåøàåòñÿ ïóòåì ïîèñêà â ãðàôå G T( ) êðàò÷àéøåãî ñðåäè ïóòåé, âåäó-
ùèõ ê âåðøèíå q � (# , , # )� . Ñëåäîâàòåëüíî, çàäà÷à î êðàò÷àéøåì îáùåì íåïîä-
òðåêå ìîæåò áûòü ðåøåíà çà âðåìÿ O m nmk( | | )� �1 , ò.å. çà âðåìÿ ïîñòðîåíèÿ ãðàôà
G T( ) è âðåìÿ ïîèñêà â íåì íóæíîãî êðàò÷àéøåãî ïóòè.
Çàäà÷à î êðàò÷àéøåì ðàçëè÷àþùåì òðåêå. Ïóñòü çàäàíû äâà ìíîæåñòâà
òðåêîâ: U u uk�{ }1 , ,� è S s sl�{ }1 , ,� , u s M Di j, ( , )� � , i k�1, ,� , j l�1, ,� .
Îïðåäåëåíèå 4. Òðåêîì, ðàçëè÷àþùèì ìíîæåñòâà òðåêîâU è S , íàçûâàåòñÿ òàêîé
òðåê v M D� ( , )� , ÷òî ëèáî v — îáùèé ïîäòðåê äëÿ òðåêîâ ìíîæåñòâà U, íî íå ÿâëÿåòñÿ
ïîäòðåêîì äëÿ êàæäîãî òðåêà ìíîæåñòâà S , ëèáî, íàîáîðîò, v ÿâëÿåòñÿ îáùèì ïîäòðå-
êîì äëÿ òðåêîâ ìíîæåñòâà S , íî íå ÿâëÿåòñÿ ïîäòðåêîì êàæäîãî òðåêà ìíîæåñòâàU .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6 23
Ðèñ. 2. Ãðàô ïåðåõîäîâ àâòîìàòà G T( )
Ïîëîæèì T u u s s U Sk l� � �{ }1 1, , , , ,� � . Çàäà÷à íàõîæäåíèÿ êðàò÷àéøåãî
ðàçëè÷àþùåãî òðåêà ðåøàåòñÿ ïóòåì ïîèñêà ïî ãðàôó G T( ) êðàò÷àéøåãî ïóòè, âåäó-
ùåãî èç q0 â âåðøèíó q q qk l� �( , ),1 � òàêóþ, ÷òî ëèáî
q qk1 � �# , , #� , íî q qk k l� �� �1 # , , #� ,
ëèáî
q qk1 � �# , , #� , íî q qk k l� �� �1 # , , #� .
Ñëåäîâàòåëüíî, çàäà÷à î êðàò÷àéøåì ðàçëè÷àþùåì òðåêå ìîæåò áûòü ðåøåíà
çà âðåìÿ O m k l nm k l( ( )| | )( )� � �� 1 , ò.å. çà âðåìÿ ïîñòðîåíèÿ G T( ) è âðåìÿ ïîèñêà â
íåì êðàò÷àéøåãî ïóòè ê âåðøèíå îïèñàííîãî âèäà. �
Ïðèìåð 5. Íà ãðàôå G T( ) , ïîñòðîåííîì íà ðèñ. 2 (ïðèìåð 4), ìîæíî ïðîèë-
ëþñòðèðîâàòü ðåøåíèå ïåðå÷èñëåííûõ çàäà÷. Ïóñòü t abc1 � [ ] , t cba2 � [ ] . Íàèáîëü-
øèì îáùèì ïîäòðåêîì äëÿ T t t�{ }1 2, ÿâëÿåòñÿ [ ]ac . Êðàò÷àéøèå îáùèå íåïîäòðå-
êè äëÿ T ñóòü [ ]aa , [ ]bb , [ ]cc . Åñëè U t�{ }1 , S t�{ }2 , òî êðàò÷àéøèå òðåêè, ðàçëè-
÷àþùèå U è S , ñóòü [ ]ab , [ ]cb . �
4. ÇÀÄÀ×È Î ÍÀÄÒÐÅÊÀÕ È ÍÅÍÀÄÒÐÅÊÀÕ ÄËß ÌÍÎÆÅÑÒÂÀ T M D� ( , )�
Ïóñòü çàäàíî ìíîæåñòâî òðåêîâ T t t M Dk� �{ }1, , ( , )� � . Ïðåäïîëîæèì e T� ,
t ti j�� ïðè i j� , i j k, , ,�{ }1 � .
Îïðåäåëåíèå 5. Ïóñòü t t M D1 2, ( , )� � . Îáùèì íàäòðåêîì äëÿ òðåêîâ t t1 2,
áóäåì íàçûâàòü òðåê t M D� ( , )� , åñëè t t1 � , t t2 � . �
Çàäà÷à î íàèìåíüøåì îáùåì íàäòðåêå. Çàäà÷à î íàèìåíüøåì îáùåì íàäòðå-
êå çàêëþ÷àåòñÿ â íàõîæäåíèè òðåêà íàèìåíüøåé äëèíû, êîòîðûé ÿâëÿåòñÿ îáùèì
íàäòðåêîì äëÿ t t1 2, . Êàæäûé òðåê t i çàäàí ñòðîêîé y ti i� .
Îáîçíà÷èì l p p( , )1 2 äëèíó îáùåãî íàèìåíüøåãî íàäòðåêà äëÿ p t1 1�Pref ( ) è
p t2 2�Pref ( ) . Ðàññìîòðèì ìíîæåñòâî òðîåê:
�( , ) , , |p p p p a1 2 1 2� � �{ a�� , (( [ ]) ( [ ]))p p a p p a1 1 2 2� � � � �
� � � �(( ) ( [ ]))p p p p a1 1 2 2 (( [ ]) ( ))p p a p p1 1 2 2� � � � },
ãäå � �p t1 1Pref ( ) è � �p t2 2Pref ( ) .
Î÷åâèäíî, ÷òî â ìíîæåñòâå �( , )p p1 2 ñóùåñòâóåò òàêàÿ òðîéêà � �p p a1 2, , ,
÷òî l p p l p p( , ) ( , )1 2 1 2 1� � � � . Ñëåäîâàòåëüíî, ðåêóððåíòíûå ôîðìóëû äëÿ âû÷èñëå-
íèÿ l p p( , )1 2 èìåþò âèä l p p l p p p p a p p( , ) min ( , ) | , ( , ),1 2 1 2 1 2 1 21� � � � � � �{ }� ,
l e e( , ) � 0 , ãäå e — ïóñòîé òðåê.
Óòâåðæäåíèå 2. Ñóùåñòâóåò ÷àñòè÷íûé àöèêëè÷åñêèé àâòîìàò B t t( , )1 2 , ðàñïî-
çíàþùèé êîíå÷íûé ÿçûê L x t t xB t t( , ) | , [ ]
1 2 1 2� �{ }, êîòîðûé ñîäåðæèò âñå êðàò÷àé-
øèå íàäòðåêè òðåêîâ t1 è t2 . Àâòîìàò B t t( , )1 2 èìååò O n O na m( ) ( )2 2� ñîñòîÿíèé,
ãäå n t t�max | | , | |{ }1 2 . Ýòîò àâòîìàò ìîæåò áûòü ïîñòðîåí çà O m n m( | | )� 2 1� øàãîâ.
Äîêàçàòåëüñòâî. Ïîñòðîèì àâòîìàò B t t( , )1 2 � ( ( ) ( )Pref Preft t1 2� , ( , )e e ,
( , ), )t t1 2 � , ãäå ãðàô ïåðåõîäîâ îïðåäåëÿeòñÿ òàê: åñëè ( , ) ( ) ( )p p t t1 2 1 2� �Pref Pref ,
òî èç âåðøèíû ( , )� �p p1 2 ñóùåñòâóåò ïåðåõîä �( , ( , )) ( , )a p p p p� � �1 2 1 2 ïðè
� � �p p a p p1 2 1 2, , ( , )� . Î÷åâèäíî, ÷òî êàæäûé ïóòü èç âåðøèíû ( , )e e â âåðøèíó
( , )p p1 2 íåñåò ñòðîêó x òàêóþ, ÷òî p p x1 2, [ ]� , ò.å. [ ]x — îáùèé íàäòðåê òðåêîâ p1
è p2 . Êàê ïîêàçàíî â [13], | ( )| ( )Pref t O nm� . Âîñïîëüçóåìñÿ ýòèì ðåçóëüòàòîì äëÿ
îöåíêè ñëîæíîñòè ïîñòðîåíèÿ àâòîìàòà B t t( , )1 2 .
Ñëîæíîñòü ïîñòðîåíèÿ àâòîìàòà B t t( , )1 2 ñîñòàâëÿåò O m n m( | | )� 2 1� , ãäå
n t t�max | | , | |{ }1 2 , òàê êàê | ( )| | |Pref t t m
1 1� , | ( )| | |Pref t t m
2 2� , à ñëîæíîñòü ïî-
ñòðîåíèÿ îäíîãî ïåðåõîäà ñîñòàâëÿåò O mn( ) .
24 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6
Çàäà÷à î íàõîæäåíèè íàèìåíüøåãî îáùåãî íàäòðåêà ñâîäèòñÿ ê ïîñòðîåíèþ
àâòîìàòà B t t( , )1 2 è íàõîæäåíèþ â åãî ãðàôå ïåðåõîäîâ êðàò÷àéøåãî ïóòè, âåäóùå-
ãî ê âåðøèíå ( , )t t1 2 . �
Çàäà÷à ëåãêî îáîáùàåòñÿ íà êîíå÷íîå ìíîæåñòâî òðåêîâ T t t k�{ }1 , ,� .
Ïðèìåð 6. Ðàññìîòðèì ìîíîèä M D( , )� , ãäå � �{ }a b c, , , D a b b c�{ }( , ), ( , ) , è
òðåêè t abc1 � [ ] , t cba2 � [ ] . Ãðàô ïåðåõîäîâ àâòîìàòà B t t( , )1 2 èçîáðàæåí íà ðèñ. 3.
 êàæäîé âåðøèíå ãðàôà óêàçàíû ñîîòâåòñòâóþùèå ïðåôèêñû òðåêîâ t1 è t2 . Êðàò-
÷àéøèì íàäòðåêîì äëÿ t1 è t2 ÿâëÿåòñÿ òðåê t acbac� [ ] . �
Çàäà÷à î íàèáîëüøåì îáùåì íåíàä-
òðåêå. Çàäà÷à î íàèáîëüøåì îáùåì íåíàä-
òðåêå äëÿ T t t M Dk� �{ }1 , , ( , )� � çàêëþ÷à-
åòñÿ â ïîñòðîåíèè òðåêà t íàèáîëüøåé äëèíû
òàêîãî, ÷òî t ti �� äëÿ âñåõ i k�1, ,� .
 [18] ïîêàçàíî, ÷òî çàäà÷à î íàõîæäå-
íèè íàèáîëüøåé îáùåé íåíàäïîñëåäîâàòåëü-
íîñòè äëÿ ìíîæåñòâà ñòðîê L â àëôàâèòå A
èìååò ðåøåíèå òîãäà è òîëüêî òîãäà, êîãäà
äëÿ êàæäîé áóêâû a A� ñòðîêà a La� � ïðè
íåêîòîðîì � a �1. Ëåãêî óâèäåòü, ÷òî ýòî
óñëîâèå ÿâëÿåòñÿ íåîáõîäèìûì è äîñòàòî÷-
íûì è äëÿ ñóùåñòâîâàíèÿ íàèáîëüøåãî îá-
ùåãî íåíàäòðåêà.
Óòâåðæäåíèå 3. Ïóñòü T t t k� �{ }1 , ,�
� M D( , )� è äëÿ êàæäîé áóêâû a�� ñóùå-
ñòâóåò ÷èñëî � a �1òàêîå, ÷òî òðåê [ ]a Ta� � .
Òîãäà çàäà÷à î ïîñòðîåíèè íàèáîëüøåãî îá-
ùåãî íåíàäòðåêà ñâîäèòñÿ ê çàäà÷å íàõîæäå-
íèÿ äëèííåéøåãî ïóòè â àöèêëè÷åñêîì ãðàôå G T( ) ñ ÷èñëîì âåðøèí, íå ïðåâîñõî-
äÿùèì | |� � , ãäå � �� � �� �a a( )1 . Ïîñòðîåíèå ãðàôà G T( ) òðåáóåò O mk( | | )�� øàãîâ.
Äîêàçàòåëüñòâî. Îïðåäåëèì ãðàô G T V E( ) ( , , )� ñëåäóþùèì îáðàçîì.
1. Âåðøèíû ãðàôà G T( ) ñóòü íàáîðû P p pk� ( , , )1 � , ãäå p ti i�Pref ( ) ,
i k�1, ,� .
2. Âåðøèíà P V0 0 0� �( , , )� .
3. Åñëè âåðøèíà P p p Vk� �( , , )1 � , òî ïåðåõîä P P p p
a
k� � � � �( , , )1 � îïðåäå-
ëåí òîãäà è òîëüêî òîãäà, êîãäà äëÿ âñåõ i k�1, ,� âûïîëíåíî ðàâåíñòâî
p
p p a t
p a t p ai
i i i
i i i
� �
�
� �
, [ ] ( ) ,
[ ], [ ] (
åñëè Pref
åñëè Pref t i ).
�
�
Ïðè ýòîì P V�� , äóãà ( , )P P E� � è ïîìå÷åíà áóêâîé a .
Àöèêëè÷íîñòü ãðàôà G T( ) î÷åâèäíà.
Ðàññìîòðèì ïðîèçâîëüíûé ïóòü P P P
a a a
l
l
0 1
1 2
� � �... . Òðåê [ ]a al1 � íå ñîäåð-
æèò áîëåå � a�1 ýêçåìïëÿðîâ áóêâû a äëÿ êàæäîé áóêâû a�� . Òðåê [ ]a al1 � ÿâëÿ-
åòñÿ îáùèì íåíàäòðåêîì äëÿ ìíîæåñòâà T , ïîñêîëüêó ñîäåðæèò ëèøü ñîáñòâåííûå
ïðåôèêñû òðåêîâ T . Ãðàô G T( ) ñîäåðæèò âñå ïóòè, íåñóùèå òðåêè ñ óêàçàííûìè
ñâîéñòâàìè. Î÷åâèäíî, ÷òî äëèííåéøèé ïóòü â G T( ) íåñåò íàèáîëüøèé îáùèé íå-
íàäòðåê ìíîæåñòâà T .
Ïðèìåð 7. Ðàññìîòðèì ìîíîèä M D( , )� , ãäå � �{ }a b c, , , D a b b c�{ }( , ), ( , ) , è
ìíîæåñòâî òðåêîâ T abc cba aa bb cc�{ }[ ], [ ], [ ], [ ], [ ] .
Äëèííåéøèìè íåíàäòðåêàìè äëÿ T ÿâëÿþòñÿ òðåêè [ ], [ ]cab bca .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6 25
ca
c a bb
bbc
b bc a
ca
abc, cba
abc, cb ab, cba
ab, cb a, cbaabc, e
a, cab, e e, cb
e, ca, e
e, c
Ðèñ. 3. Ãðàô ïåðåõîäîâ àâòîìàòà B t t( , )1 2
ÇÀÊËÞ×ÅÍÈÅ
Ïîñòðîåííûé ìèíèìàëüíûé äåòåðìèíèðîâàííûé àöèêëè÷åñêèé àâòîìàò A t( ) äëÿ
òðåêà t M D� ( , )� äîïóñêàåò ÿçûê ïîäòðåêîâ òðåêà t . Àâòîìàò èñïîëüçîâàí äëÿ ðå-
øåíèÿ çàäà÷ ïîèñêà îáùåãî íàèáîëüøåãî ïîäòðåêà, îáùåãî êðàò÷àéøåãî íåïîä-
òðåêà äëÿ òðåêîâ êîíå÷íîãî ìíîæåñòâà T è äëÿ çàäà÷è ïîèñêà êðàò÷àéøåãî ïîä-
òðåêà, ðàçëè÷àþùåãî ìíîæåñòâà. Ýòè çàäà÷è ìîãóò áûòü ðåøåíû çà ïîëèíîìèàëü-
íîå âðåìÿ ïðè îãðàíè÷åííîì | |T . Ðåøàþòñÿ òàêæå çàäà÷è î ïîñòðîåíèè
íàèìåíüøåãî îáùåãî íàäòðåêà è íàèáîëüøåãî îáùåãî íåíàäòðåêà äëÿ òðåêîâ ìíî-
æåñòâà T . Ïîëó÷åíû àëãîðèòìû ïîëèíîìèàëüíîé ñëîæíîñòè ïðè êîíå÷íîì | |T .
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. D i k e r t V . , R o z e n b e r g G . The book of traces // Handbook of Formal Languages — 3. — Beyond
Words. — N.Y.: Springer-Verlag, 1997. — 285 p.
2. L e t i c h e v s k y A . A . On the equivalence of automata over semigroup // Theoretic Cybernetics. —
1970 — 6. — P. 3–71 (in Russian).
3. M a z u r k i e w i c z A . Concurrent program schemes and their interpretations // DAIMI Rep. PB. —
Aarhus: Aarhus University. — 1977. — 78. — P. 76–92.
4. B a e z a - Y a t e s R . A . Searching sequences // Theoretical Computer Science. — 1991. — 78, N 2. —
P. 363–376.
5. F r a s e r C . B . Subsequences and supersequences of strings. Ph.D. Thesis // University of Glasgow, UK,
1955. — P. 1–121.
6. C r o c h e m o r e M . , H a n c a r t C . , L e c r o q T . Algorithms on strings // Cambridge University Press,
2007. — 392 p.
7. C r o c h e m o r e M . , R y t t e r W . Jewels of stringology // World Scientific Publiching Co. Rtc. Ltd., 2002.
— 309 p.
8. C r o c h e m o r e M . , M e l c h a r B . , T r o n i c e k Z . Directed acyclic subsequence graph: overview // J. of
Discrete Algorithms. — 2003. — 1, N 3. — P. 255–280.
9. C r o c h e m o r e M . , G i a m b r u n o L . On-line construction of a small automaton for a finite set of
words // The Prague Stringology Conference, 2009. — P. 39–51.
10. C r o c h e m o r e M . , T r o n i c e k Z . Directed aciclic subsequence graph for multiple texts // Technical Re-
port. — IGM-99. — Institut Gaspard-Monge, 1999. — Ð. 1–93.
11. M e l c h a r B . , P o l c a r T . The longest common subsequence problem. A finite automata approach //
LNCS. — 2003. — 2759. — P. 93–106.
12. T r o n i c e k Z . Problems related to subsequences and supersequences // Strong Processing and Information
Retreaval Symposium, 1999. — P. 199–205.
13. A v e l l o n e A . , G o l d w u r m M . Analysis of algorithms for the recognition of rational ànd context-free
trace languages // Theoretical Informatics and Applications. — 1998. — 32, N 2. — P. 17–65.
14. B o a s s o n L . , C e g i e l s k i P . , G u e s s a r i a n I . , M a t i y a s e v i c h Y . Window-accumulated
subsequence problem is linear // Annals of Pure and Applied Logic. — 2001. — 113, N 7. — P. 36–45.
15. G u e s s a r i a n I . , C e g i e l s k i P . Tree inclusions in windows and slices // CSIT Conference, 2000. —
P. 47–50.
16. C e g i e l s k i P . , G u e s s a r i a n I . , M a t i y a s e v i c h Y . Multiple serial episode matching // CSIT Con-
ference, 2005. — P. 26–38.
17. J i X . , B a i l e y J . , D o n g G . Mining minimal distinguishing subsequences pattern with gap con-
straints // ICDM, 2005. — P. 194–201.
18. R u b i n o v A . R . , T i m k o v s k y V . G . String noninclusion optimization problems // SIAM J. Discrete
Math. — 1998. — 11, N 3. — P. 456–467.
19. M i d d e n d o r f M . The shortest nonsubsequence problem is NP-complete // Theoret. Comput. Sci. —
1993. — 108. — P. 365–369.
20. S h a h b a z y a n K . V . , S h o u k o u r i a n Y u . H . Inclusion problems in trace monoids // CSIT Confe-
rence, 2009. — 78–92.
21. S h a h b a z y a n K . V . , S h o u k o u r i a n Y u . H . On some matching problems in trace monoids // Patrick
Cegielski, ed. / Studies in Weak Arithmetics, Lecture Notes, 196 — CSLI Public. — Stanford, 2010. —
213 p.
22. C h e u n g W . , E v a n s W . , M o s e s J . Predicated instructons for code compaction // Proceedings of the
7th International Workshop on Software and Compilers for Embedded Systems (SCOPES), LNCS. —
2003. — 2826. — P. 17–32.
Ïîñòóïèëà 14.05.2010
26 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 6
|
| id | nasplib_isofts_kiev_ua-123456789-45643 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T15:57:43Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Шахбазян, К.В. Шукурян, Ю.Г. 2013-06-17T06:11:42Z 2013-06-17T06:11:42Z 2010 Об оптимизационных проблемах включения треков / К.В. Шахбазян, Ю.Г. Шукурян // Кибернетика и системный анализ. — 2010. — № 6. — С. 17–26. — Бібліогр.: 22 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/45643 519.6 Показано поліноміальну складність оптимізаційних проблем для кінцевої множини треків Т: 1) знайти трек найбільшої довжини, вкладений в кожен трек з множини Т; 2) знайти найкоротший трек, не вкладений в кожен трек з множини Т; 3) знайти найкоротший трек, в який вкладено кожен трек з множини Т; 4) знайти трек найбільшої довжини, в який не вкладено кожен трек з множини T. Four optimization problems for a finit set of traces are considered: (i) find the longest trace that is included in each trace from a given finite set T of traces, (ii) find the shortest trace that is not included in every trace from a given finite set T of traces, (iii) find the shortest trace that includes every trace from a given finite set T of traces, (iv) find the longest trace that does not include each trace from a given finite set T of traces. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Об оптимизационных проблемах включения треков Про оптимізаційні проблеми включення треків On trace inclusion optimization problems Article published earlier |
| spellingShingle | Об оптимизационных проблемах включения треков Шахбазян, К.В. Шукурян, Ю.Г. Кибернетика |
| title | Об оптимизационных проблемах включения треков |
| title_alt | Про оптимізаційні проблеми включення треків On trace inclusion optimization problems |
| title_full | Об оптимизационных проблемах включения треков |
| title_fullStr | Об оптимизационных проблемах включения треков |
| title_full_unstemmed | Об оптимизационных проблемах включения треков |
| title_short | Об оптимизационных проблемах включения треков |
| title_sort | об оптимизационных проблемах включения треков |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/45643 |
| work_keys_str_mv | AT šahbazânkv oboptimizacionnyhproblemahvklûčeniâtrekov AT šukurânûg oboptimizacionnyhproblemahvklûčeniâtrekov AT šahbazânkv prooptimízacíiníproblemivklûčennâtrekív AT šukurânûg prooptimízacíiníproblemivklûčennâtrekív AT šahbazânkv ontraceinclusionoptimizationproblems AT šukurânûg ontraceinclusionoptimizationproblems |