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.

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