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