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

Задача обнаружения заданного повторяющегося фрагмента

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

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

Дано: вектор Y Î R^N,  вектор U Î R^q, натуральные числа  M,  N^–, N⁺, T_min и T_max.

Найти: набор (n₁,...,n_M) Î Ω_M номеров такой, что

где Y_n = (y_n,...,y_n+q-1),  n = 0,...,N - q.

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

O[M(N - q + 1)(T_max - T_min + q)] = O(MN²) = O(N³),

обоснован в [2, 17, 18].