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