В данной работе предлагается параллельный алгоритм решения задачи об изоморфизме графов. Целевым результатом для нас выступает построение подходящей подстановки вершин, либо доказательство отсутствия таковой. Задача решается для неориентированных графов без петель и кратных ребер, допускается, что графы могут быть несвязными. Вопрос о существовании либо отсутствии алгоритма с полиномиальной трудоемкостью в настоящее время является открытым. Следовательно, как и для любой трудоемкой задачи, возникает вопрос об ускорении ее решения за счет распараллеливания алгоритма. Для организации параллельных вычислений автором использовалась библиотека RPM_ParLib, которая позволяет создавать параллельные приложения, работающие в локальной вычислительной сети под управлением среды исполнения .NET Framework. Библиотека поддерживает рекурсивно-параллельный стиль программирования и обеспечивает эффективное распределение работы и динамическую балансировку загрузки вычислительных модулей в процессе исполнения программы. Она может быть использована для приложений, написанных на любом языке программирования, поддерживаемом .NET Framework. Для решения нашей задачи и проведения численного эксперимента было разработано несколько приложений на языке C#. Целью эксперимента было исследование ускорения, достигаемого за счет рекурсивно-параллельной организации вычислений. В качестве исходных данных использовались специально сгенерированные случайные регулярные графы с различной степенью вершин. Подробное описание алгоритма и эксперимента, а также полученные результаты также приводятся в работе.

В настоящей работе рассматривается понятие линейного разделяющего алгоритма прямого типа, введенное В. А. Бондаренко в 1983 г. Понятие алгоритма прямого типа определяется с помощью графа решений задачи комбинаторной оптимизации. Вершинами этого графа служат все допустимые решения задачи. Два решения называются смежными, если существуют входные данные, для которых эти решения и только они являются оптимальными. Ключевой особенностью алгоритмов прямого типа является то, что их трудоемкость оценивается снизу кликовым числом графа решений. В 2015–2018 гг. было опубликовано пять работ, основными результатами которых являются оценки кликовых чисел графов многогранников, ассоциированных с различными задачами комбинаторной оптимизации. В качестве основной мотивации в этих работах приводится тезис о том, что класс алгоритмов прямого типа является широким и включает в себя многие классические комбинаторные алгоритмы, в том числе алгоритм ветвей и границ для задачи коммивояжера, предложенный J. D. C. Little, K. G. Murty, D. W. Sweeney, C. Karel в 1963 г. Мы покажем, что этот алгоритм не является алгоритмом прямого типа. Ранее, в 2014 г., автором настоящей работы было показано, что венгерский алгоритм для задачи о назначениях не является алгоритмом прямого типа. Таким образом, класс алгоритмов прямого типа не является настолько широким, как предполагалось ранее.

Описан эксперимент по оцениванию распределения длин путей между узлами в глобальной сети и его характеристик. В частности, показана методика измерения длины пути при помощи утилиты GNU/Linux traceroute и ограничения выбора узлов, налагаемые этим инструментом. Приведены результаты измерений, отмечены высокие значения асимметрии и эксцесса для всех полученных распределений. Описана имитационная модель эксперимента, разработанная для проверки корректности полученных оценок распределения длин путей между узлами в глобальной сети. Приведены результаты моделирования измерений. Показано, что высокие значения асимметрии и эксцесса измеренных распределений не обусловлены только методикой измерения, таким образом, глобальная сеть не описывается моделью Барабаши—Альберт. Перечислены основные гипотезы о причинах отличия асимметрии и эксцесса полученных экспериментально оценок распределения длин путей между узлами в глобальной сети от значений, соответствующих модели Барабаши—Альберт. Описаны результаты моделирования различных гипотез. Показано, что наиболее правдоподобной из них является предположение об определяющем влиянии квазипредфрактальной структуры глобальной сети на асимметрию и эксцесс оценок распределения длин путей между узлами.

Схемы специального широковещательного шифрования используются для защиты легально тиражируемой цифровой продукции от несанкционированного копирования. В таких схемах распространитель тиражирует данные свободно в зашифрованном виде, а для расшифрования выдаёт каждому легальному пользователю уникальный набор ключей и идентифицирующих векторов из некоторого помехоустойчивого кода. Однако, в этих схемах возможна атака, в ходе которой группы из c недобросовестных пользователей могут объединяться в коалиции и получать нелегальный доступ к данным, комбинируя выданную им ключевую информацию для получения пиратской ключевой информации — идентификационного вектора и ключа. Для борьбы с коалиционными атаками применяются классы помехоустойчивых кодов, обладающих специальными c-FP и c-TA свойствами. Класс c-FP-кодов составляют коды, исключающие возможность прямой компрометации добросовестных пользователей, а класс c-TA-кодов составляют коды, позволяющие гарантированно определить одного из злоумышленников. Рассматривается задача нахождения нижних и верхних границ значения величины c, в пределах которых алгеброгеометрические коды L-конструкции обладают соответствующими свойствами. В лучае кодов на произвольной кривой ранее была получена нижняя граница для свойства c-TA, в настоящей работе построена нижняя граница для свойства c-FP. В случае кривых с одной бесконечной точкой получены верхние границы значения c как для c-FP, так и для c-TA свойств. При нахождении этих границ получена вспомогательная конструктивная лемма, в доказательстве которой содержится явный способ построения коалиции и пиратского идентификационного вектора; этот способ важен при анализе стойкости схем широковещательного шифрования. Доказаны свойства монотонности рубежей c-FP и c-TA свойств по подкодам.

В работе изучается разбиение отрезка, которое строится по следующему правилу:
\(
\begin{array}{l}
Q_1 =\{0,q^2,q,1\}.
  \\
Q_{n+1}' = qQ_n \cap q^2Q_n, \ \
Q_{n+1}'' = q^2+qQ_n \cap qQ_n, \ \
Q_{n+1}'''= q^2+qQ_n \cap q+q^2Q_n,
  \\
Q_{n+1} = Q_{n+1}'\cup Q_{n+1}'' \cup Q_{n+1}''',
  \end{array}
\)
где \(q^2+q=1\).

Введем последовательность  чисел \(d= 1,2,1,0,1,2,1,0,1,0,1,2,1,0,1,2,1,\dots\), положив
\(
\begin{array}{l}
  d_1=1, \ d_2=2,\ d_4 =0;
 \\
 d[2F_{2n}+1 : 2F_{2n+1}+1] = d[1:2F_{2n-1}+1];\\
 \quad  n = 0,1,2,\dots;\\
d[2F_{2n+1}+2 : 2F_{2n+1}+2F_{2n-2}] = d[2F_{2n-1}+2:2F_{2n}];\\
d[2F_{2n+1}+2F_{2n-2}+1 : 2F_{2n+1}+2F_{2n-1}+1] = d[1:2F_{2n-3}+1];\\
d[2F_{2n+1}+2F_{2n-1}+2 : 2F_{2n+2}] = d[2F_{2n-1}+2:2F_{2n}];\\
 \quad n = 1,2,3,\dots;\\
  \end{array}
\)
где \(F_n\) - числа Фибоначчи (\(F_{-1} = 0, F_0=F_1=1\)).

Основной результат работы.
\(
{\bf Теорема.}
\\
Q_n' = 1 - Q_n''' =\left \{ \sum_{i=1}^k q^{n+d_i}, \ k=0,1,\dots, m_n\right\},
\\
Q_n'' = 1 - Q_n'' = \left\{q^2 + \sum_{i=m_n}^k  q^{n+d_i}, \ k=m_n-1,m_n,\dots, m_{n+1} \right\},
\)
где \(m_{2n} = 2F_{2n-2}, \ m_{2n+1} = 2F_{2n-1}+1\).

Целью работы является разработка алгоритма сравнения форм изображений объектов, основанного на геометрическом методе потоков де Рама и предварительном аффинном преобразовании исходной формы изображения. При формировании алгоритма сравнения решены задачи обеспечения инвариантности к геометрическим преобразованиям изображений и обеспечения отсутствия требования биективного соответствия между сегментами исходного и терминального изображений. Алгоритм сравнения форм, основанный на методе потоков, устойчив к изменению топологии форм объектов и репараметризации. При анализе структур данных объекта имеет значение не только геометрическая форма, но и сигналы, ассоциированные с этой формой функциональной зависимостью. Для учета этих сигналов предлагается расширить потоки де Рама дополнительным компонентом, соответствующим структуре сигнала. Для повышения точности сравнения форм исходного и терминального изображений определяется функционал на основе формирования квадрата расстояния между формами исходного и терминального изображений, моделируемыми потоками де Рама. Исходное изображение подвергается предварительному аффинному преобразованию для минимизации квадрата расстояния между деформированным и терминальным изображениями.

В данной работе исследуется марковская модель киберугроз, действующих на компьютерную систему. В рамках данной модели компьютерная система рассматривается как система с отказами и восстанавлениями по аналогии с моделями теории надежности. Для оценки функционально-временных свойств системы мы вводим ее параметр, называемый временем жизни и определяемый как число переходов в соответствующей марковской цепи до первого попадания в финальное состояние. В силу того, что данная случайная величина играет важную роль при оценке уровня защищенности компьютерной системы, мы подробно исследуем ее распределение вероятностей в случае несовместных киберугроз; в частности, мы получаем явные аналитические формулы для ее числовых характеристик: математического ожидания и дисперсии. Затем мы существенно обобщаем рассматриваемую марковскую модель, исключив допущение о несовместности действующих на систему киберугроз. Соответствующая марковская цепь при такой модификации расширяется за счет дополнительных состояний, не меняя своей качественной структуры. Указанный факт позволил обобщить полученные ранее аналитические результаты для математического ожидания и дисперсии времени жизни на случай совместных киберугроз. В заключении работы марковская модель совместных кибеугроз используется для постановки задачи о поиске оптимальной конфигурации средств защиты информации в заданном пространстве киберугроз. Существенно, что сформулированные оптимизационные задачи принадлежат к классу задач нелинейного дискретного (булева) программирования. В заключении работы рассматривается пример, иллюстрирующий решение задачи о выборе оптимального набора средств защиты для компьютерной системы.

В функциональном анализе хорошо известно рассуждение о построении производных \(k\)-го порядка в пространствах Соболева \(W_p^k\) при помощи распространения оператора \(k\)-кратного дифференцирования с пространства \(C^k.\) В то же время имеется определение \((k,p)\)-дифференцируемости функции в индивидуальной точке, основанное на соответствующего порядка бесконечно малом отличии функции от приближающего её алгебраического многочлена \(k\)-ой степени в окрестности этой точки по норме пространства \(L_p.\) Целью данной статьи является исследование согласованности операторного и локального построений производной и непосредственное их вычисление. Функция \(f\in L_p[I], \;p>0,\) (при \(p=\infty\) рассматриваются измеримые ограниченные на отрезке \(I\) функции) называется \((k,p)\)-дифференцируемой в точке \(x \in I,\) если существует алгебраический многочлен \(\pi\) степени не больше \(k,\) для которого выполняется \( \Vert f-\pi \Vert_{L_p[J_h]} = o(h^{k+\frac{1}{p}}),\) где \(\;J_h=[x-h; x+h]\cap I.\) Во внутренней точке при \(k=1\) и \(p=\infty\) это равносильно определению обычной дифференцируемости функции. Обсуждаемое понятие исследовалось и применялось в работах С. Н. Бернштейна [1], А. П. Кальдерона и А. Зигмунда [2]. В статье автора [3] показано, что равномерная \((k,p)\)-дифференцируемость функции на отрезке \(I\) при некотором \(\; p\ge 1,\) равносильна принадлежности этой функции пространству \(C^k[I]\) (существованию эквивалентной функции в \(C^k[I]\)). В настоящей статье построены интегрально-разностные выражения для вычисления обобщённых локальных производных натурального порядка в пространстве \(L_1\) (следовательно, в пространствах \(L_p, \;1\le p\le\infty\)), а на их основе -- последовательности кусочно-постоянных функций, подчинённых равномерным разбиениям отрезка. Показано, что для функции \(f\) из пространства \(W_p^k\) последовательность кусочно-постоянных функций, определённых посредством интегрально-разностных выражений \(k\)-го порядка, сходится к \(f^{(k)}\) по норме пространства \(L_p[I].\) Построения имеют алгоритмический характер, и могут быть применены в численном исследовании на ЭВМ различных дифференциальных моделей.

Рост популярности онлайн-платформ, позволяющих пользователям общаться друг с другом, делиться мнениями о различных событиях, оставлять комментарии, подтолкнул к развитию алгоритмов обработки естественного языка. Десятки миллионов сообщений в день, которые публикуют пользователи отдельно взятой социальной сети, необходимо анализировать в режиме реального времени или близко к тому с целью модерации, чтобы не допустить распространение различной противозаконной или оскорбительной информации, угроз и других видов токсичных комментариев. Разумеется такой большой объем информации может быть обработан достаточно быстро только автоматически. Возникает необходимость научить компьютер «понимать» текст, написанный человеком, что является нетривиальной задачей, пусть даже под «пониманием» текста подразумевается лишь его классификация. Бурное развитие технологий машинного обучения обусловило повсеместное внедрение новых алгоритмов. Многие задачи, в том числе и задачи обработки естественного языка, которые долгие годы считалось практически невозможно решить, сейчас вполне успешно решаются с использованием технологий глубокого обучения. В данной статье будут рассмотрены алгоритмы, построенные с использованием технологий глубокого обучения и нейронных сетей, позволяющие успешно решать задачу распознавания и классификации токсичных комментариев. Помимо этого, в статье будут приведены результаты тестирования как разработанных алгоритмов, так и ансамбля данных алгоритмов на большой обучающей выборке, собранной и размеченной специалистами компаний Google и Jigsaw.

Составление оптимального портфеля ценных бумаг является важным и частым случаем решения задачи оптимизации. Практическое применение существующих методов составления оптимального портфеля часто затруднено из-за большого числа доступных для инвестирования ценных бумаг (и, как следствие, большой размерности исходных данных). В данной работе предлагается метод снижения размерности исходных данных, основанный на иерархической кластеризации доступных для инвестирования ценных бумаг. Для кластеризации, широко используемой в компьютерных науках, уже разработано множество алгоритмов и методов. В качестве меры близости ценных бумаг для иерархической кластеризации используется коэффициент парной корреляции Пирсона. Далее исследуется влияние предложенного метода на качество получаемого оптимального решения на нескольких примерах составления оптимального портфеля ценных бумаг по модели Марковица. Также исследуется влияние параметров иерархической кластеризации (метрики межкластерного расстояния и порогового значения кластеризации) на изменение качества получаемого оптимального решения. Исследуется зависимость между целевой доходностью портфеля и возможностью снижения размерности с помощью предложенного метода. Для каждого рассмотренного примера приводятся графики и таблицы с основными полученными результатами применения метода — понижением размерности и падением доходности (снижением качества оптимального решения) у портфеля, построенного с применением предложенного метода по сравнению с портфелем, построенным без применения предложенного метода. Для проведения экспериментов используется язык программирования Python и его библиотеки: scipy для проведения кластеризации и cvxpy для решения задачи оптимизации (построения оптимального портфеля).