RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Сиб. журн. индустр. матем.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Сиб. журн. индустр. матем., 2006, том 9, номер 1, страницы 55–74 (Mi sjim262)  

Эта публикация цитируется в 35 научных статьях (всего в 35 статьях)

Апостериорное обнаружение в числовой последовательности квазипериодического фрагмента при заданном числе повторов

Э. Х. Гимади, А. В. Кельманов, М. А. Кельманова, С. А. Хамидуллин

Институт математики им. С. Л. Соболева СО РАН

Аннотация: Изложено решение задачи апостериорного обнаружения в зашумленной числовой последовательности неизвестного квазипериодически повторяющегося фрагмента. Анализируется случай, когда: 1) число повторов известно, 2) номер члена последовательности, соответствующий началу фрагмента, – детерминированная (не случайная) величина, 3) для наблюдения доступна последовательность, искаженная аддитивной гауссовской некоррелированной помехой. Установлено, что решаемая задача состоит в проверке совокупности сложныхгипотез о среднем значении случайного гауссовского вектора; специфика задачи заключается в том, что мощность этой совокупности растет экспоненциально с увеличением числа членов последовательности и числа повторов. Доказано, что отыскание максимально правдоподобной гипотезы сводится к поиску максимума вспомогательной целевой функции. Показано, что задача максимизации этой функции в общем случае NP-трудна. Предложен приближенный полиномиальный алгоритм решения задачи. Для улучшения приближения используется алгоритм локального поиска. Численное моделирование показало результаты, приемлемые с точки зрения приложений.

Полный текст: PDF файл (375 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

УДК: 519.2:621.391
Статья поступила: 25.07.2005

Образец цитирования: Э. Х. Гимади, А. В. Кельманов, М. А. Кельманова, С. А. Хамидуллин, “Апостериорное обнаружение в числовой последовательности квазипериодического фрагмента при заданном числе повторов”, Сиб. журн. индустр. матем., 9:1 (2006), 55–74

Цитирование в формате AMSBIB
\RBibitem{GimKelKel06}
\by Э.~Х.~Гимади, А.~В.~Кельманов, М.~А.~Кельманова, С.~А.~Хамидуллин
\paper Апостериорное обнаружение в~числовой последовательности квазипериодического фрагмента при заданном числе повторов
\jour Сиб. журн. индустр. матем.
\yr 2006
\vol 9
\issue 1
\pages 55--74
\mathnet{http://mi.mathnet.ru/sjim262}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2307365}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/sjim262
  • http://mi.mathnet.ru/rus/sjim/v9/i1/p55

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. А. В. Кельманов, С. А. Хамидуллин, “Апостериорное обнаружение в числовой последовательности заданного числа неизвестных квазипериодических фрагментов”, Сиб. журн. индустр. матем., 9:3 (2006), 50–65  mathnet  mathscinet
    2. А. Е. Бабурин, Э. Х. Гимади, Н. И. Глебов, А. В. Пяткин, “Задача отыскания подмножества векторов с максимальным суммарным весом”, Дискретн. анализ и исслед. опер., сер. 2, сер. 2, 14:1 (2007), 32–42  mathnet  mathscinet  zmath; A. E. Baburin, E. Kh. Gimadi, N. I. Glebov, A. V. Pyatkin, “The problem of finding a subset of vectors with the maximum total weight”, J. Appl. Industr. Math., 2:1 (2008), 32–38  crossref
    3. А. В. Кельманов, С. А. Хамидуллин, “Оптимальное обнаружение в числовой последовательности заданного числа неизвестных квазипериодических фрагментов”, Сиб. журн. вычисл. матем., 10:2 (2007), 159–175  mathnet
    4. Э. Х. Гимади, Ю. В. Глазков, И. А. Рыков, “О двух задачах выбора подмножества векторов с целочисленными координатами с максимальной нормой суммы в евклидовом пространстве”, Дискретн. анализ и исслед. опер., 15:4 (2008), 30–43  mathnet  mathscinet  zmath; E. Kh. Gimadi, Yu. V. Glazkov, I. A. Rykov, “The vector subset problem with integer coordinates in Euclidean space with the maximum sum”, J. Appl. Industr. Math., 3:3 (2009), 343–352  crossref
    5. А. В. Кельманов, А. В. Пяткин, “Об одном варианте задачи выбора подмножества векторов”, Дискретн. анализ и исслед. опер., 15:5 (2008), 20–34  mathnet  mathscinet  zmath; A. V. Kel'manov, A. V. Pyatkin, “On one variant of the vectors subset choice problem”, J. Appl. Industr. Math., 3:4 (2009), 447–455  crossref
    6. Э. Х. Гимади, А. В. Пяткин, И. А. Рыков, “О полиномиальной разрешимости некоторых задач выбора подмножества векторов в евклидовом пространстве фиксированной размерности”, Дискретн. анализ и исслед. опер., 15:6 (2008), 11–19  mathnet  mathscinet  zmath; E. Kh. Gimadi, A. V. Pyatkin, I. A. Rykov, “On polynomial solvability of some vector subset problems in Euclidean space with fixed dimension”, J. Appl. Industr. Math., 4:1 (2010), 48–53  crossref
    7. А. В. Кельманов, “Проблема off-line обнаружения квазипериодически повторяющегося фрагмента в числовой последовательности”, Тр. ИММ УрО РАН, 14, № 2, 2008, 81–88  mathnet  zmath  elib; A. V. Kel'manov, “Off-line detection of a quasi-periodically recurring fragment in a numerical sequence”, Proc. Steklov Inst. Math. (Suppl.), 263, suppl. 2 (2008), S84–S92  crossref  isi
    8. А. В. Кельманов, А. В. Пяткин, “О сложности одного из вариантов задачи выбора подмножества «похожих» векторов”, Докл. РАН, 421:5 (2008), 590–592  mathnet  mathscinet  zmath  elib; A. V. Kel'manov, A. V. Pyatkin, “On the complexity of a search for a subset of “similar” vectors”, Doklady Mathematics, 78:1 (2008), 574–575  crossref  mathscinet  zmath  isi  scopus
    9. А. В. Кельманов, Л. В. Михайлова, С. А. Хамидуллин, “Апостериорное обнаружение в квазипериодической последовательности повторяющегося набора эталонных фрагментов”, Ж. вычисл. матем. и матем. физ., 48:12 (2008), 2247–2260  mathnet  mathscinet; A. V. Kel'manov, L. V. Mikhailova, S. A. Khamidullin, “A posteriori joint detection of a recurring tuple of reference fragments in a quasi-periodic sequence”, Comput. Math. Math. Phys., 48:12 (2008), 2276–2288  crossref  isi
    10. А. В. Кельманов, А. В. Пяткин, “О сложности некоторых задач поиска подмножеств векторов и кластерного анализа”, Ж. вычисл. матем. и матем. физ., 49:11 (2009), 2059–2065  mathnet  mathscinet; A. V. Kel'manov, A. V. Pyatkin, “Complexity of certain problems of searching for subsets of vectors and cluster analysis”, Comput. Math. Math. Phys., 49:11 (2009), 1966–1971  crossref  isi
    11. А. В. Кельманов, А. В. Пяткин, “NP-полнота некоторых задач выбора подмножества векторов”, Дискретн. анализ и исслед. опер., 17:5 (2010), 37–45  mathnet  mathscinet  zmath; A. V. Kel'manov, A. V. Pyatkin, “NP-completeness of some problems of a vectors subset choice”, J. Appl. Industr. Math., 5:3 (2011), 352–357  crossref
    12. А. В. Кельманов, “$NP$-полнота некоторых задач поиска подмножеств векторов”, Тр. ИММ УрО РАН, 16, № 3, 2010, 121–129  mathnet  elib
    13. А. В. Кельманов, “О сложности некоторых задач анализа данных”, Ж. вычисл. матем. и матем. физ., 50:11 (2010), 2045–2051  mathnet  adsnasa; A. V. Kel'manov, “On the complexity of some data analysis problems”, Comput. Math. Math. Phys., 50:11 (2010), 1941–1947  crossref  isi
    14. А. В. Долгушев, А. В. Кельманов, “Приближëнный алгоритм решения одной задачи кластерного анализа”, Дискретн. анализ и исслед. опер., 18:2 (2011), 29–40  mathnet  mathscinet  zmath; A. V. Dolgushev, A. V. Kel'manov, “An approximation algorithm for one problem of cluster analysis”, J. Appl. Industr. Math., 5:4 (2011), 551–558  crossref
    15. А. В. Кельманов, С. М. Романченко, С. А. Хамидуллин, “Приближённые алгоритмы для некоторых труднорешаемых задач поиска подпоследовательности векторов”, Дискретн. анализ и исслед. опер., 19:3 (2012), 27–38  mathnet  mathscinet; A. V. Kel'manov, S. M. Romanchenko, S. A. Khamidullin, “Approximation algorithms for some NP-hard problems of searching a vectors subsequence”, J. Appl. Industr. Math., 6:4 (2012), 443–450  crossref
    16. А. В. Кельманов, А. В. Пяткин, “О сложности некоторых задач выбора подпоследовательности векторов”, Ж. вычисл. матем. и матем. физ., 52:12 (2012), 2284–2291  mathnet
    17. А. В. Кельманов, С. М. Романченко, С. А. Хамидуллин, “Точные псевдополиномиальные алгоритмы для некоторых труднорешаемых задач поиска подпоследовательности векторов”, Ж. вычисл. матем. и матем. физ., 53:1 (2013), 143–153  mathnet  crossref  elib
    18. А. В. Кельманов, А. В. Пяткин, “О сложности некоторых задач кластерного анализа векторных последовательностей”, Дискретн. анализ и исслед. опер., 20:2 (2013), 47–57  mathnet  mathscinet; A. V. Kel'manov, A. V. Pyatkin, “On the complexity of some vector sequence clustering problems”, J. Appl. Industr. Math., 7:3 (2013), 363–369  crossref
    19. А. В. Кельманов, В. И. Хандеев, “Полиномиальный алгоритм с оценкой точности $2$ для решения одной задачи кластерного анализа”, Дискретн. анализ и исслед. опер., 20:4 (2013), 36–45  mathnet  mathscinet; A. V. Kelmanov, V. I. Khandeev, “A $2$-approximation polynomial algorithm for one clustering problem”, J. Appl. Industr. Math., 7:4 (2013), 515–521  crossref
    20. Э. Х. Гимади, И. А. Рыков, “Рандомизированный алгоритм отыскания подмножества векторов с максимальной евклидовой нормой их суммы”, Дискретн. анализ и исслед. опер., 22:3 (2015), 5–17  mathnet  crossref  mathscinet  elib; E. Kh. Gimadi, I. A. Rykov, “A randomized algorithm for the vector subset problem with the maximal Euclidean norm of its sum”, J. Appl. Industr. Math., 9:3 (2015), 351–357  crossref
    21. А. В. Кельманов, В. И. Хандеев, “Точный псевдополиномиальный алгоритм для одной задачи двухкластерного разбиения множества векторов”, Дискретн. анализ и исслед. опер., 22:4 (2015), 50–62  mathnet  crossref  mathscinet  elib; A. V. Kel'manov, V. I. Khandeev, “An exact pseudopolynomial algorithm for a bi-partitioning problem”, J. Appl. Industr. Math., 9:4 (2015), 497–502  crossref
    22. А. В. Долгушев, А. В. Кельманов, В. В. Шенмайер, “Полиномиальная аппроксимационная схема для одной задачи разбиения конечного множества на два кластера”, Тр. ИММ УрО РАН, 21, № 3, 2015, 100–109  mathnet  mathscinet  elib; A. V. Dolgushev, A. V. Kel'manov, V. V. Shenmaier, “Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters”, Proc. Steklov Inst. Math. (Suppl.), 295, suppl. 1 (2016), 47–56  crossref
    23. А. В. Кельманов, В. И. Хандеев, “Полностью полиномиальная аппроксимационная схема для специального случая одной квадратичной евклидовой задачи 2-кластеризации”, Ж. вычисл. матем. и матем. физ., 56:2 (2016), 332–340  mathnet  crossref  elib; A. V. Kel'manov, V. I. Khandeev, “Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem”, Comput. Math. Math. Phys., 56:2 (2016), 334–341  crossref  isi
    24. А. В. Кельманов, А. В. Моткова, “Точные псевдополиномиальные алгоритмы для задачи сбалансированной $2$-кластеризации”, Дискретн. анализ и исслед. опер., 23:3 (2016), 21–34  mathnet  crossref  mathscinet  elib; A. V. Kel'manov, A. V. Motkova, “Exact pseudopolinomial algorithms for a balanced $2$-clustering problem”, J. Appl. Industr. Math., 10:3 (2016), 349–355  crossref
    25. А. В. Еремеев, А. В. Кельманов, А. В. Пяткин, “О сложности и аппроксимируемости некоторых евклидовых задач оптимального суммирования”, Ж. вычисл. матем. и матем. физ., 56:10 (2016), 1831–1836  mathnet  crossref  elib; A. V. Eremeev, A. V. Kel'manov, A. V. Pyatkin, “On the complexity and approximability of some Euclidean optimal summing problems”, Comput. Math. Math. Phys., 56:10 (2016), 1813–1817  crossref  isi
    26. В. В. Шенмайер, “Решение некоторых задач поиска подмножества векторов с использованием диаграмм Вороного”, Дискретн. анализ и исслед. опер., 23:4 (2016), 102–115  mathnet  crossref  mathscinet  elib; V. V. Shenmaier, “Solving some vector subset problems by Voronoi diagrams”, J. Appl. Industr. Math., 10:4 (2016), 560–566  crossref
    27. Eremeev A.V., Kel'manov A.V., Pyatkin A.V., “On the Complexity of Some Euclidean Optimal Summing Problems”, Dokl. Math., 93:3 (2016), 286–288  crossref  isi
    28. Kel'manov A., Motkova A., “A Fully Polynomial-Time Approximation Scheme For a Special Case of a Balanced 2-Clustering Problem”, Discrete Optimization and Operations Research (DOOR 2016), Lecture Notes in Computer Science, 9869, eds. Kochetov Y., Khachay M., Beresnev V., Nurminski E., Pardalos P., Springer, Cham, 2016, 182–192  crossref  isi
    29. А. В. Кельманов, А. В. Моткова, В. В. Шенмайер, “Приближенная схема для задачи взвешенной 2-кластеризации с фиксированным центром одного кластера”, Тр. ИММ УрО РАН, 23, № 3, 2017, 159–170  mathnet  crossref  elib
    30. В. В. Шенмайер, “Точный алгоритм для нахождения подмножества векторов с суммой максимальной длины”, Дискретн. анализ и исслед. опер., 24:4 (2017), 111–129  mathnet  crossref  elib; V. V. Shenmaier, “An exact algorithm for finding a vector subset with the longest sum”, J. Appl. Industr. Math., 11:4 (2017), 584–593  crossref
    31. Kel'manov A., Khandeev V., “Some Algorithms With Guaranteed Accuracy For 2-Clustering Problems With Given Center of One Cluster”, 2017 International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON), IEEE, 2017, 91–93  crossref  isi
    32. Eremeev A.V., Kel'manov A.V., Pyatkin A.V., “On Complexity of Searching a Subset of Vectors With Shortest Average Under a Cardinality Restriction”, Analysis of Images, Social Networks and Texts, AIST 2016, Communications in Computer and Information Science, 661, eds. Ignatov D., Khachay M., Labunets V., Loukachevitch N., Nikolenko S., Panchenko A., Savchenko A., Vor, Springer International Publishing Ag, 2017, 51–57  crossref  isi  scopus
    33. В. В. Шенмайер, “Сложность и аппроксимация задачи о длиннейшем суммарном векторе”, Ж. вычисл. матем. и матем. физ., 58:6 (2018), 883–889  mathnet  crossref  elib; V. V. Shenmaier, “Complexity and approximation of finding the longest vector sum”, Comput. Math. Math. Phys., 58:6 (2018), 850–857  crossref  isi
    34. А. В. Кельманов, С. А. Хамидуллин, В. И. Хандеев, “Рандомизированный алгоритм для задачи двухкластерного разбиения последовательности”, Ж. вычисл. матем. и матем. физ., 58:12 (2018), 2169–2178  mathnet  crossref  elib; A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, “A randomized algorithm for a sequence 2-clustering problem”, Comput. Math. Math. Phys., 58:12 (2018), 2078–2085  crossref  isi
    35. Kel'manov A., Khamidullin S., Khandeev V., “A Randomized Algorithm For 2-Partition of a Sequence”, Analysis of Images, Social Networks and Texts, Aist 2017, Lecture Notes in Computer Science, 10716, eds. VanDerAalst W., Ignatov D., Khachay M., Kuznetsov S., Lempitsky V., Lomazova I., Loukachevitch N., Napoli A., Panchenko A., Pardalos P., Savchenko A., Wasserman S., Springer International Publishing Ag, 2018, 313–322  crossref  mathscinet  isi  scopus
  • Сибирский журнал индустриальной математики
    Просмотров:
    Эта страница:315
    Полный текст:83
    Литература:39

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019