Общероссийский семинар «Информатика, управление и системный анализ»

ОБЩЕРОССИЙСКИЙ СЕМИНАР «ИНФОРМАТИКА, УПРАВЛЕНИЕ И СИСТЕМНЫЙ АНАЛИЗ»
под общим руководством
Академика РАН Юрия Ивановича Журавлева,
Академика РАН Евгения Ивановича Моисеева,
Академика РАН Станислава Николаевича Васильева,
Члена-корреспондента РАН Юрия Соломоновича Попкова
организатор и ученый секретарь семинара
профессор Михаил Васильевич Ульянов

Сайт семинара: www.commonmind.ru

ЗАСЕДАНИЕ № 16

Вторник 27 октября 2015 г. 16-30 ауд. 685 ВМК МГУ
ПОВЕСТКА ДНЯ

1.Научный доклад:
«О РЕКОНСТРУКЦИИ СЛОВ ПО ПОДСЛОВАМ В ГИПОТЕЗЕ СДВИГА 1»

Докладчики:
д.ф-м. н., г.н.с. ФИЦ ИУ РАН СМЕТАНИН ЮРИЙ ГЕННАДИЕВИЧ,
д.т.н., проф., в.н.с. ИПУ РАН УЛЬЯНОВ МИХАИЛ ВАСИЛЬЕВИЧ

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