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


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

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

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

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

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

при ограничениях:

 

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

O[M(N - q + 1)(Tmax - Tmin + Kq3)] = O(KMN 4) = O(KN 5),  

обоснован в [29, 35].

 

Описание

Демо-версия

 


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

предыдущая

следующая

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