Том 16, номер 4, 2009 г., Стр. 31-46
УДК 519.2+621.391
А. В. Кельманов, Л. В. Михайлова, С. А. Хамидуллин
Об одном варианте задачи поиска упорядоченного набора векторов в числовой последовательности
Аннотация:
Рассматривается дискретная экстремальная задача, к которой сводится один из вариантов проблемы помехоустойчивого off-line обнаружения в числовой последовательности повторяющегося упорядоченного набора фрагментов. Анализируется вариант проблемы, в котором фрагменты из искомых наборов в отсутствие помехи совпадают с элементами из заданного упорядоченного эталонного набора векторов. Обоснован новый точный полиномиальный алгоритм решения редуцированной задачи, гарантирующий оптимальность решения по критерию минимума суммы квадратов уклонений, а также по критерию максимума правдоподобия в случае, когда помеха аддитивна и является гауссовской последовательностью независимых одинаково распределённых случайных величин. Трудоёмкость предложенного алгоритма меньше, чем у известного аналога.
Библиогр. 4.
Ключевые слова: дискретная экстремальная задача, числовая последовательность, упорядоченный набор фрагментов, off-line алгоритм.
Кельманов Александр Васильевич 1
Михайлова Людмила Викторовна 1
Хамидуллин Сергей Асгадуллович 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: kelm@math.nsc.ru, mikh@math.nsc.ru, kham@math.nsc.ru
Статья поступила 10 февраля 2009 г.
Исправленный вариант — 5 марта 2009 г.
