Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. I. Реконструкция без запретов

Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. I. Реконструкция без запретов

Рассмотрена задача реконструкции слов по заданному множеству подслов в гипотезе, что оно порождено смещением окна фиксированной длины по неизвестному слову со сдвигом 1. Предложено решение для задачи реконструкции слов без запрещенного подслова, основанное на поиске эйлеровых путей или циклов в муль...

Full description

Saved in:
Bibliographic Details
Date:2014
Main Authors: Сметанин, Ю.Г., Ульянов, М.В.
Format: Article
Language:Russian
Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2014
Series:Кибернетика и системный анализ
Subjects:
Новые средства кибернетики, информатики, вычислительной техники и системного анализа
Online Access:https://nasplib.isofts.kiev.ua/handle/123456789/115773
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:Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. I. Реконструкция без запретов / Ю.Г. Сметанин, М.В. Ульянов // Кибернетика и системный анализ. — 2014. — Т. 50, № 1. — С. 168-177. — Бібліогр.: 25 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-115773
record_format dspace
fulltext
spelling nasplib_isofts_kiev_ua-123456789-1157732025-06-03T16:25:10Z Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. I. Реконструкция без запретов Реконструкція слів за кінцевою мультимножиною пiдслiв у гіпотезі зміщення 1. I. Реконструкцiя без заборон Reconstruction of words given a finite set of its subwords under the hypothesis of unit shift 1. I. Reconstruction without forbidden words Сметанин, Ю.Г. Ульянов, М.В. Новые средства кибернетики, информатики, вычислительной техники и системного анализа Рассмотрена задача реконструкции слов по заданному множеству подслов в гипотезе, что оно порождено смещением окна фиксированной длины по неизвестному слову со сдвигом 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. Работа выполнена при поддержке РФФИ, грант № 13-07-00516. 2014 Article Реконструкция слов по конечному мультимножеству подслов в гипотезе сдвига 1. I. Реконструкция без запретов / Ю.Г. Сметанин, М.В. Ульянов // Кибернетика и системный анализ. — 2014. — Т. 50, № 1. — С. 168-177. — Бібліогр.: 25 назв. — рос. https://nasplib.isofts.kiev.ua/handle/123456789/115773 519.16,519.17 ru Кибернетика и системный анализ application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
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 https://nasplib.isofts.kiev.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
AT smetaninûg rekonstrukcíâslívzakíncevoûmulʹtimnožinoûpidslivugípotezízmíŝennâ1irekonstrukciâbezzaboron
AT ulʹânovmv rekonstrukcíâslívzakíncevoûmulʹtimnožinoûpidslivugípotezízmíŝennâ1irekonstrukciâbezzaboron
AT smetaninûg reconstructionofwordsgivenafinitesetofitssubwordsunderthehypothesisofunitshift1ireconstructionwithoutforbiddenwords
AT ulʹânovmv reconstructionofwordsgivenafinitesetofitssubwordsunderthehypothesisofunitshift1ireconstructionwithoutforbiddenwords
first_indexed 2025-11-25T23:46:37Z
last_indexed 2025-11-25T23:46:37Z
_version_ 1849808017974886400

Similar Items