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


Задача совместного обнаружения и идентификации фрагментов

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

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

Дано:  вектор Y Î RN, натуральные числа  M, N, N+, Tmin и Tmax, алфавит A Ì  {UU Î Rq, 0 < ||U|| < } векторов, причем | A | = K.

Найти: набор (n1,...,nM) Î ΩM номеров и набор (U1,...,UM) векторов из алфавита такие, что

 

где Yn = (yn,...,yn+q-1),  n = 0,...,N - q.

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

O[M(N - q + 1)(Tmax - Tmin + Kq)] = O(KMN 2) = O(KN 3),  

обоснован в [3, 7].

 

Описание

Демо-версия

 


начало страницы

предыдущая

следующая

главная страница