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


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

 

Структура последовательности (модель без вставок):

 

(U1,...,UL) набор векторов, порождающих серии идентичных фрагментов;

0 = μ0 < μ1 < ... < μL,  L ≤ μL ограничения, определяющие допустимые границы серий;

ΔL(M) = {(μ1,..., μL): 0 < μ1 < ... < μL,  L ≤ μL ≤ M};

Y = X(n1,...,nμL, μ1,..., μL, U1,...,UL) + E;

(U1,...,UL) Î W, W словарь эталонных наборов.

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

 

задан словарь эталонных наборов

вставок нет

имеются вставки

потеря

данных

 нет  число

 фраг-

 ментов

M

 

 изв.

+

?

 неизв. + ?
 есть  изв. ± ?
 неизв. ± ?

 

Здесь используются следующие обозначения:

+

  обоснован точный полиномиальный алгоритм;

±

  обоснован, но еще не опубликован точный полиномиальный алгоритм;

?

 – статус сложности не выяснен, какие либо алгоритмы неизвестны.

 


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

предыдущая

следующая

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