2019 год, том 23, выпуск 2 (PDF)
В данной работе рассматривается восстановление нот из одновременного звучания двух нот в терминах амплитуд и частот. Приведены методы восстановления амплитуд двух нот, которые были одновременно сыграны двумя различными музыкальными инструментами. Описаны случаи существования и не существования одновременно двух решений для задачи восстановления нот.
Ключевые слова: основной тон, обертон, амплитуда, частота, огибающая ноты, суммарная спектрограмма.
В работе предложен новый метод введения персистентных топологических инвариантов для марковских цепей. Продемонстрирован пример использования этих инвариантов для прикладной задачи классификации текстов.
Ключевые слова: Топологический анализ данных, персиcтентные гомологии, марковские цепи, текст на естественном языке
В работе исследуется возможность надежной передачи информации в ситуации, когда противник в каждой момент времени может блокировать некоторое подмножество символов алфавита. Показано, что гарантированно надежный канал существует тогда и только тогда, когда мощность алфавита n и число разрешенных символов k удовлетворяют неравенству n ≤ 2k − 2.
Ключевые слова: скрытые каналы, блуждания по плоскости, запрещения алфавитных символов, передаваемый язык
Изображением в работе называем конечное ( непустое) множество точек в евклидовых пространствах разной размерности. Кратко работа состоит в том, чтобы имея изображение, принадлежащую некоторому образу, извлечь из этого изображения то, что можно было бы назвать описанием этого образа.
Ключевые слова: математическое определение изображения, описание зрительного образа, распознавание изображений.
В работе исследуются свойства так называемой перестановочной конструкции, введенной ранее. Выясняется, что конструкция несколько избыточна, но в результате ее улучшения, она оказывается инъективной для случая линейных правильных семейств булевых функций, и, возможно, инъективной в общем.
Ключевые слова: квазигруппы, правильные семейства булевых функций, латинские квадраты, параметрическое задание
Рассматривается алгоритм проверки наличия подквазигруппы в квазигруппе. Сравнивается скорость выполнения его последовательной и параллельной версий на вычислительной архитектуре CUDA.
Ключевые слова: квазигруппа, подквазигруппа, GPU, CUDA.
Автомат прогнозирует следующий символ входного сверхслова, если он выдает этот символ на выходе в предыдущий момент времени. В работе для произвольного сверхслова в многозначном алфавите исследуется вопрос его почти полного прогнозирования, т.е. когда прогноз правильный почти всегда. Получен результат, позволяющий сузить класс автоматов, которыми прогнозируется сверхслово, а также доказан критерий почти полной прогнозируемости сверхслова.
Ключевые слова: почти полное прогнозирование, прогнозирующий автомат, автоматное прогнозирование сверхслов, критерий прогнозируемости.
В данной работе рассматриваются объёмные схемы, являющиеся обобщением плоских схем в пространстве. Был рассмотрен класс схем, реализующих булевы операторы. Для этого класса получена верхняя оценка потенциала — меры мощности, равной количеству элементов схемы, выдающих единицу на данном входном наборе. Показано, что любой оператор от n переменных можно реализовать объемной схемой, потенциал которой не превосходит O(m · 2n/3 ), если m ≤ n, и √ O( m n · 3 n · 2n/3 ), если m > n.
Ключевые слова: схемы из функциональных элементов, объёмные схемы, мощность схемы, потенциал.
В настоящей работе рассматривается 2-полнота в классе P согласованных функций. Данный класс был рассмотрен ранее в работах [3, 4]. Он является предполным в классе P L кусочно-линейных функций. В нем было найдено два 2-предполных класса: класс CP L непрерывных функций, класс P F согласованных финитных функций.
Ключевые слова: Класс кусочно-линейных функций, класс кусочно-линейных непрерывных функций, класс согласованных функций, класс финитных функций, класс согласованных финитных функций, 2-предполнота, функция Хэвисайда.
В математике часто новые понятия вводятся с помощью некоторых кванторных определений. При наличии достаточно большого запаса таких понятий они могут позволить переформулировать новые кванторные определения бескванторным образом. Это делает заслуживающей рассмотрения задачу отыскания базисных понятий в заданной предметной области, которые делают избыточным дальнейшее кванторное определение. Интересной также является задача создания компьютерных программ, автоматически вводящих такие базисы. В данной работе рассматриваются 3 простых случая сведения кванторной выразимости к бескванторной. Исследуются предикаты и функции, определенные через ∈ и заданные на множестве Z ∪ 2Z , где Z — множество целых чисел. Кроме того, рассматриваются предикаты, выразимые через тот же предикат на множестве точек плоскости и прямых, лежащих в ней. Также рассмотрены предикаты, выразимые на множестве натуральных чисел с отношением делимости на нем. Во всех случаях удалось найти базисы бескванторной выразимости.
Ключевые слова: кванторная выразимость, логика предикатов.
Определяется семантика реализуемости для формул языка теории множеств, основанная на гиперарифметических видах. Исследуется вопрос о корректности аксиом теории множеств Цермело-Френкеля относительной этой семантики.
Ключевые слова: конструктивная семантика, реализуемость, аксиоматическая теория множеств, гиперарифметические виды.
2019 год, том 23, выпуск 1 (PDF)
Разработан алгоритм обучения для задачи позиционирования систем с дискретным управлением, основанный на методе обобщения проб и ошибок, сохраняющихся в базе данных, с помощью глобальной интерполяции и градиентного спуска. Оптимизация алгоритма производится по критерию сокращения времени обучения (числа попыток). Алгоритм был протестирован на симуляторе для моделей систем, действующих на плоскости, двух разных типов: для мобильного робота с двумя ведущими гусеницами и для открытой кинематической цепи с вращательными и призматическими сочленениями.
Ключевые слова: позиционирование, алгоритм обучения, робот, интерполяция, аппроксимация.
Данная работа относится к области семантического анализа юридических документов. Под семантикой нормативно-правовых актов будем понимать отображение, на вход которого поступает текст нормативно-правового акта, а на выходе получается его формальная модель. В статье описывается один из возможных подходов построения формальной модели правил дорожного движения.
Ключевые слова: семантический анализ нормативно-правовых актов, прагматический анализ, построение формальных моделей.
В работе рассматривается задача конечного представления логических систем пропозициональными исчислениями. Исследуются три типа логических систем: линейные, монотонные и импликативные. Для каждого из этих типов логических систем доказаны достаточные условия их конечного задания. Кроме того, доказан критерий конечного задания произвольной логической системы множества классических тавтологий.
Ключевые слова: логические системы, пропозициональные исчисления, конечное задание, правила вывода.
Приводится обзор результатов, связанных с проверкой полиномиальной полноты конечных квазигрупп. Работа подготовлена по материалам доклада на семинаре “Теория автоматов”.
Ключевые слова: квазигруппа, латинский квадрат, полиномиальная полнота, простота, аффинность
В статье изучается множество K(n) := N \ (n, n), исследуется его представление в виде объединения как можно меньшего количества арифметических прогрессий с ограничением на начало или шаг. В каждом из двух случаев найдены соответствующие точные оценки.
Ключевые слова: арифметическая прогрессия, натуральный ряд, проблема минимизации, типы ограничений.
Определяются различные варианты понятия V -реализуемости для формул языка логики предикатов, основанные на использовании функций из множества V для интерпретации импликации и квантора всеобщности. Устанавливается, что принцип Маркова является слабо V -реализуемым, не является равномерно V - реализуемым и является V -реализуемым равномерно в области M , если множество M ⊆ N является V -перечислимым.
Ключевые слова: конструктивная семантика, реализуемость, абсолютная реализуемость, обобщенная реализуемость, принцип Маркова.
В настоящей статье рассматривается класс нейронных кусочно- параллельных функций с двоично-рациональными коэффициентами(BPP). Приводится доказательство существования в нем минимальной Шефферовой функции. Под минимальной Шефферовой функцией в рассматриваемом классе, понимается функция этого класса, порождающая этот класс по операциям суперпозиции и содержащая минимально возможное количество переменных и пороговых функций. Было установлено, что в данном классе минимальная Шефферова функция содержит две переменных и одну пороговую функцию. Также в статье приводится одно из необходимых условий Шефферовости функции, принадлежащей BPP.
Ключевые слова: класс, кусочно-параллельные функции, нейронные функции, двоично-рациональные коэффициенты, операции суперпозици, Шефферова функция.
В данной работе рассматриваются объёмные схемы, являющиеся обобщением плоских схем в пространстве. Был рассмотрен класс схем, реализующих булевы функции. Для этого класса получена верхняя оценка потенциала — меры мощности, равной количеству элементов схемы, выдающих единицу на данном входном наборе. Показано, что любую функцию от n переменных можно реализовать объемной схемой, потенциал которой не превосходит O(2n/3 ).
Ключевые слова: схемы из функциональных элементов, объёмные схемы, мощность схемы, потенциал.
Пусть L — некоторое расширение языка арифметики, V — некоторый класс числовых функций. Определяется понятие V - реализуемости для предикатных формул, основанное на оценке предикатных переменных формулами языка L. Устанавливается корректность и полнота классической логики относительно семантики V -реализуемости в случае, когда класс V содержит все функции, определимые в языке L.
Ключевые слова: конструктивная семантика, реализуемость, обобщенная реализуемость, формальная арифметика.
Рассматривается проблема полноты систем автоматных функций с операциями суперпозиции и обратной связи вида Φ ∪ ν, где Φ ⊆ Pk , ν - конечно. При k = 2 решение этой задачи приводит к разделению решётки замкнутых классов Поста на сильные (наличие которых в исследуемой системе гарантирует разрешимость задачи полноты конечных базисов) и слабые (наличие которых в исследуемой системе этого не гарантирует). При k = 2 эта задача для систем автоматных функций произвольного вида была решена (Бабин Д.Н. 1998). В статье рассмотрены следствия и возможные обощения этой задачи, а также некоторые результаты для Pk , k > 2.
Ключевые слова: булева функция, конечный автомат, алгоритмическая разрешимосить.