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

От редакции K 85-летнему юбилею Валерия Борисовича Кудрявцева

От редакции К 80-летнему юбилею Станислава Владимировича Алешина

В. А. Антонюк Об алгоритме строгого консенсусного ранжирования

Рассматривается комбинаторный подход к задаче отыскания оптимального строгого консенсусного ранжирования для заданной совокупности нестрогих упорядочений альтернатив. Вводится понятие «облегчённой» матрицы потерь (антисимметричной), позволяющей сделать процесс (и результат) оптимизации более простым и наглядным. Сформулированы процедуры поиска оптимальных строгих ранжирований (в т.ч. — всех множественных) в различных ситуациях.

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

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