Проблема распознавания последова

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

Проблема распознавания последовательности, включающей повторяющийся набор фрагментов

Числовая квазипериодическая последовательность, в составе которой имеется повторяющийся упорядоченный набор из L ненулевых фрагментов размерности q, определяется следующей формулой общего члена (модель без вставок):

l(m | L) = (m- $1) mod$ L+1, m Î {1,...,M};

Y = X(n₁,...,n_M, U₁,...,U_L) + E;

(U₁,...,U_L) Î W – повторяющийся набор эталонных векторов (фрагментов).

W – совокупность (словарь) эталонных наборов, |W| = K.

Имеем следующие варианты задач


				вставок нет	имеются вставки
					задан алфавит вставок B		множество вставок не ограничено
число повторов J				=J₀	изв.	неизв.	изв.	неизв.
по-теря дан-ных	нет	число фраг- ментов `M`	изв.	+	?	?	?	?
	нет		неизв.	+	?	?	?	?
	есть		изв.	±	?	?	?	?
	есть		неизв.	±	?	?	?	?

J₀ = ë(M+L-1)/Lû, ëzû – целая часть z.

Здесь используются следующие обозначения:
+	– обоснован точный полиномиальный алгоритм;
±	– обоснован, но еще не опубликован точный полиномиальный алгоритм;
?	– статус сложности не выяснен, какие либо алгоритмы неизвестны.

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

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