Standard

ДВЕ ЗАДАЧИ О ВОССТАНОВЛЕНИИ ПОВРЕЖДЕННЫХ СТРОК. / Рубинчик, Михаил Валентинович; Гамзова, Юлия Васильевна.
In: Siberian Electronic Mathematical Reports, Vol. 10, 2013, p. 538-550.

Research output: Contribution to journal › Article › peer-review

Harvard

Рубинчик, МВ & Гамзова, ЮВ 2013, 'ДВЕ ЗАДАЧИ О ВОССТАНОВЛЕНИИ ПОВРЕЖДЕННЫХ СТРОК', Siberian Electronic Mathematical Reports, vol. 10, pp. 538-550.

APA

Рубинчик, М. В., & Гамзова, Ю. В. (2013). ДВЕ ЗАДАЧИ О ВОССТАНОВЛЕНИИ ПОВРЕЖДЕННЫХ СТРОК. Siberian Electronic Mathematical Reports, 10, 538-550.

Vancouver

Рубинчик МВ, Гамзова ЮВ. ДВЕ ЗАДАЧИ О ВОССТАНОВЛЕНИИ ПОВРЕЖДЕННЫХ СТРОК. Siberian Electronic Mathematical Reports. 2013;10:538-550.

Author

Рубинчик, Михаил Валентинович ; Гамзова, Юлия Васильевна. / ДВЕ ЗАДАЧИ О ВОССТАНОВЛЕНИИ ПОВРЕЖДЕННЫХ СТРОК. In: Siberian Electronic Mathematical Reports. 2013 ; Vol. 10. pp. 538-550.

BibTeX

@article{1e8b5ab7b7e84a6abe820a861614678e,
title = "ДВЕ ЗАДАЧИ О ВОССТАНОВЛЕНИИ ПОВРЕЖДЕННЫХ СТРОК",
abstract = "Мы рассматриваем две задачи родственные поиску по шаблону в повреждённом тексте. В обеих задачах наша цель – восстановление оригинальных неповреждённых текста и шаблона оптимальным способом. Задача 1. Для данных повреждённых текста и шаблона восстановить текст и шаблон, максимизировав количество вхождений шаблона в текст. Мы определили суммарное расстояние Хэмминга между текстом длины n и шаблоном длины m как сумму расстояний между всеми парами вида (шаблон, подстрока текста длины m). Задача 2. Для данных повреждённых текста и шаблона восстановить текст и шаблон, минимизировав суммарное расстояние Хэмминга между ними. Мы доказали, что обе задачи NP-трудны и привели эффективные (полиномиальные) алгоритмы решения некоторых важных частных случаев.",
author = "Рубинчик, {Михаил Валентинович} and Гамзова, {Юлия Васильевна}",
year = "2013",
language = "Русский",
volume = "10",
pages = "538--550",
journal = "Siberian Electronic Mathematical Reports",
issn = "1813-3304",
publisher = "Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук",

}

RIS

TY - JOUR

T1 - ДВЕ ЗАДАЧИ О ВОССТАНОВЛЕНИИ ПОВРЕЖДЕННЫХ СТРОК

AU - Рубинчик, Михаил Валентинович

AU - Гамзова, Юлия Васильевна

PY - 2013

Y1 - 2013

N2 - Мы рассматриваем две задачи родственные поиску по шаблону в повреждённом тексте. В обеих задачах наша цель – восстановление оригинальных неповреждённых текста и шаблона оптимальным способом. Задача 1. Для данных повреждённых текста и шаблона восстановить текст и шаблон, максимизировав количество вхождений шаблона в текст. Мы определили суммарное расстояние Хэмминга между текстом длины n и шаблоном длины m как сумму расстояний между всеми парами вида (шаблон, подстрока текста длины m). Задача 2. Для данных повреждённых текста и шаблона восстановить текст и шаблон, минимизировав суммарное расстояние Хэмминга между ними. Мы доказали, что обе задачи NP-трудны и привели эффективные (полиномиальные) алгоритмы решения некоторых важных частных случаев.

AB - Мы рассматриваем две задачи родственные поиску по шаблону в повреждённом тексте. В обеих задачах наша цель – восстановление оригинальных неповреждённых текста и шаблона оптимальным способом. Задача 1. Для данных повреждённых текста и шаблона восстановить текст и шаблон, максимизировав количество вхождений шаблона в текст. Мы определили суммарное расстояние Хэмминга между текстом длины n и шаблоном длины m как сумму расстояний между всеми парами вида (шаблон, подстрока текста длины m). Задача 2. Для данных повреждённых текста и шаблона восстановить текст и шаблон, минимизировав суммарное расстояние Хэмминга между ними. Мы доказали, что обе задачи NP-трудны и привели эффективные (полиномиальные) алгоритмы решения некоторых важных частных случаев.

UR - https://elibrary.ru/item.asp?id=25411892

M3 - Статья

VL - 10

SP - 538

EP - 550

JO - Siberian Electronic Mathematical Reports

JF - Siberian Electronic Mathematical Reports

SN - 1813-3304

ER -

ID: 8247345