Система QPSLab для анализа и распознавания числовых последовательностей с квазипериодической структурой

Задача распознавания последовательности, включающей повторяющийся фрагмент

(число повторов неизвестно)

Эта задача редуцируется к следующей экстремальной задаче.

Дано: вектор Y Î R^N, натуральные числа N^–, N⁺, T_min и T_max, алфавит A Ì  {U: U Î R^q, 0 < ||U|| < ∞} векторов, причем | A | = K.

Найти: вектор U Î A такой, что

где Y_n = (y_n,...,y_n+q-1),  n = 0,...,N - q, при ограничении (n₁,...,n_M) Î Ω.

Задача разрешима за полиномиальное время. Алгоритм, имеющий временную сложность

O[K(N - q + 1)(T_max - T_min + q)] = O(KN²),  

обоснован в [21, 25].