Система 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
|
изв. |
+ |
? |
неизв. | + | ? | |||
есть | изв. | ± | ? | ||
неизв. | ± | ? |
Здесь используются следующие обозначения: |
|
+ |
– обоснован точный полиномиальный алгоритм; |
± |
– обоснован, но еще не опубликован точный полиномиальный алгоритм; |
? |
– статус сложности не выяснен, какие либо алгоритмы неизвестны. |
предыдущая |
следующая |