Geodesic
On one problem of searching for tuples of fragments in a numerical sequence
Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 4, pp. 31-46 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

A discrete optimization problem is considered to which the problem of the noise-proof detection of the recurring tuple of fragments in a numerical sequence is reduced. A variant of the problem in which the fragments from the desired tuples coincide (in the noiseless case) with the elements of the given tuple of vectors is analyzed. A new exact polynomial algorithm for solving this special optimization problem is proved. This algorithm provides that the solution is optimal under the minimum sum-of-squared deviations criterion. If noise is additive and it is a Gaussian sequence of independent identically distributed variables, then the solution is optimal under the maximum likelihood criterion as well. The time complexity of our algorithm is proved to be less then the complexity of the previously known algorithm. Bibl. 4.
Keywords: discrete optimization problem, numerical sequence, recurring tuple of fragments, off-line algorithm. 
@article{DA_2009_16_4_a2,
     author = {A. V. Kel'manov and L. V. Mikhaylova and S. A. Khamidullin},
     title = {On one problem of searching for tuples of fragments in a~numerical sequence},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {31--46},
     year = {2009},
     volume = {16},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2009_16_4_a2/}
}
TY  - JOUR
AU  - A. V. Kel'manov
AU  - L. V. Mikhaylova
AU  - S. A. Khamidullin
TI  - On one problem of searching for tuples of fragments in a numerical sequence
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2009
SP  - 31
EP  - 46
VL  - 16
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DA_2009_16_4_a2/
LA  - ru
ID  - DA_2009_16_4_a2
ER  - 
%0 Journal Article
%A A. V. Kel'manov
%A L. V. Mikhaylova
%A S. A. Khamidullin
%T On one problem of searching for tuples of fragments in a numerical sequence
%J Diskretnyj analiz i issledovanie operacij
%D 2009
%P 31-46
%V 16
%N 4
%U http://geodesic.mathdoc.fr/item/DA_2009_16_4_a2/
%G ru
%F DA_2009_16_4_a2
A. V. Kel'manov; L. V. Mikhaylova; S. A. Khamidullin. On one problem of searching for tuples of fragments in a numerical sequence. Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 4, pp. 31-46. http://geodesic.mathdoc.fr/item/DA_2009_16_4_a2/

[1] Kelmanov A. V., Mikhailova L. V., Khamidullin S. A., “Optimalnoe obnaruzhenie v kvaziperiodicheskoi posledovatelnosti povtoryayuschegosya nabora etalonnykh fragmentov”, Materialy Rossiiskoi konf. “Diskretnaya optimizatsiya i issledovanie operatsii” (Vladivostok, 7–14 sentyabrya 2007), Izd-vo In-ta matematiki SO RAN, Novosibirsk, 2007, 178; http://math.nsc.ru/conference/door07/DOOR_abstracts.pdf

[2] Kelmanov A. V., Mikhailova L. V., Khamidullin S. A., “Aposteriornoe obnaruzhenie v kvaziperiodicheskoi posledovatelnosti povtoryayuschegosya nabora etalonnykh fragmentov”, Zhurn. vychisl. matematiki i mat. fiziki, 48:12 (2008), 2247–2260 | MR

[3] Kelmanov A. V., Mikhailova L. V., Khamidullin S. A., “Optimalnoe obnaruzhenie v kvaziperiodicheskoi posledovatelnosti povtoryayuschegosya nabora etalonnykh fragmentov”, Sib. zhurn. vychisl. matematiki, 11:3 (2008), 311–327

[4] http://math.nsc.ru/~serge/qpsl/