English
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\)-конечнопорожденными, в то время как остальные являются.
Ключевые слова: конечные автоматы, линейные автоматы, двоично-рациональные числа, \(А\)-полнота, предполный класс, конечнопорожденность.