Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. I. Реконструкция без запретов
Рассмотрена задача реконструкции слов по заданному множеству подслов в гипотезе, что оно порождено смещением окна фиксированной длины по неизвестному слову со сдвигом 1. Предложено решение для задачи реконструкции слов без запрещенного подслова, основанное на поиске эйлеровых путей или циклов в муль...
Збережено в:
| Дата: | 2014 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2014
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/115773 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. I. Реконструкция без запретов / Ю.Г. Сметанин, М.В. Ульянов // Кибернетика и системный анализ. — 2014. — Т. 50, № 1. — С. 168-177. — Бібліогр.: 25 назв. — рос. |
Репозитарії
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 |
2023-10-18T20:26:10Z |
| last_indexed |
2023-10-18T20:26:10Z |
| _version_ |
1796150189937917952 |