В процессе генерализации картографических данных необходимо сохранять взаимное расположение объектов. В то же время общепринятой является практика упрощения каждого типа картографических объектов независимо (сначала административные границы, потом дорожная сеть, гидрографическая сеть и т. д.), а потом проведение ручной или автоматической коррекции ошибок. В связи с развитием вычислительной техники и переводом большого числа картографической информации в электронную форму возникла необходимость в автоматизации этого процесса. Для выявления пространственных конфликтов необходимо уточненное описание пространственных отношений.В работе проанализированы модели описания топологических отношений пространственных объектов: модель девяти пересечений, модель топологической цепочки и модель E-WID. Каждая рассмотренная модель позволяет учитывать некоторые отношения между объектами, но не позволяет передавать их в точности. Вследствие этого становится актуальным направление исследований, посвященное уточнению таких моделей. Нами предложена усовершенствованная модель девяти пересечений, учитывающая порождение топологического конфликта, состоящего в нарушении “правила буравчика”, при упрощении ломаной линии, рядом с которой располагается точечный объект. Несмотря на кажущуюся простоту рассматриваемых объектов, упрощение ломаной является одним из наиболее востребованных действий при работе с картами. При покрытии карты сеткой, внутри ячейки могут находиться точечные объекты и элементы линейных и полигональных топологических объектов, которые, при достаточной мелкости сетки, представляют собой полилинейные объекты. Таким образом, вопрос об упрощении топологических объектов внутри ячейки сводится к вопросу упрощения полилинейных объектов (ломаных). Разработанный алгоритм планируется применять для решения задачи согласованной генерализации пространственных данных. Идеи, изложенные в данной статье, лягут в основу нового индекса пространственных данных, сохраняющего их топологические отношения.

В данной статье рассматривается NP-трудная задача о двухшаговой раскраске графа. Она состоит в нахождении такой раскраски в заданное число цветов, при которой ни одна пара вершин на расстоянии 1 или 2 друг от друга не будет окрашена в одинаковый цвет. Оптимальной считается двухшаговая раскраска в минимально возможное количество цветов.Задача о двухшаговой раскраске исследуется применительно к графам решетки. Рассмотрены четыре типа решеток: треугольная, квадратная, шестиугольная и восьмиугольная. Показано, что в общем случае для оптимальной двухшаговой раскраски графов шестиугольной и восьмиугольной решетки требуется 4 цвета, приводятся полиномиальные алгоритмы получения такой раскраски. Для графа квадратной решетки, в котором максимальная степень вершины равна 3, может потребоваться 4 или 5 цветов для двухшаговой раскраски. В данной работе предложен алгоритм поиска с возвратом для этого случая. Для графов треугольной решетки представлен линейный относительно количества вершин алгоритм двухшаговой раскраски в 7 цветов, показано, что раскраска будет всегда корректной. Если максимальная степень вершины равна 6, решение будет оптимальным.

Линейные коды широко применяются для защиты от ошибок в системах передачи и хранения данных, обеспечения стойкости различных криптографических алгоритмов и протоколов, для защиты скрытой информации от ошибок в стегоконтейнере. Одним из классов кодов, находящих применение в ряде перечисленных областей, является класс линейных самодополнительных кодов над бинарным полем. Такие коды содержат вектор из всех единиц, а их нумератор весов является симметрическим многочленом. В прикладных задачах от самодополнительных [n, k]-кодов часто требуется при заданной длине n и размерности k иметь максимально возможное кодовое расстояние d(k, n). Для n < 13 значения d(k, n) уже известны. В настоящей работе для самодополнительных кодов длины n=13, 14, 15 ставится задача нахождения нижних оценок на d(k, n), а также нахождение самих значений d(k, n). Разработка эффективного способа получения нижней оценки, близкой к d(k, n), является актуальной задачей, так как нахождение самих значений d(k, n) в общем случае является трудной задачей. В работе предложены четыре способа нахождения нижних оценок: на основе циклических кодов, на основе остаточных кодов, на основе (u|u + v)-конструкции и на основе тензорного произведения кодов. На совместном использовании этих способов для рассмотренных длин удалось получить эффективным образом нижние оценки, либо совпадающие с найденными значениями d(k, n), либо отличающиеся на единицу. В работе предложена последовательность проверок, которая в ряде случаев помогает доказать отсутствие самодополнительного [n, k]-кода с кодовым расстоянием d. В заключительной части работы на основе самодополнительных кодов предлагается конструкция для сокрытия информации, устойчивая к помехам в стегоконтейнере. Приведенные расчеты показывают большую эффективность новой конструкции по сравнению с известными конструкциями.

Исследование посвященно классификации новостных статей о Ярославском государственном университете им. П. Г. Демидова (ЯрГУ) на 4 категории: общество, образование, наука и технологии, нерелевантная.Предложенные подходы основаны на нейронной сети BERT и методах машинного обучения SVM, Logistic Regression, K-Neighbors, Random Forest в сочетании с эмбеддингами различных видов: Word2Vec, FastText, TF-IDF, GPT-3. Также предложены способы предобработки текстов для достижения более высокого качества классификации. В ходе экспериментов установлено, что лучше всего с задачей справляется SVM-классификатор с эмбеддингом TF-IDF, обученный на полных текстах статей с заголовками. Его значения микро- и макро-F-меры достигают 0.8214 и 0.8308 соответственно. Сопоставимые результаты показывает нейронная сеть BERT, обученная на фрагментах абзацев с упоминанием ЯрГУ, из которых брались 128 слов из начала и 384 слова из конца. Её показатели микро- и макро-F-меры достигают 0.8304 и 0.8181 соответственно. Таким образом, установлено, что абзацев с упоминанием конкретной организации оказывается достаточно, чтобы классификация по категориям была эффективной.

Когда алгоритмы на основе данных, особенно основанные на глубоких нейронных сетях (ГНС), заменяют классические, их более высокая производительность часто сопряжена с трудностями при анализе. Чтобы компенсировать этот недостаток, для ГНС были разработаны методы формальной верификации, которые могут предоставить надежные гарантии поведения программы. Эти методы, однако, обычно рассматривают только саму ГНС, исключая среду, в которой она работает, и применимость методов, учитывающих такие среды, часто ограничена. В данной работе рассматривается задача формальной верификации нейросетевого контроллера для задачи маршрутизации в конвейерной сети. В отличие от известных постановок задачи, рассматриваемые ГНС выполняются в распределенной среде, и производительность алгоритма маршрутизации, которая измеряется как среднее время доставки, зависит от многократного выполнения этих ГНС. При некоторых предположениях, проблема верификации сводится к ряду проблем достижимости выходов ГНС, которые можно решить с помощью существующих программных средств. Эксперименты показывают, что в таких случаях возможна строгая и полная формальная верификация, хотя она заметно медленнее, чем градиентный поиск состязательных примеров.Статья построена следующим образом. Раздел 1 вводит основные понятия. Затем в Разделе 2 представлена проблема маршрутизации и алгоритм DQN-маршрутизации на основе ГНС, который ее решает. В Разделе 3 описывается вклад данной статьи: новый надежный и полный подход к формальной проверке верхней границы среднего времени доставки маршрутизации на основе ГНС. Этот подход экспериментально оценивается в Разделе 4. Статья завершается обсуждением результатов и описанием возможной будущей работы.

В работе проводится анализ возможностей трансформации конструкций языка программирования C в объекты языка программирования EO. Особенностью рассматриваемого подхода является транспиляция из языка системного программирования в язык с более высоким уровнем абстракции, не поддерживающий непосредственные манипуляции с компьютерной памятью. К действиям, которые в этом случае необходимо поддерживать, относится использование разыменованных указателей, наложение данных различного типа на одну и ту же область памяти, а также различная интерпретация одних и тех же данных, расположенных в одном и том же адресном пространстве памяти. Принято решение о создании дополнительных EO-объектов, напрямую имитирующих непосредственную работу с компьютерной памятью в языке C и инкапсулирующих ненадежные операции с данными посредством указателей. Для отображения возможностей языка C, обеспечивающих взаимодействие с компьютерной памятью, предлагается абстрактный объект-память. Он представляет собой массив байт, при работе с которым возможны запись и чтение по заданному индексу. Для исследования вариантов и анализа полученных результатов разработан транспилятор, обеспечивающий необходимые трансформации. Он реализован на основе Clang, который формирует абстрактное синтаксическое дерево. Обработка этого дерева осуществляется с использованием библиотек LibTooling и LibASTMatchers. Рассмотренный подход оказывается целесообразным при решении ряда задач, к одной из которых относится статический анализ кода. Подобные решения позволяют выделить в отдельные программные объекты низкоуровневые фрагменты кода, акцентировав внимание на их изучении и возможных преобразованиях в более надежный код.

Одним из основных методов вычислительной топологии и топологического анализа данных является персистентная гомология, объединяющая геометрическую и топологическую информацию об объекте с использованием персистентных диаграмм и баркодов. Метод персистентной гомологии из вычислительной топологии обеспечивает баланс между уменьшением размерности данных и характеристикой внутренней структуры объекта. Объединению машинного обучения и персистентной гомологии препятствуют топологические представления данных, метрики расстояния и представление объектов данных. В работе рассматриваются математические модели и функции представления объектов персистентного ландшафта на основе метода персистентной гомологии. Функции персистентного ландшафта позволяют отображать персистентные диаграммы в гильбертово пространство. Рассмотрены представления топологических функций в различных моделях машинного обучения. Приведен пример нахождения расстояния между изображениями на основе построения функций персистентного ландшафта.На основе алгебры полиномов в пространстве баркодов, которые используются в качестве координат, определяются расстояния в пространстве баркода сопоставлением интервалов от одного баркода к другому и расчета штрафов. Для этих целей используются тропические функции, которые учитывают базовую структуру пространства баркода. Рассмотрены методы построения рациональных тропических функций. Приведен пример нахождения расстояния между изображениями на основе построения тропических функций. Для повышения разнообразия параметров (признаков машинного обучения) построены фильтрации сканирования объекта по строкам слева направо и сканирования по столбцам снизу вверх. Это добавляет пространственную информацию к топологической информации. Метод построения персистентных ландшафтов совместим с подходом построения тропических рациональных функций при получении персистентных гомологий.

Процесс тестирования зависимостей и правил вывода может быть использован в двух направлениях. Во-первых, тестирование позволяет проверить гипотезы относительно неизвестных правил вывода. Основная цель при этом поиск реализации отношения - контрпримера, который удовлетворяет исходным зависимостям и противоречит следствию. Найденный контрпример опровергает гипотезу, отсутствие контрпримера позволяет приступить к поиску обобщения правила и условий его выполнимости (logically imply). Тестирование не может служить доказательством выполнимости правил вывода, поскольку процесс обобщения требует поиска универсальных условий выводимости для каждого правила, что невозможно запрограммировать, поскольку даже вид этих условий неизвестен. Во-вторых, при проектировании конкретной базы данных может потребоваться проверка выполнимости правила, для которого отсутствует теоретическое обоснование. Такая ситуация может проявиться при наличии аномалий в суперключе. Решение этой проблемы основывается на использовании правил вывода зависимостей соединения. Для этих зависимостей пока не найдена полная система правил (аксиом). В данной статье рассматривается: 1) методика проведения тестирования правил вывода на примере зависимостей соединения, 2) предложена схема алгоритма тестирования, 3) рассмотрены некоторые гипотезы, для которых отсутствуют контрпримеры и правила вывода, 4) предложен пример использования тестирования при поиске корректной декомпозиции суперключа.