Система QPSLab для анализа и распознавания числовых последовательностей с квазипериодической структурой
Задача совместного обнаружения и идентификации фрагментов по их обрывкам
(число фрагментов известно)
Эта задача редуцируется к следующей экстремальной задаче.
Дано: вектор Y Î RN, натуральные числа M, N–, N+, Tmin и Tmax, алфавит A Ì {U: U Î 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].
предыдущая |
следующая |