Система QPSLab для анализа и распознавания числовых последовательностей с квазипериодической структурой
Проблема обнаружения повторяющегося набора фрагментов
Числовая квазипериодическая последовательность, в составе которой имеется повторяющийся упорядоченный набор из ненулевых фрагментов размерности , определяется следующей формулой общего члена:
-, m Î {1,...,M};
Y = X(n1,...,nM, U1,...,UL) + E;
(U1,...,UL) – повторяющийся набор ненулевых фрагментов.
Имеем следующие задачи
| Задан образец набора | Образец набора не задан | ||||||||||||
|
вставок нет |
имеются вставки |
вставок нет |
имеются вставки |
||||||||||
|
задан алфавит вставок B |
множество вставок не ограничено |
|
задан алфавит вставок B |
множество вставок не ограничено |
|||||||||
|
число повторов J |
=J0 |
изв.
|
неизв.
|
изв.
|
неизв.
|
=J0 |
изв.
|
неизв.
|
изв.
|
неизв.
|
|||
| по-теря дан-ных |
нет | число фраг- ментов M
|
изв. |
+ |
? |
? |
? |
? |
Np-h
|
Np-h
|
Np-h ? |
Np-h
|
Np-h ? |
| неизв. | + | ? | ? | ? | ? |
Np-h ? |
Np-h
|
Np-h ? |
Np-h
|
Np-h ? |
|||
| есть | изв. | ± | ? | ? | ? | ? |
Np-h
|
Np-h
|
Np-h ? |
Np-h
|
Np-h ? |
||
| неизв. | ± | ? | ? | ? | ? |
Np-h ? |
Np-h
|
Np-h ? |
Np-h
|
Np-h ? |
|||
J0 = ë(M+L-1)/Lû, ëzû – целая часть z.
|
Здесь используются следующие обозначения: |
|
|
+ |
– обоснован точный полиномиальный алгоритм; |
|
± |
– обоснован, но еще не опубликован точный полиномиальный алгоритм; |
|
Np-h |
– задача NP–трудна, какие либо алгоритмы неизвестны; |
|
Np-h ? |
– задача скорее всего NP–трудна, какие либо алгоритмы неизвестны; |
|
? |
– статус сложности не выяснен, какие либо алгоритмы неизвестны. |