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