English language
2021 год, том 25, выпуск 4 (PDF)
У кластерного анализа очень широкий спектр применения, его методы используются в медицине, химии, археологии, маркетинге, геологии и других дисциплинах. Кластеризация состоит в объединении в группы схожих объектов, и эта задача является одной из фундаментальных в области интеллектуального анализа данных. Обычно под кластеризацией понимается разбиение заданного множества точек некоторого метрического пространства на подмножества таким образом, чтобы близкие точки попали в одну группу, а дальние – в разные. В данной работе предлагается метод локального осреднения для вычисления плотности распределения данных как точек в метрическом пространстве. Выбирая далее срезы множества точек по определенному уровню плотности, мы получаем разбиение на кластеры. Предложенный метод предлагает устойчивое разбиение на кластеры и свободен от ряда недостатков, присущих известным методам кластеризации.
Ключевые слова: кластер, алгоритм, плотность, метод осреднения.
В данной работе рассказывается о научной школе профессора Валерия Борисовича Кудрявцева и созданной им кафедре математической теории интеллектуальных систем.
Ключевые слова: Теория автоматов, теория интеллектуальных систем, распознавание образов.
Многие задачи, такие как раскраска графа или решение систем линейных уравнений, могут быть представлены как задачи удовлетворения ограничениям для какого-то языка допустимых ограничений. При этом некоторые из этих задач решаются за полиномиальное время, а некоторые являются NP-полными. В 2017 году сложность задачи удовлетворения ограничениям была описана для любого языка ограничений, но осталось много вариаций этой задачи, для которых сложность по-прежнему неизвестна. Например, можно разрешить кроме квантора существования использовать квантор всеобщности или потребовать, чтобы найденное решение было сюръективным или сбалансированным. Также можно потребовать, чтобы входные данные удовлетворяли какому-то наперед заданному условию, как если нам надо покрасить граф в 100 цветов, если известно, что его можно покрасить в 3 цвета. В работе мы обсудим как обычную задачу удовлетворения ограничениям, так и сложность этих и некоторых других вариаций и обобщений этой задачи.
Ключевые слова: Задача удовлетворения ограничениям, вычислительная сложность, кванторная задача удовлетворения ограничениям.
Мозг человека очевидным образом является «родовым» объектом для определения понятия искусственных «интеллектуальных систем». Однако механизмы собственно интеллектуальной деятельности мозга до сих пор остаются не раскрытыми в своей самой сущностной части. В значительной мере это связано с тем, также очевидным обстоятельством, что естественный интеллект в широком смысле обладает свойством субъективного представления реальности, операциональная архитектоника которого, его форматы, способы и полнота описания реальности вне субъективного «Я» нам неизвестны. В этой связи и с учетом отсутствия «общей теории мозга» становится проблематичным создание нейроморфных систем искусственного интеллекта, построенных на структурно-функциональных аналогиях с мозгом. Уровень такой «нейроморфности» всецело будет определяться не полнотой нейроанатомических описаний, а границами нашего понимания того, как работает мозг человека. Между тем, свойство нейроморфности систем искусственного интеллекта может быть достигнуто не столько за счет построения подобной мозгу структурно-функциональной архитектоники этих систем (сети искусственных нейронов, алгоритмы глубокого обучения и т. д.), сколько посредством их обучения двусторонней коммуникации с естественным интеллектом. Мы полагаемы, что каналы информационного взаимодействия мозг-искусственный интеллект для запуска процессов обучения «общению» могут быть построены на основе технологий неинвазивных интерфейсов мозг-компьютер (ИМК) нового поколения. Ключевым звеном этих технологий, станут контуры обратной связи, в рамках которых модули искусственного интеллекта, подключенные к анализу ЭЭГ, будут через естественные сенсорные каналы демонстрировать человеку свои гипотезы относительно принадлежности специфических паттернов ЭЭГ тем или иным мысленным актам человека. В интерактивном процессе эти гипотезы будут уточняться до полной сходимости, формируя таким образом в памяти мозга человека и машины траектории взаимодействия до приемлемого уровня «взаимопонимания». В докладе будут рассмотрены нейрофизиологические и нейротехнологические основания к созданию интерфейсов «мозг-искусственный интеллект».
Ключевые слова: мозг человека, электроэнцефалограмма, интерфейсы мозг-компьютер искусственный интеллект, нейроморфные системы.
В работе кратко изложены основные идеи алгебраической теории автоматов и её связь с алгебраической теорией полугрупп. Автомат рассматривается как полигон над полугруппой. Указаны основные направления развития теории полигонов.
Ключевые слова: автомат, полугруппа, полигон над полугруппой, алгебраическая теория автоматов.
Эта работа описывает серию экспериментов над конечными автоматами и выявляет классы потенциально простых и потенциально сложных регулярных выражений, ведущих к экспоненциальному взрыву в числе состояний.
Ключевые слова: конечные автоматы, регулярные выражения, экспоненциальный взрыв, вычислительные эксперименты.
Рассмотрена простейшая система уравнений вирусной динамики ([1]). Получено аналитическое решение системы. Также получены формулы пиковой вирусной нагрузки и времена достижения максимального и безопасного значений вирусной нагрузки.
Ключевые слова: дифференциальные уравнения, Лотка-Вольтерра, COVID-19.
Целью настоящей работы является изучение замкнутых классов в функциональной системе рациональных функций с рациональными коэффициентами, которые играют ключевую роль при решении проблемы полноты.
Ключевые слова: функциональная система, проблема полноты, замкнутые классы, рациональная функция.
В работе рассмотрены градуированные квазифробениусовы кольца и модули, установлены связи между различными опредлениями, получен ряд эквивалентных характеристик.
Ключевые слова: градуированные кольца и модули, квазифробениусовы кольца, квазифробениусовы модули, фробениусовы аагебры.
В данной работе представлена автоматная модель обучения нейронных сетей, реализованная с помощью языка программирования высокого уровня python и апробированная на задаче бинарной классификации. Также внутри рассматриваемой системы реализована процедура автоматизации обучения нейронных сетей с помощью выбора стратегии обучения с точки зрения «лучших практик».
Ключевые слова: искусственные нейронные сети, конечный автомат, бесконечный автомат, система для работы с нейронными сетями, автоматизация обучения нейронных сетей, оптимизация выбора гиперпараметров с использованием «лучших практик», компьютерное зрение, бинарная классификация.
С помощью характеристического многочлена пучка гиперплоскостей можно посчитать количество регионов пучка. Это позволяет использовать пучки гиперплоскостей в решении сложных комбинаторных задач. В работе изучается пучок гиперплоскостей, построенный по подмножеству множества всех простых путей графа. Полученные результаты связывают этот пучок с задачей о нахождении паросочетания с наибольшим весом в графе, а также позволяют найти характеристический многочлен построенного пучка для некоторых графов.
Ключевые слова: пучок гиперплоскостей, графический пучок, задача о максимальном паросочетании.
В данной статье описывается клеточный автомат с локаторами, решающий задачу поиска ближайшего соседа. Задача заключается в том, чтобы из конечного множества точек выделить одну, самую близкую к заранее определенной “центральной” точке. В отличие от классической модели клеточного автомата, в рассматриваемой модели допускается мгновенная передача сигналов через эфир на произвольное расстояние. Показано, что такая возможность позволяет решить задачу за константное время, что в корне отличается от одномерного случая, где получена логарифмическая по искомому расстоянию нижняя оценка сложности.
Ключевые слова: клеточные автоматы с локаторами, однородные структуры, поиск ближайшей точки.
В работе описан алгоритм вычисления функций Белого для заданного детского рисунка с использованием техники модулярных функций. Приведена функция Белого с группой монодромии M24, вычисленная с использованием этого метода.
Ключевые слова: детские рисунки, функции Белого, модулярные функции.
В работе описывается использование глубоких нейронных сетей совместно с методом скользящего разделения смесей для построения моделей анализа валютного рынка и выбора торговых стратегий. Рассмотрены архитектура нейронной сети и способы статистического расширения признакового пространства, а также приведены результаты модельных торгов, демонстрирующие преимущества предложенного подхода.
Ключевые слова: глубокие нейронные сети, LSTM-сети, скользящее разделение смесей, валютные пары.
В работе получена верхняя оценка переключательной мощно- сти реализации периодической последовательности автономной ав- томатной схемой. Приводится схема, реализующая произвольную наперёд заданную последовательность длины \[ 2^n \] для натуральных n с переключательной мощностью не более \[ \frac{2^{n/2}}{n} \].
Ключевые слова: плоские схемы, переключательная мощ- ность, верхние оценки, функция Шеннона.
В работе показано, что задача проверки правильности семейства функций при компактном задании входа является coNP-полной, а также предложены процедуры для порождения множества всех правильных семейств заданного порядка и равномерного распределения на этом множестве.
Ключевые слова: правильные семейства функций, цепи Маркова.
В работе описан алгоритм проверки наличия n-подквазигрупп, приведена оценка временной и пространственной сложности и исследована практическая эффективность этого алгоритма.
Ключевые слова: n-квазигруппы, n-подквазигруппы.
В данной работе показано, что базы данных типа "ключ-значение" могут быть реализованы клеточными автоматами с локаторами таким образом, что время выполнения основных операций, таких как поиск, вставка, удаление, не будет зависеть от размера базы данных и будет равно суммарной длине ключа и значения.
Ключевые слова: Клеточные автоматы с локаторами, базы данных, ключ-значение.
В данной работе рассматриваются автоматы, осуществляющие обход связных плоских простых неориентированных графов с целью установления их свойств. Приводится алгоритм, с использованием которого автомат с двумя красками может установить, является ли граф, обход которого он совершает, деревом или псевдодеревом, и определяются оценки для числа шагов, которое должен совершить автомат.
Ключевые слова: Автоматы, графы, деревья, псевдодеревья.
В данной работе рассматриваются объёмные схемы, являющиеся укладкой схем функциональных элементов в пространстве. Был рассмотрен класс объёмных схем, реализующих частичные булевы операторы. Для этого класса получена нижняя оценка потенциала — меры мощности, равной количеству элементов схемы, выдающих единицу на данном входном наборе. Получен порядок функции Шеннона потенциала для класса всюду определенных операторов для объёмных схем без ограничений и схем с близкими выходами.
Ключевые слова: схемы из функциональных элементов, объёмные схемы, мощность схемы, потенциал.
Работа посвящена исследованию глубоких нейросетевых архитектур с реализацией смесей нормальных распределений в скрытых слоях для решения задач кластеризации и регрессии. Проведено сравнение таких моделей с различными наборами гиперпараметров относительно классических методов: k-средних, линейной регрессии, смешанных гауссовских моделей GMM и других.
Ключевые слова: глубокие нейронные сети, смеси нормальных распределений, ЕМ-алгоритм.
Автор исследует вопрос количества возможных разметок ребер сильно-связного ориентированного графа, чтобы образованная диаграмма Мура соответствовала некоторому абелевому автомату. Доказано, что в случае алфавита из двух элементов такая разметка единственна (кроме крайнего случая) и приведен алгоритм такого восстановления. В случае алфавита из большего числа элементов показано, что максимальное количество разметок экспоненциально зависит от количества вершин.
Ключевые слова: абелевые автоматы, диаграмма Мура, граф переходов, разметка графа автомата, структура графа автомата.
Для конечного множества A с заданным на нём множеством операций M определена функция, называемая темпом роста. Порядок роста этой функции характеризует силу и исчислимость множества операций. Показано, что если среди множества всех предикатов, сохраняемых всеми функциями из M , встречается лишь конечное число важных существенных предикатов, то темп роста пары (A, M) имеет логарифмический порядок.
Ключевые слова: темп роста, конечные множества, язык ограничений, логарифмический темп роста.
Для неадаптивного группового тестирования предложен способ ускорения вычисления тестовой функции при оценке качества порогового решающего правила принятия решения о позитивности множества образцов. Ускорение достигается использованием наряду с дуальными блоками комбинаторной блок схемы ее блоков, соответствующих элементам анализируемого множества.
Обсуждается соответствие между детскими рисунками Гротендика и парами Белого на приводимых кривых. Особое внимание будет уделено приложениям.
Ключевые слова: детские рисунки, вложенные графы, пары Белого.
В работе рассматривается реализация клеточным автоматом различных законов движения точки на бесконечном экране. Найдены алгоритмы построения изображений для трёх классов законов движения. Показано, что для моделирования этих законов движения точки на луче минимальное число состояний клеточного автомата равно 4.
Ключевые слова: клеточный автомат, число состояний, бесконечный экран, двунаправленное движение, конструирование изображений.
В работе рассматривается задача безопасного объединения систем с моделью take-grant с точки зрения добавления новых доступов и соответствия субъектов. Объединение систем безопасно, если множество доступов внутри каждой из систем не изменилось. Получены критерии безопасного объединения для каждого из способов объединения.
Ключевые слова: формальные модели безопасности, модель take-grant, безопасное объединение.
В докладе рассматривается авторский алгоритм, позволяющий получить аппаратную реализацию произвольной системы из m булевых функций от n переменных и его применение к сбалансированным S-блокам. После этого в плане сложности сравниваются аппаратные реализации S-блоков, полученные при помощи нового алгоритма и других известных методов.
Ключевые слова: S-блок, аппаратная реализация, оптимизация сложности схем, потоковые шифры, блочные шифры.
В работе установлен порядок роста функции Шеннона длины проверяющего теста относительно источника неисправностей, который может произвольным образом менять местами любые k подряд идущих входов схемы.
Ключевые слова: проверяющий тест, тесты на входах СФЭ, функция Шеннона, перестановки.
Доказано, что в произвольном полном базисе любую булеву функцию можно реализовать неизбыточной схемой из функциональных элементов, допускающей диагностический тест длины не более 3 при инверсных неисправностях на выходах элементов.
Ключевые слова: схема из функциональных элементов, единичный диагностический тест, инверсная неисправность на выходе элемента, функция Шеннона, легкотестируемая схема.
Доказано, что любую булеву функцию можно реализовать k-неизбыточной схемой из функциональных элементов в некотором конечном полном базисе, допускающей k-диагностический тест длины не более 2 при инверсных неисправностях на выходах элементов.
Ключевые слова: схема из функциональных элементов, тест, инверсная неисправность на выходе элемента, функция Шеннона.
В задачах ИИ приходится работать не только с признаковыми, но и метрическими описаниями объектов. Это требует методов построения, преобразования, коррекции и использования метрических описаний. В работе проводится систематизация такого комплекса задач. Рассматривается новый подход к задаче сопоставления компонентов объектов. Во-первых, мы использeем «универсальный граф» для обогащения индивидуальной задачи информацией о предметной области. Это сводит задачу сопоставления компонентов к задаче сопоставления графов. Во-вторых, мы предлагаем быстрый метод сопоставления графов на основе обучения метрики. Эксперименты показывают высокое качество результатов по сравнению с традиционными методами.
Ключевые слова: метрическое описание объектов, представление на основе компонентов, сопоставление компонентов, сопоставление графов, графовая сверточная сеть, обучение расстояния.
Реализованы алгоритмы работы с примитивными элементами в свободных неассоциативных алгебрах в системе компьютерной алгебры SageMath. В ряде случаев подсчитано количество примитивных элементов в свободных неассоциативных алгебрах над конечными полями.
Ключевые слова: свободная неассоциативная алгебра, примитивный элемент, компьютерная алгебра.
Рассматриваются частично упорядоченные алгебраические системы: линейные пространства над частично упорядоченными телами, псевдоупорядоченные кольца и алгебры над частично упорядоченными полями. Такое упорядочение колец и алгебр аналогично частичному упорядочению алгебр Ли, определенному ранее. Частичный порядок аддитивной группы кольца (алгебры) индуцирует данный порядок на неассоциативных кольцах (алгебрах) (кольцах (алгебрах) Ли, йордановых кольцах, например). Доказываются вторая и третья теоремы о порядковых изоморфизмах интерполяционных упорядоченных систем.
Ключевые слова: частично упорядоченные линейные пространства, кольца и алгебры, интерполяционная группа, порядковые гомоморфизмы.
Задача назначения командира состоит в следующем. В начальный момент времени, каждая клетка двумерного клеточного автомата может быть белой или чёрной. Черные клетки в совокупности составляют связную фигуру. Необходимо, чтобы в финальной конфигурации ровно одна черная клетка перешла в специальное состояние «командир». Получена верхняя оценка времени решения задачи.
Ключевые слова: Плоский клеточный автомат, связная фигура, назначение командира.
В работе показывается существование асимптотически хорошего семейства квантовых низкоплотностных кодов, что доказывает qLDPC гипотезу. Также показано существование асимптотически хорошего семейства локально тестируемых кодов с константными параметрами локальности и корректности, что также является положительным решением известной гипотезы в области классических локально тестируемых кодов.
Ключевые слова: локально тестируемы коды, квантовые LDPC коды, асимптотически хорошие коды.
Данная работа посвящена описанию простого эвристического метода генерации вещественных тестовых матриц с заданным числом обусловленности для обоснованного практического выбора методов решения задач линейной алгебры.
Ключевые слова: системы линейных алгебраических уравнений, число обусловленности, спектр матрицы, тестовые матрицы.
В работе рассматриваются вопросы компьютерного моделирования процессов решения задач и автоматического создания приемов решателя. Излагается архитектура процесса перехода от теорем к приемам (алгоритмизации знаний), сложившаяся в процессе обработки многочисленных примеров. Создана компьютерная система, позволяющая решать задачи из различных разделов математики и способная пополнять свою базу приемов.
Ключевые слова: компьютерный решатель задач, логическая система, искусственный интеллект.
Регулярным графом кольца матриц над полем называется граф, множеством вершин которого являются невырожденные матрицы, а ребра соединяют в точности те вершины, сумма которых является вырожденной матрицей. В 2009 году на 22-ой Британской конференции по комбинаторике был сформулирован вопрос о конечности хроматического числа этого графа. Этот вопрос остается открытым для полей характеристики 0. Для исследования этого вопроса в статье [4] было введено определение регулярного графа множества, обобщающее понятие регулярного графа кольца матриц. Между этими понятиями присутствует тесная связь. Например, в случае, если хроматическое число регулярного графа окружности на евклидовой плоскости бесконечно, то таковым будет и хроматическое число регулярного графа кольца матриц порядка выше двух. В этой работе исследована структура регулярных графов множеств из трех элементов, а сами графы классифицированы с точностью до изоморфизма.
Ключевые слова: регулярный граф кольца матриц, классификация графов с точностью до изоморфизма.
Прпедставлены условия K-полноты и A-полноты автоматных систем с добавками в классе автоматов, функционирующих над полем рациональных чисел.
Ключевые слова: конечные автоматы, линейные автоматы, рациональные числа, K-полнота, A-полнота.
В работе исследуется задача поиска отклонений от известных сценариев типичного использования веб-приложений. Рассмотрена модификация существующей формальной постановки задачи, для которой предложена рекуррентная процедура проверки соответствия трассы шаблону. Разработан алгоритм обнаружения аномалий в трассе, эффективный относительно длины трассы и размера шаблона.
Ключевые слова: поиск аномалий, ациклический ориентированный граф, анализ последовательностей событий.
В работе приводится алгоритм получения изотопными преобразованиями простой квазигруппы из некоторой заданной квазигруппы. Также доказывается, что алгоритм имеет квадратичную сложность и что полученная в результате квазигруппа не содержит собственных подквазигрупп. Приведен пример реализации алгоритма на языке Python.
Ключевые слова: квазигруппа, простота квазигруппы, подквазигруппа, изотопность квазигрупп, латинский квадрат.
Для классов линейных автоматов над конечными полями найдены все предполные классы по операциям суперпозиции.
Ключевые слова: конечный автомат, линейный автомат, операции суперпозиции, полнота, предполный класс, конечное поле.
Мы формулируем задачу распределения полочного пространства с учетом разных вариантов размещения товаров (возможность боковой ориентации, каппинги и нестинги). Представлен способ линеаризации нелинейных ограничений, возникающих в такой постановке. Данная методика позволяет найти оптимальное решение задачи, в том числе и для больших объемов входных данных.
Ключевые слова:
Рассмотрена задача онлайнового обучения моделей, где данные для обучения становятся доступными не сразу, а поступают в последовательном порядке. Для решения поставленной задачи используется алгоритм «Полоска», предложенный В.А. Якубовичем. Эффективность метода показана в его сравнении со стандартной моделью, обученной стохастическим градиентным спуском.
Ключевые слова: онлайновое машинное обучение, линейные модели, алгоритм "Полоска".
В работе рассматривается задача построения оптимальных зон транспортной достижимости для нескольких объектов. Предлагается новый алгоритм, основанный на обходе графов, использующий разбиение карты на гексагоны для ускорения вычислений. Обсуждаются часто используемые алгоритмы решения рассматриваемой задачи: для одного объекта — изохроны, которые обобщаются на случай нескольких объектов; для нескольких объектов — диаграммы Вороного. Далее подходы и их модификации сравниваются с новым алгоритмом.
Ключевые слова: интеллектуальный анализ больших данных, геопространственный анализ, оптимальные зоны транспортной достижимости.
В докладе рассматривается подход к автоматическому извлечению терминов из научно-технического текста, комбинирующий известные методы: лингвистические шаблоны, статистические меры терминологичности, методы графового ранжирования. Описываются комбинируемые методы и этапы для извлечения, отбора и ранжирования терминов, реализованные для обработки документов на русском языке. Приводятся результаты экспериментов по извлечению терминов из учебных текстов по математике и программированию. Полученные оценки эффективности извлечения (74% средней точности) показывают перспективность описанного подхода.
Ключевые слова: обработка текстов на естественном языке, автоматическое извлечение терминов, лингвистические шаблоны, графовые методы ранжирования.
NEREL - русский публично доступный набор данных для решения задачи извлечения именованных сущностей и задачи извлечения отношений. Датасет содержит более 56K размеченных сущностей и более 39K отношений. Важным отличием NEREL от предыдущих датасетов является наличие разметки для вложенных именованных сущностей. Методы извлечения вложенных именованных сущностей отличаются от методов извлечения ”плоских” именованных сущностей в первую очередь архитектурой решения. Поскольку NEREL предоставляет аннотации для вложенных сущностей, в работе было проведено сравнение различных подходов к решению этой задачи с переносом на тексты русского языка.
Ключевые слова: извлечение именованных сущностей, извлечение вложенных именованных сущностей, датасет, набор данных.
В работе рассматривается вопрос применения разработанного метода на основе использования мета-векторных представлений слов для автоматизированного (с использованием аннотаторов) расширения таксономии на конкретную предметную область. Рассматривается область информационной безопасности, которая используется для обогащения Онтологии Естественных Наук и Технологий (ОЕНТ).
Ключевые слова: тезаурус, пополнение таксономии, метавекторное представление, интерфейс.
Существующие алгоритмы прореживания позволяют получать разреженные нейронные сети, обладающие хорошим качеством. Однако, при обучении с нуля полученной разреженной структуры, зачастую не получается достичь качества, полученного в результате прореживания (это особенно заметно для сильно разреженных архитектур). В данной работе описывается метод, позволяющий улучшать качество при обучении с нуля, восстанавливая некоторые веса в разреженной архитектуре.
Ключевые слова: нейронные сети, прореживание, разреженные архитектуры, гипотеза "лотерейного билета".
В данной работе решается задача сегментации трещин в дорожном покрытии. Предложена сеть Unet-подобной архитектуры с энкодером, представляющим из себя предобученный ResNet18 (без двух классифицирующих слоёв), и стандартным декодером. Показано, что данная архитектура в совокупности с сильной системой аугментации и удачно выбранной функцией потерь способна превзойти существующие решения по используемым в этой области метрикам оценки качества.
Ключевые слова: машинное обучение, нейронные сети, детектирование трещин.
В настоящей работе мы предлагаем градиентную маску, которая отфильтровывает градиенты шума в процессе обратного распространения. Такое обучение позволяет увеличивать плотность и амплитуду представления сигналов в сети. В работе мы представляем новую меру качества градиента. Мы демонстрируем аналитическими методами, как латеральное торможение в искусственных нейронных сетях улучшает качество распространяемых градиентов. Наконец, проводим несколько различных экспериментов, чтобы изучить, как градиентная маска улучшает количественную и качественную производительность сети.
Ключевые слова: латеральное торможение, градиентная маска, свёрточные нейронные сети.
Работа представляет собой продолжение исследований в области оценок архитектур нейронных сетей, достаточных для приближения определенных классов функций. В работе рассматривается вопрос об улучшении оценки сверху архитектуры нейронной сети, которая хорошо приближает зависимости, описывающиеся кусочно-линейными функциями.
Ключевые слова: схема из функциональных элементов, нейронные сети, аппроксимация функций, кусочно-линейные функции.
В работе предлагается метод построения распределенного регулятора специального вида для стабилизации системы с запаздыванием, основанный на использовании генетических алгоритмов. Проводится численное моделирование и анализ полученных результатов.
Ключевые слова: системы с запаздыванием, стабилизация, генетические алгоритмы.
Рассматривается опыт учебного робототехнического проекта реализуемого сотрудниками факультета вычислительной математики и кибернетики МГУ имени М.В. Ломоносова на базе Университетской гимназии (школа-интернат) МГУ имени М. В. Ломоносова. В работе приводится описание проекта и его текущие результаты. Представляются промежуточные итоги педагогической деятельности, рассматриваются вопросы о сложности ведения проектов по робототехнике и их соответствии уровню образования учащихся старших классов.
Ключевые слова: Научно-исследовательский образовательный проект, робототехника, образовательная модель.
В данной работе рассматриваются задачи нелинейного программирования, в которых целевой функционал и функции ограничений заданы относительно небольшими выражениями, содержащими переменные с индексами. За счет анализа зависимости выражений задачи от индексов может быть получена структура разреженных матрицы Якоби ограничений и матрицы Гессе лагранжиана задачи. Это позволяет выписать общие формулы для расчета их ненулевых элементов, использование которых приводит к эффективному применению численного метода для решения задачи нелинейного программирования.
Ключевые слова: планирование траекторий, нелинейное программирование, разреженные матрицы Якоби и Гессе, IpOpt, SymPy
На точность идентификации дифференциальными нейронными сетями значительное влияние оказывают параметры функций активации. Предложен способ оптимизировать эти параметры с помощью алгоритма имитации отжига, результаты оптимизации продемонстрированы на примере задачи идентификации динамики платформы.
Ключевые слова: дифференциальные нейронные сети, глобальная оптимизация, алгоритм имитации отжига.
Рассматривается понятие относительного порядка для гипервыходных систем (то есть систем, у которых размерность выхода больше чем размерность входа). Его условия, как и в случае квадратных систем (для которых размерности входа и выхода совпадают), являются ограничительными, и не являются инвариантными по отношению к невырожденной замене выходов. Ставится задача приведения гипервыходной системы к форме, в которой условия относительного порядка выполняются. Для этого, по аналогии со случаем квадратных систем, вводятся обобщения относительного порядка с менее ограничительными условиями. С их помощью удается решить поставленную задачу.
Ключевые слова: относительный порядок, гипервыходные системы.
Целью исследования является разработка алгоритмов построения цифровых стабилизаторов для переключаемых систем, функционирующих в условиях параметрической неопределённости. Для решения поставленной задачи предлагается использовать методы: точной дискретизации непрерывных управляемых систем, теории сверхстабилизации, теории линейных матричных неравенств и интеллектуальных вычислений.
Ключевые слова: переключаемые системы, интервальная неопределенность, стабилизация, робастная устойчивость, цифровые системы управления, интеллектуальные вычисления.
Электрическая активность мозга выявлялась в задачах на восприятие, и проговаривание отдельных фонем и слогов русского языка при различных условиях инициации процесса проговаривания. В качестве условий инициации было зрительное предъявление (демонстрировалась буква), аудиальное предъявление, а также аудиальное предъявление условных стимулов (слов на незнакомом испытуемым языке, ассоциированных предварительно с соответствующими фонемами). Получены ВП по группе из 25 испытуемых для восприятия и внутреннего проговаривания 7 фонем и 10 слогов для каждого из условий инициации. В результате показано, что усредненный вызванный потенциал на сигнал проговаривания фонемы и слогов зависит от способа инициализации. Это важно учитывать при разработке методов декодирования внутренней речи и автоматических классификаторов.
Ключевые слова: ЭЭГ, ВП, внутреннее проговаривание, слоги, фонемы, слова, условные стимулы, несуществующие слова, японский язык.
Работа посвящена изучению динамики формирования когнитивных карт новой обстановки в гиппокампе бодрствующих мышей в свободном поведении. Было измерено среднее время, требующееся для формирования стабильных нейронных репрезентаций пространства, а также охарактеризована пространственная селективность когнитивных карт. Было исследовано изменение этих параметров в последующие дни эксперимента, а также был проведён популяционный анализ нейронной активности с целью верификации полученных результатов.
Ключевые слова: клетки места, поля места, когнитивные карты, гиппокамп.
Функционирование головного мозга основано на параллельной синхронной работе формирующих его нейросетей, архитектура которых определяет свойства протекающих когнитивных процессов. Для построения функциональных коннектомов головного мозга человека обычно используются данные неинвазивных методов: электроэнцефалографии (ЭЭГ), магнитной энцефалографии (МЭГ) и функциональной магнитно-резонансной томографии (фМРТ), полученных в стимульных когнитивных задачах или в состоянии покоя. Для каждой комбинации из приведенных экспериментальных методов и исследуемого когнитивного процесса есть ряд особенностей в методах построения функциональных коннектомов. Особый интерес представляет фМРТ исследование нейросетевого взаимодействия в состоянии покоя головного мозга, как модели базового уровня работы процессов сознания. При посредственной величине пространственного разрешения (порядка 2 мм) и временного разрешения (0,5 Гц) сигнала,фМРТ является единственным из современных методов одновременной регистрации физиологических сигналов от коры и глубинных структур головного мозга. В данной работе на примере полученных фМРТ данных состояния покоя головного мозга приводится описание характерных особенностей построения функциональных коннектомов.
Ключевые слова: нейросети, фМРТ, функциональный коннектом, глобальный сигнал, функционально-однородные регионы, стационарность, автокорреляция, функциональный атлас, состояние покоя.
Бинарный классификатор, основанный на свёрточной и рекуррентной нейронной сети, показал точность, равную в среднем 60%, с максимальным значением 78,9% при классификации данных ЭЭГ от людей, перенесших SARS-CoV-2 (COVID-19) и людей, которые не имели перенесенного диагностированного COVID-19. Полученные данные подтверждают гипотезу о наличии определенных паттернов электрической активности мозга у людей, перенесших SARS-CoV-2 (COVID-19).
Ключевые слова: COVID-19, ЭЭГ, нейронные сети, SARS-CoV-2.
В прикладных задачах машинного обучения часто встречается проблема неоднородности выборки. Например, это приводит к трудностям в решении задачи распознавания паттернов электрической активности мозга при разработке нейроинтерфейса у людей разных социальных характеристик. В работе мы предложили новый метод оценки работы алгоритма кластеризации, имеющий низкие вычислительные затраты и основанный на способности алгоритма распознать скрытые закономерности, то есть выделять группы, схожие по внешнему признаку. Мы показали области практического применения алгоритма, в частности в задачах классификации данных электрической активности мозга при произнесении 8 слов у людей с разными социальными характеристиками.
Ключевые слова: кластеризация, критерий качества кластеризации, нейроинтерфейс.
В работе предлагается использовать синтетический подход к формальному представлению рассуждений в искусственном интеллекте. Основу это подхода составляют положения теории двойного процесса, позволяющие различить элементарные, быстрые, интуитивные базовые рассуждения и контролируемые, осознаваемые, медленные рассуждения, основанные на размышлениях. Другим источником являются развиваемые в логике и формальной аргументации идеи представления метарассуждений как трансформации исходных рассуждений.
Ключевые слова: человеко-совместимый искусственный интеллект, метарассуждения, трансформация рассуждений.
Рассматривается объединённая логика задач и высказываний QHC, введённая С. А. Мелиховым. Доказана теорема о полноте данной логики относительно моделей Крипке, получающихся обогащением моделей Крипке с отмеченными мирами для её пропозиционального фрагмента HC. Кроме того, показано, что логика QHC является консервативным расширением предикатного варианта интуиционистской эпистемической логики IEL+, предложенной С. А. Артёмовым и Т. Протопопеску.
Ключевые слова: неклассические логики, модальная логика, семантика Крипке.
Компьютерное доказательство теоремы о четырех красках, которое было впервые опубликовано Аппелем, Хакеном и Кохом в 1977-м году, спровоцировало продолжающуюся по сегодняшний день философскую дискуссию об эпистемической ценности компьютерных доказательств. В настоящей работе мы показываем, опираясь на поход предложенный в 2006 году Баслером, как унивалентные основания математики (УО) решают некоторые эпистемологические проблемы, которые ранее обсуждались в литературе в связи с компьютерными доказательствами, и тем самым сглаживают различия между компьютерными и традиционными математическими доказательствами. Мы иллюстрируем наши аргументы примером формализованной и компьютеризированной версии доказательства из области алгебраической топологии.
Ключевые слова: унивалентные основания, компьютерные доказательства, пространственная интуиция.
В статье анализируется представление знания в предложенной С. Яськовским дискуссивной (дискурсивной) логике D2, которая является одной из первых паранепротиворечивых логик. Показывается возможность упрощения её аксиоматизации и обсуждается решение проблемы независимости аксиом.
Ключевые слова: дискуссивная логика, дискурсивная логика, паранепротиворечивая логика, представление знания.
2021 год, том 25, выпуск 3 (PDF)
Рассматривается комбинаторный подход к задаче отыскания оптимального строгого консенсусного ранжирования для заданной совокупности нестрогих упорядочений альтернатив. Вводится понятие «облегчённой» матрицы потерь (антисимметричной), позволяющей сделать процесс (и результат) оптимизации более простым и наглядным. Сформулированы процедуры поиска оптимальных строгих ранжирований (в т.ч. — всех множественных) в различных ситуациях.
Ключевые слова: ранжирования, медиана Кемени, антисимметричные матрицы, параллельное формирование перестановок, язык Julia, OpenCL.
Задача Ферма—Штейнера заключается в поиске такой точки метрического пространства \[ Y \] , что сумма расстояний от нее до точек некоторого конечного фиксированного подмножества \[ A \subset Y \], называемого границей, минимальна. Минимальную сумму расстояний мы будем называеть длиной минимальной астросети. Мы рассматриваем эту задачу в гиперпространстве \[ Y = H(X) \] непустых, замкнутых и ограниченных подмножеств ограниченно компактного метрического пространства \[ X \]; причем на \[ H(X) \] введена метрика Хаусдорфа. В силу ограниченной компактности \[ X \] все элементы \[ H(X) \] являются компактами. Каждое решение задачи Ферма—Штейнера будем называть астрокомпактом Штейнера; их множество разбивается на классы одинаковой взвешенности, каждый из которых соответствует своему вектору расстояний до граничных компактов. В настоящей статье доказаны три достаточных условия того, что для данной границы предъявленный компакт является астрокомпактом Штейнера. Также эти условия гарантируют единственность класса астрокомпактов Штейнера одинаковой взвешенности. Данная теория применяется для полного решения задачи Ферма—Штейнера для некоторых симметричных выпуклых трехэлементных границ в \[ \mathbb {R}^2 \], что демонстрируется примерами.
Ключевые слова: задача Ферма-Штейнера, сеть типа звезда, минимальная астросеть, астрокомпакт Штейнера, гиперпространство, расстояние Хаусдорфа, метрическая проекция, функция расстояния от точки до множества, первая вариация.
В работе доказано, что в базисе, состоящем из элементарного и всех поляризуемых слабоповторных функций, функция Шеннона для длины теста относительно бесповторной альтернативы не превышает \[ 3n − 2 \].
Ключевые слова: бесповторная функция, проверяющее тестирование, слабоповторные функции
В статье рассматривается один специальный тип взаимодействия коллективов автоматов в лабиринтах. Для данного класса лабиринтов решается, относительно всех типов коллективов автоматов, следующая проблема: для каких пар типов существуют коллектив первого типа и коллектив второго типа такие, что если их в начальный момент поместить в любые две вершины любого лабиринта из данного класса лабиринтов, то они обязательно когда-то встретятся. Эту проблему называем проблемой типовой встречи (type meeting) для автоматов в данном классе лабиринтов. Здесь эта задача полностью решена как для случая класса всех конечных плоских мозаичных лабиринтов, так и для случая класса всех конечных плоских прямоугольных лабиринтов. В случае класса всех (конечных и бесконечных) плоских мозаичных лабиринтов для некоторых пар типов коллективов проблема типовой встречи пока остается открытой, а в случае класса всех плоских прямоугольных лабиринтов она все еще является полностью неисследованной.
Ключевые слова: коллектив автоматов, тип коллектива автоматов, плоский прямоугольный лабиринт, плоский мозаичный лабиринт, типовая встреча.
В работе представлен ряд формул характеристической функции булевского решения линейного уравнения с целыми коэффициентами. Аргументами функции выступают двоичные разложения этих коэффициентов.
Ключевые слова: линейное уравнение, булевское решение, характеристическая функция.
Для конечной системы кусочно-параллельных функций, реализуемых схемами из линейных элементов и функций Хэвисайда, дополненной всеми одноместными линейными функциями получен критерий выразимости кусочно-постоянных функций. Таким образом получен критерий выразимости бинарного классификатора, реализованного нейронной схемой МакКаллока-Питтса.
Ключевые слова: кусочно-постоянная функция, кусочно-параллельная функция, проблема полноты, проблема выразимости, нейронные-схемы МакКаллока-Питтса.
Для конечного множества \[A\] с заданным на нем множеством операций M определена функция \[ d_{(A,M )} (n) \], называемая темпом роста. Порядок роста этой функции характеризует силу и исчислимость множества операций. Известно, что темп роста принадлежит либо классу \[ O(n^k) \] для некоторого \[ k \in \mathbb {N} \], либо классу \[ 2^{\Theta(n)} \]. В работе исследуются классы экспоненциальных темпов роста, на которые разбиваются темпы роста из класса \[ 2^{\Theta(n)} \] при выносе асимптотического ограничения из показателя. Показано, что для любых заранее заданных натуральных \[k\] и \[c\] существует такая пара \[(A, M)\], что \[ d_{(A,M)}(n) \in \Theta (n^k \cdot c^n)\]. Если дополнительно \[c > k + 1\], то существует такая пара \[(A, M)\], что \[ d_{(A,M)}(n) \in \Theta (\log n \cdot n^k \cdot c^n)\].
Ключевые слова: темп роста, генерирующие множества, конечные множества, EGP.
В работе исследуется сложность реализации (минимально возможное число операций) систем мономов схемами, использующими двухвходовую операцию композиции, которую можно рассматривать как обобщение операции умножения. Установлено, что асимптотика роста функции Шеннона, характеризующей максимальную сложность среди систем из \[p\] мономов от \[q\] переменных с показателями степеней не более \[K\], при условии \[pq \log K \rightarrow \infty\] и некоторых дополнительных ограничениях имеет вид \[ \min(p,q) \log_2 K + \frac{pq}{\log_2(pq)}\].
Ключевые слова: система мономов, сложность вычисления, схемная сложность, схема композиции, функция Шеннона.
В работе схематично доказывается интуитивно понятный факт о соответствии полиномиальной сложности СФЭ в базисе из штриха Шеффера полиномиальному числу шагов машины Тьюринга. Приведены числовые оценки.
Ключевые слова: сложность схемы, штрих Шеффера, машина Тьюринга.
Исследуются вопросы конечной порожденности найденных ранее \[A\]-предполных классов линейных автоматов над кольцом двоично-рациональных чисел. Показано, что два из них не являются \[A\]-конечнопорожденными, в то время как остальные являются.
Ключевые слова: конечные автоматы, линейные автоматы, двоично-рациональные числа, \[А\]-полнота, предполный класс, конечнопорожденность.
2021 год, том 25, выпуск 2 (PDF)
В работе рассматривается задача перемешения трехзвенной цепочки с одним закрепленным краем из начального положения в положение, в котором второй край попадает в заданную точку. В качестве начального положения берется положение, при котором все звенья цепочки лежат на оси абсцисс. При этом каждое звено цепи имеет фиксированную длину, но может изгибаться под углом 90 градусов в любой своей точке. В работе предложен алгоритм доставляющий минимум расстояния между начальным и конечным положениями цепочки, причем расстояние измеряется на основе метрики городских кварталов.
Ключевые слова: манхэттенская цепочка, манхэттенское расстояние, алгоритм, метрика городских кварталов.
Возникновение неблагоприятных событий в процессе оказания медицинской помощи возникает у 10-15% госпитализированных пациентов. Снижение даже на несколько процентов возникновения таких событий позволит сохранить тысячи жизней. Одним из путей решения этой важнейшей проблемы является использование интеллектуальных информационных технологий, позволяющих прогнозировать риск возникновения неблагоприятного клинического исхода у пациентов. В работе представлены результаты исследования, выполненного совместно сотрудниками Национального медицинского исследовательского центра терапии и профилактической медицины МЗ РФ и механико-математического факультета МГУ имени М.В. Ломоносова, показывающего применимость методов анализа данных в решении этой важной проблемы.
Ключевые слова: профилактическая медицина, неблагоприятный клинический исход, углубленный анализ данных.
Для каждого счетного расширения L языка арифметики определяется абсолютная L-реализуемость предикатных формул. Доказывается, что базисная логика является корректной относительно этих семантик.
Ключевые слова: конструктивная семантика, реализуемость, абсолютная реализуемость, формальная арифметика, базисная логика.
Мультифункции представляют собой функции, задаваемые на конечном множестве и возвращающие в качестве своих значений все подмножества рассматриваемого множества. Оператор суперпозиции приводит к континууму замкнутых множеств. Поэтому возникает необходимость рассмотрения операторов замыкания, которые наряду с суперпозицией содержат другие операции. В работе рассматривается \[ ES_I \]-замыкание мультифункций, полученное применением операции суперпозиции, основанной на пересечении множеств, и оператора разветвления по предикату равенства. Для мультифункций, задаваемых на двухэлементном множестве, указаны все предполные множества, сформулирован и доказан критерий полноты. Приведена классификация мультифункций, основанная на принадлежности предполным множествам, описаны все типы базисов.
Ключевые слова: замыкание; предикат равенства; мульти- функция; замкнутое множество; суперпозиция, критерий полноты.
Задача Ферма—Штейнера заключается в поиске такой точки метрического пространства Y (которую будем называть астровершиной Штейнера), что сумма расстояний от нее до точек некоторого конечного фиксированного подмножества \[ A \subset Y \], называемого границей, минимальна. Минимальную сумму расстояний мы будем называть длиной минимальной астросети. Мы рассматриваем эту задачу в гиперпространстве \[ Y = H(X) \] непустых, замкнутых и ограниченных подмножеств ограниченно компактного пространства X, в данном пространстве являющихся компактами. В настоящей статье описывается широкий класс деформаций граничных компактов, не увеличивающих длину минимальной астросети. Также рассматривается усреднение в смысле суммы Минковского конечного числа границ, состоящих из равного числа элементов, и показывается, что при таком усреднении также не увеличивается длина минимальной астросети.
Ключевые слова: задача Ферма-Штейнера, минимальное дерево Штейнера, минимальная параметрическая сеть, минимальная астросеть, астрокомпакт Штейнера, гиперпространство, расстояние Хаусдорфа.
В данной работе исследуется применение автоматов со стираемыми красками для определения свойств связных планарных неориентированных простых графов. Доказываются следующие факты: автоматам хватит двух стираемых красок для того, чтобы определить, является ли граф деревом или псевдодеревом.
Ключевые слова: Автоматы, графы, деревья, псевдодеревья.
В работе представлена формула, задающая функцию Шеннона для схем в базисе из штриха Шеффера.
Ключевые слова: штрих Шеффера, схема из функциональных элементов, функция Шеннона.
В данной работе рассматривается модель многослойных схем с одним функциональным слоем. В качестве графов-носителей выступают \[ \lambda \]-сепарируемые графы. Доказана нижняя оценка функции Шеннона для сложности данного вида схем \[ \max \left(\frac{2^n}{n}, \frac{2^n (1 - \lambda)}{\log k} \right)\], где k — число слоев. Для d-мерных графов, которые являются частным случаем \[ \lambda \]-сепарируемых графов для \[ \lambda \] = \[ \frac{d - 1}{d} \], таким образом получена нижняя оценка функции Шеннона \[ \frac{2^n}{\min(n, d \log k)} \]. Для прямоугольных многомерных схем доказанная нижняя оценка асимптотически совпадает с верхней оценкой.
Ключевые слова: многослойные схемы, многомерные схемы, асимптотика функции Шеннона, сложность схем, сепараторы в графах.
Для классов линейных автоматов над простыми конечными полями с операциями суперпозиции найдены все предполные классы.
Ключевые слова: конечный автомат, линейный автомат, операции суперпозиции, полнота, замкнутый класс, предполный класс, простое поле.
2021 год, том 25, выпуск 1 (PDF)
Статья является продолжением статьи [1]. Рассматривается алгоритм верификации формализованных математических доказательств для логики предикатов первого порядка с равенством. Доказываются теоремы о его корректности и полноте.
Ключевые слова: автоматическое доказательство теорем, система автоматизации дедукции, верификация доказательств, язык первого порядка, исчисление предикатов, продукционная система, искусственный интеллект.
Формулируется и обосновывается тезис о необходимом и достаточном требовании к наличию искусственного интеллекта умных систем различного назначения. Необходимость – это присутствие избыточных показаний первой сигнальной системы или первичного сенсориума умных систем. Достаточность – это присутствие второй сигнальной системы или языка общения умных систем как языковой надстройки, языкового сенсориума осознанной части первичного сенсориума. Обсуждаются проблемы создания и безопасной эксплуатации умных систем. Статья написана с целью активного участия в актуальной дискуссии глубокоуважаемых специалистов МГУ имени М.В. Ломоносова по теме «Искусственный интеллект: проблемы и перспективы» [1].
Ключевые слова: искусственный интеллект, умная система, радикал, язык, интернет вещей, интерфейс, естественный интеллект, информационно-системная безопасность интеллекта.
Рассматривается задача о равновесном взаимном расположении двух треугольников. Предлагается решение этой задачи на основе метода множителей Лагранжа. Двукратная итерация этого метода дает аналитическое решение.
Ключевые слова: метод Лагранжа, преобразование на плоскости, подобие, вращение, сдвиг, треугольник.
В данной статье построен алгоритм сведения задачи прогнозирования спортивных результатов к задаче бинарной классификации. При этом обоснована оптимальность этого алгоритма с точки зрения применения результатов прогнозирования в игре против букмекерских контор.
Ключевые слова: машинное обучение, прогнозирование спортивных результатов, бинарная классификация.
В работе рассматривается задача построения распределенного алгоритма поиска траекторий-компаньонов. Под траекториями-компаньонами понимается пара траекторий такая, что обе траектории обладают участком достаточной длины, на котором оба объекта в каждый момент времени находятся на достаточно близком расстоянии друг от друга. Рассматривается задача поиска в базе данных траекторий, которая из-за своего размера не может быть размещена и обработана на одной рабочей станции. Подобные задачи принято называть задачами на больших данных или просто big-data-задачами. Определена процедура квантизации траекторий, вводится понятие клеточного индекса, введено определение похожих траекторий, построен эффективный алгоритм поиска похожих траекторий. На базе данного алгоритма построены локальный и распределенный алгоритмы поиска траекторий-компаньонов, получены оценки их сложности.
Ключевые слова: большие данные, анализ пространственно-временных данных, анализ траекторий, поиск траекторий-компаньонов, поиск близких траекторий, анализ трафика.
Локально восстанавливаемые коды (LRC коды) это линейные коды с представляющим большой интерес для приложений свойством, что каждый символ кодового слова можно восстановить по небольшому множеству других символов. Символы кода можно интерпретировать как серверы с некоторой информацией. Тогда становится естественным задание топологии этих серверов в виде графа, в котором для каждого сервера указаны сервера, по данным из которых можно однозначно восстановить его данные. В статье рассматриваются LRC коды для некоторых типов топологий и приводятся оценки на скорость таких кодов.
Ключевые слова: коды исправляющие ошибки, локально восстанавливаемые коды, коды на графах.
В данной работе рассматриваются \[ \Lambda \]-выражения, построенные на основе универсальных функций для классов примитивно-рекурсивных функций иерархии Гжегорчика. Найдено достаточное условие на вид \[ \Lambda \]-выражения, при котором это \[ \Lambda \]-выражение определяет примитивно-рекурсивную функцию из заданного класса иерархии Гжегорчика.
Ключевые слова: иерархия Гжегорчика, примитивно-рекурсивные функции, строгая примитивно-рекурсивная реализуемость.
В работе рассматривается реализация одного класса законов движения клеточным автоматом на бесконечном экране. Показано, что минимальное число состояний клеточного автомата, моделирующего двунаправленное движение точки на луче, при котором точка не совершает 2 движения вправо подряд, равно 5.
Ключевые слова: клеточный автомат, число состояний, бесконечный экран, двунаправленное движение, конструирование изображений.
Исследуются вопросы A-полноты конечных систем линейных автоматов над кольцом двоично-рациональных чисел. Описано условие полноты конечной системы линейных автоматов, содержащей автомат, реализующий сумматор в первый такт. Доказана алгоритмическая разрешимость задачи определения принадлежности конечного множества линейных автоматов сформулированному набору предполных классов.
Ключевые слова: конечные автоматы, линейные автоматы, двоично-рациональные числа, А-полнота, предполный класс, алгоримическая разрешимость.