2019 год, том 23, выпуск 4 (PDF)

Сухарева А.В., Воронцов К.В. Построение полного набора тем вероятностных тематических моделей

Интерпретируемость, линейное увеличение сложности с ростом данных, масштабируемость сделали тематическое моделирование одним из наиболее популярных инструментов статистического анализа текстов. Однако есть и ряд недостатков, вызванных зависимостью решения от инициализации. Известно, что построение тематической модели сводится к решению некорректно поставленной задачи неотрицательного матричного разложения. Множество её решений в общем случае бесконечно. Всякий раз модель находит локальный экстремум. Многократное обучение модели по одной и той же коллекции может приводить к обнаружению всё новых и новых тем. На практике часто требуется определить все темы корпуса. Для решения этой задачи в статье предложен и исследован новый алгоритм нахождения полного набора тем, который основан на построении выпуклой оболочки. Экспериментально показано, что за конечное число моделей можно построить базис тем. Правдоподобие базиса тем выше, чем одной модели с аналогичным числом тем. Сравнение базисов моделей LDA (latent Dirichlet allocation) и ARTM (additive regularization for topic modeling) позволяет сделать вывод, что темы наборов совпадают с высокой точностью.

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

Бернадотт А., Галатенко А.В. Аппаратная конструкция для решения проблемы экспоненциального взрыва для одного класса регулярных языков

Известно, что язык, задаваемый регулярным выражением вида ∪_{i=1}^n . * α_i . * β_i .*, где α_i , β_i — слова над некоторым алфавитом, в общем случае для распознавания конечным детерминированным автоматом требует экспоненциальное по n число состояний. В работе предлагается конструкция структурного автомата, распознающего языки из данного класса и имеющего полиномиальную пространственную сложность.

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

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

Рассматривается метод поиска вывода в односукцедентном секвенциальном варианте классического исчисления предикатов. В этом алгоритме используются метапеременные и частичная скулемизация. Для рассматриваемого алгоритма доказываются теоремы о корректности и полноте.

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

Алексиадис Н.Ф. О функциональной системе полиномов с рациональными коэффициентами

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

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

Быстрыгова А.В. Запросы на сравнение в задаче параметро-эффективной расшифровки булевых функций

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

Ключевые слова: точная расшифровка, параметро-эффективная расшифровка, запросы на значение, запросы на сравнение, замкнутые классы Поста.

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

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

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

Доклады семинара «Теория автоматов»

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

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

Менькин М.И. Автоматический перевод правил дорожного движения в теоретико-графовую формальную модель

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

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

Боков Г.В. О графовом расширении метода резолюции для булевых формул

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

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

Еременко А.Р., Яшунский А.Д. О весе функций, заданных бесповторными И/ИЛИ формулами

Рассматривается множество функций, заданных бесповторными формулами с бинарными операциями конъюнкции (логического И) и дизъюнкции (логического ИЛИ). Для функций, заданных формулами с фиксированным числом операций, исследуются значения весов — числа наборов, на которых функция принимает значение 1. Найдены асимптотические оценки для числа бесповторных формул, задающих функции с весом из определенных диапазонов, в частности, — числа формул, задающих функции, у которых доля единиц среди значений не превышает четверти.

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

В.Н. Козлов Коды, определяющие изображения с точностью до аффинных преобразований

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

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

Сытдыков Т. Р. Сложность синтеза многомерных прямоугольных схем

В данной статье рассматривается модель прямоугольных многомерных схем. Элементы схем расположены в ячейках d-мерной прямоугольной решетки. Каждая пара соседних ячеек решетки соединена шиной, в которой может быть до k проводов. Доказана верхняя оценка функции Шеннона для сложности данного вида схем 2^n / min(n,d log k).

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

Часовских А.А. О числе максимальных надклассов в классе линейных автоматов

Уточнены перечни предполных классов в классах линейных автоматов над конечными полями. Найден критерий конечности числа предполных надклассов для заданного множества линейных автоматов.

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

Бабин Д.Н. Автоматы с линейными переходами

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

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

Попков К.А. Короткие единичные проверяющие тесты для контактных схем при обрывах и замыканиях контактов

Рассматривается задача реализации булевых функций неизбыточными двухполюсными контактными схемами, допускающими короткие единичные проверяющие тесты относительно обрывов и замыканий контактов. Описаны все функции, для которых минимальная длина указанного теста равна 0, 1, 2 и 3. Доказано, что для почти всех булевых функций от n переменных эта длина равна 4.

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

Коновалов А.Ю. Некорректность интуиционистской теории множеств относительно конструктивной семантики, основанной на гиперарифметических видах.

Исследуется вопрос о корректности аксиом интуиционистской теории множеств относительной семантики реализуемости, основанной на гиперарифметических видах.

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

Часовских А.А. О классах передаточных функций линейных автоматов

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

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

Доклады семинара «Теория автоматов»

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 -реализуемым, не является равномерно V - реализуемым и является V -реализуемым равномерно в области M , если множество M ⊆ N является V -перечислимым.

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

Агафонова М.В. О минимальной Шефферовой функции в классе кусочно-параллельных функций, определенных над двоично-рациональными числами

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

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

Ефимов А.А. Верхняя оценка энергопотребления в классе объемных схем

В данной работе рассматриваются объёмные схемы, являющиеся обобщением плоских схем в пространстве. Был рассмотрен класс схем, реализующих булевы функции. Для этого класса получена верхняя оценка потенциала — меры мощности, равной количеству элементов схемы, выдающих единицу на данном входном наборе. Показано, что любую функцию от n переменных можно реализовать объемной схемой, потенциал которой не превосходит O(2n/3 ).

Ключевые слова: схемы из функциональных элементов, объёмные схемы, мощность схемы, потенциал.

Коновалов А. Ю. Условие корректности и полноты классической логики для семантики относительной V -реализуемости

Пусть L — некоторое расширение языка арифметики, V — некоторый класс числовых функций. Определяется понятие V - реализуемости для предикатных формул, основанное на оценке предикатных переменных формулами языка L. Устанавливается корректность и полнота классической логики относительно семантики V -реализуемости в случае, когда класс V содержит все функции, определимые в языке L.

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

Кудрявцев В.Б., Бабин Д.Н. О классификациях базисов в Pk по разрешимости полноты для автоматов

Рассматривается проблема полноты систем автоматных функций с операциями суперпозиции и обратной связи вида Φ ∪ ν, где Φ ⊆ Pk , ν - конечно. При k = 2 решение этой задачи приводит к разделению решётки замкнутых классов Поста на сильные (наличие которых в исследуемой системе гарантирует разрешимость задачи полноты конечных базисов) и слабые (наличие которых в исследуемой системе этого не гарантирует). При k = 2 эта задача для систем автоматных функций произвольного вида была решена (Бабин Д.Н. 1998). В статье рассмотрены следствия и возможные обощения этой задачи, а также некоторые результаты для Pk , k > 2.

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