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