English language
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-полноты конечных систем линейных автоматов над кольцом двоично-рациональных чисел. Описано условие полноты конечной системы линейных автоматов, содержащей автомат, реализующий сумматор в первый такт. Доказана алгоритмическая разрешимость задачи определения принадлежности конечного множества линейных автоматов сформулированному набору предполных классов.
Ключевые слова: конечные автоматы, линейные автоматы, двоично-рациональные числа, А-полнота, предполный класс, алгоримическая разрешимость.