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