Система QPSLab для анализа и распознавания числовых последовательностей с квазипериодической структурой
Задача совместного обнаружения и идентификации фрагментов
(число фрагментов
неизвестно)Эта задача редуцируется к следующей экстремальной задаче.
Дано: вектор Y Î RN, натуральные числа N–, N+, Tmin и Tmax, алфавит A Ì {U: U Î Rq, 0 < ||U|| < ∞} векторов, причем | A | = K.
Найти: оптимальное значение M, набор (n1,...,nM) Î Ω номеров и набор (U1,...,UM) векторов из алфавита такие, что
где Yn = (yn,...,yn+q-1), n = 0,...,N - q.
Задача разрешима за полиномиальное время. Алгоритм, имеющий временную сложность
O[(N - q + 1)(Tmax - Tmin + Kq)] = O(KN 2),
обоснован в [10, 12].