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

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

 (число фрагментов неизвестно)

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

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

 Найти: наборы (n₁,...,n_M) Î Ω и (μ₁,..., μ_L) Î Δ_L(M_max) такие, что

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

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

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