2021 год, том 25, выпуск 2 (PDF)

И. О. Бергер Алгоритм перевода конца цепочки в заданную точку в пространстве с метрикой городских кварталов

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

Ключевые слова: манхэттенская цепочка, манхэттенское расстояние, алгоритм, метрика городских кварталов.

Б. Э. Горный, А. П. Рыжов, А. С. Строгалов, А. Д. Журавлев, А. А. Хусаенов, И. А. Шергин, Д. А. Фещенко, А. М. Абдуллаев, А. В. Концевая Оценка риска неблагоприятного клинического исхода методами углубленного анализа данных

Возникновение неблагоприятных событий в процессе оказания медицинской помощи возникает у 10-15% госпитализированных пациентов. Снижение даже на несколько процентов возникновения таких событий позволит сохранить тысячи жизней. Одним из путей решения этой важнейшей проблемы является использование интеллектуальных информационных технологий, позволяющих прогнозировать риск возникновения неблагоприятного клинического исхода у пациентов. В работе представлены результаты исследования, выполненного совместно сотрудниками Национального медицинского исследовательского центра терапии и профилактической медицины МЗ РФ и механико-математического факультета МГУ имени М.В. Ломоносова, показывающего применимость методов анализа данных в решении этой важной проблемы.

Ключевые слова: профилактическая медицина, неблагоприятный клинический исход, углубленный анализ данных.

А. Ю. Коновалов Корректность базисной логики относительно абсолютной L-реализуемости

Для каждого счетного расширения L языка арифметики определяется абсолютная L-реализуемость предикатных формул. Доказывается, что базисная логика является корректной относительно этих семантик.

Ключевые слова: конструктивная семантика, реализуемость, абсолютная реализуемость, формальная арифметика, базисная логика.

В. И. Пантелеев, Э. С. Тагласов \[ ES_I \]-замыкание мультифункций ранга 2: критерий полноты, классификация и типы базисов

Мультифункции представляют собой функции, задаваемые на конечном множестве и возвращающие в качестве своих значений все подмножества рассматриваемого множества. Оператор суперпозиции приводит к континууму замкнутых множеств. Поэтому возникает необходимость рассмотрения операторов замыкания, которые наряду с суперпозицией содержат другие операции. В работе рассматривается \[ ES_I \]-замыкание мультифункций, полученное применением операции суперпозиции, основанной на пересечении множеств, и оператора разветвления по предикату равенства. Для мультифункций, задаваемых на двухэлементном множестве, указаны все предполные множества, сформулирован и доказан критерий полноты. Приведена классификация мультифункций, основанная на принадлежности предполным множествам, описаны все типы базисов.

Ключевые слова: замыкание; предикат равенства; мульти- функция; замкнутое множество; суперпозиция, критерий полноты.

А. М. Тропин Оценка длины минимальной параметрической сети в гиперпространствах при деформации граничного множества

Задача Ферма—Штейнера заключается в поиске такой точки метрического пространства Y (которую будем называть астровершиной Штейнера), что сумма расстояний от нее до точек некоторого конечного фиксированного подмножества \[ A \subset Y \], называемого границей, минимальна. Минимальную сумму расстояний мы будем называть длиной минимальной астросети. Мы рассматриваем эту задачу в гиперпространстве \[ Y = H(X) \] непустых, замкнутых и ограниченных подмножеств ограниченно компактного пространства X, в данном пространстве являющихся компактами. В настоящей статье описывается широкий класс деформаций граничных компактов, не увеличивающих длину минимальной астросети. Также рассматривается усреднение в смысле суммы Минковского конечного числа границ, состоящих из равного числа элементов, и показывается, что при таком усреднении также не увеличивается длина минимальной астросети.

Ключевые слова: задача Ферма-Штейнера, минимальное дерево Штейнера, минимальная параметрическая сеть, минимальная астросеть, астрокомпакт Штейнера, гиперпространство, расстояние Хаусдорфа.

А. А. Демидова Автоматный анализ свойств графа быть деревом и псевдодеревом

В данной работе исследуется применение автоматов со стираемыми красками для определения свойств связных планарных неориентированных простых графов. Доказываются следующие факты: автоматам хватит двух стираемых красок для того, чтобы определить, является ли граф деревом или псевдодеревом.

Ключевые слова: Автоматы, графы, деревья, псевдодеревья.

М. В. Носов О формульном представлении функции Шеннона

В работе представлена формула, задающая функцию Шеннона для схем в базисе из штриха Шеффера.

Ключевые слова: штрих Шеффера, схема из функциональных элементов, функция Шеннона.

Т. Р. Сытдыков, Г. В. Калачев Сложность многослойных d-мерных схем

В данной работе рассматривается модель многослойных схем с одним функциональным слоем. В качестве графов-носителей выступают \[ \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)} \]. Для прямоугольных многомерных схем доказанная нижняя оценка асимптотически совпадает с верхней оценкой.

Ключевые слова: многослойные схемы, многомерные схемы, асимптотика функции Шеннона, сложность схем, сепараторы в графах.

А. А. Часовских Классы линейных p-автоматов с операциями суперпозиции

Для классов линейных автоматов над простыми конечными полями с операциями суперпозиции найдены все предполные классы.

Ключевые слова: конечный автомат, линейный автомат, операции суперпозиции, полнота, замкнутый класс, предполный класс, простое поле.

Доклады семинара "Вопросы сложности алгоритмов поиска"

2021 год, том 25, выпуск 1 (PDF)

Памяти Октая Мурадовича Касим-Заде

Вторушин Ю.И. Алгоритм очевидности для первопорядковой логики предикатов с равенством

Статья является продолжением статьи [1]. Рассматривается алгоритм верификации формализованных математических доказательств для логики предикатов первого порядка с равенством. Доказываются теоремы о его корректности и полноте.

Ключевые слова: автоматическое доказательство теорем, система автоматизации дедукции, верификация доказательств, язык первого порядка, исчисление предикатов, продукционная система, искусственный интеллект.

Чечкин А.В. Тезис о наличии искусственного интеллекта

Формулируется и обосновывается тезис о необходимом и достаточном требовании к наличию искусственного интеллекта умных систем различного назначения. Необходимость – это присутствие избыточных показаний первой сигнальной системы или первичного сенсориума умных систем. Достаточность – это присутствие второй сигнальной системы или языка общения умных систем как языковой надстройки, языкового сенсориума осознанной части первичного сенсориума. Обсуждаются проблемы создания и безопасной эксплуатации умных систем. Статья написана с целью активного участия в актуальной дискуссии глубокоуважаемых специалистов МГУ имени М.В. Ломоносова по теме «Искусственный интеллект: проблемы и перспективы» [1].

Ключевые слова: искусственный интеллект, умная система, радикал, язык, интернет вещей, интерфейс, естественный интеллект, информационно-системная безопасность интеллекта.

Алешин С.В. Треугольники и уравнения Лагранжа

Рассматривается задача о равновесном взаимном расположении двух треугольников. Предлагается решение этой задачи на основе метода множителей Лагранжа. Двукратная итерация этого метода дает аналитическое решение.

Ключевые слова: метод Лагранжа, преобразование на плоскости, подобие, вращение, сдвиг, треугольник.

Журавлев А. Д. Возможный подход к задаче прогнозирования спортивных результатов методами анализа данных

В данной статье построен алгоритм сведения задачи прогнозирования спортивных результатов к задаче бинарной классификации. При этом обоснована оптимальность этого алгоритма с точки зрения применения результатов прогнозирования в игре против букмекерских контор.

Ключевые слова: машинное обучение, прогнозирование спортивных результатов, бинарная классификация.

Соколов А.П., Алисейчик П.А., Моисеев С.В. Распределенный алгоритм поиска траекторий-компаньонов

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

Ключевые слова: большие данные, анализ пространственно-временных данных, анализ траекторий, поиск траекторий-компаньонов, поиск близких траекторий, анализ трафика.

Валинуров Д.Ю. Локально восстанавливаемые коды на графах

Локально восстанавливаемые коды (LRC коды) это линейные коды с представляющим большой интерес для приложений свойством, что каждый символ кодового слова можно восстановить по небольшому множеству других символов. Символы кода можно интерпретировать как серверы с некоторой информацией. Тогда становится естественным задание топологии этих серверов в виде графа, в котором для каждого сервера указаны сервера, по данным из которых можно однозначно восстановить его данные. В статье рассматриваются LRC коды для некоторых типов топологий и приводятся оценки на скорость таких кодов.

Ключевые слова: коды исправляющие ошибки, локально восстанавливаемые коды, коды на графах.

Коновалов А.Ю. \[ \Lambda \]-выражения для примитивно-рекурсивных функций в иерархии Гжегорчика

В данной работе рассматриваются \[ \Lambda \]-выражения, построенные на основе универсальных функций для классов примитивно-рекурсивных функций иерархии Гжегорчика. Найдено достаточное условие на вид \[ \Lambda \]-выражения, при котором это \[ \Lambda \]-выражение определяет примитивно-рекурсивную функцию из заданного класса иерархии Гжегорчика.

Ключевые слова: иерархия Гжегорчика, примитивно-рекурсивные функции, строгая примитивно-рекурсивная реализуемость.

Кузнецова Е.В. Число состояний универсального автомата бесконечного экрана, реализующего двунаправленное движение на луче

В работе рассматривается реализация одного класса законов движения клеточным автоматом на бесконечном экране. Показано, что минимальное число состояний клеточного автомата, моделирующего двунаправленное движение точки на луче, при котором точка не совершает 2 движения вправо подряд, равно 5.

Ключевые слова: клеточный автомат, число состояний, бесконечный экран, двунаправленное движение, конструирование изображений.

Ронжин Д.В. Распознавание A-полноты конечных систем линейных автоматов с добавками над кольцом двоично-рациональных чисел

Исследуются вопросы A-полноты конечных систем линейных автоматов над кольцом двоично-рациональных чисел. Описано условие полноты конечной системы линейных автоматов, содержащей автомат, реализующий сумматор в первый такт. Доказана алгоритмическая разрешимость задачи определения принадлежности конечного множества линейных автоматов сформулированному набору предполных классов.

Ключевые слова: конечные автоматы, линейные автоматы, двоично-рациональные числа, А-полнота, предполный класс, алгоримическая разрешимость.