Издательство СО РАН

Издательство СО РАН

Адрес Издательства СО РАН: Россия, 630090, а/я 187
Новосибирск, Морской пр., 2

soran2.gif

Baner_Nauka_Sibiri.jpg


Яндекс.Метрика

Array
(
    [SESS_AUTH] => Array
        (
            [POLICY] => Array
                (
                    [SESSION_TIMEOUT] => 24
                    [SESSION_IP_MASK] => 0.0.0.0
                    [MAX_STORE_NUM] => 10
                    [STORE_IP_MASK] => 0.0.0.0
                    [STORE_TIMEOUT] => 525600
                    [CHECKWORD_TIMEOUT] => 525600
                    [PASSWORD_LENGTH] => 6
                    [PASSWORD_UPPERCASE] => N
                    [PASSWORD_LOWERCASE] => N
                    [PASSWORD_DIGITS] => N
                    [PASSWORD_PUNCTUATION] => N
                    [LOGIN_ATTEMPTS] => 0
                    [PASSWORD_REQUIREMENTS] => Пароль должен быть не менее 6 символов длиной.
                )

        )

    [SESS_IP] => 3.238.116.201
    [SESS_TIME] => 1720997417
    [BX_SESSION_SIGN] => 9b3eeb12a31176bf2731c6c072271eb6
    [fixed_session_id] => 20f33a5bb5542e3aa9972146bccf979c
    [UNIQUE_KEY] => 37dee0a8371cd93b46b9649ae3191e8a
    [BX_LOGIN_NEED_CAPTCHA_LOGIN] => Array
        (
            [LOGIN] => 
            [POLICY_ATTEMPTS] => 0
        )

)

Поиск по журналу

Сибирский журнал вычислительной математики

2020 год, номер 2

Задача минимизации суммы разностей взвешенных сверток, случай заданного числа элементов в сумме

А.В. Кельманов1,2, Л.В. Михайлова1, П.С. Рузанкин1,2, С.А. Хамидуллин1
1Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук, Новосибирск, Россия
mikh@math.nsc.ru
2Новосибирский национальный исследовательский государственный университет, Новосибирск, Россия
ruzankin@math.nsc.ru
Ключевые слова: числовые последовательности, разность взвешенных сверток, переменная длина свертки, минимум суммы, точный полиномиальный алгоритм, численное моделирование, ECG-подобный сигнал, PPG-подобный сигнал, numerical sequences, difference of weighted convolutions, variable length convolution, minimum of sum, exact polynomial-time algorithm, numerical modeling, electrocardiogram-like signal, photoplethysmogram-like signal
Страницы: 127-142

Аннотация

В работе рассматривается неизученная экстремальная задача суммирования элементов числовых последовательностей Y длины N и U длины q ≤ N . В задаче требуется минимизировать сумму разностей взвешенных сверток последовательностей переменной длины (не менее q ). В каждой разности первая невзвешенная свертка - автосвертка растянутой на переменную длину последовательности U (путем кратных повторов ее элементов), вторая - взвешенная свертка этой растянутой последовательности с подпоследовательностью из Y. Анализируется вариант задачи с заданным на входе числом суммируемых разностей. Мы показываем, что задача эквивалентна одной из проблем аппроксимации последовательности Y элементом X из экспоненциального по мощности множества последовательностей. Это множество объединяет все последовательности длины N , которые в качестве подпоследовательностей включают M допустимых квазипериодических (флуктуационных) повторов последовательности U . Каждый квазипериодический повтор порождается допустимыми преобразованиями последовательности U . Этими преобразованиями являются: 1) сдвиг U на переменную величину, которая между соседними повторами не превышает Tmax ≤ N ; 2) переменное растягивающее отображение U в последовательность переменной длины, которое определяется в виде повторов элементов из U , кратность этих повторов - переменная величина. Критерием аппроксимации является минимум суммы квадратов расстояний между элементами последовательностей. Мы доказываем, что рассматриваемая экстремальная задача и вместе с ней задача аппроксимации разрешимы за полиномиальное время. А именно, мы показываем, что существует точный алгоритм, который находит решение задачи за время O(T3max M N ). Если Tmax - фиксированный параметр задачи, то время работы алгоритма равно O( M N ). Примерами численного моделирования проиллюстрирована применимость алгоритма к решению модельных прикладных задач помехоустойчивой обработки ECG- и PPG-подобных квазипериодических сигналов (electrocardiogramlike и photoplethysmogram-like signals).

DOI: 10.15372/SJNM20200202