Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. I. Реконструкция без запретов
Рассмотрена задача реконструкции слов по заданному множеству подслов в гипотезе, что оно порождено смещением окна фиксированной длины по неизвестному слову со сдвигом 1. Предложено решение для задачи реконструкции слов без запрещенного подслова, основанное на поиске эйлеровых путей или циклов в муль...
Gespeichert in:
| Datum: | 2014 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2014
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/115773 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. I. Реконструкция без запретов / Ю.Г. Сметанин, М.В. Ульянов // Кибернетика и системный анализ. — 2014. — Т. 50, № 1. — С. 168-177. — Бібліогр.: 25 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-115773 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1157732017-04-13T03:02:44Z Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. I. Реконструкция без запретов Сметанин, Ю.Г. Ульянов, М.В. Новые средства кибернетики, информатики, вычислительной техники и системного анализа Рассмотрена задача реконструкции слов по заданному множеству подслов в гипотезе, что оно порождено смещением окна фиксированной длины по неизвестному слову со сдвигом 1. Предложено решение для задачи реконструкции слов без запрещенного подслова, основанное на поиске эйлеровых путей или циклов в мультиорграфе де Брейна путем символического умножения матриц смежности с применением специальных операций умножения и сложения имен дуг. Рассмотрены особенности задачи и метод ее решения, позволяющий найти как число реконструкций, так и реконструируемые слова. Розглянуто задачу реконструкцiї слiв за заданою множиною пiдслiв у гіпотезі, що ця множина породжена зміщенням вікна фіксованої довжини уздовж невідомого слова зі змiщенням 1. Запропоновано розв’язання для задачі реконструкції слів без забороненого підслова, яке ґрунтується на пошуку ейлерових шляхiв чи циклiв у мультиорграфi де Брейна шляхом символічного множення матриць cуміжності із застосуванням спеціальних операцій множення та додавання імен дуг. Розглянуто особливості задачi та метод її розв’язання, що дозволяє знайти як число реконструкцій, так і реконструйовані слова. The problem of reconstruction of words given a set of its subwords is considered. It is assumed that the set is generated by unit shifts of a fixed window along the unknown word. For the problem without restrictions on the unknown word, a method of reconstruction is proposed based on the search of Euler paths or Euler cycles in the de Bruijn multidigraph. The search is based on symbolic multiplication of the adjacency matrices with specific operations of multiplication and addition of edge names. The method gives both the number of reconstructions and reconstructed words. 2014 Article Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. I. Реконструкция без запретов / Ю.Г. Сметанин, М.В. Ульянов // Кибернетика и системный анализ. — 2014. — Т. 50, № 1. — С. 168-177. — Бібліогр.: 25 назв. — рос. http://dspace.nbuv.gov.ua/handle/123456789/115773 519.16,519.17 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Новые средства кибернетики, информатики, вычислительной техники и системного анализа Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| spellingShingle |
Новые средства кибернетики, информатики, вычислительной техники и системного анализа Новые средства кибернетики, информатики, вычислительной техники и системного анализа Сметанин, Ю.Г. Ульянов, М.В. Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. I. Реконструкция без запретов Кибернетика и системный анализ |
| description |
Рассмотрена задача реконструкции слов по заданному множеству подслов в гипотезе, что оно порождено смещением окна фиксированной длины по неизвестному слову со сдвигом 1. Предложено решение для задачи реконструкции слов без запрещенного подслова, основанное на поиске эйлеровых путей или циклов в мультиорграфе де Брейна путем символического умножения матриц смежности с применением специальных операций умножения и сложения имен дуг. Рассмотрены особенности задачи и метод ее решения, позволяющий найти как число реконструкций, так и реконструируемые слова. |
| format |
Article |
| author |
Сметанин, Ю.Г. Ульянов, М.В. |
| author_facet |
Сметанин, Ю.Г. Ульянов, М.В. |
| author_sort |
Сметанин, Ю.Г. |
| title |
Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. I. Реконструкция без запретов |
| title_short |
Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. I. Реконструкция без запретов |
| title_full |
Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. I. Реконструкция без запретов |
| title_fullStr |
Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. I. Реконструкция без запретов |
| title_full_unstemmed |
Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. I. Реконструкция без запретов |
| title_sort |
реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. i. реконструкция без запретов |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2014 |
| topic_facet |
Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/115773 |
| citation_txt |
Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. I. Реконструкция без запретов / Ю.Г. Сметанин, М.В. Ульянов // Кибернетика и системный анализ. — 2014. — Т. 50, № 1. — С. 168-177. — Бібліогр.: 25 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT smetaninûg rekonstrukciâslovpokonečnomumulʹtimnožestvupodslovvgipotezesdviga1irekonstrukciâbezzapretov AT ulʹânovmv rekonstrukciâslovpokonečnomumulʹtimnožestvupodslovvgipotezesdviga1irekonstrukciâbezzapretov |
| first_indexed |
2025-07-08T09:20:52Z |
| last_indexed |
2025-07-08T09:20:52Z |
| _version_ |
1837069976130813952 |
| fulltext |
ÓÄÊ 519.16, 519.17
Þ.Ã. ÑÌÅÒÀÍÈÍ, Ì.Â. ÓËÜßÍÎÂ
ÐÅÊÎÍÑÒÐÓÊÖÈß ÑËΠÏÎ ÊÎÍÅ×ÍÎÌÓ ÌÓËÜÒÈÌÍÎÆÅÑÒÂÓ
ÏÎÄÑËÎÂ Â ÃÈÏÎÒÅÇÅ ÑÄÂÈÃÀ 1.
I. ÐÅÊÎÍÑÒÐÓÊÖÈß ÁÅÇ ÇÀÏÐÅÒÎÂ1
Àííîòàöèÿ. Ðàññìîòðåíà çàäà÷à ðåêîíñòðóêöèè ñëîâ ïî çàäàííîìó ìíîæåñòâó ïîäñëîâ
â ãèïîòåçå, ÷òî îíî ïîðîæäåíî ñìåùåíèåì îêíà ôèêñèðîâàííîé äëèíû ïî íåèçâåñòíîìó
ñëîâó ñî ñäâèãîì 1. Ïðåäëîæåíî ðåøåíèå äëÿ çàäà÷è ðåêîíñòðóêöèè ñëîâ áåç çàïðåùåííî-
ãî ïîäñëîâà, îñíîâàííîå íà ïîèñêå ýéëåðîâûõ ïóòåé èëè öèêëîâ â ìóëüòèîðãðàôå äå Áðåé-
íà ïóòåì ñèìâîëè÷åñêîãî óìíîæåíèÿ ìàòðèö ñìåæíîñòè ñ ïðèìåíåíèåì ñïåöèàëüíûõ îïå-
ðàöèé óìíîæåíèÿ è ñëîæåíèÿ èìåí äóã. Ðàññìîòðåíû îñîáåííîñòè çàäà÷è è ìåòîä åå ðå-
øåíèÿ, ïîçâîëÿþùèé íàéòè êàê ÷èñëî ðåêîíñòðóêöèé, òàê è ðåêîíñòðóèðóåìûå ñëîâà.
Êëþ÷åâûå ñëîâà: ðåêîíñòðóêöèÿ ñëîâ, ãðàôû, ýéëåðîâû ïóòè, ïåðå÷èñëåíèå ïóòåé, ðåêîí-
ñòðóêöèÿ áåç çàïðåòîâ, ãðàôû äå Áðåéíà, ñèìâîëè÷åñêîå óìíîæåíèå ìàòðèö.
ÂÂÅÄÅÍÈÅ. ÎÁËÀÑÒÈ ÏÐÈÌÅÍÅÍÈß
 íàñòîÿùåé ðàáîòå ðàññìàòðèâàåòñÿ çàäà÷à, êîòîðàÿ ïî ïðîáëåìàòèêå îòíîñèòñÿ
ê êîìáèíàòîðèêå ñëîâ — íîâîìó ñîâðåìåííîìó ðàçäåëó äèñêðåòíîé ìàòåìàòèêè.
Êîìáèíàòîðèêà ñëîâ — òåðìèí, ïîÿâèâøèéñÿ ïðèáëèçèòåëüíî òðèäöàòü ëåò
íàçàä äëÿ îáúåäèíåíèÿ íàïðàâëåíèé èññëåäîâàíèé, ñâÿçàííûõ îáùèìè ïîäõîäà-
ìè, íî ðàññìàòðèâàåìûõ â ðàçëè÷íûõ îáëàñòÿõ ìàòåìàòèêè — îò òåîðèè ÷èñåë äî
òåîðåòè÷åñêîé èíôîðìàòèêè. Ãëàâíîé öåëüþ èññëåäîâàíèé â ýòîé îáëàñòè ÿâëÿ-
åòñÿ èçó÷åíèå ñëîâ êàê ñàìîñòîÿòåëüíûõ îáúåêòîâ ñ òî÷êè çðåíèÿ èõ âíóòðåííåé
ñòðóêòóðû. Êîìáèíàòîðèêà ñëîâ îõâàòûâàåò êîìáèíàòîðíûå ìåòîäû àíàëèçà
ìíîæåñòâ ñëîâ, èñïîëüçóåìûå â òåîðèè ôîðìàëüíûõ ÿçûêîâ è àâòîìàòîâ [1], òåî-
ðèè ãðóïï [2], òåîðèè õàîñà [3], ôðàêòàëüíîì àíàëèçå [4], ñèìâîëè÷åñêîé äèíà-
ìèêå [5] è àíàëèçå âðåìåííûõ ðÿäîâ, áèîèíôîðìàòèêå [6] (â êîòîðîé êîìáèíà-
òîðíûå ìåòîäû ïðèìåíÿë åùå Ã. Ãàìîâ [7]), ëèíãâèñòèêå è äð. Ïðîãðåññ â äàííîé
îáëàñòè îïèñûâàåòñÿ â ðåãóëÿðíî ïîÿâëÿþùèõñÿ êíèãàõ ãðóïïû ìàòåìàòèêîâ,
ïóáëèêóåìûõ ïîä ïñåâäîíèìîì M. Lothaire [8–10].
Îáúåêòàìè ðàññìîòðåíèÿ â êîìáèíàòîðèêå ñëîâ ÿâëÿþòñÿ ñëîâà íàä ïðîèç-
âîëüíûìè àëôàâèòàìè, à ïðåäìåòîì èññëåäîâàíèé — èçó÷åíèå êîìáèíàòîðíûõ
ñâîéñòâ ðàçëè÷íûõ ìíîæåñòâ ñëîâ, êàê êîíå÷íûõ, òàê è áåñêîíå÷íûõ.  ðåàëü-
íûõ ïðèêëàäíûõ çàäà÷àõ èíôîðìàöèÿ î ñëîâàõ ÷àñòî îêàçûâàåòñÿ íåïîëíîé; íà-
ïðèìåð, òàêàÿ ñèòóàöèÿ íåèçáåæíà â àíàëèçå áåñêîíå÷íûõ âðåìåííûõ ðÿäîâ, èç-
ìåðÿåìûõ íà ïðîòÿæåíèè êîíå÷íûõ èíòåðâàëîâ âðåìåíè.
 íàñòîÿùåé ñòàòüå ðàññìàòðèâàåòñÿ îäíà èç ïîñòàíîâîê çàäà÷è ðåêîíñòðóê-
öèè ñëîâ ïî èõ èçâåñòíûì ïîñëåäîâàòåëüíûì ôðàãìåíòàì — ïîäñëîâàì. Çàäà÷è
ðåêîíñòðóêöèè ñëîâ òåñíî ñâÿçàíû, íàïðèìåð, ñ çàäà÷àìè êîäèðîâàíèÿ [11]
è ðàñïîçíàâàíèåì îáðàçîâ [12], à òàêæå âîçíèêàþò â ðÿäå äðóãèõ îáëàñòåé. Êîäè-
ðîâàíèå èíôîðìàöèè è ðàñïîçíàâàíèå îáðàçîâ — â íåêîòîðîì ñìûñëå ïðåäåëüíûå
ñëó÷àè çàäà÷è ðåêîíñòðóêöèè ñëîâ: çàäà÷ó ïîñòðîåíèÿ êîäîâ ìîæíî ñ÷èòàòü çàäà-
÷åé îïðåäåëåíèÿ ìíîæåñòâ ñëîâ, âîññòàíàâëèâàåìûõ ïî åäèíñòâåííîìó èñêàæåí-
íîìó îáðàçöó ïðè èñêàæåíèÿõ çàäàííîãî âèäà; çàäà÷è ðåêîíñòðóêöèè ñ íåôîð-
ìàëüíûì îïèñàíèåì êëàññîâ ñëîâ îòíîñÿòñÿ ê êëàññó çàäà÷ ðàñïîçíàâàíèÿ.
 çàäà÷àõ èññëåäîâàíèÿ âðåìåííûõ ðÿäîâ [13] êîäèðîâàíèå çíà÷åíèé íàáëþ-
äàåìîé âåëè÷èíû ìîæåò îñóùåñòâëÿòüñÿ â íåêîòîðîì àëôàâèòå, íàïðèìåð
( , , , , , )A B C D E F , ñèìâîëàìè êîòîðîãî ìîãóò áûòü èìåíîâàíû ïîëóñåãìåíòû çíà-
÷åíèé íàáëþäàåìîé âåëè÷èíû â ïîðÿäêå èõ âîçðàñòàíèÿ: A — èìÿ ïîëóñåãìåíòà
168 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1
1
Ðàáîòà âûïîëíåíà ïðè ïîääåðæêå ÐÔÔÈ, ãðàíò ¹ 13-07-00516.
© Þ.Ã. Ñìåòàíèí, Ì.Â. Óëüÿíîâ, 2014
íàèìåíüøèõ çíà÷åíèé, F — íàèáîëüøèõ. Åñëè íàáëþäåíèÿ âåäóòñÿ â äèñêðåòíîì
âðåìåíè, òî îïèñàíèå çíà÷åíèé âðåìåííîãî ðÿäà ïî èìåíàì ïîëóñåãìåíòîâ åñòü
ñëîâî íàä àëôàâèòîì èìåí.  ñëó÷àå, åñëè íàáëþäàåìûé ïðîöåññ õàðàêòåðèçóåò-
ñÿ ðåçêèìè âûáðîñàìè çíà÷åíèé íàáëþäàåìîé âåëè÷èíû (äî óðîâíÿ F) îòíîñè-
òåëüíî áàçàëüíîãî óðîâíÿ ( , )A B çà îäèí äèñêðåò âðåìåíè, òàê æå, êàê è ðåçêèìè
ñïàäàìè (îò F äî B), òî ïîëó÷àåìûå êîäîâûå ñëîâà âðåìåííîãî ðÿäà íå áóäóò ñî-
äåðæàòü ïîäñëîâ CDE è EDC. Åñëè ïðè ýòîì èñõîäíûå äàííûå — ðàçðîçíåííûå
ôðàãìåíòû íàáëþäåíèé, òî çàäà÷à ðåêîíñòðóêöèè ñëîâà áåç çàïðåùåííûõ ïîäñëîâ
ÿâëÿåòñÿ çàäà÷åé âîññòàíîâëåíèÿ âñåãî îïèñàíèÿ âðåìåííîãî ðÿäà â ïðåäïîëîæå-
íèè îá îñîáåííîñòÿõ åãî ïîâåäåíèÿ.
 áèîèíôîðìàòèêå ñ êîìáèíàòîðèêîé ñëîâ íàèáîëåå òåñíî ñâÿçàíû çàäà÷è
àíàëèçà ïîñëåäîâàòåëüíîñòåé ÄÍÊ [6, 14] è ðàñïîçíàâàíèÿ âòîðè÷íîé ñòðóêòóðû
áåëêîâ [15]. Çàäà÷à ðàñïîçíàâàíèÿ âòîðè÷íîé ñòðóêòóðû áåëêà çàêëþ÷àåòñÿ
â ñëåäóþùåì. Áåëîê ìîæíî ïðåäñòàâëÿòü êàê îäíîìåðíóþ ïîñëåäîâàòåëüíîñòü
àìèíîêèñëîò èëè êàê îäíîìåðíóþ ïîñëåäîâàòåëüíîñòü õàðàêòåðíûõ ëîêàëüíûõ
êîíôèãóðàöèé. Â íàñòîÿùåå âðåìÿ îáùåïðèíÿòûì ÿâëÿåòñÿ äîïóùåíèå, ÷òî ïåð-
âè÷íàÿ ñòðóêòóðà îäíîçíà÷íî îïðåäåëÿåò âòîðè÷íóþ. Ïðè ýòîì çàäà÷à îïðåäåëå-
íèÿ âòîðè÷íîé ñòðóêòóðû (ñòðóêòóðû ëîêàëüíûõ êîíôèãóðàöèé) ôîðìóëèðóåòñÿ
êàê çàäà÷à ïðåîáðàçîâàíèÿ ñëîâ â àëôàâèòå èìåí àìèíîêèñëîò â ñëîâà íàä
àëôàâèòîì ëîêàëüíûõ êîíôèãóðàöèé ñ ïîìîùüþ êîäîâ ñêîëüçÿùåãî áëîêà.
Ïðè îïèñàíèè áèçíåñ-ïðîöåññîâ àïïàðàòîì òåîðèè ãðàôîâ [16] ìîäåëü (ãðàô
áèçíåñ-ïðîöåññà) ìîæíî ïðåäñòàâèòü ñëåäóþùèì îáðàçîì: ñîñòîÿíèÿ ïðîöåññà êî-
äèðóþòñÿ èìåíîâàííûìè âåðøèíàìè, à ïåðåõîäû ñîñòîÿíèé — ðåáðàìè, îòîæäå-
ñòâëåííûìè ñ ýòàïàìè áèçíåñ-ïðîöåññà. Òîãäà çàïèñü êîíêðåòíîé ðåàëèçàöèè áèç-
íåñ-ïðîöåññà åñòü íåêîòîðîå ñëîâî íàä àëôàâèòîì èìåí âåðøèí, îòðàæàþùåå ïîðÿ-
äîê ïåðåõîäà ñîñòîÿíèé. Åñëè ïðîöåññ ôèçè÷åñêè ðàñïðåäåëåí ìåæäó ðàçëè÷íûìè
îðãàíèçàöèÿìè, òî, ñêîðåå âñåãî, ïîëó÷èì èíôîðìàöèþ î åãî ïîëíîì ïðîõîæäåíèè
â âèäå íàáîðà ïîäñëîâ. Ïðè ýòîì çàïðåùåííûå ïîäñëîâà ìîãóò áûòü èíòåðïðåòèðî-
âàíû êàê íàðóøåíèÿ ìîäåëè — ðåãëàìåíòà áèçíåñ-ïðîöåññà. Âîçíèêàþùàÿ çàäà÷à
ðåêîíñòðóêöèè áåç çàïðåùåííûõ ïîäñëîâ ñîäåðæàòåëüíî îçíà÷àåò âîçìîæíîñòü ïî-
ëíîé ðåêîíñòðóêöèè âñåãî ïðîöåññà, ñîîòâåòñòâóþùåãî òåîðåòè÷åñêîé ìîäåëè.
Òàêèì îáðàçîì, ïðåäñòàâëÿåò èíòåðåñ ïîäðîáíîå èçó÷åíèå ðàçëè÷íûõ âàðè-
àíòîâ çàäà÷è ðåêîíñòðóêöèè ñëîâ ïî íåêîòîðîìó ìíîæåñòâó ïîäñëîâ ìåíüøåé
äëèíû, èíòåðïðåòèðóåìûõ êàê ìíîæåñòâî ïîñëåäîâàòåëüíûõ ôðàãìåíòîâ íåèç-
âåñòíîãî ñëîâà. Ïðè ýòîì âûäåëÿåòñÿ ñëó÷àé, êîãäà ðåêîíñòðóèðóåìîå ñëîâî íå
ñîäåðæèò çàðàíåå çàäàííîãî çàïðåùåííîãî ïîäñëîâà. Îäèí èç âîçìîæíûõ âàðè-
àíòîâ ðåøåíèÿ ýòîé çàäà÷è íà îñíîâå ïîäñëîâ ôèêñèðîâàííîé äëèíû â ãèïîòåçå
ñäâèãà 1 è ñîñòàâëÿåò ïðåäìåò èññëåäîâàíèÿ íàñòîÿùåé ðàáîòû; ïåðâàÿ ÷àñòü ïî-
ñâÿùåíà ðåêîíñòðóêöèè áåç çàïðåùåííîãî ñëîâà; ðåêîíñòðóêöèÿ ïðè íàëè÷èè
çàïðåòà áóäåò ðàññìîòðåíà âî âòîðîé ÷àñòè.
ÒÅÐÌÈÍÎËÎÃÈß È ÎÁÎÇÍÀ×ÅÍÈß
 ñòàòüå èñïîëüçóþòñÿ òåðìèíîëîãèÿ è îáîçíà÷åíèÿ êàê îáùåïðèíÿòûå â òåî-
ðèè ôîðìàëüíûõ ãðàììàòèê è ÿçûêîâ [1] è ñèìâîëè÷åñêîé äèíàìèêå [5], òàê
è ñïåöèàëüíûå àâòîðñêèå îáîçíà÷åíèÿ, ñâÿçàííûå ñî ñïåöèôèêîé èçó÷àåìîé
çàäà÷è.  òåîðèè ÿçûêîâ èñòîðè÷åñêè òåðìèíû «ñëîâî» è «ñòðîêà» ñ÷èòàþòñÿ
ðàâíîïîëîæåííûìè. Íàïðèìåð, èçâåñòíàÿ çàäà÷à ñèìâîëüíîãî ïîèñêà ôîðìó-
ëèðóåòñÿ êàê «Ïîèñê ïîäñòðîêè â ñòðîêå» [14]. Â ïîñòàíîâêàõ çàäà÷ ðåêîíñò-
ðóêöèè [12] áîëåå óïîòðåáèì òåðìèí «ñëîâî», êîòîðûé èñïîëüçóåòñÿ äàëåå.
Òàêæå, íå òåðÿÿ îáùíîñòè, áóäåì ðàññìàòðèâàòü ñëîâà, ïîðîæäåííûå áèíàð-
íûì àëôàâèòîì. Ââåäåì ñëåäóþùèå îáîçíà÷åíèÿ:
� � � { }0 1, — áèíàðíûé àëôàâèò, s — ïðîèçâîëüíûé ñèìâîë àëôàâèòà;
� �0 �� — ïóñòîå ìíîæåñòâî;
� �k — k-ÿ äåêàðòîâà ñòåïåíü ìíîæåñòâà � (k-ýëåìåíòíûé êîðòåæ);
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1 169
� � �* �
�
�
k
k
0
� — òðàíçèòèâíîå çàìûêàíèå � (ìíîæåñòâî âñåõ âîçìîæíûõ
êîðòåæåé);
� c — ïðîèçâîëüíûé êîðòåæ (äëÿ êîðòåæà c îïðåäåëèì äëèíó — ÷èñëî ñî-
ñòàâëÿþùèõ åãî ýëåìåíòîâ — êàê ìîùíîñòü ìóëüòèìíîæåñòâà, îáðàçîâàííîãî èç
êîðòåæà: | |c n� , íàïðèìåð | ( , , , ) |0 1 1 0 4� ; äëèíà ïóñòîãî êîðòåæà ðàâíà íóëþ);
� R c i( , ) — ôóíêöèÿ âûáîðà ýëåìåíòà êîðòåæà, îïðåäåëåííàÿ ïðè 1� �i c| |
è âîçâðàùàþùàÿ ýëåìåíò ñ íîìåðîì i èç êîðòåæà c ; åñëè i c� | |, òî R c i( , ) ��;
åñëè ýëåìåíòû êîðòåæà ïðèíàäëåæàò �, òî ôóíêöèÿ âîçâðàùàåò ñèìâîë àëôàâèòà,
íàïðèìåð R (( , , , ), )1 0 0 1 3 0� ;
� w — ñëîâî (íàä àëôàâèòîì) — ïîñëåäîâàòåëüíîñòü ñèìâîëîâ àëôàâèòà,
ïðè ýòîì ñîáñòâåííî ñèìâîëû àëôàâèòà — ñëîâà ïî îïðåäåëåíèþ;
� � — ïóñòîå (íå ñîäåðæàùåå ñèìâîëîâ) ñëîâî;
� — îïåðàöèÿ êîíêàòåíàöèè (ñêëåéêè) ñëîâ: w w w w1 2 1 2 � ; ðåçóëüòàò
îïåðàöèè — ñëîâî, ïðåäñòàâëÿþùåå ñîáîé ïîñëåäîâàòåëüíîñòü ñèìâîëîâ ñëîâà
w1, çà êîòîðîé ñëåäóåò ïîñëåäîâàòåëüíîñòü ñèìâîëîâ ñëîâà w2 , íàïðèìåð
01 11 0110 � ;
� D D c w( ) : ( )
� , ãäå c��* — êîðòåæ, w — ñëîâî; îïåðàòîð D( )
— äåñòðóê-
òîð êîðòåæà — îïåðàòîð ñîçäàíèÿ ñëîâà èç êîðòåæà ïóòåì êîíêàòåíàöèè ñèìâî-
ëîâ àëôàâèòà �,
D c w R c R c R c c( ) ( , ) ( , ) ( , | | )� � 1 2 � ,
íàïðèìåð D(( , , , ))1 1 0 1 1101� ;
� L L C W( ) : ( )
� , ãäå C � �* — ìíîæåñòâî êîðòåæåé, W — ìíîæåñòâî ñëîâ;
L( )
— îïåðàòîð ñîçäàíèÿ ìíîæåñòâà ñëîâ, ñîñòîÿùèõ èç ñèìâîëîâ àëôàâèòà � ,
äåéñòâóþùèé íà ìíîæåñòâî êîðòåæåé ïîñðåäñòâîì ïîñëåäîâàòåëüíîãî ïðèìåíå-
íèÿ îïåðàòîðà D( )
,
L C W w c Cw D c( ) | ( )� �
� �{ },
íàïðèìåð L( ( , , , ), ( , , ) ) ,{ } { }1 1 0 1 0 1 1 1101 011� ;
� w s s s Lk
k� �1 2 � ( )� — ïðîèçâîëüíîå ñëîâî èç ìíîæåñòâà L k( )� íàä àë-
ôàâèòîì � ;
� | | | ( ) |w k L w� � �1 — äëèíà ñëîâà, îïðåäåëÿåìàÿ êàê ÷èñëî ýëåìåíòîâ â êîð-
òåæå, ïîðîæäàþùåì ýòî ñëîâî;
� L L w w kk
k� � �( ) { | | | }� — ìíîæåñòâî âñåõ ñëîâ äëèíû k íàä àëôàâèòîì �;
� L L* *( )� � — ïîëíûé ÿçûê íàä àëôàâèòîì � — ìíîæåñòâî âñåõ âîçìîæ-
íûõ ñëîâ;
� L L� * — ïðîèçâîëüíûé íåïîëíûé ÿçûê íàä àëôàâèòîì � .
Ïóñòü w s s s Ln
n� �1 2 � ( )� , òîãäà ïðè k n� èìååì: u s s si i ik
�
1 2
� , 1 1� �i
� � � �i i nk2 � , — ôðàãìåíò ñëîâà w äëèíû k, � � s s si i ik1 2
� , 1 1� i , i i2 1 1� ,� ,
i i nk k� ��1 1 , — ïîäñëîâî ñëîâà w äëèíû k; Q w i l( , , ) — îïåðàòîð âûäåëåíèÿ
ïîäñëîâà äëèíû l â ñëîâå w, íà÷èíàÿ ñ ñèìâîëà â ïîçèöèè i. Ïóñòü | |w n� , òîãäà
îïåðàòîð îïðåäåëåí ïðè i l n � �1 :
Q s s s i l u s s sn i i i l( , , )1 2 1 1� �� � � .
Äëÿ ñëåäóþùèõ òðåõ îïåðàòîðîâ ïîëàãàåì, ÷òî | |w k� � 2:
� P w Q w k s s s Lk
k( ) ( , , ) ( )� � � ��
�1 1 1 2 1
1
� � — ïîëíûé ïðåôèêñ äëèíû
| |w �1 ñëîâà w;
� S w Q w k s s Lk
k( ) ( , , ) ( )� � � � �2 1 2
1
� � — ïîëíûé ñóôôèêñ äëèíû | |w �1
ñëîâà w;
170 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1
� Sn w Q w k s Lk( ) ( , , ) ( )� � �1 1� — ñóôôèêñ ñëîâà w äëèíû 1 — ñèìâîë àëôà-
âèòà;
� V L mk( , ) — îïåðàòîð âûáîðêè: åãî ðåçóëüòàò — ïðîèçâîëüíîå ïîäìíîæåñ-
òâî (âîçìîæíî, ñ ïîâòîðåíèÿìè) èç m ñëîâ ìíîæåñòâà Lk :
V L m i m s s s Lk i i
i i
k
i
k( , ) | , ; ( ) ( ) ( )� � � �{ }� �1
1 2
� ;
çàìåòèì, ÷òî â ñèëó îñîáåííîñòåé çàäà÷è äîïóñêàåì ðàññìîòðåíèå V L mk( , )
êàê ìóëüòèìíîæåñòâà ñ êðàòíîñòÿìè ýëåìåíòîâ, â ýòîì ñëó÷àå m — ñóììà
êðàòíîñòåé ýëåìåíòîâ;
� SH w k1( , ) — îïåðàòîð ñäâèãà 1; îïðåäåëåííûé ïðè | |w k� îïåðàòîð ïî-
ðîæäàåò ìíîæåñòâî ïîäñëîâ äëèíû k ìîùíîñòè | |w k� 1, âûïîëíÿÿ ñäâèã íà 1
îêíà äëèíû k ïî ñëîâó w, íà÷èíàÿ ñ êðàéíåé ëåâîé ïîçèöèè ñëîâà w:
SH w k u j w k u Q w j kj j1 1 1( , ) | , | | ; ( , , )� � � �{ };
äëÿ îïåðàòîðà SH w k1( , ) äîïóñêàåì ñîçäàíèå ìóëüòèìíîæåñòâà, íàïðèìåð:
SH1 1101010 4 1101 1010 0101 1010 1101 1010 2( , ) { , , , } { , ( )� � , }0101 .
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È ÐÅÊÎÍÑÒÐÓÊÖÈÈ
Ñ÷èòàåì çàäàííûìè: äëèíó ïîäñëîâà k, ÷èñëî ïîäñëîâ m è èñõîäíîå ìóëüòè-
ìíîæåñòâî ñëîâ V L mk( , ) íàä àëôàâèòîì � � { }0 1, , ðàññìàòðèâàåìîå êàê áàçèñ
ðåêîíñòðóêöèè. Ïðèíèìàåìàÿ ãèïîòåçà ñäâèãà 1 ñîñòîèò â òîì, ÷òî V L mk( , )
ðàññìàòðèâàåòñÿ êàê ìóëüòèìíîæåñòâî ïîäñëîâ ñäâèãà 1 îòíîñèòåëüíî íåêîòî-
ðîãî íåèçâåñòíîãî ñëîâà w.  ðàìêàõ äàííîé çàäà÷è ðåêîíñòðóêöèè èññëåäóåòñÿ
ïîñòàíîâêà, â êîòîðîé íà ðåêîíñòðóèðóåìîå ñëîâî íå íàëîæåíî äîïîëíèòåëü-
íûõ îãðàíè÷åíèé (çàïðåòîâ).
Ïîñòàíîâêà çàäà÷è ðåêîíñòðóêöèè áåç çàïðåòîâ. Ñîäåðæàòåëüíî. Âîç-
ìîæíî ëè â óñëîâèÿõ ãèïîòåçû ñäâèãà 1 îòíîñèòåëüíî ìóëüòèìíîæåñòâàV L mk( , )
âûïîëíèòü ðåêîíñòðóêöèþ ñëîâà w â ïðèíöèïå, è åñëè ýòà çàäà÷à èìååò ðåøåíèå,
òî ÿâëÿåòñÿ ëè òàêàÿ ðåêîíñòðóêöèÿ åäèíñòâåííîé?
Ôîðìàëüíî. Ââåäåì â ðàññìîòðåíèå ìíîæåñòâî
W w w m k V L m SH w kk� � � �{ }| | | , ( , ) ( , )1 1 ,
ïðè ýòîì ðàâåíñòâî ïîíèìàåòñÿ êàê ðàâåíñòâî ìóëüòèìíîæåñòâ (ðàâíû êàê
ýëåìåíòû, òàê è èõ êðàòíîñòè). Òîãäà, åñëè:
� | |W � 0 — ðåøåíèÿ íåò, ðåêîíñòðóêöèÿ íåâîçìîæíà è ìíîæåñòâî V L mk( , )
íå ÿâëÿåòñÿ ðåêîíñòðóèðóþùèì ìóëüòèìíîæåñòâîì;
� | |W �1 — ðåøåíèå åñòü è åäèíñòâåííî (ðåêîíñòðóêöèÿ âîçìîæíà è îäíî-
çíà÷íà);
� | |W � 2 — ñóùåñòâóåò íåñêîëüêî ðåøåíèé (ðåêîíñòðóêöèÿ âîçìîæíà
è ìíîãîçíà÷íà).
 ïîñëåäíåì ñëó÷àå ïðåäñòàâëÿåò èíòåðåñ íàõîæäåíèå òî÷íîãî ÷èñëà ðåøå-
íèé, ò.å. çíà÷åíèÿ M W� | | , òàê æå, êàê è ñàìèõ ðåøåíèé çàäà÷è — ñëîâ, ñîñòàâ-
ëÿþùèõ ìíîæåñòâî W.
ÈÑÒÎÐÈß ÂÎÏÐÎÑÀ È ÐÅÇÓËÜÒÀÒÛ
Ñðåäè çàäà÷ ðåêîíñòðóêöèè ñëîâ ïî ÷àñòè÷íîé èíôîðìàöèè íàèáîëüøåå âíè-
ìàíèå èññëåäîâàòåëåé ïðèâëåêëà çàäà÷à, êîãäà èìåþùàÿñÿ èíôîðìàöèÿ ïðåä-
ñòàâëÿåò ñîáîé èëè íàáîð ôðàãìåíòîâ íåèçâåñòíîãî ñëîâà, èëè íàáîð ïîäñëîâ
èçâåñòíîé äëèíû k, ïîñòðîåííûõ â ñîîòâåòñòâèè ñ îïðåäåëåííûìè ïðàâèëàìè;
ïðè îòñóòñòâèè èíôîðìàöèè î ïàðàõ «ïðàâèëî, ôðàãìåíò». Íèæå ïðèâîäÿòñÿ
èçâåñòíûå â íàñòîÿùåå âðåìÿ ðåçóëüòàòû äëÿ ðàçíûõ âàðèàíòîâ ïîñòàíîâêè
äàííîé çàäà÷è.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1 171
Ñëó÷àé 1. Äëÿ íåèçâåñòíîãî ñëîâà èçâåñòíîé äëèíû n èçâåñòíî ìóëüòèìíî-
æåñòâî âñåõ åãî ôðàãìåíòîâ äëèíû k.
Âïåðâûå ýòà çàäà÷à áûëà ñôîðìóëèðîâàíà â [17], çàòåì ôîðìàëèçîâàíà
â [18], ãäå áûëà íàéäåíà âåðõíÿÿ îöåíêà: ïðè k n� / 2 âîññòàíîâëåíèå íåèçâåñòíî-
ãî ñëîâà âîçìîæíî, è ýòà ðåêîíñòðóêöèÿ îäíîçíà÷íà. Äëÿ íèæíåé ãðàíèöû ðå-
çóëüòàò [19], ïîëó÷åííûé îäíèì èç àâòîðîâ ñòàòüè, ñîñòîèò â òîì, ÷òî ïðè
k n� log 2 èìåþòñÿ ñëîâà, íåðàçëè÷èìûå ïî ìóëüòèìíîæåñòâó âñåõ ôðàãìåíòîâ
äëèíû k. Çàòåì çàäà÷à î ðåêîíñòðóêöèè ïî ìóëüòèìíîæåñòâó ôðàãìåíòîâ, ïîëó-
÷åííûõ ñ ïîìîùüþ ïðîèçâîëüíîãî çàäàííîãî íàáîðà ïðàâèë, áûëà ñâåäåíà ê ðåøå-
íèþ ñèñòåìû äèîôàíòîâûõ óðàâíåíèé îïðåäåëåííîãî âèäà [20, 21]. Íà îñíîâàíèè
ýòîãî ðåçóëüòàòà óòî÷íåíà íèæíÿÿ îöåíêà: äëÿ îäíîçíà÷íîñòè ðåêîíñòðóêöèè íå-
îáõîäèìî (íî íåäîñòàòî÷íî) óñëîâèå
k c n c� � log , log ( )2 2 1 5 .
Ñëåäóþùèé øàã áûë ñäåëàí â ðàáîòå [22], ãäå âåðõíÿÿ ãðàíèöà ïîíèçèëàñü äî
�( )n .
Ñëó÷àé 2. Äëÿ íåèçâåñòíîãî ñëîâà èçâåñòíîé äëèíû n èçâåñòíî ìíîæåñòâî
âñåõ åãî ôðàãìåíòîâ äëèíû k.
 òàêîì ñëó÷àå èçâåñòíûå âåðõíÿÿ è íèæíÿÿ ãðàíèöû ñîâïàäàþò [23]: äëÿ
îäíîçíà÷íîé ðåêîíñòðóêöèè ïðîèçâîëüíîãî ñëîâà íåîáõîäèìî è äîñòàòî÷íî âû-
ïîëíåíèÿ óñëîâèÿ � �k n� / 2 1. Ðåêîíñòðóêöèÿ îñóùåñòâëÿåòñÿ çà k N| | îïåðà-
öèé, ãäå N — ìîùíîñòü ìíîæåñòâà ôðàãìåíòîâ.
Äëÿ çàäà÷è âîññòàíîâëåíèÿ ïðîèçâîëüíîãî ñëîâà ïî ìóëüòèìíîæåñòâó ïîä-
ñëîâ óäàëîñü íàéòè ñëåäóþùèé îáùèé ðåçóëüòàò. Åñëè ïîñòðîèòü îðãðàô
äå Áðåéíà [24], âåðøèíû êîòîðîãî ïîìå÷åíû ïîäñëîâàìè èç ìóëüòèìíîæåñòâà,
à ðåáðà ñîîòâåòñòâóþò âåðøèíàì, ïîëó÷åííûì îäíà èç äðóãîé ñäâèãîì íà 1, òî
ðåøåíèÿ çàäà÷è ðåêîíñòðóêöèè ñîîòâåòñòâóþò ãàìèëüòîíîâûì ïóòÿì â ãðàôå.
Î÷åâèäíûé íåäîñòàòîê ýòîãî ïîäõîäà ñâÿçàí ñ òåì, ÷òî îí ñâîäèò èñõîäíóþ çàäà-
÷ó î ðåêîíñòðóêöèè ê NP-òðóäíîé çàäà÷å î ãàìèëüòîíîâîì ïóòè â ãðàôå. Òàêèì
îáðàçîì, çàäà÷à î ðåêîíñòðóêöèè ïî ïîäñëîâàì â îáùåé ïîñòàíîâêå çà ïîëèíîìè-
àëüíîå âðåìÿ îñòàåòñÿ îòêðûòîé.
ÐÅÊÎÍÑÒÐÓÊÖÈß ÑËÎÂ ÁÅÇ ÇÀÏÐÅÒÀ Â ÃÈÏÎÒÅÇÅ ÑÄÂÈÃÀ 1
 îñíîâå ïðåäëàãàåìîãî ðåøåíèÿ çàäà÷è ðåêîíñòðóêöèè â ãèïîòåçå ñäâèãà 1
ëåæèò ïîñòðîåíèå ñïåöèàëüíîãî ìóëüòèîðãðàôà äå Áðåéíà G D H� ( , ) [24], ãäå
D — ìíîæåñòâî âåðøèí, à H — ìíîæåñòâî äóã. Ïðåäëàãàåìàÿ ðàçìåòêà âåð-
øèí è äóã G ïîçâîëÿåò ñâåñòè çàäà÷ó ðåêîíñòðóêöèè áåç çàïðåòîâ ê çàäà÷å ïî-
èñêà âñåõ ýéëåðîâûõ ïóòåé (öèêëîâ), ñóùåñòâåííî ìåíåå òðóäîåìêîé, ÷åì ïî-
èñê ãàìèëüòîíîâà ïóòè â ãðàôå.
Ìóëüòèîðãðàô G D H� ( , ) ñòðîèòñÿ ïî ìóëüòèìíîæåñòâó V L mk( , ) ñëåäóþ-
ùèì îáðàçîì.
Ïîñòðîåíèå âåðøèí. Îáîçíà÷èì � i i m, ,�1 , ýëåìåíòû V L mk( , ) — ñëîâà
äëèíû k, èíòåðïðåòèðóåìûå êàê ïîäñëîâà ñäâèãà 1 ïî íåèçâåñòíîìó ñëîâó w.
Îáðàçóåì èç ïîëíûõ ïðåôèêñîâ P i( )� è ïîëíûõ ñóôôèêñîâ S i( )� âñåõ ñëîâ � i
îáúåäèíåííîå ìíîæåñòâî áåç ïîâòîðåíèé:
T P S t i T
i
m
i
i
m
i i� � �
� �1 1
1� ��( ) ( ) | , | |� � { };
î÷åâèäíî, ÷òî 1 2� �| |T m.
Áóäåì ñ÷èòàòü, ÷òî ìíîæåñòâî ñëîâ T ïîðîæäàåò ìíîæåñòâî èìåí âåðøèí. Ââå-
äåì â ðàññìîòðåíèå ìíîæåñòâî íîìåðîâ âåðøèí I i i T� �{ }| , | |1 è ïîñòàâèì âî âçà-
èìíî îäíîçíà÷íîå ñîîòâåòñòâèå êàæäîìó ýëåìåíòó ìíîæåñòâà I ýëåìåíò (ïîäñëîâî)
172 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1
èç ìíîæåñòâà T , îáðàçîâàâ òåì ñàìûì ìíîæåñòâî óïîðÿäî÷åííûõ ïàð. Ïîëó÷åííîå
ìíîæåñòâî D I T� � ÿâëÿåòñÿ ìíîæåñòâîì âåðøèí ìóëüòèîðãðàôà äå Áðåéíà:
D d i t i Ti i� � �{ }( , ) | , | |1 .
Ïîñòðîåíèå äóã. Äëÿ ïîñòðîåíèÿ ìíîæåñòâà äóã ââåäåì â ðàññìîòðåíèå
îáû÷íîå (áåç ïîâòîðåíèé) ìíîæåñòâî Vp, ïîñòðîåííîå ïî ìóëüòèìíîæåñòâó
V L mk( , ). Ïóñòü | |Vp n� , î÷åâèäíî, ÷òî n m� , òîãäà
Vp p i ni� �{ }� , ,1 .
Ââåäÿ îáîçíà÷åíèå �pi
ri( )
äëÿ ñëîâà �pi êðàòíîñòè ri â V L mk( , ), ïîëó÷èì ïðåä-
ñòàâëåíèå
V L m p i n r mk i
r
i
i
n
i( , ) , , ,
( )� � �
�
�{ }� 1
1
. (1)
Ýëåìåíòû ìíîæåñòâà äóã ïðåäñòàâèì â âèäå óïîðÿäî÷åííûõ ïÿòåðîê, ñîñòîÿ-
ùèõ èç íà÷àëüíîé âåðøèíû, êîíå÷íîé âåðøèíû, ñèìâîëè÷åñêîãî èìåíè äóãè,
êðàòíîñòè è çíà÷åíèÿ:
h d d e r pi j l i i i� ( , , , , )� .
Òîãäà îáîáùåííûå äóãè hi ìóëüòèîðãðàôà äå Áðåéíà ñòðîÿòñÿ ñ ïîìîùüþ ñëå-
äóþùåé ïðîöåäóðû.
Äëÿ âñåõ ñëîâ �p i ni
ri( )
, ,�1 , èç V L mk( , ), çàïèñàííûõ â ïðåäñòàâëåíèè (1),
âûïîëíèòü òàêèå îïåðàöèè:
1) îïðåäåëèòü ïðåôèêñ P ( )
è ñóôôèêñ S ( )
äëÿ ñëîâà �pi ;
2) íàéòè âåðøèíû ãðàôà äå Áðåéíà d dj l, : � �
j l R d Pj, : ( , ) ( )2 , R d Sl( , ) ( )2 �
,
èìåíà êîòîðûõ ñîâïàäàþò ñ ïðåôèêñîì è ñóôôèêñîì ñëîâà �pi ; ñóùåñòâîâàíèå
òàêèõ âåðøèí ãàðàíòèðîâàíî ïî ïîñòðîåíèþ;
3) ïîñòàâèòü â ñîîòâåòñòâèå ñëîâó �pi
ri( )
äóãó hi ñ íà÷àëüíîé âåðøèíîé d j ,
êîíå÷íîé âåðøèíîé dl , ñèìâîëè÷åñêèì èìåíåì ei , êðàòíîñòüþ ri è çíà÷åíèåì
ñëîâà �pi :
� �p h d d e r pi
r
i j l i i i
i( )
( , , , , )� � . (2)
Çàìåòèì, ÷òî åñëè P S d j( ) ( )
�
� , òî äóãà ( , )d dj j — ïåòëÿ; îòìåòèì òàêæå,
÷òî, ïîñêîëüêó V L mk( , ) — ìóëüòèìíîæåñòâî, ôîðìàëüíî G D E� ( , ) — ìóëüòè-
îðãðàô.  öåëÿõ äàëüíåéøåé îáðàáîòêè ãðàôà áóäåì ñ÷èòàòü, ÷òî îò âåðøèíû d j
ê âåðøèíå dl èäåò äóãà hi , ïîìå÷åííàÿ èìåíåì e R hi i� ( , )3 , ñ êðàòíîñòüþ ri . Òà-
êèì îáðàçîì, ìóëüòèîðãðàô G ñîäåðæèò n îáîáùåííûõ äóã, èìåþùèõ ñîâîêóïíî
îáùóþ êðàòíîñòü m.
Íà îñíîâå ïîñòðîåííîãî ìóëüòèîðãðàôà G D E� ( , ) ðåøåíèå çàäà÷è ñóùåñò-
âîâàíèÿ ðåêîíñòðóêöèè îïðåäåëÿåòñÿ ñëåäóþùåé ëåììîé.
Ëåììà 1 (î ñóùåñòâîâàíèè). Åñëè ìóëüòèîðãðàô G íå ýéëåðîâ, òî | |W � 0, çàäà-
÷à íå èìååò ðåøåíèÿ è ìíîæåñòâî V L mk( , ) íå ÿâëÿåòñÿ ðåêîíñòðóèðóþùèì ìóëü-
òèìíîæåñòâîì. Âñå âîçìîæíûå ðåøåíèÿ çàäà÷è ðåêîíñòðóêöèè, äàþùèå | |W � 1, ñî-
îòâåòñòâóþò ýéëåðîâûì ïóòÿì (ýéëåðîâûì öèêëàì) â G ñ ó÷åòîì êðàòíîñòè äóã.
Äîêàçàòåëüñòâî. Ïî ñóòè, äîêàçàòåëüñòâî î÷åâèäíî: ýéëåðîâ ïóòü èëè ýéëå-
ðîâ öèêë â G âêëþ÷àåò âñå äóãè ñ ñèìâîëè÷åñêèìè èìåíàìè e i ni , ,�1 , ñ ó÷åòîì
èõ êðàòíîñòåé. Â ñèëó (1) è ïðîöåäóðû ïîñòðîåíèÿ îáîáùåííûõ äóã (2) ýòîò ïóòü
(öèêë) ïðîõîäèò ïî âñåì ñëîâàì � i èç ìóëüòèìíîæåñòâà V L mk( , ), ïðè÷åì ïî
êàæäîìó ñëîâó ïî îäíîìó ðàçó â ñèëó îïðåäåëåíèÿ ýéëåðîâà ïóòè èëè öèêëà.
Ñîãëàñíî ïðèíöèïó ïîñòðîåíèÿ ìíîæåñòâà âåðøèí ýòîò ïóòü (öèêë) ïðîõîäèò ïî
ïîäñëîâàì íåêîòîðîãî ñëîâà ñî ñìåùåíèåì 1. Òàêèì îáðàçîì, èìååì
� �w V L m SH w kk: ( , ) ( , )1 .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1 173
Åñëè ýéëåðîâà ïóòè (öèêëà) â G íåò, ÷òî ìîæíî ýëåìåíòàðíî ïðîâåðèòü [25],
òî | |W � 0. Åñëè â G ñóùåñòâóåò ýéëåðîâ ïóòü è îí åäèíñòâåííûé, òî | |W �1.
 ñëó÷àå ýéëåðîâà öèêëà ðåêîíñòðóêöèþ ìîæíî íà÷àòü, âûáðàâ ëþáóþ âåðøè-
íó öèêëà â êà÷åñòâå íà÷àëüíîé. Ïîýòîìó åñëè åñòü íåñêîëüêî ïóòåé èëè õîòÿ
áû îäèí öèêë, òî âîçìîæíî | |W �1, ïîñêîëüêó íå îáÿçàòåëüíî âñå ðàçëè÷íûå
ïóòè èëè ïóòè, ïîñòðîåííûå, íà÷èíàÿ ñ ðàçëè÷íûõ âåðøèí öèêëà, ïðèâîäÿò
ê ðàçëè÷íûì ðåêîíñòðóèðóåìûì ñëîâàì. Ëåììà äîêàçàíà.
 ñèëó ëåììû 1 êîíñòðóêòèâíûå ðåøåíèÿ äëÿ çàäà÷è ðåêîíñòðóêöèè áåç
çàïðåòîâ ïîëó÷àþò ýéëåðîâûìè ïóòÿìè èëè öèêëàìè â G. Çàìåòèì, ÷òî äóãà hi è
åå ñèìâîëè÷åñêîå èìÿ ei èìåþò îäèíàêîâûé íîìåð i.  ñèëó îïðåäåëåíèÿ hi
(ôîðìóëà (2)) ââåäåì äîïîëíèòåëüíî ôóíêöèþ, âîçâðàùàþùóþ ñëîâî �pi èç êîð-
òåæà hi ïî ñèìâîëè÷åñêîìó èìåíè äóãè ei :
u e pi i( ) � � .
Òîãäà ðåøåíèå çàäà÷è ðåêîíñòðóêöèè ïîëó÷àåì ñ èñïîëüçîâàíèåì ñëåäóþùåé
ëåììû.
Ëåììà 2 (î ðåêîíñòðóêöèè). Ïóñòü ýéëåðîâ ïóòü èëè öèêë â ìóëüòèîðãðàôå
äå Áðåéíà çàäàí êîðòåæåì îáõîäà èìåí äóã Ew e e e�
( , , , )( ) ( ) ( )� � �� , ãäå �( )
—
ïåðåñòàíîâêà èíäåêñîâ èìåí äóã ñ ó÷åòîì êðàòíîñòåé, | |Ew m� . Òîãäà ðåêîí-
ñòðóèðóåìîå â ãèïîòåçå ñäâèãà 1 ñëîâî w ïðåäñòàâëÿåò ñîáîé êîíêàòåíàöèþ:
w u R Ew Sn u R Ew Sn u R Ew m� ( ( , )) ( ( ( , ))) ( ( ( , )))1 2 � .
Äîêàçàòåëüñòâî. Ðåêîíñòðóêöèÿ êîððåêòíà ïî ïîñòðîåíèþ ìóëüòèîðãðàôà
äå Áðåéíà è ïðèíÿòîé ãèïîòåçå ñäâèãà 1. Ñëîâî w íà÷èíàåòñÿ ñ ïîäñëîâà, ñîäåðæà-
ùåãîñÿ â ïåðâîé äóãå ýéëåðîâà ïóòè (öèêëà). Â ñèëó îïðåäåëåíèÿ ôóíêöèé R è u
ýòà ïîäñòðîêà åñòü u R Ew( ( , ))1 . Ê ïîäñëîâó äîáàâëÿþòñÿ ñóôôèêñû äëèíû 1 îò ïîä-
ñëîâ, ïðåäñòàâëåííûõ äóãàìè ýéëåðîâà ïóòè (öèêëà) â ïîðÿäêå èõ îáõîäà, íî ýòè
ñóôôèêñû îïðåäåëÿþòñÿ ÷åðåç Sn u R Ew i( ( ( , ))) â ñèëó îïðåäåëåíèÿ ôóíêöèè Sn.
 ñëó÷àå, åñëè ðåáðà ei , i n�1, , ñ ó÷åòîì êðàòíîñòåé îáðàçóþò ýéëåðîâ öèêë,
ó ðåêîíñòðóèðóåìîãî ñëîâà w ñîâïàäàþò ïðåôèêñ è ñóôôèêñ äëèíû k �1. Òîãäà
ðåøåíèÿìè ðåêîíñòðóêöèè ÿâëÿþòñÿ âñå ïóòè, ïîëó÷åííûå öèêëè÷åñêèìè ïåðå-
ñòàíîâêàìè äóã ýéëåðîâà öèêëà. Ëåììà äîêàçàíà.
Ïðèìåð. Ïóñòü èñõîäíûå äàííûå äëÿ ðåêîíñòðóêöèè òàêîâû: äëèíà ñëîâà
k � 2, ÷èñëî ñëîâ m � 4, V L( , ) , , ,2 4 00 01 10 11� { }.
Ïîñòðîèì ìóëüòèîðãðàô G. Âåðøèíû G: ïðåôèêñû è ñóôôèêñû èñõîäíûõ
ïîäñëîâ îáðàçóþò ìíîæåñòâî T � { }0 1, ; òàêèì îáðàçîì, ìóëüòèîðãðàô G èìååò
äâå âåðøèíû, D d d� � �{ }1 21 0 2 1( , ), ( , ) . Äóãè G: âî ìíîæåñòâå V L( , )2 4 íåò ïî-
âòîðÿþùèõñÿ ýëåìåíòîâ, ïîýòîìó ìíîæåñòâî Vp ñîâïàäàåò ñ V L mk( , ) , | |Vp � 4 ,
è G — îðãðàô.  ñîîòâåòñòâèè ñ (2) ïîëó÷àåì ìíîæåñòâî ðåáåð:
h d d e1 1 1 1 1 00� ( , , , , ), h d d e2 1 2 2 1 01� ( , , , , ),
h d d e3 2 1 3 1 10� ( , , , , ) , h d d e4 2 2 4 1 11� ( , , , , ) .
Òàêèì îáðàçîì, G — îðãðàô äå Áðåé-
íà ñ äâóìÿ âåðøèíàìè, äâóìÿ äóãàìè
è äâóìÿ ïåòëÿìè. Îðãðàô ïðèâåäåí íà
ðèñ. 1, ãäå äëÿ äóã ïîêàçàíû òîëüêî
ñèìâîëè÷åñêèå èìåíà è çíà÷åíèÿ �pi .
 ñîîòâåòñòâèè ñ ëåììîé î ðåêîí-
ñòðóêöèè äëÿ ðåøåíèÿ çàäà÷è ðåêîí-
ñòðóêöèè áåç çàïðåòîâ íåîáõîäèìî óêà-
çàòü ñïîñîá ïîèñêà è ïåðå÷èñëåíèÿ âñåõ
ýéëåðîâûõ ïóòåé (öèêëîâ) â ìóëüòèîð-
ãðàôå äå Áðåéíà.
174 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1
e1, 00 d1
d2
e2, 01
e3, 10
e4, 11
Ðèñ. 1. Îðãðàô äå Áðåéíà äëÿ ìíîæåñòâà ïîä-
ñëîâ V L( , ) , , ,2 4 00 01 10 11� { }
ÏÎÈÑÊ È ÏÅÐÅ×ÈÑËÅÍÈÅ ÂÑÅÕ ÝÉËÅÐÎÂÛÕ ÏÓÒÅÉ
Äëÿ çàäà÷è ïîèñêà âñåõ ýéëåðîâûõ ïóòåé èñïîëüçóåì èäåþ âîçâåäåíèÿ â ñòåïåíü
ìàòðèöû ñìåæíîñòè ãðàôà íà îñíîâå ñèìâîëè÷åñêîãî óìíîæåíèÿ èìåí äóã [25].
Ñ÷èòàåì äàëåå, ÷òî ýéëåðîâ öèêë, ïðè ôèêñàöèè íà÷àëüíîé âåðøèíû îáõîäà
öèêëà, ÿâëÿåòñÿ ýéëåðîâûì ïóòåì.
 ñîîòâåòñòâèè ñ [25] ðàññìîòðèì ìàòðèöó ñìåæíîñòè ãðàôà G — êâàäðàò-
íóþ ìàòðèöó A ðàçìåðà | |D è ïðîöåäóðó åå ïîñòðîåíèÿ.
Èíèöèàëèçàöèÿ: a i j Dij ��
�, , | |1 .
Äëÿ âñåõ äóã h i ni , ,�1 , èç ìíîæåñòâà H âûïîëíèòü ñëåäóþùèå îïåðàöèè:
1) îïðåäåëèòü íà÷àëüíóþ è êîíå÷íóþ âåðøèíû äóãè — d R hj i� ( , )1 ,
d R hl i� ( , )2 ;
2) ïðèñâîèòü ýëåìåíòó a jl ìàòðèöû A çíà÷åíèå â âèäå êîðòåæà äëèíû 1,
ýëåìåíòîì êîòîðîãî ÿâëÿåòñÿ ñèìâîëè÷åñêîå èìÿ äóãè hi — ( ) ( ( , ))e R hi i� 3 .
Íà îñíîâå òåîðåìû [25, ñ. 108] äëÿ îïðåäåëåíèÿ ìàðøðóòîâ, ñîñòîÿùèõ èç m
äóã, íåîáõîäèìî âîçâåñòè ìàòðèöó A â ñòåïåíü m è ïðîàíàëèçèðîâàòü
ïîëó÷åííûå ìàðøðóòû.
Îñîáåííîñòè ïîèñêà ýéëåðîâûõ ïóòåé â ìóëüòèîðãðàôå çàêëþ÷àþòñÿ â òîì,
÷òî â ìàðøðóòå äîëæíû ïðèñóòñòâîâàòü âñå äóãè â òî÷íîì êîëè÷åñòâå èõ êðàò-
íîñòåé, òîãäà êîðòåæ Ew e e em( )
( ) ( ) ( )( , , , )�
� � �� — ýéëåðîâ ïóòü.  ñâÿçè
ñ ýòèì ââîäèì ñïåöèàëüíóþ îïåðàöèþ óìíîæåíèÿ èìåí äóã, èñïîëüçóÿ èíôîðìà-
öèþ îá èõ êðàòíîñòÿõ.
Îïðåäåëèì ñîäåðæàòåëüíî îïåðàöèþ ñèìâîëè÷åñêîãî óìíîæåíèÿ (*) êîðòå-
æà èìåí íà îäíîýëåìåíòíûé êîðòåæ äëÿ ïîëó÷åíèÿ ýëåìåíòîâ ïðîèçâåäåíèÿ
A A k mk * ,
� �1 1 êàê îïåðàöèþ äîáàâëåíèÿ èìåíè äóãè â êîðòåæ ïðè óñëîâèè,
÷òî íå ïðåâûøåíà êðàòíîñòü äàííîé äóãè â èñõîäíîì ãðàôå. Äëÿ êîðòåæà ñèìâî-
ëè÷åñêèõ èìåí Ew e e e Ew kk k( )
( ) ( ) ( )
( )( , , , ), | |� �
� � �� , îïðåäåëèì äîïîëíè-
òåëüíî ôóíêöèþ N Ew ek
i( , )( ) , çíà÷åíèåì êîòîðîé ÿâëÿåòñÿ êðàòíîñòü äóãè ei
â êîðòåæå Ew k( ) . Òîãäà îïåðàöèÿ ñèìâîëè÷åñêîãî óìíîæåíèÿ (*) îïðåäåëÿåòñÿ
ñëåäóþùèì îáðàçîì:
Ew e
Ew Ew e N Ew e R hk
i
k k
i
k
i i( )
( ) ( ) ( )
* ( )
( ), ( , ) ( ,
�
� � � 1 1 4),
, ( , ) ( , ),
* ,
* ( ) ,
*
( )
( )
� �
�
�
�
� ��
� ��
�
N Ew e R h
Ew
e
k
i i
k
i
1 4
� ��
�
�
�
�
�
�
�
�
� .
(3)
 ðåçóëüòàòå äîïóñòèìîãî â ñìûñëå (3) óìíîæåíèÿ ïîëó÷àåì êîðòåæ
Ew Ew e e e e ek k
i i
( ) ( )
( ) ( ) ( )( ) ( , , , , )
� � �1
� � �� ,
â êîòîðîì êðàòíîñòè äóã íå ïðåâûøàþò êðàòíîñòè äóã èñõîäíîãî ìóëüòèîðãðàôà.
Îïðåäåëèì îïåðàöèþ ñèìâîëè÷åñêîãî ñëîæåíèÿ �, èñïîëüçóåìóþ ïðè ñèì-
âîëè÷åñêîì óìíîæåíèè A Ak
* , êàê îïåðàöèþ, îáîçíà÷àþùóþ íàëè÷èå íåñêîëü-
êèõ êîðòåæåé â ýëåìåíòå a Aij
k� 1. Ñîäåðæàòåëüíî íàëè÷èå íåñêîëüêèõ êîðòå-
æåé â aij îçíà÷àåò íàëè÷èå íåñêîëüêèõ ïóòåé èç âåðøèíû di äî âåðøèíû d j , ñî-
ñòîÿùèõ èç k 1 äóã, ò.å. ïóòåé äëèíû k 1.
Ëåììà 3. Ìàòðèöà A m , ãäå m — ÷èñëî äóã ñ ó÷åòîì èõ êðàòíîñòåé
â G D H� ( , ), â íåïóñòûõ ýëåìåíòàõ ñîäåðæèò âñå ýéëåðîâû ïóòè ãðàôà G, ïðè
ýòîì ñèìâîëè÷åñêîå óìíîæåíèå (*) êîðòåæà èìåí íà îäíîýëåìåíòíûé êîðòåæ
âûïîëíÿåòñÿ ïî ïðàâèëó (3), à îïåðàöèÿ ñèìâîëè÷åñêîãî ñëîæåíèÿ � îçíà÷àåò
íàëè÷èå íåñêîëüêèõ êîðòåæåé â ýëåìåíòå aij .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1 175
Äîêàçàòåëüñòâî. Ýéëåðîâ ïóòü ïðîõîäèò ïî âñåì ðåáðàì îðãðàôà. ×èñëî ïðî-
õîæäåíèÿ ÷åðåç ðåáðî ðàâíî êðàòíîñòè ýòîãî ðåáðà. Ñîãëàñíî òåîðåìå [25, ñ. 108]
ìàòðèöà A m ñîäåðæèò âñå ìàðøðóòû, ñîñòîÿùèå èç m äóã, à â ñèëó ââåäåííîé
îïåðàöèè óìíîæåíèÿ (*) êðàòíîñòü êàæäîé äóãè â êîðòåæå Ew m( ) â òî÷íîñòè ðàâ-
íà èõ êðàòíîñòè â èñõîäíîì ìóëüòèîðãðàôå äå Áðåéíà. Ëåììà äîêàçàíà.
Ïðîèëëþñòðèðóåì ïîèñê ýéëåðîâûõ ïóòåé íà ïðèìåðå ãðàôà G D H� ( , ), ïî-
ñòðîåííîãî ïî ìíîæåñòâó ïîäñëîâ V L( , ) , , ,2 4 00 01 10 11� { } (ðèñ. 1). Óìíîæåíèå
âûïîëíåíî ïî ôîðìóëå (3). Îòìåòèì, íàïðèìåð, ÷òî ñîîòâåòñòâóþùèå ýëåìåíòû
ìàòðèöû A 2 îïèñûâàþò âñå ïóòè äëèíû äâà ìåæäó ñîîòâåòñòâóþùèìè
âåðøèíàìè áåç ïîâòîðîâ äóã:
A
e e
e e
�
�
�
!
"
##
( ) ( )
( ) ( )
1 2
3 4
,
A
e e e e e e
e e e e e e
2 2 3 1 2 2 4
3 1 4 3 3 2
�
�
�
�
�
( , ) ( , ) ( , )
( , ) ( , ) ( , )
!
"
## ,
A
e e e e e e e e e e e e
e e
3 2 3 1 1 2 3 2 4 3 1 2 4
4
�
� �( , , ) ( , , ) ( , , ) ( , , )
( , 3 1 3 1 2 4 3 2 3 2 4, ) ( , , ) ( , , ) ( , , )e e e e e e e e e e� �
�
�
!
"
## ,
A
e e e e e e e e
e e e e e
4 2 4 3 1 1 2 4 3
4 3 1 2 3
�
� �
� �
( , , , ) ( , , , )
( , , , ) ( , e e e1 2 4, , )
�
�
!
"
## .
Òàêèì îáðàçîì, â äàííîì ãðàôå ñóùåñòâóåò ýéëåðîâ öèêë. Ïðåäëîæåííàÿ
ïðîöåäóðà ïîçâîëèëà ïîëó÷èòü âñå âîçìîæíûå ïóòè, êîòîðûå ìîãóò áûòü îáðàçî-
âàíû èç ýòîãî öèêëà. Íàïîìíèì, ÷òî êàæäîìó ïóòè ñîîòâåòñòâóåò íåêîòîðîå âîñ-
ñòàíàâëèâàåìîå ïî íåìó ñëîâî. Ïîñòðîèì ýòè ñëîâà, èñïîëüçóÿ ïðàâèëî
ðåêîíñòðóêöèè, óêàçàííîå â ëåììå 2:
Ew e e e e w� $ �( , , , )2 4 3 1 01100 ,
Ew e e e e w
Ew e e e e w
� $ �
� $ �
( , , , ) ,
( , , , ) ,
1 2 4 3
4 3 1 2
00110
11001
(4)
Ew e e e e w� $ �( , , , )3 1 2 4 10011.
 äàííîì ñëó÷àå âñå ñëîâà ðàçëè÷íû, ïîýòîìó èñõîäíîå ìíîæåñòâî
V L( , ) , , ,2 4 00 01 10 11� { }, ðàññìàòðèâàåìîå êàê ìíîæåñòâî ïîäñëîâ â ãèïîòåçå
ñäâèãà 1, ÿâëÿåòñÿ ðåêîíñòðóèðóþùèì, à ïîðîæäåííîå èì ìíîæåñòâî W ñîñòîèò
èç ÷åòûðåõ ñëîâ, óêàçàííûõ â (4).
ÇÀÊËÞ×ÅÍÈÅ
 ðàáîòå ïðåäëîæåí îñíîâàííûé íà îïåðàòîðíîì ïîäõîäå ôîðìàëèçì îïèñàíèÿ
îïåðàöèé íàä ñëîâàìè, ïîðîæäåííûìè êîíå÷íûì àëôàâèòîì. Èñõîäÿ èç ýòîãî,
ñôîðìóëèðîâàíà ïîñòàíîâêà çàäà÷è ðåêîíñòðóêöèè ñëîâ â ãèïîòåçå ñäâèãà 1.
Ïðåäëîæåíà ïðîöåäóðà ñïåöèàëüíîé ðàçìåòêè âåðøèí è äóã â ìóëüòèîðãðàôå äå
Áðåéíà, ïîçâîëèâøàÿ ñâåñòè ðåøåíèå çàäà÷è ðåêîíñòðóêöèè ê çàäà÷å ïîèñêà âñåõ
ýéëåðîâûõ ïóòåé (öèêëîâ). Â òåðìèíàõ îïèñàííîãî ôîðìàëèçìà ñôîðìóëèðîâàíû
è äîêàçàíû ëåììû î ñóùåñòâîâàíèè è ðåêîíñòðóêöèè ñëîâ ïî ïîäñëîâàì â ãèïî-
òåçå ñäâèãà 1.  ðåçóëüòàòå àäàïòàöèè ñèìâîëè÷åñêîãî óìíîæåíèÿ ìàòðèö ê îñî-
áåííîñòÿì ðàññìàòðèâàåìîé çàäà÷è ââåäåíà ñïåöèàëüíàÿ îïåðàöèÿ ñèìâîëè÷åñêî-
ãî óìíîæåíèÿ äóã, ïîçâîëÿþùàÿ ñòðîèòü ýéëåðîâû ïóòè â ãðàôå äå Áðåéíà.
Ðàçâèòèå äàííîé ïîñòàíîâêè ïðåäïîëàãàåò ðàññìîòðåíèå çàäà÷è ðåêîíñòðóê-
öèè ïðè íàëè÷èè çàïðåùåííûõ ñëîâ, ñîîòâåòñòâóþùåé ðåêîíñòðóêöèè ñëîâ èç
çàäàííîãî ÿçûêà, à òàêæå èññëåäîâàíèå, àíàëèç è îáîñíîâàíèå âû÷èñëèòåëüíîé
ñëîæíîñòè àëãîðèòìà ñèìâîëè÷åñêîãî óìíîæåíèÿ, ïîçâîëÿþùåãî îïðåäåëèòü âñå
ýéëåðîâû ïóòè â ãðàôå äå Áðåéíà. Èíòåðåñ ê òàêîìó èññëåäîâàíèþ âûçâàí íåêî-
òîðûìè îñîáåííîñòÿìè ïîðîæäåíèÿ äóã ãðàôà äå Áðåéíà, êîòîðûå âîçíèêàþò
â ðàññìàòðèâàåìîé çàäà÷å.
176 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Õ î ï ê ð î ô ò Ä . , Ì î ò â à í è Ð . , Ó ë ü ì à í Ä æ . Ââåäåíèå â òåîðèþ àâòîìàòîâ, ÿçûêîâ
è âû÷èñëåíèé. — Ì.: Èçä. äîì «Âèëüÿìñ», 2008. — 528 ñ.
2. M o r s e M . , H e d l u n d G . Unending chess, symbolic dynamics and a problem in semigroups //
Duke Math. J. — 1944. — N 11. — P. 1–7.
3. Ñ è ì è ó Ý . Õàîòè÷åñêèå ïåðåõîäû â äåòåðìèíèðîâàííûõ è ñòîõàñòè÷åñêèõ ñèñòåìàõ. — Ì.:
Ôèçìàòëèò, 2007. — 208 ñ.
4. À ô ð à é ì î â è ÷ Â . , Ó ã à ë ü ä å Ý . , Ó ð è à ñ Õ . Ôðàêòàëüíûå ðàçìåðíîñòè äëÿ âðåìåí âîç-
âðàùåíèÿ Ïóàíêàðå. — Ìîñêâà-Èæåâñê: Èí-ò êîìïüþòåð. èññëåä., R&C Dynamics, 2011. —
292 ñ.
5. L i n d D . , M a r c u s B . An introduction to symbolic dynamics and coding. — Cambridge (UK):
Cambridge Univ. press, 1995. — 495 p.
6. Ì à ò å ì à ò è ÷ å ñ ê è å ìåòîäû äëÿ àíàëèçà ïîñëåäîâàòåëüíîñòåé ÄÍÊ. — Ì.: Ìèð, 1999. —
349 ñ.
7. Ã à ì î â Ã . Êîìáèíàòîðíûå ïðèíöèïû â ãåíåòèêå // Ïðèêëàäíàÿ êîìáèíàòîðíàÿ ìàòåìàòèêà:
Ñá. ñòàòåé / Ïîä ðåä. Ý. Áåêêåíáàõà. — Ì.: Ìèð, 1968. — Ñ. 288–308.
8. L o t h a i r e M . Combinatorics of words // Encyclopedia of mathematics and its applications. —
Reading (Mass.): Addison-Wesley Publ. Co., 1983. — 17. — 228 p.
9. L o t h a i r e M . Algebraic combinatorics on words. — Cambridge: Cambridge Univ. press, 2002.
— 455 p.
10. L o t h a i r e M . Applied combinatorics on words // Encyclopedia of mathematics and its
applications. — Cambridge: Cambridge Univ. press, 2005. — 610 p.
11. Ëå â å í ø ò å é í  . È . Âîññòàíîâëåíèå îáúåêòîâ ïî ìèíèìàëüíîìó ÷èñëó èñêàæåííûõ îáðàç-
öîâ // Äîêë. ÐÀÍ. — 1997. — 354, ¹ 5. — Ñ. 593–596.
12. Ë å î í ò ü å â  . Ê . Ðàñïîçíàâàíèå äâîè÷íûõ ñëîâ ïî èõ ôðàãìåíòàì // Äîêë. ÐÀÍ. — 1993. —
330, ¹ 4. — Ñ. 434–436.
13. D r e y e r W . , K o t z D i t t r i c h A . , S c h m i d t D . Research perspectives for time series
management systems // SIGMOD Record. — 1994. — 23, N 1. — P. 10–15.
14. à à ñ ô è ë ä Ä . Ñòðîêè, äåðåâüÿ è ïîñëåäîâàòåëüíîñòè â àëãîðèòìàõ: Èíôîðìàòèêà è âû÷èñ-
ëèòåëüíàÿ áèîëîãèÿ / Ïåð ñ àíãë. — ÑÏá.: Íåâñê. äèàëåêò; ÁÕÂ-Ïåòåðáóðã, 2003. — 654 ñ.
15. Ð ó ä à ê î â Ê .  . , Ò î ð ø è í È . Þ . Îá îòáîðå èíôîðìàòèâíûõ çíà÷åíèé ïðèçíàêîâ íà áàçå
êðèòåðèåâ ðàçðåøèìîñòè â çàäà÷å ðàñïîçíàâàíèÿ âòîðè÷íîé ñòðóêòóðû áåëêà // ÄÀÍ. — 2011.
— 441, ¹ 1. — Ñ. 1–5.
16. À í ä å ð ñ å í Á . Áèçíåñ-ïðîöåññû. Èíñòðóìåíòû ñîâåðøåíñòâîâàíèÿ / Ïåð. ñ àíãë. Ñ.Â. Àðè-
íè÷åâà; Íàó÷. ðåä. Þ.Ï. Àäëåð. — Ì.: ÐÈÀ «Ñòàíäàðòû è êà÷åñòâî», 2003. — 272 ñ.
17. Ê à ë à ø í è ê  .  . Âîññòàíîâëåíèå ñëîâà ïî åãî ôðàãìåíòàì // Âû÷èñë. ìàòåìàòèêà è âû-
÷èñë. òåõíèêà. — Õàðüêîâ, 1973. — Âûï. 4. — Ñ. 56–57.
18. Çå í ê è í À . È . , Ë å î í ò ü å â  . Ê . Îá îäíîé íåêëàññè÷åñêîé çàäà÷å ðàñïîçíàâàíèÿ // Æóðí.
âû÷èñë. ìàòåìàòèêè è ìàò. ôèçèêè. — 1984. — 24, ¹ 6. — Ñ. 925–931.
19. Ñ ì å ò à í è í Þ . à . Îá àëãåáðàè÷åñêîé ñëîæíîñòè çàäà÷ âîññòàíîâëåíèÿ âåêòîðîâ. — Ì.,
1986. — Äåï. â ÂÈÍÈÒÈ 03.09.86, ¹ 6643–Â86.
20. Ë å î í ò ü å â Â . Ê . , Ñ ì å ò à í è í Þ . Ã . Î âîññòàíîâëåíèè âåêòîðà ïî íàáîðó åãî ôðàãìåí-
òîâ // Äîêë. ÀÍ ÑÑÑÐ. — 1988. — 302, ¹ 6. — Ñ. 1319–1322.
21. L e o n t ’ e v V . K . , S m e t a n i n Y u . G . Problems of information on the set of words // J. Math.
Sci. — New York: Kluwer Acad./Consult. Bureau, 2000. — 108, N 1. — P. 49–70.
22. K r a s i k o v I . , R o d i t y Y . On a reconstruction problem for sequences // J. Comput. Theory.
Ser. A. — 1997. — 77. — P. 344–348.
23. Ë å î í ò ü å â  . Ê . Çàäà÷è âîññòàíîâëåíèÿ ñëîâ ïî ôðàãìåíòàì è èõ ïðèëîæåíèÿ // Äèñêðåò.
àíàëèç è èññëåä. îïåðàöèé. — 1995. — 2, ¹ 2. — Ñ. 26–48.
24. B r u i j n N . G . d e . A combinatorial problem // Indagationes Math. — 1946. — 8. — P. 461–467.
25. Ø à ï î ð å â Ñ . Ä . Äèñêðåòíàÿ ìàòåìàòèêà. Êóðñ ëåêöèé. — ÑÏá.: ÁÕÂ-Ïåòåðáóðã, 2006. —
400 ñ.
Ïîñòóïèëà 15.04.2013
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 1 177
|