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