О числе реконструкций по подсловам в бинарном алфавите при наложении на один символ

  • Galina Nikolaevna Zhukova Национальный исследовательский университет "Высшая школа экономики" http://orcid.org/0000-0003-1835-7422
  • Yuri Gennadievich Smetanin Федеральный исследовательский центр "Информатика и управление" РАН http://orcid.org/0000-0003-0242-6972
  • Mikhail Vasilevich Ulyanov Институт проблем управления им. В.А. Трапезникова РАН; Московский государственный университет имени М.В. Ломоносова http://orcid.org/0000-0002-5784-9836

Аннотация

Рассмотрена задача получения точных оценок числа реконструкций для слов над бинарным алфавитом. Подслова различной длины из заданного множества соединяются методом наложения концевых символов. Соединять можно только такую пару подслов, у которых последний символ первого подслова совпадает с первым символом второго. При наложении пары подходящих подслов на один символ из двух одинаковых символов (в конце первого и в начале второго подслова) в реконструкцию входит только один. Предложен подход, основанный на рассмотрении усеченных подслов, состоящих из префикса и суффикса данного подслова, имеющих длину один. При построении реконструкции вместо самих подслов из заданного множества соединяются усеченные слова вида "00", "01", "10" и "11". Число реконструкций находится в предположении, что каждое из усеченных подслов соответствует уникальному подслову в заданном множестве подслов. В результате при соединении слов "00" и "00" возможны две реконструкции, соответствующие соединению исходных подслов "0x0" и "0y0" в "0x0y0" и "0y0x0", где x и y — различные последовательности символов бинарного алфавита, одна из которых может быть пустой (но не обе одновременно).
Такой подход позволил определить условия существования реконструкции по заданному множеству подслов различной длины. Показано, при каких условиях, касающихся количества усеченных подслов каждого вида, реконструкция невозможна. Например, невозможна реконструкция по множеству подслов, содержащему только подслова вида "00" и "11". Также невозможно соединить все подслова заданного множества, если число усеченных подслов вида "01" и "10" отличается больше, чем на один. Для различных случаев, допускающих полную реконструкцию, получены формулы точного числа реконструкций. Точное число реконструкций зависит от наличия или отсутствия подслов, соответствующих усеченным подсловам каждого вида.
Поскольку возможность реконструкции главным образом зависит от соотношения числа подслов вида "01" и "10", то отдельно была рассмотрена модель с возможностью инверсий слов. Предполагается, что множество подслов для реконструкции содержит только слова вида вида "00", "01" "00", Часть слов вида "01" записывается в обратном порядке и становится словами вида "10". Если слов "01" было четное число, то в "01" преобразуется половина слов "01", иначе — половина от ближайшего четного числа. В последнем случае из множества подслов вида «01» получается два варианта наборов подслов вида "01" и "10", в одном больше подслов "01", в другом — "10". Для каждого случая приведены формулы точного числа реконструкций при условии уникальности подслов в заданном множестве, а также несимметричности подслов, порождающих усеченные подслова вида "00" и "11".

Сведения об авторах

Galina Nikolaevna Zhukova, Национальный исследовательский университет "Высшая школа экономики"

доцент Департамента программной инженерии, факультет компьютерных наук, кандидат физико-математических наук, доцент

Yuri Gennadievich Smetanin, Федеральный исследовательский центр "Информатика и управление" РАН

главный научный сотрудник Вычислительного центра им. А.А. Дородницына РАН, доктор физико-математических наук

Mikhail Vasilevich Ulyanov, Институт проблем управления им. В.А. Трапезникова РАН; Московский государственный университет имени М.В. Ломоносова

ведущий научный сотрудник; профессор кафедры алгоритмических языков, факультет вычислительной математики и кибернетики, доктор технических наук, профессор

Опубликована
2020-09-30
Как цитировать
ZHUKOVA, Galina Nikolaevna; SMETANIN, Yuri Gennadievich; ULYANOV, Mikhail Vasilevich. О числе реконструкций по подсловам в бинарном алфавите при наложении на один символ. Международный научный журнал «Современные информационные технологии и ИТ-образование», [S.l.], v. 16, n. 2, sep. 2020. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/650>. Дата доступа: 02 dec. 2020
Раздел
Теоретические вопросы информатики, прикладной математики, компьютерных наук

Наиболее читаемые статьи этого автора (авторов)